- •9. Вопросы к экзамену
- •10. Рекомендуемая литература
- •1. Основная литература
- •2. Дополнительная литература
- •Лекция № 2.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция № 3.
- •Основные вопросы, рассматриваемые на лекции:
- •Законы алгебры высказываний
- •Краткое содержание лекционного материала
- •Лекция № 4.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция № 5.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция № 6.
- •Основные вопросы, рассматриваемые на лекции:
- •Лекция № 7.
- •Основные вопросы, рассматриваемые на лекции:
- •Лекция № 8.
- •Основные вопросы, рассматриваемые на лекции:
- •Лекция № 9.
- •Основные вопросы, рассматриваемые на лекции:
- •Непротиворечивость исчисления высказываний
- •Независимость аксиом исчисления высказываний
- •Лекция № 10.
- •Основные вопросы, рассматриваемые на лекции:
- •Лекция №11.
- •Основные вопросы, рассматриваемые на лекции:
- •Операции над предикатами Краткое содержание лекционного материала
- •Лекция №12.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция №13.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция №14.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция №15.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция №15.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция №16.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция №18.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Лекция №19.
- •Основные вопросы, рассматриваемые на лекции:
- •Краткое содержание лекционного материала
- •Практическое занятие №2 Тема: Запись предложений на языке пропозициональной логики
- •Практическое занятие №3 Тема: Тавтологии. Законы логики
- •Практическое занятие №4 Тема: Логическое следование
- •Практическое занятие №5 Тема: Равносильность формул
- •Практическое занятие №6 Тема: Дизъюнктивные и конъюнктивные нормальные формы
- •Практическое занятие №7 Тема: Виды теорем. Необходимые и достаточные условия
- •Практическое занятие №11 Тема: Полные системы связок
- •Практическое занятие №12 Тема: Построение выводов теорем
- •Практическое занятие №13 Тема: Независимость аксиом исчисления высказываний
- •Практическое занятие №14 Тема: Операции над предикатами
- •Практическое занятие №15 Тема: Интерпретации. Виды формул
- •Практическое занятие №16 Тема: Запись математических предложений на языке логики предикатов
- •Практическое занятие №17 Тема: Свойства обобщений и подтверждений
- •Практическое занятие №18 Тема: Логически общезначимые формулы
- •Практическое занятие №19 Тема: Отрицание формул
- •1. Мендельсон э. Введение в математическую логику. – м.: Наука, 1976. – 320 с.
- •2. Игошин в.И. Задачи и упражнения по математической логике и теории алгоритмов. - м.: Академия, 2007. – 304 с.
Лекция № 4.
Тема: РЕЛЕЙНО-КОНТАКТНЫЕ СХЕМЫ
Основные вопросы, рассматриваемые на лекции:
Электрические схемы с двухпозиционными переключателями
Применение алгебры высказываний к релейно-контактным схемам
Применение алгебры высказываний к дизъюнктивным и конъюнктивным нормальным фопмам
Краткое содержание лекционного материала
Рассмотрим электрические схемы, в которых двухпозиционные переключатели соединяются последовательно или параллельно. По виду одной из технических реализаций такие схемы называются релейно-контактными.
Каждой релейно-контактной схеме поставим в соответствие формулу, составленную из букв и связок , , .
Каждый переключатель обозначим некоторой буквой A. При этом считается, что A1, если переключатель пропускает ток, и A0, если переключатель не пропускает ток.
Переключатели, обозначенные одной и той же буквой, работают в одном и том же режиме.
Некоторые переключатели обознаются отрицанием буквы. Предполагается, что переключатель A пропускает ток тогда и только тогда, когда переключатель A не пропускает ток.
Параллельному (последовательному) соединению электрических схем X и Y соответствует дизъюнкция (конъюнкция) высказываний X и Y.
Формула X, соответствующая данной схеме, истинна (ложна) тогда и только тогда, когда эта схема (не) пропускает ток.
Задача. Упростите релейно-контактную схему:
Решение. Составим формулу, соответствующую данной схеме:
(AC)(BC)(ABC)(C(B(AC))).
Применяя законы алгебры высказываний, полученную формулу преобразуем к более простому виду: (AB(AB))C)((CB)(CAC))
(AB)C)((CB)0)(ABB)C(A1)C1CC.
Ответ:
Пропозициональная переменная p или ее отрицание p называется литералом от переменной p. Конъюнкция (дизъюнкция) литералов переменных p1, …, pn называется конъюнктом (дизъюнктом).
Дизъюнктивной (конъюнктивной) нормальной формой от переменных p1, …, pn называется дизъюнкция (конъюнкция) некоторых конъюнктов (дизъюнктов), содержащие переменные p1,…, pn.
Легко увидеть из определения, что отдельные буквы, отрицания букв, дизъюнкции и конъюнкции букв и их отрицаний являются дизъюнктивными и конъюнктивными нормальными формами. Формула p(qr) является дизъюнктивной, но не конъюнктивной, нормальной формой. Эта формула эквивалентна формуле (pq)(pr), являющейся конъюнктивной, но не дизъюнктивной, нормальной формой. Формула в дизъюнктивной (конъюнктивной) форме, равносильная формуле A, называется дизъюнктивной (конъюнктивной) нормальной формой формулы A.
Дизъюнктивная и конъюнктивная нормальная форме формулы A определяются неоднозначно (даже с точностью до перестановки членов и с точностью до числа одинаковых членов дизъюнкции и конъюнкции). Формулы pq и (pq)q являются дизъюнктивными формами формулы (pq).
Задача. Приведите формулу A(p(qr)) к дизъюнктивной и конъюнктивной нормальной форме.
Решение. Применим законы де Моргана, дистрибутивности и двойного отрицания: Ap(qr)p(qr)(pq)(pr).
Ответ: Ap(qr) – дизъюнктивная нормальная форма, A(pq)(pr) – конъюнктивная нормальная форма.