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

Если 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) является тавтологией.

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

Понятие тавтологиисовпадает с понятиемтеоремываксиоматической системе.Аксиоматическая система обладает свойством адекватности, то есть она состоит из множества аксиом, считающихся тавтологиями. Кроме аксиом в аксиоматическую систему входит множествоправил вывода, позволяющих строить новые тавтологии из аксиом и уже полученных тавтологий. Выводимая формула обозначаетсяú--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.

2.2.7 Правила вывода исчисления высказываний

Существует три обязательных правила вывода, входящих в множество Bв исчислении высказываний:

1. Все аксиомы выводимы.

2. Правило одновременной подстановки: если некоторая тавтология U содержит атомP, то одновременная замена всех вхождений атомаPвUна любую формулуQприводит к порождению тавтологии.

3. Modus Ponens(заключение): еслиP– тавтология, иP® Q, то Q – тавтология.

Часто необходимо преобразовывать формулы из одной формы в другую. Поэтому, кроме аксиом и правил вывода необходимо иметь набор эквивалентных формул (законов), которые позволяют производить преобразования формул:

1. P « Q = P ® Q Ù Q ® P;

2. P ® Q = Ø P Ú Q;

3. Коммуникативные законы: P Ú Q = Q Ú P; P Ù Q = Q Ù P;

4. Ассоциативные законы: (P Ú Q) Ú R = Q Ú (P Ú R); (P Ù Q) Ù R = Q Ù (P Ù R);

5. Дистрибутивные законы: P Ú (Q Ù R) = (P Ú Q) Ù (P Ú R); P Ù (Q Ú R) = (P Ù Q) Ú (P Ù R);

6. Законы идемпотентности: P Ú P = P; P Ù P = P;

7. P Ú Л = P; P Ù И = P;

8. P Ú И = И; P Ù Л = Л;

9. P Ú ØP = И; P Ù ØP = Л;

10. Ø(ØP )= P;

11. Законы де Моргана: Ø(P Ú Q) = ØQ Ù ØP; Ø(P Ù Q) =ØQ Ú ØP;

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

Утверждение 1.

Если P - тавтология, то Q ®P – тавтология.

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

Доказательство следует из аксиомы 1 классической системы аксиом и правила вывода 3.

По аксиоме 1 P ®( Q ® P),тогда, еслиP– тавтология, то по правилуModus PonensQ ® P– тоже тавтология.

Утверждение 2.

Свойство транзитивности отношения следования: если P® Q,Q® R– тавтологии, тоP® R– тавтология.

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

Эквивалентная формулировка утверждения 2 заключается в том, что формула (((P® Q) Ù (Q® R))®(P® R)) является тавтологией.Воспользуемся законами эквивалентных преобразований исчисления высказываний:

(((P® Q) Ù (Q® R))®(P® R))«

Ø ((ØPÚ Q) Ù (ØQÚ R)) Ú (ØPÚ R) «

((PÙ ØQ) Ú (Q Ù ØR)) Ú (ØP Ú R) «

((PÚ Ø P) Ù (ØQ Ú Ø P)) Ú ((Q Ú R) Ù (ØR Ú R)) «

((И Ù (ØQ Ú Ø P)) Ú ((Q Ú R) Ù И)) «

ØQ Ú Ø P Ú Q Ú R «

И Ú Ø P Ú Q «И.

Утверждение 3.

Теорема дедукции: необходимым и достаточным условием выводимости Qиз гипотезR, Pявляется выводимостьP® QизR. Данную теорему можно записать следующим образом:R, P ú-- Q« R ú-- (P® Q).