- •Методические указания
- •1. Цель работы
- •2. Краткие теоретические сведения
- •2.1. Основные логические функции исчисления высказываний
- •2.2. Дизъюнктивно-нормальная и конъюнктивно- нормальная формы
- •3. Контрольные вопросы и задания
- •Цель работы
- •1. Цель работы
- •2. Краткие теоретические сведения
- •2.1. Метод прямого преобразования
- •2.2. Метод семантических таблиц
- •2.3. Метод резолюций
- •2.3.1. Метод насыщения уровня
- •2.3.2. Стратегия вычеркивания
- •2.3.3. Метод лок- резолюции
- •1. Цель работы 1
- •1. Цель работы 10
- •1. Цель работы 23
- •394026 Воронеж, Московский просп., 14
ГОУВПО
«Воронежский государственный технический университет»
Кафедра автоматизированных и вычислительных систем
62-2009
Методические указания
к выполнению лабораторных работ 1-3
по дисциплине
«Математическая логика и теория алгоритмов»
для студентов специальности 230101
«Вычислительные машины, комплексы, системы и сети»
очной, сокращенной очной, заочной и сокращенной заочной форм обучения
Воронеж 2009
Составители: канд. техн. наук Л.В. Холопкина,
ст. преп. М.П. Носачева
УДК 681.3.06:800.92(075)
Методические указания к выполнению лабораторных работ 13 по дисциплине “Математическая логика и теория алгоритмов” для студентов специальности 230101 очной и сокращенной очной, сокращенной очной, заочной и сокращенной заочной форм обучения / ГОУВПО «Воронежский государственный технический университет»; сост. Л.В. Холопкина, М.П. Носачева. Воронеж, 2009. 47 с.
Методические указания содержат краткие теоретические сведения по основным темам курса, примеры решения типовых задач, перечень задач, предназначенных для самостоятельного решения.
Предназначены для студентов второго курса.
Табл.2. Ил. 3 Библиогр.: 5 назв.
Рецензент канд. техн. наук, доц. А.А. Кисурин
Ответственный за выпуск зав. кафедрой д-р техн. наук,
проф. С.Л. Подвальный
Печатается по решению редакционно-издательского совета Воронежского государственного технического университета
© ГОУВПО «Воронежский государственный
технический университет», 2009
ЛАБОРАТОРНАЯ РАБОТА № 1
АЛГЕБРА ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ
1. Цель работы
Целью работы является теоретическое изучение основных логических функций и эквивалентностей исчисления высказываний и приобретение навыков при решении практических задач.
2. Краткие теоретические сведения
Высказывание – это повествовательное предложение, которое может быть классифицировано либо как истинное, либо как ложное, но не как, то и другое одновременно.
2.1. Основные логические функции исчисления высказываний
Пусть и - высказывания. Основные логические функции исчисления высказываний задаются с помощью следующих таблиц истинности.
Отрицание высказывания ( )
|
|
|
|
|
|
Дизъюнкция высказываний и ()
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Пусть “60 делится на 5 ”; : “60 делится на 6”;
“60 делится на 5 или на 6”
Конъюнкция высказываний и ()
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Пусть “”; : “”;
“3<x<10”.
Импликация высказываний и
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- посылка импликации; - заключение импликации.
Пусть “число кратно 10 ”; : “число кратно 5”;
“Если число кратно 10, то оно кратно 5”.
Эквиваленция высказываний и
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Используя таблицы истинности, можно выразить импликацию и эквиваленцию через элементарные логические операции.
2
В исчислении высказываний справедливы следующие эквивалентности (равносильности).
Таблица 1
Основные эквивалентности
Для дизъюнкции |
Для конъюнкции |
Название закона |
|
|
Коммутативный |
= |
|
Сочетательный |
|
|
Дистрибутивный |
|
|
|
|
|
Законы де Моргана |
|
|
|
|
|
|
|
|
|
|
|
Формула поглощения |
|
|
Формула поглощения |
|
|
|
3