Система аксиом исчисления высказываний

Определение логического следствия

Если Q - тавтология, то ее обозначают как ъ= Q. Если E – множество формул, то запись E ъ= Q означает, что при всех интерпретациях, при которых истинны все формулы из E, истинна также формула Q. Формула Q называется логическим следствием из E. Таким образом, тавтология – логическое следствие из пустого множества.

Если E содержит единственный элемент P, то P ъ= Q. Тогда Q является логическим следствием P тогда и только тогда, когда импликация P ® Q есть тавтология, или P ъ= Q « ъ= (P® Q).

В более общем виде, можно написать:

{ F₁, F₂,…, F_n }ъ= Q « ъ= (F₁ Щ F₂ Щ…F_n) →ъъ= Q.

Выявление того факта, что из множества высказываний (формул исчисления) логически следует некоторое другое высказывание (формула) и является, по существу, одной из основных задач исчисления.

Определение 5: Пусть даны формулы F₁, F₂,…, F_n и формула Q. Говорят, что Q есть логическое следствие формул F₁, F₂,…, F_n тогда и только тогда, когда для всякой интерпретации I, в которой F₁ Щ F₂ Щ…F_n истинна, Q также истинна. F₁, F₂,…, F_n называются аксиомами (или постулатами, или посылками, или гипотезами).

Если формулы P и Q – логические следствия друг друга, то они называются логически эквивалентными. Такая ситуация имеет место тогда и только тогда, когда формула (P « Q) является тавтологией.

Понятие тавтологии совпадает с понятием теоремы в аксиоматической системе. Аксиоматическая система обладает свойством адекватности, то есть она состоит из множества аксиом, считающихся тавтологиями. Кроме аксиом в аксиоматическую систему входит множество правил вывода, позволяющих строить новые тавтологии из аксиом и уже полученных тавтологий. Выводимая формула обозначается ъ--P.

Исчисление высказываний тоже является аксиоматической системой. Любая аксиоматическая система должна удовлетворять следующим требованиям:

1. Непротиворечивость: невозможность вывода отрицания уже доказанного выражения (которое считается общезначимым);

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

3. Полнота (взаимность адекватности): любая тавтология выводима из системы аксиом. В адекватной системе аксиом любая выводимая формула есть тавтология, то есть верно, что ъ-- P® ъ= P. Соответственно в полной систем верно: ъ= P® ъ--P.

Некоторое множество тавтологий составляет систему аксиом A. Приведем две наиболее известные системы аксиом, обладающие всеми вышеперечисленными свойствами.

Классическая система аксиом:

1. P ®(Q ® P);

2. (P ®(Q ® R))®((P ® Q)®(P ® R));

3. (ШP ® Ш Q) ® ((ШP ® Q) ® P).

Система аксиом Новикова:

1. P ®(Q ® P);

2. (P ®(Q ®R))®((P ® Q)®(P ® R));

3. P Щ Q ® P;

4. P Щ Q ® Q;

5. (P ® Q) ®((P ® R) ®(P ® Q Щ R));

6. P ® P Ъ Q;

7. Q ® P Ъ Q;

8. (P ® R) ®((Q ® R) ®(P Ъ Q ® R));

9. (P ® Q) ®(Ш Q ®Ш P);

10. P ®ШШ P;

11. ШШ P ® P.