Теорема за дедукция в пропозиционалното смятане

Теорема 1(относно дедукцията). Некаφ1,…,φm,φ,ψса IW формули. Тогаваφ1,…,φm,φ⊢ψ

пропозиционалното
φ1,…,φm,⊢φ→ψ.

Решение.Чрез теоремата за дедукция

φ→ψ⊢¬ψ→¬φ

дедукция
φ→ψ, ¬ψ⊢¬φ.

φ→¬ψ(правилото за извод е приложено към параграфи 2 и 5);

¬φ(правилото за извод беше приложено към параграфи 6 и 4).

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

φ→(ψ→χ)⊢ψ→(φ→χ)

теорема
φ→(ψ→χ),ψ⊢(φ→χ)
теорема
φ→(ψ→χ),ψ,φ⊢χ.

4)ψ→χ(правилото за извод е приложено към точки 2 и 1);

5)χ(правилото за извод е приложено към параграфи 3 и 4).

Теоремата за заместване в пропозиционалното смятане

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

Бележка 2.За всякакви формулиφиψIV

φ≡ψ

пропозиционалното
⊢φ→ψи ⊢ψ→φ.

Твърдение 1.Отношението≡е отношение на еквивалентност върху набора от IV формули, т.е. за всякакви формулиφ,ψ, χIV:

б)φ≡ψ

дедукция
ψ≡φ;

в)φ≡ψ,ψ≡x

пропозиционалното
φ≡x.

Теорема 2(относно заместването). Некаφе IV формула,ψнейната подформула,φ'се получава отφчрез заместване на някакво появяване наψс формулатаψ'IV иψ≡ψ'.Тогаваφ≡φ'.

Свойства на производни и еквивалентни формули на пропозиционалното смятане

Твърждение 3.Некаφ,ψ, χ саIW формули. Тогава

φ,ψ⊢φ

пропозиционалното
ψ;

Доказателство.Точки 1, 4, 6, 8 са доказани в примери 13, 14, 16, 17.

Нека докажем т. 7. Нека покажем, чеφ→(ψ→χ)⊢φ

пропозиционалното
ψ→χ.По теоремата за дедукция

φ→(ψ→χ)⊢φ

теорема
ψ→χ
пропозиционалното
φ→(ψ→χ),φ
теорема
ψ⊢χ.

Изграждаме извеждането на формулатаχот формулитеφ→(ψ→χ),φ

дедукция
ψ:

φ

пропозиционалното
ψ(хипотеза);

φ

теорема
ψ→φ(схема на аксиома 3);

φ(правилото за извод е приложено към точки 2 и 4);

φ

дедукция
ψ→ψ(Схема на аксиома 4);

ψ(правилото за извод е приложено към параграфи 2 и 5);

ψ→χ(правилото за извод е приложено към точки 4 и 1);

χ(правилото за извод е приложено към точки 6 и 7).

Нека покажем, чеφ

дедукция
ψ→χ⊢φ→(ψ→χ).Чрез теоремата за дедукция

φ

пропозиционалното
ψ→χ⊢φ→(ψ→χ)
пропозиционалното
φ
теорема
ψ→χ,φ⊢φ→χ
пропозиционалното
φ
теорема
ψ→χ,φ,ψ⊢χ.

Конструираме квазиизвод на формулатаχот формулитеφ

пропозиционалното
ψ→χ,φ,ψ:

φ

пропозиционалното
ψ→χ(хипотеза);

φ

дедукция
ψ(свойство 4 е приложено към позиции 2 и 3);

χ(правилото за извод беше приложено към параграфи 4 и 1).

Основни еквивалентности на пропозиционалното смятане

Теорема 3.Некаφ,ψ, χса IW формули. Тогава са валидни следните еквивалентности: