Элементарной конъюнкцией называется конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.
Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции элементарных конъюнкций.
Процедура приведения к ДНФ:
1. Все отрицания «спустить » до переменных по формулам (6) и (8).
Раскрыть скобки с помощью (1),(3),(4).
Удалить лишние конъюнкции и повторения переменных с помощью (5),(9),(10).
Удалить константы с помощью (7).
Приведение к конъюнктивной нормальной форме (КНФ)
Элементарной дизъюнкцией называется дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.
Конъюнктивной нормальной формой называется конъюнкция элементарных дизъюнкций.
Процедура приведения ДНФ к КНФ:
1. Применить к формуле правило двойного отрицания:
F=k1∨k2∨…∨kn= k1∨k2∨…∨kn =q1 ˅q2…˅qn, где qi – элементарные конъюнкции.
С помощью правил де Моргана освободиться от второго отрицания и преобразовать отрицания элементарных конъюнкций в элементарные дизъюнкции.
Логика предикатов
Предикат – это повествовательное предложение, содержащее предметные переменные, определенные на соответствующих множествах; при замене переменных конкретными элементами этих множеств предложение принимает значение «истинно» или «ложно».
Например:
А – «Рубль – валюта России» - истинно;
В – «Доллар – валюта России» - ложно;
С – «Доллар – валюта США» - истинно.
Р(х) – «х - валюта России », одноместный предикат.
Пусть хЄ { рубль, доллар, фунт стерлингов, евро }.
Р(х,у) – «х – валюта у », двухместный предикат.
Пусть уЄ { Россия, Германия, Англия, США }.
С помощью логических связок и скобок предикаты могут объединяться в различные логические – предикатные формулы.
Исследование предикатных формул и способов установления их истинности является основным предметом логики предикатов.
Основные понятия
n – местный предикат – это функция Р(х1,х2,х3,…,хn) от n переменных, принимающих значение из заданных множеств, так что х1Є М1, х 2Є М2,..,х nЄ Мn, а сама функция принимает два логических значения В = { И,Л} или В = {1,0}.
Множества Мi – называются предметными областями предиката.
Тип функции Р: Мn®В.
С помощью логических связок и скобок предикаты могут объединяться в различные логические предикатные формулы.
Исследование предикатных формул и способов установления их истинности является основным предметом логики предикатов.
n – местный предикат – это функция Р(х1,х2,х3,…,хn) от n переменных, принимающих значение из заданных множеств, так что х1Є М1, х 2Є М2,..,х nЄ Мn, а сама функция принимает два логических значения В = { И,Л} или В = {1,0}.
Множества Мi – называются предметными областями предиката.
Тип функции Р: Мn®В.
Алгебраические предикаты
1.Предикат тождества Е: N2 ® B:
Е(а1,а2)=1 ⇔ а1 = а2
2. Предикат порядка Q: N2 ® B:
Q(a1,a2)=1 ⇔ а1 ≤ а2
3. Предикат делимости D: N2 ® B:
D(a1,a2)=1 ⇔ а1 делится на а2
4. Предикат суммы S: N3 ® B:
S(a1,a2,a3)=1 ⇔ а1 + а2 = а3
5. Предикат произведения П: N3 ® B:
П(а1,а2,а3)=1 ⇔ а1 · а2 = а3
Упражнения:
- Проиллюстрировать на примере предиката делимости понятие переменного высказывания, истинного высказывания, ложного высказывания.
- Записать формулой логики предикатов свойство транзитивности отношения делимости целых чисел.
- Дать словесные формулировки следующих составных высказываний:
(S(a,b,c)∧ D(a,d)∧D(b,d))® D(c,d)
(П(a,b,c)˄(D(a,3)˅D(b,3))→D(c,3)
S(a,b,c)= S(b,a,c)
Кванторы
Пусть Р(х) – предикат, определенный на множестве М.
Высказывание «для всех х из М Р(х) - истинно» обозначается ∀х Р(х),
знак ∀х называется квантором общности.
Высказывание «существует такой х из М, что Р(х) - истинно» обозначается Ǝх, знак Ǝ называется квантором существования.
Переход от Р(х) к ∀х Р(х) или Ǝх Р(х) называется связыванием переменной х, или навешиванием квантора на переменную х (или на предикат Р).
Переменная, на которую навешен квантор, называется связанной, не связанная квантором переменная называется свободной.
Навешивать кванторы можно и на многоместные предикаты. Выражение, на которое навешивается квантор ∀х и Ǝх называется областью действия квантора.
Дать словесную формулировку следующей предикатной формулы:
Пусть х определен на множестве людей М, а Р(х) - «х - смертен».
∀х Р(х)=
Ǝх Р(х)=
∀х Р(х)=
Ǝх Р(х)=
Выполнимость и истинность
При логической интерпретации формул логики предикатов возможны три основных ситуации:
- Формула F(х1,х2,…,хn) называется просто выполнимой (ПВ), если существует такая подстановка констант (а1,а2,…,аn), что формула F(а1,а2,…,аn)=1.
2. Формула F(х1,х2,…,хn) называется тождественно истинной (ТИ), если она выполнима при любых подстановках констант.
3. Формула F(х1,х2,…,хn) называется тождественно ложной (ТЛ), если она невыполнима ни при каких подстановках констант.
Упражнения.
Определить вид формулы:
1. (П(x,y,z)∧П(x,y,u))®E(z,u);
2. П(х,х,у);
3. П(х,у,у);
4. (S(x,y,z)∧S(x,y,u))®E(z,u);
5. (S(x,y,z)∧S(y,x,u))®E(z,u);
6. (П(x,x,y)®S(x,x,y));
7. (П(x,y,z)∧ ך E(x,y))®S(x,y,z);
8. Q(x,z)®(S(x,y,z)∨E(x,z));
9. П(x,y,z)®D(z,y);
10. S(x,х,y)® S(у,y,х)
Доказательство истинности формулы методом от противного:
∀х ((Р(х)∧Q(х))® Р(х))
Пусть формула ложна. Тогда:
Р(х)∧Q(x)=1 и Р(х)=0;
Р(х)∧Q(х)=1, тогда Р(х)=1 и Q(х)=1.
Получили противоречие.
Следовательно предположение, что формула ложна, неверно, следовательно формула истинна.
∀х ((Р(х)∧Q(х))® Р(х))=1