- •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 с.
Лекция № 8.
Тема: ТЕОРЕМЫ В ИСЧИСЛЕНИИ ВЫСКАЗЫВАНИЙ
Основные вопросы, рассматриваемые на лекции:
Пример доказательства теорем
Доказательства производных правил вывода
Теорема дедукции
Краткое содержание лекционного материала
Теоремы подразделяются на аксиомы и на доказываемые теоремы. Среди правила вывода также имеется основное правило (MP) и производные правила вывода – доказываемые следствия из конечного множества формул.
Приведем примеры теоремы системы S1:
(T1) AA.
Построим вывод теоремы (T1):
1) (A((AA)A))(((AA)A)(AA)) (A2)
2) A((AA)A) (A1)
3) ((AA)A)(AA) (MP), 2), 1)
4) A(AA) (A1)
5) AA (MP), 4), 3)
Приведем пример производного правила вывода системы S1:
(P1) A BA.
Построим вывод правила (P1):
1) A гипотеза
2) A(BA) (A1)
3) BA (MP), 1), 2)
Далее для доказательства теорем и правил, мы приводим сокращенные выводы, в которых имеются не только аксиомы и заключения правила (MP), но и доказанные теоремы и заключения доказанных новых правил вывода (конечно, при условии, что посылки предшествуют заключениям).
Следующее правило вывода называется правилом силлогизма:
(P2) AB,BC AC.
Построим (сокращенный) вывод правила (P2):
1) AB гипотеза
2) BC гипотеза
3) A(BC) (P1), 2)
4) (A(BC))((AB)(AC)) (A2)
5) (AB)(AC) (MP), 3), 4)
6) AC (MP), 1), 5)
«Две посылки импликации можно будет переставлять местами»:
(P3) A(BC) B(AC).
Вывод правила (P3):
1) A(BC) гипотеза
2) (A(BC))((AB)(AC)) (A2)
3) (AB)(AC) (MP), 1), 2)
4) B(AB) (A1)
5) B(AC) (P2), 4), 3)
«Из двойного отрицания следует сама формула»:
(T2) AA.
Вывод теоремы (T2):
1) (AA)((AA)A) (A3)
2) (AA)((AA)A) (P3), 1)
3) AA (T1)
4) (AA)A (MP), 2), 3)
5) A(AA) (A1)
6) AA (P2), 5), 4)
«Из формулы следует ее двойное отрицание»:
(P4) A A.
Вывод правила (P4):
1) (AA)((AA)A) (A3)
2) AA (T2)
3) (AA)A (MP), 1), 2)
4) A гипотеза
5) AA (P1), 4)
6) A (MP), 5), 3)
«Из отрицания посылки следует вся импликация»:
(P5) AAB.
Вывод правила (P5):
1) A гипотеза
2) (BA)((BA)B) (A3)
3) BA (P1), 1)
4) (BA)B (MP), 3), 2)
5) A(BA) (A1)
5) AB (P2), 5), 4)
Версия закона о противоречии:
(P6) A,AB.
Вывод правила (P6):
1) A гипотеза
2) A гипотеза
3) AB (P5), 2)
4) B (MP), 1), 3)
Версия правила (MP):
(P7) A (AB)B.
Вывод правила (P7):
1) (AB)(AB) (T1)
2) A((AB)B) (P3), 1)
3) A гипотеза
4) (AB)B (MP), 3), 2)
«Если посылка истинна, а заключение ложно, то импликация ложна»:
(P8) A,B (AB).
Вывод правила (P8):
1) A гипотеза
2) B гипотеза
3) (AB)B (P7), 1)
4) (AB)B (P1), 2)
5) (AB)(AB) (T2)
6) (AB)B (P2), 5), 3)
7) ((AB)B)(((AB)B)(AB)) (A3)
8) ((AB)B)(AB) (MP), 4), 7)
9) (AB) (MP), 6), 8)
В силу правила (MP) справедливо следующее утверждение:
если AB, то , AB.
Обратное утверждение называется теоремой дедукции и существенно упрощает доказательства некоторых теорем исчисления высказываний.
Теорема дедукции. Если , AB, то AB.
Доказательство. Применим индукцию по следствиям.
Если B – аксиома или B, то AB по правилу (P1).
Если BA, то AB в силу теоремы (T1).
Пусть следствие , AB получается по правилу (MP) из формул D и DB, таких, что , AD и , ADB. Тогда, по индуктивному предположению, AD и A(DB). Далее, в силу аксиомы (A1), верно, что (A(DB))((AD)(AB)). К этим трем следствиям из множества два раз применим (MP), и получим AB.
Следствие. Если AB, то AB.
При помощи теоремы дедукции легче доказываются многие теоремы и правила вывода исчисления высказывания. Для примера приведем доказательства правил (P2) и (P3) при помощи теоремы дедукции.
(P2) AB,BC,A C.
Вывод правила (P2):
1) AB гипотеза
2) BC гипотеза
3) A гипотеза
4) B (MP), 3), 1)
5) C (MP), 4), 2)
По теореме дедукции из (P2) следует (P2).
(P3) A(BC),B,A C.
Вывод правила (P3):
1) A(BC) гипотеза
2) B гипотеза
3) A гипотеза
4) BC (MP), 3), 1)
5) C (MP), 2), 4)
По теореме дедукции из (P3) следует (P3).