lec11
.pdf
Кафедра Прикладной математики Института информационных технологий РТУ МИРЭА
Дисциплина
«Математическая логика и теория алгоритмов»
2022-2023 уч.г.
Наполнение курса
Объем курса
16 лекционных и 8 практических занятий
Темы лекционных занятий
1.Элементы теории множеств. Булева алгебра
2.Булевы вектора и булевы функции
3.ДНФ, СДНФ, КНФ, СКНФ
4.Минимизация ДНФ
5.Метод Карно и метод Квайна
6.Двойственные функции
7.Функциональная полнота. Полные классы. Алгебра Жегалкина.
8.Замкнутые классы функций: монотонные, самодвойственные, сохраняющие const.
9.Теорема Поста
10.Исчисление высказываний
11.Исчисление предикатов. Основные положения. Кванторы
12.Нормальные формы. Доказательства
13.Конечные автоматы
14.Соединения и синтез автоматов
15.Машина Тьюринга
16.ЧРФ и НАМ
2
Лекция 11.
Исчисление предикатов. Основные положения. Кванторы.
11.1.Исчисление предикатов. Основные положения.
11.2.Навешивание кванторов.
11.3.Основные равносильности содержащие кванторы.
Часть 1.
Исчисление предикатов. Основные положения.
Пусть x1, x2, … xi, … xn – символы переменных произвольной природы.
Наборы переменных (x1, x2, … xi, … xn) принадлежат множеству S2, которое будем называть предметной областью, а переменные будем называть
предметами.
N-местным предикатом, определённым на предметной области S2, называют отображение S2 во множество высказываний. То есть это утверждение о предметных переменных обладающее свойством, что при фиксации значений всех переменных об этом утверждении можно сказать, истинно оно или ложно.
Пример 11.1.
а) P(x,y,z) = “x2 + y2 ≤ z2; x,y,z ϵ “
–трёхместный предикат определённый на 3: P(1,2,3)=«И»; P(3,2,1)=«Л».
б) P(x1,x2) = “натуральное число x1 кратно натуральному числу x2”
–двухместный предикат определённый на множестве пар натуральных чисел: P(6,3)=«И»; P(5,2)=«Л».
5
Множеством истинности предиката называется:
P-1({«И»}) = {(x1,…,xn) S2 / P(x1,…,xn) = «И»}.
Множеством ложности предиката называется:
P-1({«Л»}) = {(x1,…,xn) S2 / P(x1,…,xn) = «Л»}.
Предикат P, определённый на S2 называется тождественно истинным, если
P-1({«И»}) = S2,
а тождественно ложным – если
P-1({«Л»}) = S2.
Предикат P, определённый на S2 называется нетривиально выполнимым при
P-1({«И»}) ≠ ø и P-1({«Л»}) ≠ ø.
6
Поскольку предикаты – это отображения со значениями во множестве высказываний, где введены логические операции, то эти операции естественно определяются и для предикатов.
Утверждение 11.1. Множество n-местных предикатов, определённых на S2 образует булеву алгебру предикатов, т.е. для них справедливы все аксиомы булевых алгебр (свойства операций).
Фиксация значений переменных: пусть Р(x1, x2, … xi, … xn) n-местный предикат,
определённый на S2. Зафиксируем xi=a (1≤i≤n). Получим (n–1)-местный предикат Q:
Q(x1, x2, … xi-1, xi+1, … xn) ≡ P(x1, x2, … xi-1, a, xi+1, … xn).
Q определён на множестве S2 значений переменных x1, x2, … xi-1, xi+1, … xn. Пример 11.2. Фиксация значений переменных 3-местного предиката.
P(x,y,z) = «x2 + y2 ≤ z2; (x,y,z) 3»
– 3-местный предикат. Зафиксируем z=2 получим |
|
“x2 + y2 ≤ 4; (x,y) 2” |
|
– 2-местный предикат. |
7 |
|
Часть 2.
Навешивание кванторов.
Пусть P(x) – одноместный предикат.
Поставим ему в соответствие высказывание, обозначаемое
x P(x) – «для любого x P(x)»,
которое истинно тогда и только тогда, когда P(x) тождественно истинный предикат.
О высказывании x P(x) говорят, что оно получено из предиката Р навешиванием квантора всеобщности по переменной х.
Р(х) – одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое
x P(x) - «существует х Р(х)»,
которое ложно тогда и только тогда, когда Р(х) тождественно ложный предикат.
О высказывании x P(x) говорят, что оно получено из предиката Р навешиванием квантора по переменной х.
9
Квантор всеобщности обобщает , а квантор существования – в случае предикатов, определённых на бесконечных множествах. Т.е. играют роль бесконечности и .
Утверждение 11.2. Если Р(х) – одноместный предикат определённый на конечном множестве S2 = {a1, a2, … an . Тогда справедливо:
x P(x) ≡ Р(a1) P(a2) … P(an).
x P(x) ≡ Р(a1) P(a2) … P(an).
Доказательство. из определения кванторов и логических операций.
!!! 1. Высказывания можно считать предикатами, не содержащими переменных, т е 0-местными предикатами.
2.Кванторы можно рассматривать как отображения уменьшающие размерность на 1.
3.Формулы алгебры высказываний от n высказывательных переменных можно рассматривать как n-местные предикаты от этих переменных.
10