Основные эквивалентности исчисления высказываний

Теорема 3. Пусть φ, ψ, χ ‑формулы ИВ. Тогда имеют место эквивалентности:

1) φ∧φ≡φ, φ∨φ≡φ (законы идемпотентности);

2) φ∧ψ≡ψ∧φ, φ∨ψ≡ψ∨φ (законы коммутативности);

3) (φ∧ψ)∧χ≡φ∧(ψ∧χ), (φ∨ψ)∨χ≡φ∨(ψ∨χ) (законы ассоциативности);

4) φ∧(ψ∨χ)≡(φ∧ψ)∨(φ∧χ), φ∨(ψ∧χ)≡(φ∨ψ)∧(φ∨χ) (законы дистрибутивности)

5) (φ∧ψ)≡φ∨ψ, (φ∨ψ)≡φ∧ψ (законы де Моргана);

6) φ≡φ (закон двойного отрицания);

7) φ→ψ≡φ∨ψ;

8) φ∧(φ∨ψ)≡φ, φ∨(φ∧ψ)≡φ (законы поглощения);

9) φ∨(φ∧ψ)≡φ∨ψ, φ∨(φ∧ψ)≡φ∨ψ;

10) φ∧(φ∨ψ)≡φ∧ψ, φ∧(φ∨ψ)≡φ∧ψ.

11) ├φ∨φ.

Доказательство. В примере 15 показано, что φ├φ, покажем, что φ├φ. По теореме о дедукции φ├φ φ→φ (аксиома), значит, φ├φ.

Докажем закон де Моргана (φ∧ψ)≡φ∨ψ. Строим квазивывод формулы (φ∧ψ)→φ∨ψ:

1) ((φ∨ψ)→φ)→(((φ∨ψ)→ψ)→((φ∨ψ)→φ∧ψ)) (схема аксиом 5);

2) φ→φ∨ψ (схема аксиом 6);

3) (φ∨ψ)→φ (к п. 2 применили пример 15);

4) φ→φ (схема аксиом 10);

5) (φ∨ψ)→φ (к пп. 3 и 4 применили пример 13);

6) (φ∨ψ)→ψ (получается аналогично формуле 5);

7) ((φ∨ψ)→ψ)→((φ∨ψ)→φ∧ψ) (к пп.5 и 1 применили правило вывода);

8) (φ∨ψ)→φ∧ψ (кпп. 6 и 7 применили правило вывода);

9) (φ∧ψ)→(φ∨ψ) (к п. 7 применили пример 15);

10) (φ∨ψ)→(φ∨ψ) (схема аксиом 10);

11) (φ∧ψ)→φ∨ψ (к пп. 9 и 10 применили пример 13).
Строим квазивывод формулы φ∨ψ→(φ∧ψ):

1) (φ→(φ∧ψ))→((ψ→(φ∧ψ))→((φ∨ψ)→(φ∧ψ))) (схема аксиом 8);

2) φ∧ψ→φ (схема аксиом 3);

3) φ→(φ∧ψ) (к п. 2 применили пример 15);

4) φ∧ψ→ψ (схема аксиом 4);

5) ψ→(φ∧ψ) (к п. 4 применили пример 15);

6) (ψ→(φ∧ψ))→((φ∨ψ)→(φ∧ψ)) (к пп. 3 и 1 применили правило вывода);

7) (φ∨ψ)→(φ∧ψ) (к 5 и 6 применили правило вывода).

Таким образом, закон де Моргана (φ∧ψ)≡φ∨ψ доказан.

Формула φ(x₁,…,x_n) ИВ называется тождественно истинной (обозначается ╞φ), если φ(x₁,…,x_n) – тождественно истинная формула как формула алгебры высказываний.

Теорема 4 (о полноте). Формула φ ИВ доказуема тогда и только тогда, когда φ тождественно истинна:

├φ ╞φ.

Таким образом, для того чтобы установить, доказуема ли формула ИВ, достаточно составить ее таблицу истинности. Как известно, существует эффективный алгоритм построения таблицы истинности, и, значит, ИВ разрешимо. Кроме того, из теоремы о дедукции и теоремы о полноте легко следует, что отношение эквивалентности ≡ в АВ и ИВ совпадают.

Пример 6. Доказать, что φ├φ.

По теореме о дедукции это равносильно тому, что ├φ→φ. В свою очередь, по теореме о полноте, достаточно доказать, что ╞φ→φ. Составляя таблицу истинности для формулы φ→φ, убеждаемся, что φ→φ тождественно истинна и, следовательно, доказуема.

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

Исчисление называется непротиворечивым, если оно не является противоречивым

Теорема 5 (о непротиворечивости). ИВ непротиворечиво.

Доказательство. По теореме о полноте любая формула, не являющаяся тождественно истинной, не доказуема в ИВ. Например, такой формулой является формула х∧х. Следовательно, ИВ непротиворечиво.

Множество формул Г называется противоречивым, если Г├x∧x. Если Г ‑ противоречивое множество формул, то будем обозначать этот факт через Г К Множество формул Г называется непротиворечивым, если Г не является противоречивым множеством.

Утверждение 3. Формула φ выводима из множества формул Г тогда и только тогда, когда множество Г∨{φ}‑ противоречиво:

Г├φ Г,φ├.

Доказательство. Поскольку отношение эквивалентности ≡ в АВ и ИВ совпадают, то φ≡φ→x∧x в ИВ. Пусть Г={φ₀,…, φ_n}. Тогда, пользуясь утверждением 2, следствием 1 и теоремой о замене, получаем

Г├φ φ₀∧…∧φ_n├φ ├φ₀∧…∧φ_n→φ ├φ₀∧…∧φ_n→(φ→x∧x)

φ₀∧…∧φ_n,φ├x∧x Г∨{φ}├x∧x,

что и доказывает утверждение.

Схема аксиом называется независимой в исчислении, если хотя бы один ее частный случай не доказуем в исчислении без этой схемы. Доказательство следующей теоремы не приводится в виду его громоздкости.

Теорема 6. Схемы аксиом ИВ независимы.