3. Теорема о дедукции в исчислении высказываний

Теорема 1 (о дедукции). Пусть φ₁,…,φ_m,φ,ψ – формулы ИВ. Тогда φ₁,…,φ_m,φ⊢ψ φ₁,…,φ_m,⊢φ→ψ.

Пример 4. Покажем, что φ→ψ⊢¬ψ→¬φ;

Решение. По теореме о дедукции

φ→ψ⊢¬ψ→¬φ φ→ψ, ¬ψ⊢¬φ.

Строим вывод формулы ¬φ из формул φ→ψ,¬ψ:

1) φ→ψ (гипотеза);

2) ¬ψ (гипотеза);

3. (φ→ψ)→((φ→¬ψ)→¬ψ) (схема аксиом 9);

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

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

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

7. ¬φ (к пп. 6 и 4 применили правило вывода).

Пример 5. Покажем, чтоφ→(ψ→χ)⊢ψ→(φ→χ)

Решение.По теореме о дедукции

φ→(ψ→χ)⊢ψ→(φ→χ)φ→(ψ→χ),ψ⊢(φ→χ)φ→(ψ→χ),ψ,φ⊢χ.

Строим вывод формулы χ из формул φ→(ψ→χ),ψ,φ:

1) φ→(ψ→χ) (гипотеза);

2) φ (гипотеза);

3) ψ (гипотеза);

4) ψ→χ (к пп. 2 и 1 применили правило вывода);

5) χ (к пп. 3 и 4 применили правило вывода).

4. Теорема о замене в исчисления высказываний

Формулы φ и ψ назовем эквивалентными (обозначим φ≡ψ), если

φ⊢ψ и ψ⊢φ.

Замечание 2. Для любых формул φ и ψ ИВ

φ≡ψ⊢φ→ψ и ⊢ ψ→φ.

Утверждение 1. Отношение ≡ является отношением эквивалентности на множестве формул ИВ, т.е. для любых формул φ, ψ, χ ИВ:

а) φ≡φ;

b) φ≡ψψ≡φ;

с) φ≡ψ, ψ≡xφ≡x.

Утверждение 2. Для любых формул φ, ψ, φ₁, ψ₁, φ₂, ψ₂ ИВ таких, что φ₁≡ψ₁ и φ₂≡ψ₂, имеют место эквивалентности:

φ₁∧φ₂≡ψ₁∧ψ₂, φ₁∨φ₂≡ψ₁∨ψ₂, φ₁→φ₂≡ψ₁→ψ₂, ¬φ₁≡¬ψ₁.

Теорема 2 (о замене). Пусть φ ‑ формула ИВ, ψ ‑ ее подформула, φ' получается из φ заменой некоторого вхождения ψ на формулу ψ' ИВ и ψ≡ψ'. Тогда φ≡φ'.

5. Свойства выводимых и эквивалентных формул исчисления высказываний

Утверждение 3. Пусть φ,ψ, χ – формулы ИВ. Тогда

1. ⊢φ→φ;

2. φ∧ψ⊢φ;

3. φ∧ψ⊢ψ;

4. φ,ψ⊢φψ;

5. φ→ψ, ψ→χ⊢φ→χ (свойство транзитивности);

6. φ→(ψ→χ)≡ψ→(φ→χ) (свойство перестановочности посылок);

7. φ→(ψ→χ)≡φ∧ψ→χ (свойство соединения и разъединения посылок);

8. φ→ψ≡¬ψ→¬φ (свойство контрапозиции).

Доказательство.Пункты 1, 4, 6, 8 доказаны в примерах 13, 14, 16, 17.

Докажем пункт 7. Покажем, что φ→(ψ→χ)⊢φψ→χ. По теореме о дедукции

φ→(ψ→χ)⊢φψ→χφ→(ψ→χ), φψ⊢χ.

Строим вывод формулы χ из формул φ→(ψ→χ), φψ:

1. φ→(ψ→χ) (гипотеза);

2. φψ (гипотеза);

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

4. φ (к пп. 2 и 4 применили правило вывода);

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

6. ψ (к пп. 2 и 5 применили правило вывода);

7. ψ→χ (к пп. 4 и 1 применили правило вывода);

8. χ (к пп. 6 и 7 применили правило вывода).

Покажем, что φψ→χ⊢φ→(ψ→χ). По теореме о дедукции

φψ→χ⊢φ→(ψ→χ)φψ→χ, φ⊢φ→χφψ→χ, φ, ψ⊢χ.

Строим квазивывод формулы χ из формул φψ→χ, φ, ψ:

1. φψ→χ (гипотеза);

2. φ (гипотеза);

3. ψ (гипотеза);

4. φψ (к п.п. 2 и 3 применили свойство 4);

5. χ (к пп. 4 и 1 применили правило вывода).

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

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