lec10
.pdf
Кафедра Прикладной математики Института информационных технологий РТУ МИРЭА
Дисциплина
«Математическая логика и теория алгоритмов»
2022-2023 уч.г.
Наполнение курса
Объем курса
16 лекционных и 8 практических занятий
Темы лекционных занятий
1.Элементы теории множеств. Булева алгебра
2.Булевы вектора и булевы функции
3.ДНФ, СДНФ, КНФ, СКНФ
4.Минимизация ДНФ
5.Метод Карно и метод Квайна
6.Двойственные функции
7.Функциональная полнота. Полные классы. Алгебра Жегалкина.
8.Замкнутые классы функций: монотонные, самодвойственные, сохраняющие const.
9.Теорема Поста
10.Исчисление высказываний
11.Исчисление предикатов. Основные положения. Кванторы
12.Нормальные формы. Доказательства
13.Конечные автоматы
14.Соединения и синтез автоматов
15.Машина Тьюринга
16.ЧРФ и НАМ
2
Лекция 10.
Исчисление высказываний.
10.1.Исчисление высказываний. Основные положения.
10.2.Семантические таблицы.
10.3.Аксиоматические системы вывода.
10.4.Метод резолюций.
Часть 1.
Исчисление высказываний. Основные положения.
Высказывание – повествовательное предложение (утверждение, тезис), которое может быть только истинно или ложно.
Пусть есть множество высказываний, принимающих значение «истина» или «ложь». Элементарные высказывания – высказывания, которые не подвергаются дальнейшему членению на составляющие (обозначаются прописными буквами латинского алфавита).
Из элементарных высказываний строятся более сложные высказывания в результате применения трех видов операций:
1) Кванторные конструкции ( , ) применяются к высказывательным формам и дают высказывания, соответственно:
«Для всех x выполнено A(x)»
и
«Существует x, для которого выполнено A(x)»,
где A(x) – какая-то высказывательная форма. |
|
(Рассматривается в лекции 11). |
5 |
|
2) Модальности – категории, выражающие отношение говорящего к содержанию тезиса (т.е. к реальной действительности): применяются к высказываниям и могут изменять наше отношение к ним. Получаются квазивысказывания, изучающиеся в модальной логике.
Пример. 10.1. «По словам Пушкина, любви все возрасты покорны.»
!!! Для высказываний на ЕЯ понятия "истинности" и "ложности" более расплывчаты. Например, такие словесные формы, как "Иди домой" и "Идёт ли дождь?", не являются высказываниями. Т.е. высказывание – такая словесная форма, в которой что-либо утверждается. Не являются высказываниями вопросительные или восклицательные предложения, обращения, а также пожелания или требования.
3) С помощью логических связок «не», «и», «или», «то же, что» («эквивалентно»), «из … следует …» («… влечет …»).
6
Связки логики высказываний представляют функции алгебры логики:
Отрицанием высказывания А называется высказывание C, которое истинно только тогда, когда А ложно: C = A.
Конъюнкцией высказываний А и В называется высказывание С, которое истинно только тогда, когда А и В истинны
С = А В.
Дизъюнкцией высказываний А и В называется высказывание С, которое ложно тогда и только тогда, когда оба высказывания ложны
С = А B.
Импликацией высказываний А и В называется высказывание С, которое ложно тогда и только тогда, когда А истинно, а В ложно
С = А → В.
Эквиваленцией высказываний А и В называется высказывание С, которое истинно только тогда, когда значения высказываний А и В совпадают.
С = А ~ В (или А↔В) |
|
C = (А → B) (В → A). |
7 |
|
Каждое сложное (или составное) высказывание, полученное с помощью логических связок (которым соответствуют формулы), как и элементарное, принимает значение «истина» или «ложь», („И“, „Л“), („T’’. „F’’), („t”, „f’’).
Определение формулы:
1)Всякое элементарное высказывание является формулой
2)Если А и В формулы, то ( A), (A B), (A B), (A → B), (A ↔ B) тоже формулы.
3)Формулы получаются с помощью правил 1) и 2)
Две формулы равносильны (эквивалентны), если для любых наборов значений переменных они принимают одинаковые значения.
Сложное высказывание (формула) называется общезначимым, тождественноистинным или тавтологией, если оно истинно при любых наборах значений переменных (элементарных высказываний).
Пусть S = H1, H2, … Hn – множество высказываний, высказывание А есть |
|
логическое следствие высказываний H1, H2, … Hn (или логическое следствие |
|
из S), если всякий раз, когда все Hi = «истина», значение А также равно |
|
«истина». |
8 |
|
|
Часть 2.
Семантические таблицы.
Для проверки того является ли высказывание тавтологией или противоречием метод ТИ удобен при небольшом количестве атомов (переменных), однако при числе атомов n=10 ТИ будет содержать 210=1024 строк, поэтому существовала проблема алгоритмизации и автоматизации такого решения.
В 1934 немецкий математик Генцен (1909-1945) доказал существование алгоритмических процедур, позволяющих установить тавтологичность формул, применяя сформулированные им правила вывода. Эти правила стали основой исчисления высказываний.
Используя теорию доказательства, Бет и Хинтика (1955) предложили алгоритм, устанавливающий, является ли составное высказывание тавтологией или нет, называемый методом семантических таблиц Бета.
При помощи семантических таблиц Бета можно определить значения, которые принимают данные сложные высказывания: «ложь» или «истина».
10