Доказательство клауз. Лекция 7

1. 2. Доказательство клауз

Лекция 7
1

2. Понятие высказывания

Определение
Высказывание – утверждение об изучаемых в рамках
области знаний объектах, имеющее однозначно и точно
определенное значение.
В классической (булевой, двузначной) логике
высказываний значение может быть либо истинным либо
ложным.
В русском языке под высказыванием понимается
повествовательное предложение, относительно которого
можно сказать, истинно оно или ложно.
2

3. Понятие формулы алгебры логики (алгебры высказываний)

Определение
1) Логические переменные, символы 0 и 1 – формулы алгебры логики.
2) Если А – логическая формула, то (A) – логическая формула алгебры
логики.
3) Если А, В – логические выражения, то A , А В, А В, А В, А~В –
формулы алгебры логики.
3

4. Основные определения

Опр. Пусть A(x1, ..., xn) - пропозициональная формула, где x1, ..., xn входящие в нее пропозициональные переменные.
Конкретный набор истинности значений, приписанных
переменным x1, ..., xn , называется интерпретацией формулы
А.
Формула может быть истинной (иметь значение 1) при одной
интерпретации и ложной (иметь значение 0) при другой
интерпретации.
Опр. Формула, истинная при некоторой интерпретации,
называется выполнимой. Формула, истинная при всех
возможных интерпретациях, называется общезначимой (или
тавтологией).
Опр. Формула, ложная при всех возможных интерпретациях,
называется невыполнимой (или противоречием).
Опр. Две формулы назовем равносильными, если для любых наборов
они принимают одинаковые значения.
4

5. Основные определения

Опр. Говорят, что формула В логически следует из
формул A1, A2 ,..., An :
A1, A2 ,..., An ╞ B,
если формула В имеет значение
1 при всех
интерпретациях,
при
которых
формулы
A1, A2 ,..., An имеют одновременно значение 1.
Свойства:
1) A1, A2 ,..., An ╞ B, A1, A2 ,..., An , ¬B ╞;
2) A1, A2 ,..., An ╞ ¬B, A1, A2 ,..., An , B ╞;
3) A1, A2 ,..., An ╞ B→С, A1, A2 ,..., An , B ╞ С –
теорема о дедукции;
5
4) A╞ B, B╞ C, A╞ С – правило силлогизма.

6. Доказательство от противного

1)
- Предположить, что существует такая интерпретация
формул A1, A2 ,..., An, B, при которой
A1 =1, A2 =1,..., An=1; B = 0;
- прийти к противоречию.
2)
- Предположить, что существует такая интерпретация
формул A1, A2 ,..., An, B, при которой
A1 =1, A2 =1,..., An=1, B = 1,
следовательно,
A1A2...An B = 1;
- прийти к противоречию.
6

7. Доказательство от противного

Пример 1:
А → (В С), ¬В D, (Е → ¬F) → ¬D, ¬В (А ¬Е) |= В → Е;
1)
А → (В С), ¬В D, (Е → ¬F) → ¬D, ¬В (А ¬Е) |= В → Е;
(1)
(2)
(3)
(4)
(5)
Предположим, что существуют значения переменных A, B, C, D, E, F,
для которых (1) = 1, (2) = 1, (3) = 1, (4) = 1, (5) = 0.
(5): В → Е = 0 B = 1, E = 0;
(4): ¬В (А ¬Е) = 1 0 (А 1) = 1 A = 1;
(2): ¬В D = 1 0 D = 1 D = 1;
(3): (Е → ¬F) → ¬D = 1 (0 → ¬F) → 0 = 1 1 → 0 = 1 – противоречие.
7

8. Доказательство от противного

