Лекция № 8

Тема: ТЕОРЕМЫ В ИСЧИСЛЕНИИ ВЫСКАЗЫВАНИЙ

Основные вопросы, рассматриваемые на лекции:

1. Пример доказательства теорем

2. Доказательства производных правил вывода

3. Теорема дедукции

Краткое содержание лекционного материала

Теоремы подразделяются на аксиомы и на доказываемые теоремы. Среди правила вывода также имеется основное правило (MP) и производные правила вывода – доказываемые следствия из конечного множества формул.

Приведем примеры теоремы системы S ₁:

(T ₁) |¾ A Þ A.

Построим вывод теоремы (T ₁):

1) (A Þ((A Þ A)Þ A))Þ(((A Þ A)Þ A)Þ(A Þ A)) (A ₂)

2) A Þ((A Þ A)Þ A) (A ₁)

3) ((A Þ A)Þ A)Þ(A Þ A) (MP), 2), 1)

4) A Þ(A Þ A) (A ₁)

5) A Þ A (MP), 4), 3)

Приведем пример производного правила вывода системы S ₁:

(P ₁) A |¾ B Þ A.

Построим вывод правила (P ₁):

1) A гипотеза

2) A Þ(B Þ A) (A ₁)

3) B Þ A (MP), 1), 2)

Далее для доказательства теорем и правил, мы приводим сокращенные выводы, в которых имеются не только аксиомы и заключения правила (MP), но и доказанные теоремы и заключения доказанных новых правил вывода (конечно, при условии, что посылки предшествуют заключениям).

Следующее правило вывода называется правилом силлогизма:

(P ₂) A Þ B, B Þ C |¾ A Þ C.

Построим (сокращенный) вывод правила (P ₂):

1) A Þ B гипотеза

2) B Þ C гипотеза

3) A Þ(B Þ C) (P ₁), 2)

4) (A Þ(B Þ C))Þ((A Þ B)Þ(A Þ C)) (A ₂)

5) (A Þ B)Þ(A Þ C) (MP), 3), 4)

6) A Þ C (MP), 1), 5)

«Две посылки импликации можно будет переставлять местами»:

(P ₃) A Þ(B Þ C)|¾ B Þ(A Þ C).

Вывод правила (P ₃):

1) A Þ(B Þ C) гипотеза

2) (A Þ(B Þ C))Þ((A Þ B)Þ(A Þ C)) (A ₂)

3) (A Þ B)Þ(A Þ C) (MP), 1), 2)

4) B Þ(A Þ B) (A ₁)

5) B Þ(A Þ C) (P ₂), 4), 3)

«Из двойного отрицания следует сама формула»:

(T ₂) |¾ØØ A Þ A.

Вывод теоремы (T ₂):

1) (Ø A ÞØØ A)Þ((Ø A ÞØ A)Þ A) (A ₃)

2) (Ø A ÞØ A)Þ((Ø A ÞØØ A)Þ A) (P ₃), 1)

3) Ø A ÞØ A (T ₁)

4) (Ø A ÞØØ A)Þ A (MP), 2), 3)

5) ØØ A Þ(Ø A ÞØØ A) (A ₁)

6) ØØ A Þ A (P ₂), 5), 4)

«Из формулы следует ее двойное отрицание»:

(P ₄) A |¾ØØ A.

Вывод правила (P ₄):

1) (ØØØ A ÞØ A)Þ((ØØØ A Þ A)ÞØØ A) (A ₃)

2) ØØØ A ÞØ A (T ₂)

3) (ØØØ A Þ A)ÞØØ A (MP), 1), 2)

4) A гипотеза

5) ØØØ A Þ A (P ₁), 4)

6) ØØ A (MP), 5), 3)

«Из отрицания посылки следует вся импликация»:

(P ₅) Ø A |¾ A Þ B.

Вывод правила (P ₅):

1) Ø A гипотеза

2) (Ø B ÞØ A)Þ((Ø B Þ A)Þ B) (A ₃)

3) Ø B ÞØ A (P ₁), 1)

4) (Ø B Þ A)Þ B (MP), 3), 2)

5) A Þ(Ø B Þ A) (A ₁)

5) A Þ B (P ₂), 5), 4)

Версия закона о противоречии:

(P ₆) A,Ø A |¾ B.

Вывод правила (P ₆):

1) A гипотеза

2) Ø A гипотеза

3) A Þ B (P ₅), 2)

4) B (MP), 1), 3)

Версия правила (MP):

(P ₇) A |¾(A Þ B)Þ B.

Вывод правила (P ₇):

1) (A Þ B)Þ(A Þ B) (T ₁)

2) A Þ((A Þ B)Þ B) (P ₃), 1)

3) A гипотеза

4) (A Þ B)Þ B (MP), 3), 2)

«Если посылка истинна, а заключение ложно, то импликация ложна»:

(P ₈) A,Ø B |¾Ø(A Þ B).

Вывод правила (P ₈):

1) A гипотеза

2) Ø B гипотеза

3) (A Þ B)Þ B (P ₇), 1)

4) ØØ(A Þ B)ÞØ B (P ₁), 2)

5) ØØ(A Þ B)Þ(A Þ B) (T ₂)

6) ØØ(A Þ B)Þ B (P ₂), 5), 3)

7) (ØØ(A Þ B)ÞØ B)Þ((ØØ(A Þ B)Þ B)ÞØ(A Þ B)) (A ₃)

8) (ØØ(A Þ B)Þ B)ÞØ(A Þ B) (MP), 4), 7)

9) Ø(A Þ B) (MP), 6), 8)

В силу правила (MP) справедливо следующее утверждение:

если G|¾ A Þ B, то G, A |¾ B.

Обратное утверждение называется теоремой дедукции и существенно упрощает доказательства некоторых теорем исчисления высказываний.

Теорема дедукции. Если G, A |¾ B, то G|¾ A Þ B.

Доказательство. Применим индукцию по следствиям.

Если B – аксиома или B ÎG, то G|¾ A Þ B по правилу (P ₁).

Если B = A, то |¾ A Þ B в силу теоремы (T ₁).

Пусть следствие G, A |¾ B получается по правилу (MP) из формул D и D Þ B, таких, что G, A |¾ D и G, A |¾ D Þ B. Тогда, по индуктивному предположению, G|¾ A Þ D и G|¾ A Þ(D Þ B). Далее, в силу аксиомы (A ₁), верно, что G|¾(A Þ(D Þ B))Þ((A Þ D)Þ(A Þ B)). К этим трем следствиям из множества G два раз применим (MP), и получим G|¾ A Þ B. ÿ

Следствие. Если A |¾ B, то |¾ A Þ B.

При помощи теоремы дедукции легче доказываются многие теоремы и правила вывода исчисления высказывания. Для примера приведем доказательства правил (P ₂) и (P ₃) при помощи теоремы дедукции.

(P ₂¢) A Þ B, B Þ C, A |¾ C.

Вывод правила (P ₂¢):

1) A Þ B гипотеза

2) B Þ C гипотеза

3) A гипотеза

4) B (MP), 3), 1)

5) C (MP), 4), 2)

По теореме дедукции из (P ₂¢) следует (P ₂).

(P ₃¢) A Þ(B Þ C), B, A |¾ C.

Вывод правила (P ₃¢):

1) A Þ(B Þ C) гипотеза

2) B гипотеза

3) A гипотеза

4) B Þ C (MP), 3), 1)

5) C (MP), 2), 4)

По теореме дедукции из (P ₃¢) следует (P ₃).