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

Теорема 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. Для любой формулыφ ИВ существует ДНФ (КНФ)ψИВ такая, чтоφ≡ψ.