2)
А → (В С), ¬В D, (Е → ¬F) → ¬D, ¬В (А ¬Е), ¬(В → Е) |=;
(1)
(2)
(3)
(4)
(5)
Предположим, что существуют значения переменных A, B, C, D, E, F,
для которых (1) = 1, (2) = 1, (3) = 1, (4) = 1, (5) = 1, следовательно,
конъюнкция (1) (2) (3) (4) (5) = 1.
ДНФ для (5): ¬(В → Е) = B ¬Е;
ДНФ для (1): А → (В С) = ¬А В С;
ДНФ для (3): (Е → ¬F) → ¬D = E F ¬D;
(¬А В С)(¬В D)(E F ¬D)(¬В А ¬Е)(В ¬Е) =
= (¬А¬В (¬А В С) D)(E F ¬D) А B ¬Е =
= (¬А¬В (¬А В С) D) А B ¬D ¬Е =
= (¬А¬В (¬А В С) D) А B ¬D ¬Е = 0 – противоречие.
8

9. Доказательство от противного

Пример 2:
А → С, D → F, В → Е, ¬D → ¬С, А → В |= А → (Е F);
(1)
(2)
(3)
(4)
(5)
(6)
А → (Е F) = 0 A = 1, E F = 0 A = 1, E =0 или F = 0;
1.
(6): A = 1, E =0;
(5): А → В = 1 B = 1;
(3): B → E = 1 E = 1 – противоречие;
2.
(6): A = 1, F =0;
(1): А → C = 1 C = 1;
(4): ¬D → ¬С = 1 D = 1;
(2): D → F = 1 F = 1 – противоречие.
9

10. Метод резолюций

- Привести Ai, ¬B представлены в КНФ;
- составить конъюнкцию A1 A2...An¬B;
- последовательно применять правило резолюции
A C, B C
A B
к дизъюнктам конъюнкции A1 A2...An¬B.
При последовательном применении правила
резолюций происходит уменьшение числа
переменных, вплоть до их полного исчезновения
(если клауза верна).
10

11. Метод резолюций

Пример:
А → В, С → D, B → E, D → F, Е → ¬F, А → С |= ¬А
По свойству 1:
А → В, С → D, B → E, D → F, Е → ¬F, А → С, А |=;
После приведения посылок к КНФ:
¬A В, ¬С D, ¬В Е, ¬D F, ¬E ¬F, ¬A С, А 0 |=;
(1)
№
1.
2.
3.
4.
5.
6.
(2)
Вывод
¬В ¬F
¬С F
¬A ¬F
¬A F
¬A
0
(3)
(4)
(5)
(6)
(7)
Как получили
(3), (5)
(2), (4)
1, (1)
2, (6)
3, 4
5, (7)
11

12. Аксиоматический метод

Логика высказывания является расширением
логики Буля. Поэтому все истинные тождества
логики
Буля
автоматически
становятся
справедливыми клаузами логики высказываний.
Например, закон склеивания:
(A ¬В) (A В) = A
можно представить следующими справедливыми
клаузами:
(A ¬В) (A В) |= A,
A |= (A ¬В) (A В).
12

13. Аксиоматический метод

Пример:
№
Вывод
Как
получили
1
С
МP: (6), (1)
2
D
MT: (4), 1
3
F
MP: 2, (2)
4
B
MP: (6), (5)
По свойству 1:
5
E
MP: 4, (3)
А → С, D → F, В → Е, ¬D → ¬С, А → В, А, ¬(Е F) |=;
6
¬Е
противоречие
TP: 3, (7)
7
¬F
противоречие
TP: 5, (7)
А → С, D → F, В → Е, ¬D → ¬С, А → В |= А → (Е F);
(1)
(2)
(3)
(4)
(5)
(6)
По свойству 3 (теореме о дедукции):
А → С, D → F, В → Е, ¬D → ¬С, А → В, А |= (Е F);
(1)
(1)
(2)
(2)
(3)
(3)
(4)
(4)
(5) (6)
(5)
(6)
(7)
(7)
По закону Де Моргана:
А → С, D → F, В → Е, ¬D → ¬С, А → В, А, ¬Е ¬F |=;
(1)
(2)
(3)
(4)
(5)
(6)
(7)
13