Формы представления формул логики высказываний

Скобочная форма, образуется непосредственно после формализации высказывания.

Дизъюнктивная нормальная форма – дизъюнкция элементарных конъюнкций.

Конъюнктивная нормальная форма – конъюнкция элементарных дизъюнкций.

КНФ также называют клаузальной формой.

Клауза – элементарная дизъюнкция.

Литера, литерал – элементарное высказывание или его отрицание.

Дизъюнкт – дизъюнкция конечного числа литералов.

Хорновский дизъюнкт имеет не более одной не инверсной литеры.

Пример.

.

Хорновские дизъюнкты используются в языке ПРОЛОГ (PROLOG, от PROgramming in LOGic – программирование в логике; разработан в 1972 г. Аланом Колмари) для описания правил типа «Если, то». Кстати, в ПРОЛОГЕ с помощью импликации записываются и так называемые факты: .

.

Т.е. факт – это утверждение истинности некой формулы.

Преобразование в КНФ обычно производится при помощи распределительного закона.

СКНФ получают из КНФ путём добавления к каждому дизъюнкту тождественно ложной литеры.

 

Проблема дедукции в логике высказываний

Помимо равносильности в логике широко используется отношение следования. Говорят, что формула S является следствием множества формул H (записывается так: H├S) если при всех интерпретациях, при которых истинны все формулы из H, истинна также и формула S [32].

Таким образом, тавтология – следствие из пустого множества формул. Записывается так: ├T, т.е. слева от знака ├ нет символа, но он подразумевается равным константе 0, – как в факте.

S является следствием из H тогда и только тогда, когда их импликация истинна H→S≡1:

(H├S)↔[(H→S)≡1];

├(H→S).

Если рассматривается множество формул или гипотез H₁,H₂,…,H_n, то (H₁,H₂,…,H_n)├S↔├(H₁×H₂×…×H_n)→S – т.е. подразумевается импликация из конъюнкций этих формул, которая общезначима. Таким образом, из множества формул выводима формула S (├S).

Фундаментальная проблема логики: определить является ли S следствием из множества формул H (проблема дедукции).

Проблема описывается так: необходимо установить общезначимость следования H→S.

Доказательство может быть проведено следующим образом:

,

или, наоборот, путем доказательства невыполнимости:

.

Во втором случае говорят, что доказывают невыполнимости объединения формулы H и формулы S.

 

ПРОВЕРКА ПРАВИЛЬНОСТИ ЛОГИЧЕСКИХ ВЫВОДОВ.

МЕТОД РЕЗОЛЮЦИЙ

 

Закон контрапозиции

 

На основе данного сложного высказывания А®В можно сформулировать обратное ему высказывание B®A. Нетрудно убедиться, что оно не равносильно исходному.

Для всякого сложного высказывания A®B можно сформулировать противоположное . Нетрудно убедиться, что оно не равносильно исходному.

Высказывание типа называется обратно – противоположным.

Нетрудно убедиться, что оно равносильно исходному:

.

Такая равносильность называется законом контрапозиции [25].

Согласно этому закону:

1) высказывания A®B и одновременно истинны либо одновременно ложны;

2) высказывание, которое является обратно противоположной данной теореме A®B также является теоремой (здесь сложное высказывание называется теоремой);

3) вместо данной теоремы можно доказать обратно противоположную ей теорему.

Кроме того, если высказывание A®B – теорема, то A есть достаточное условие B, а B – необходимое условие A.

Если оба высказывания являются теоремами (A®B, B®A; т.е. A«B), то A – необходимое и достаточное условие B, а B – необходимое и достаточное условие A.

Если A®B – теорема, а B®A не теорема, то A – достаточное, но не необходимое условие B, а B – необходимое, но не достаточное условие A.