Высказываний

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

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

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

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

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

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

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

7) φ→ψ≡¬φ∨ψ;

8) ⊢φ∨¬φ.

Доказательство. В примере 3 показано, что φ⊢¬¬φ. Покажем, что ¬¬φ⊢ φ. По теореме о дедукции

¬¬φ⊢ φ ⊢¬¬φ→ φ,

что выполняется, т.к. ¬¬φ→ φ – частный случай схемы аксиом 10.

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

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

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

3) ¬(¬φ∨¬ψ)→¬¬φ (к п. 2 применили свойство контрапозиции);

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

5) ¬(¬φ∨¬ψ)→φ (к пп. 3 и 4 применили свойство транзитивности);

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

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

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

9) ¬(φ∧ψ)→¬¬(¬φ∨¬ψ) (к п. 7 применили свойство контрапозиции);

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

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

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

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

3) ¬φ→¬(φ∧ψ) (к п. 2 применили свойство транзитивности);

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

5) ¬ψ→¬(φ∧ψ) (к п. 4 применили свойство транзитивности);

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

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

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

Формула ИВ, получаемая из ДНФ (КНФ) АВ заменой логических переменных на переменные ИВ, называется ДНФ (КНФ) ИВ.

Теорема 2. Для любой формулы φ ИВ существует ДНФ (КНФ) ψ ИВ такая, что φ≡ψ.