lec12
.pdf
Кафедра Прикладной математики Института информационных технологий РТУ МИРЭА
Дисциплина
«Математическая логика и теория алгоритмов»
2022-2023 уч.г.
Наполнение курса
Объем курса
16 лекционных и 8 практических занятий
Темы лекционных занятий
1.Элементы теории множеств. Булева алгебра
2.Булевы вектора и булевы функции
3.ДНФ, СДНФ, КНФ, СКНФ
4.Минимизация ДНФ
5.Метод Карно и метод Квайна
6.Двойственные функции
7.Функциональная полнота. Полные классы. Алгебра Жегалкина.
8.Замкнутые классы функций: монотонные, самодвойственные, сохраняющие const.
9.Теорема Поста
10.Исчисление высказываний
11.Исчисление предикатов. Основные положения. Кванторы
12.Нормальные формы. Доказательства
13.Конечные автоматы
14.Соединения и синтез автоматов
15.Машина Тьюринга
16.ЧРФ и НАМ
2
Лекция 12.
Нормальные формы и доказательства.
12.1.Нормальные формы.
12.2.Метод семантических таблиц в логике предикатов.
12.3.Метод резолюций в логике предикатов.
12.3. Аксиоматическое основание логики предикатов.
Часть 1.
Нормальные формы.
В логике предикатов существуют две важные нормальные формы (т.е. формулы специального вида).
Предваренная нормальная форма (ПНФ). Сколемовская нормальная форма (СНФ).
Каждая отличается типами кванторов входящих в предложение.
Преобразуя каждое из двух заданных предложений в одну из этих нормальных форм, можно легко их сравнивать и определять эквиваленты ли они, является ли одно из них отрицанием другого или просто обладают ли они какими-либо особенностями.
СНФ играет важную роль в логическом программировании.
5
ПНФ: Формула ƍ находится в ПНФ если она имеет вид:
(Q1x1)(Q2x2) … (Qixi) … (Qnxn) Ϭ,
где Qi обозначает один из кванторов или (1≤i≤n), а Ϭ – формула без кванторов.
Выражение (Q1x1)(Q2x2) … (Qixi) … (Qnxn) – префикс формулы
(допустим вид префикса: Q1x1 Q2x2 … Qnxn, где – пробел);
Ϭ – матрица формулы.
Пример 12.1. Проверка ПНФ высказывания.
A ≡ х у [Q(x,y) P(x,y)]
Q1x1 = х, Q2x2 = у, Ϭ = Q(x,y) P(x,y)
Высказывание A в ПНФ.
6
Чтобы привести формулу к ПНФ надо использовать эквивалентность логики высказываний и логики предикатов.
!!! Важна корректность эквивалентных преобразований для областей действия кванторов: квантор всеобщности обобщает , а квантор существования – : в случае предикатов, определённых на бесконечных множествах.
Два часто встречающихся случая:
а) х Р(х) х G(х) х (Р(х) G(х))
для преобразования этого выражения надо сначала переименовать все вхождения переменной х в формуле ( х G(х)). Это важно, т.к. х связанная переменная в формуле Р(х), которая и является областью действия квантора. Переменную х в формуле ( х G(х)) можно заменить на новую переменную (например z), которая не будет встречаться в формуле Р, тогда
х Р(х) z G(z) ≡ х z (Р(х) G(z))
7
б) |
х Р(х) х G(х) х (Р(х) G(х)) |
|
х Р(х) х G(х) ≡ х Р(х) z G(z) ≡ |
≡х (Р(х) z G(z)) ≡
≡х z (Р(х) G(z)).
!!!Квантор существования не обладает свойством дистрибутивности относительно , а квантор всеобщности – относительно .
8
Алгоритм приведения формул к ПНФ:
1 шаг) избавляемся от символов → и ↔ с помощью представления импликации (→) и эквивалентности (↔, ~) через основные логические связки:
(A → B) ≡ ( А B)
(A ↔ B) ≡ (A→B) (B→A) ≡ ( А B) (A B)
2 шаг) проносим отрицание вглубь формулы до элементарных формул.
(А B) ≡ А B,
(А B) ≡ А B,
( А) ≡ А,
( х A) ≡ х А,
( х A) ≡ х А.
9
Алгоритм приведения формул к ПНФ (продолжение):
3 шаг) Выносим кванторы наружу с помощью формул:
(Здесь В не содержит свободных вхождений х. Qx – это x или x).
Qx A(x) B ≡ Qx (A(x) B)
Qx A(x) B ≡ Qx (A(x) B)
x A(x) x B(x) ≡ x (A(x) B(x))x A(x) x B(x) ≡ x (A(x) B(x))
x A(x) x B(x) ≡ x z (A(x) B(z))x A(x) x B(x) ≡ x z (A(x) B(z))
10