42 |
Математическая логика |
¬D) (¬A&¬B&C&D)(¬A&B&¬C&D) (¬A&B&C&D) (A&¬B&C&¬D) (A&
B&¬C&D) и СКНФ F=(A¬B C D)&(A¬B¬C D)&(¬A B C D)&(¬A B
C¬D)&(¬A B¬C
¬D)& (¬A¬B C D)&(¬A¬B¬C D)&(¬A¬B¬C¬D).
Элементарные конъюнкции формируются для значений формулы “и”. Число элементарных конъюнкций СДНФ равно числу истинных значений формулы. Пропозициональные переменные, элементарной конъюнкции записываются без изменений, если их значение равно “и” и с логической связкой “¬”, если их значение равно “л”.
Элементарные дизъюнкции СКНФ формируются для значения формулы, равной “л”. Число элементарных дизъюнкций равно числу ложных значений формулы. Пропозициональные переменные элементарной дизъюнкции, записываются без изменений, если их значение равно “л” и с логической связкой “¬”, если их значение равно
“и”.
1.1.2. Исчисление высказываний
Исчисление высказываний – это формальная систе-
ма, позволяющая формировать новые высказывания путем указания исходных высказываний, имеющих значение «истина», а также аксиом и правил вывода, каждое из которых описывает, как формировать новое высказывание из исходных и уже построенных высказываний. Поэтому изучение исчисления высказываний следует начинать с
1.1. Логика высказываний |
43 |
определения аксиом и правил вывода, обеспечивающих доказательство истинности заключения.
Аксиома – это высказывание, имеющее значение истины при любых значениях пропозициональных переменных, входящих в это высказывание.
Правилом вывода называют такое отношение между высказываниями, которое позволяет из множества посылок и аксиом делать выводы об истинности заключения.
Доказательством или выводом называют такую ли-
нейно упорядоченную последовательность высказываний, каждое из которых является либо аксиомой, либо выводимо из одного или нескольких предыдущих высказываний.
Задание необходимого числа аксиом определяет пол-
ноту исчисления, а задание правил вывода – метод исчисления.
1.1.2.1. Интерпретация формул
Определение истинного или ложного значений формулы высказывания для данного набора пропозициональных переменных называют интерпретацией , а все мно-
жество формул - полем интерпретации.
Наиболее простой способ определения истинности или ложности формулы является использование таблиц истинности. Основной недостаток таблиц истинности состоит в том, что при большом числе пропозициональных переменных число строк таблицы равно 2n, а число столбцов не меньше (n+m), где n – число пропозициональных переменных, а m – число логических операций.
axiÖma (гр.) – отправное, исходное положение, лежащее в основе доказательств теорем.
interpretatio (лат.) – истолкование, разъяснение смысла чего-л.
44 |
Математическая логика |
Все множество формул можно разбить на три класса: тождественно истинные, тождественно ложные и выводимые.
Тождественно истинные формулы – это особый класс формул, которые принимают значение «истина» при любом значении пропозициональных переменных, входящих в формулу. Эти формулы играют роль аксиом и законов логики высказываний.
Например. F = ((A→B)&(A→C)→(A→(B&C))=и.
|
|
|
|
|
|
|
Таблица 1.6 |
|
|
|
||
|
A |
B |
C |
A→ A→ B& |
4&5 1→67→8 |
В |
девятом |
|||||
|
B |
C |
C |
|||||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
столбце |
таб- |
|
|
л |
л |
л |
и |
и |
л |
и |
и |
и |
лицы 1.6 |
фор- |
|
|
л |
л |
и |
и |
и |
л |
и |
и |
и |
|||
|
л |
и |
л |
и |
и |
л |
и |
и |
и |
мула |
имеет |
|
|
л |
и |
и |
и |
и |
и |
и |
и |
и |
значение |
ис- |
|
|
и |
л |
л |
л |
л |
л |
л |
л |
и |
|||
|
и |
л |
и |
л |
и |
л |
л |
л |
и |
тины для всех |
||
|
и |
и |
л |
и |
л |
л |
л |
л |
и |
возможных |
||
|
и |
и |
и |
и |
и |
и |
и |
и |
и |
|
|
|
|
|
Тождественно ложные формулы - это особый класс |
||||||||||
формул, которые принимают значение «ложь» |
при лю- |
|||||||||||
бых значениях пропозициональных переменных, входящих в формулу.
Например, F=A&(¬B ¬C)&(A→B)&(A→C)=л.
|
|
|
|
|
|
|
|
|
|
Таблица 1.7 |
|
|
|||
|
A |
|
B |
|
C |
|
¬2 ¬ 1& 1→ 1→ 5& 8& |
|
|
|
|||||
|
1 |
|
2 |
|
3 |
|
4 |
5 |
6 |
7 |
8 |
9 |
|
В |
девятом |
|
л |
|
л |
|
л |
|
и |
л |
и |
и |
л |
л |
|
||
|
л |
|
л |
|
и |
|
и |
л |
и |
и |
л |
л |
|
столбце |
табли- |
|
л |
|
и |
|
л |
|
и |
л |
и |
и |
л |
л |
|
||
|
л |
|
и |
|
и |
|
л |
л |
и |
и |
л |
л |
|
цы 1.7 формула |
|
|
и |
|
л |
|
л |
|
и |
и л л л |
л |
|
ее з а е е |
||||
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
1.1. Логика высказываний |
45 |
|||||
|
и |
|
л |
|
и |
|
и |
и |
л |
л |
л |
л |
|
|
|
|
|
|
|
|
|
||||||||||
|
и |
|
и |
|
л |
|
и |
и |
и |
л |
и |
л |
|
|
|
|
и |
|
и |
|
и |
|
л |
л |
и |
и |
л |
л |
|
|
|
Выводимые формулы - это класс формул, которые принимают значения истина или ложь в зависимости от значений пропозициональных переменных.
Например, F=(¬А→C&¬В)&(¬C→B&¬A)&(A→¬C).
|
|
|
|
|
Таблица 1.8 |
|
|
|
||
ABC |
3&¬¬1→2&¬¬3→1→¬ 5&7 |
В |
девятом |
|
||||||
1 2 3 |
4 |
5 |
6 |
7 |
8 |
9 |
столбце |
табли- |
|
|
ллл |
л |
л |
л |
л |
|
и |
л |
|
||
лли |
и |
и |
л |
и |
|
и |
и |
цы 1.8 |
формула |
|
лил |
л |
л |
и |
и |
|
и |
л |
|||
лии |
л |
л |
и |
и |
|
и |
л |
имеет значение |
||
илл |
л |
и |
л |
л |
|
и |
л |
истины |
только |
|
или |
и |
и |
л |
и |
|
л |
л |
|||
иил |
л |
и |
л |
л |
|
и |
л |
для А=л, В=л и |
||
иии |
л |
и |
л |
и |
|
л |
л |
|
|
|
1.1.2.2. Аксиомы исчисления высказываний
Среди множества тождественно истинных формул можно выделить подмножества, которые представляют аксиомы исчисления высказываний. В зависимости от числа логических связок могут быть найдены различные полные системы аксиом.
Например, известна полная система аксиом, опирающаяся на две логические связки «¬» и «→», которая содержит три аксиомы:
•(F1→(F2→F1)),
•(F1→(F2→F3))→((F1→F2)→(F1→F3)),
•(¬F1→¬F2)→((¬F1→F2)→F1).
Возможны и другие полные системы аксиом, опирающиеся на другие сочетания логических связок. Так
46 |
Математическая логика |
система аксиом, опирающаяся на четыре логические связки ¬, &, , →, содержит двенадцать аксиом:
•А1. F1→(F2→F1),
•А2. (F1→F2)→ ((F2→ F3)→ → (F1→ F3)),
•А3. (F1& F2)→F1,
•А4. (F1& F2)→F2,
•А5. F1→(F2→(F1&F2)),
•А6. F1→(F1 F2),
•А7. F2→(F1 F2),
•А8. (F1→F3)→((F2→F3)→((F1 F2)→F3)),
•А9. (F1→F2)→(( F1→¬F2)→ ¬F1),
•A10. (F1→F2)→((F1&F3)→(F2&F3)),
•A11. (F1→ F2)→((F1 F3)→(F2 F3)),
•А12. ¬¬F1 → F1.
Приведенные полные системы аксиом равносильны между собой в том смысле, что порождают одно и то же множество формул. Их равносильность может быть доказана выводимостью аксиом первой системы из аксиом второй и наоборот.
Для проверки истинности аксиом достаточно рассмотреть аксиомы A2 и A8 (см. таблицы 1.9 и 1.10). В 9-м столбце каждой таблицы приведены значения этих формул.
Таблица
1.9
F1 |
F2 |
F3 |
1→ 1→ 2→ 1→ 7→ 4→ |
|||||
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Таблица 1.10
F1 |
F2 |
F3 |
1 1→ 2→ 4→ 6→ 5→ |
|||||
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
|
1.1. Логика высказываний |
47 |
|||||
|
|
|
|
|
|
|
|
|
|
л |
л |
л |
и и и и и и |
л |
л |
л |
л и и и и и |
|
|
л |
л |
и |
и и и и и и |
|
л |
л |
и |
л и и и и и |
|
л |
и |
л |
и и л и и и |
|
л |
и |
л |
и и л л и и |
|
л |
и |
и |
и и и и и и |
|
л |
и |
и |
и и и и и и |
|
и |
л |
л |
л л и и л и |
|
и |
л |
л |
и л и л л и |
|
и |
л |
и |
л и и и и и |
|
и |
л |
и |
и и и и и и |
|
и |
и |
л |
и л л л и и |
|
и |
и |
л |
и л л л и и |
|
и |
и |
и |
и и и и и и |
|
и |
и |
и |
и и и и и и |
|
Для понимания механизма вывода заключения следует рассмотреть алгебраические правила введения и удаления логических связок. Эти правила – аналог аксиомам исчисления высказываний - существенно облегчают преобразования сложных формул:
П1. Правило введения логической связки «&»: если формулы F1 и F2 истинны, то истинной является их конъюнкция, т. е.
F1 ,F2 Это - аксиома А5.
F1 & F2 .
П2. Правило удаления логической связки «&»: если формула (F1&F2) истинна, то истинными являются форму-
лы F1 и F2, т. е. |
F1 & F2 |
и |
F1 & F2 |
Это - аксиомы А3 и А4. |
||||||
|
F |
F . |
|
|
|
|
|
|||
1 |
|
2 |
|
|
|
|
|
|
|
|
П3. Правило введения логической связки « »: если |
||||||||||
хотя бы одна из формул F1 или F2 истинна, то истинной яв- |
||||||||||
ляется их дизъюнкция, т. е. |
F1 |
или |
F2 |
|
Это - аксиомы |
|||||
|
|
|
|
|
F F |
F F . |
|
|||
|
|
|
1 |
2 |
1 |
2 |
|
|||
А6 и А7.
П4. Правило удаления логической связки « »: если формула (F1 F2) истинна, то истинными могут быть фор-
48 Математическая логика
мулы F1 или F2, т. е. |
|
|
|
|
|
|
|
F1 F2 ,¬F2 |
или |
F1 F2 ,¬F1 |
|
|
|
|
F |
F . |
|
|
||
1 |
|
2 |
|
|
|
|
П5. Правило введения логической связки «→»: если |
||||||
формула F2 истинна, то |
истинной |
является формула |
||||
(F1→F2) при любом значении F1, т. е. |
F2 |
Это - аксиома |
||||
F1 → F2.
А1 («истина из чего угодно»).
П6. Правило контрапозиции: если формула (F1→F2) истинна, то истинной является формула ( F2→ F ), т. е. F1 → F2 Это - аксиома А9.
¬F2 → ¬F1.
П7. Правило введения в формулу (F1→F2) логической связки « »: если формула (F1→F2) истинна, то истинной является формула ((F1 F3)→(F2 F3) при любом значении
F3, т. е.
F1 → F2 Это - аксиома А11.
(F1 F3 ) → (F2 F3 ).
П8. Правило введения в формулу (F1→F2) логической связки «&»: если формула (F1→F2) истинна, то истинной является формула ((F1&F3)→(F2&F3)) при любом значении
F3, т. е.
F1 → F2 Это - аксиома А10.
(F1 & F3 ) → (F2 & F3 ).
П9. Правило силлогизма: если формулы (F1→F2) и (F2→F3) истины, то истинной является формула (F1→F3), т. е.
(F1 → F2 ),(F2 → F3 ) Это - аксиома А2.
(F1 → F3 ).
П10. Правило введения логической связки «↔»: если формулы (F1→F2) и (F2→F1) истинны, то истинной является формула (F1↔F2),