1.8 Естествена дедукция

Схеми за извод

Естествената дедукция е метод за доказване на логическата валидност на произволни аргументи, който, за разлика от истинностно-функционалния анализ и таблиците за истинност, наподобява начина, по който разсъждаваме. При него с помощта на предварително фиксирани, прости схеми за извод и схеми еквивалентности се конструира доказателство за това, че от някакви предпоставки следва някакъв извод. Следните три схеми за извод са сред тези, които ще използваме:

α → β
α модус поненс
β
α → β
¬β модус толенс
¬α
α ∨ β
¬α дизюнктивен силогизъм
β

Логическата валидност на тези схеми за извод може да бъде проверена с таблици за истинност или с истинностно-функционален анализ, но това едва ли е нужно, тъй като валидността им е достатъчно очевидна за интуицията. Отстрани на всяка от схемите е написано името, с което ще я обозначаваме. За видим как функционира методът на естествената дедукция, нека приемем, че „A“, „B“, „C“, „D“ и „Е“ са някакви конкретни изречения, които участват в петте предпоставки на следния извод:

1. АВ
2. B∨(AC)
3. BD
4. ¬D
5. CE/ E

Заключението на извода е твърдението E. (Знакът „/“ изпълнява функцията на чертата, която отделя предпоставките от заключението.) Искаме да докажем, че заключението следва от предпоставките. За целта, ще използваме горните три схеми за извод. От 3. и 4. по модус толенс можем да изведем „¬В“:

6. ¬В от 3. и 4. по модус толенс

Номерираме всеки от редовете, за да можем да се отнасяме към съответните твърдения, ако по-нататък правим изводи, в които те са предпоставки. Отдясно на всяко изведено твърдение пишем името на схемата за извод и номерата на предпоставките, въз основа на които е изведено. Продължавайки по-нататък от твърденията в 2. и 6. по схемата за извод дизюнктивен силогизъм можем да изведем „АС“ (на α в схемата за извод отговаря „В“, а на β – „АС“):

7. АС от 2. и 6. по дизюнктивен силогизъм

От 1. и 6. по модус толенс можем да изведем „¬А“:

8. ¬А от 1. и 6. по модус толенс

От последните две твърдения получаваме:

9. C от 7. и 8. по дизюнктивен силогизъм

И накрая от 5. и 9. по модус поненс получаваме търсения извод „Е“:

10. E от 5. и 9. модус поненс

По принцип за доказателствата с естествената дедукция ще използваме следните схеми за извод1:

α → β модус поненс α → β модус толенс
α ¬β
β ¬α


α ∨ β дизюнктивен силогизъм α → β хипотетичен силогизъм
¬α β → γ
β α → γ


α ∧ β симплификация α добавяне
α α ∨ β


α конюнкция (α→β) ∧ (γ→δ) конструктивна дилема
β α ∨ γ
α ∧ β β ∨ δ


α → β aбсорбиране
α → (α∧β)

Като следващ пример нека разгледаме сега следното доказателство с естествена дедукция:

1. FG
2. ¬(FG)∧L
3. (GH)→(IJ)
4. F∨(KG)
5. ¬KL / IH
6. ¬(FG) от 2. по симплификация
7. F→(FG) от 1. по абсорбиране
8. ¬F от 6. и 7. по модус толенс
9. KG от 4. и 8. по дизюнктивен силогизъм
10. ¬К от 5. по симплификация
11. G от 9. и 10. по дизюнктивен силогизъм
12. GH от 11. по добавяне
13. IJ от 3. и 12. по модус поненс
14. I от 13. по симплификация
15. IH от 14. по добавяне

Имаме пет предпоставки, от които искаме да покажем, че следва „IH“. Винаги пишем твърдението, което трябва да докажем, веднага след последната предпоставка, отделено от нея с наклонена черта, както е в 5. Твърдението в 6. е получено от това в 2. по симплификация, като на мястото на α в схемата на симплификацията стои „¬(FG)“, а на мястото на β – „L“. Изразът в 8. е получен от 6. и 7. по модус толенс, като на мястото на α в схемата за извод е „F“, а на мястото на β – „FG“. 9. е получено от 4. и 8. по дизюнктивен силогизъм (α е „F“, а β е „KG“). 10. е получено от 5. по симплификация (α е „¬K“, а β е „L“). 13. е получено от 3. и 12. по модус поненс (α е „GH“, а β е „IJ“).

Нека сега докажем валидността на един извод, формулиран с думи:

Ако Иван е тръгнал сутринта, той вече трябва да е пристигнал.
Ако Иван е пристигнал, Петър знае за това.
Иван е тръгнал сутринта или на обяд.
Ако Петър знаеше, че Иван е пристигнал, той щеше да се обади.
Петър не се е обадил.
Иван е тръгнал на обяд.

Представяме простите твърдения в извода например по следния начин:

A – Иван е тръгнал сутринта.
B – Иван е пристигнал.
C – Петър знае, че Иван е пристигнал.
D – Иван е тръгнал на обяд.
E – Петър се е обадил.

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

AB
BC
AD
CE
¬E
D

Ето едно доказателство с естествена дедукция, че изводът е валиден:

1. AB
2. BC
3. AD
4. CE
5. ¬E / D
6. AC от 1. и 2. по хипотетичен силогизъм
7. AE от 6. и 4. по хипотетичен силогизъм
8. ¬А от 5. и 7. по модус толенс
9. D от 3. и 8. по дизюнктивен силогизъм

Обикновено съществуват различни доказателства. Например валидността на горния извод може да бъде доказана и така:

1. AB
2. BC
3. AD
4. CE
5. ¬E / D
6. ¬C от 4. и 5. по модус толенс
7. ¬B от 2. и 6. по модус толенс
8. ¬А от 1. и 7. модус толенс
9. D от 3. и 8. по дизюнктивен силогизъм

Естествената дедукция се различава от таблиците за истинност и истинностно-функционалния анализ по това, че е доказателствена, а не разрешителна процедура. Разрешителните процедури са общи рецепти (алгоритми), чрез който винаги стигаме до интересуващия ни отговор. Използвайки таблица за истинност или истинностно-функционален анализ имаме гаранция, че ще получим отговор на въпроса, дали (по отношение на пропозиционалната логика) от някакви твърдения (или формули) следва друго твърдение (формула), както и дали две твърдения (формули) са логически еквивалентни. Напротив, доказателствените процедури не са рецепти, чието прилагане гарантира стигането до желания резултат. Въпреки че, ако даден извод е логически валиден, съществува доказателство или доказателства с естествената дедукция за това, може и да не успеем да намерим нито едно то тях. Заради тази разлика по принцип разрешителните процедури са за предпочитане пред доказателствените, но първите не винаги са възможни. Например, за разлика от пропозиционалната логика, в предикатната логика (с която предстои да се занимаваме) не е възможно формулирането на универсална разрешителна процедура за логическо следване и логическа еквивалентност, каквито са таблиците за истинност и истинностно-функционалният анализ в пропозиционалната логика. В предикатната логика обаче може да бъде формулирана универсална доказателствена процедура за логическо следване и логическа еквивалентност (т.е. такава, че ако един извод е валиден, в нея съществува доказателство за това, но няма гаранция, че ще го намерим). По-нататък, занимавайки се с предикатна логика, ще формулираме такава процедура, и естествената дедукция, с която се занимаваме в момента, ще бъде част от нея.

Схеми еквивалентности

Освен изводи, които се основават на схеми за извод като въведените по-горе, при метода на естествената дедукция се използват и изводи, които се основават на логически еквивалентности. Ще наричаме логическата еквивалентност между два израза с определена форма схема еквивалентност. Името на следната схема еквивалентност е „транспозиция“:

α→β ¬β→¬α

Това, че произволни изрази с формата „α→β“ и „¬β→¬α“ са логически еквивалентни, може да се провери с истинностно-функционален анализ или с таблица за истинност. За разлика от схемите за извод схемите еквивалентности в естествената дедукция могат да бъдат използвани не по един, а по два начина. Първият се основава на това, че логическата еквивалентност между два израза означава, че те логически следват един от друг. Следователно например горната схема еквивалентност съдържа в себе си следните две схеми за извод:

α → β ¬β → ¬α
¬β → ¬α α → β

Можем да правим изводи както по едната, така и по другата. Да кажем, ако при някакво доказателство с метода на естествената дедукция сме стигнали до израза

А→(В∧¬С)

от него можем да изведем

¬(В∧¬С)→¬А

(първият израз има формата „α→β“, а вторият „¬β→¬α“). Но също и обратно – ако сме стигнали до втория израз, можем да изведем първия. Това е единият от начините, по който могат да се използват схемите еквивалентности.

Другият начин се основава на принципа за заменимост на еквивалентните, за който стана дума в края на 1.6. Принципът ни дава право да заместваме даден израз с логически еквивалентен на него израз, когато първият е част от друг израз. Например въз основа на принципа за заменимост на еквивалентните, използвайки транспозиция, можем да заместим всеки израз от вида „α→β“ с „¬β→¬α“ и обратно, когато тези изрази са части от други изрази. Например, ако в някакво доказателство сме стигнали до израза

¬[А→(В∧¬С)]∧D

от него можем да изведем израза

¬[¬(В∧¬С)→¬А]∧D

Вторият израз е получен от първия, като частта му „А→(В∧¬С)“, имаща формата „α→β“, е заменена с логически еквивалентния израз „¬(В∧¬С)→¬А“, който има формата „¬β→¬α“.

Като илюстрация за двата начина на използването на схеми еквивалентности нека видим как посредством транспозиция и схемата еквивалентност

α ¬¬α

която ще наричаме „двойно отрицание“, от „АВ“ и „С→¬В“ можем да изведем „A→¬C“ (доказателството използва също и една схема за извод):

1. AB
2. C→¬B / A→¬C
3. ¬¬B→¬C от 2. по транспозиция
4. В→¬С от 3. по двойно отрицание
5. А→¬С от 1. и 4. по хипотетичен силогизъм

Извеждането на 3. е пример за първия начин, по който може да се използва една схема еквивалентност – изрази се извеждат от логически еквивалентни на тях въз основа на това, че логическата еквивалентност е следване в двете посоки. При извеждането на 4. е използван принципът за заменимост на еквивалентните, тъй като твърдението е получено от твърдението в 3. чрез замяна на негова част („¬¬B“) с логически еквивалентен израз („B“).

Ето и пълният списък от схеми еквивалентности, които ще използваме при метода на естествената дедукция. За всяка от тях чрез истинностно-функционален анализ или таблица за истинност може да се види, че от двете страни на „⇔“ стоят наистина логически еквивалентни изрази.

транспозиция: α→β ¬β→¬α

двойно отрицание: ¬¬α α

експортиране: α→(β→γ) (α∧β)→γ

материална импликация: α→β ¬α∨β
¬(α→β) α∧¬β

закони на Де Морган: ¬(α∧β) ¬α∨¬β
¬(α∨β) ¬α∧¬β

комутация (комутативен закон): α∧β β∧α
α∨β β∨α

асоциация (асоциативен закон): α∧(β∧γ) (α∧β)∧γ
α∨(β∨γ) (α∨β)∨γ

дистрибуция (дистрибутивен закон): α∧(β∨γ) (α∧β)∨(α∧γ)
α∨(β∧γ) (α∨β)∧(α∨γ)

материална еквивалентност: α↔β (α→β)∧(β→α)
α↔β (α∧β)∨(¬α∧¬β)

тавтология: α∧α α
α∨α α

Като следващ пример нека покажем, че следният аргумент за това, че Бог не съществува, е логически валиден. (От валидността на аргумента не следва непременно, че заключението му е истинно, тъй като може някоя от предпоставките да е неистинна. Кои от предпоставките би оспорил някой, който вярва, че Бог съществува?)

Ако Бог съществува, той е добър и всемогъщ.
Ако Бог е неспособен да премахне страданието в света, тогава той не е всемогъщ.
Ако Бог не иска да премахне страданието, тогава той не е добър.
Ако Бог искаше да премахне страданието в света и беше способен да го стори, тогава нямаше да има страдание.
Но в света има страдание.
Бог не съществува.

Представяме символно простите твърдения например по следния начин:

S – Бог съществува.
D – Бог е добър.
V – Бог е всемогъщ.
M – Бог е способен да премахне страданието в света.
I – Бог иска да премахне страданието в света.
N – В света има страдание.

Използвали сме общо взето такива букви, които да ни напомнят кои са твърденията, на мястото на които стоят. По принцип това е причината при естествената дедукция да използваме за символно представяне големи латински букви вместо обичайните букви за твърдения („p“, „q“, …). Аргументът приема следния символен вид:

S → (DV)
¬M → ¬V
¬I → ¬D
(IM) → ¬N
N
¬S

Логическата му валидност се вижда например от следното доказателство:

1. S→(DV)
2. ¬M→¬V
3. ¬I→¬D
4. (IM)→¬N
5. N / ¬S
6. ¬¬N от 5. по двойно отрицание
7. ¬(IM) от 4. и 6. по модус толенс
8. ¬I∨¬M от 7. по Де Морган
9. I→¬D)∧(¬M→¬V) от 3. и 2. по конюнкция
10. ¬D∨¬V от 8. и 9. по конструктивна дилема
11. ¬(DV) от 10. по Де Морган
12. ¬S от 1. и 11. по модус толенс

Доказателство чрез свеждане до противоречие и условно доказателство

Доказателството чрез свеждане до противоречие, наричано още „индиректно доказателство“ или „reductio ad absurum“ („свеждане до абсурд“ на латински), е прийом в рамките на естествената дедукция, при който, за да докажем, че дадено твърдение логически следва от предпоставките, допускаме неговото отрицание. Ако тогава успеем да стигнем да противоречие, т.е. до някакво твърдение и до неговото отрицание, това би показало, че допускането не може да е истинно при дадените предпоставки и че следователно обратното на допускането по необходимост е истинно при дадените предпоставки, с други думи – следва от тях.

Логическата правомерност на доказателството чрез свеждане до противоречие се основава на закона за непротиворечието и на закона за изключеното трето. Това се вижда от следното разсъждение. Фактът, че с поредица от логически валидни изводи от допускането на „¬α“ се стига до някакво противоречие („β∧¬β“), показва, че ако „¬α“ е истинно, то и „β∧¬β“ също трябва да е истинно. Но Законът за непротиворечието изключва последното, поради което „¬α“ не може да е истинно (при дадените предпоставки). Обаче съгласно закона за изключеното трето поне едното двете – α или „¬α“ – трябва да е истинно и щом това не е „¬α“, остава да е α.

Да разгледаме следния пример, при който е използвано доказателство чрез свеждане до противоречие:

1. (AB)→¬D
2. D∨(C∧¬E)
3. CE / A
4. ¬A допускане
5. ¬AB от 4. по добавяне
6. AB от 5. по мат. импликация
7. ¬D от 1. и 6. по модус поненс
8. C∧¬E от 2. и 7. по дизюнктивен силогизъм
9. C от 8. по симплификация
10. ¬EC от 8. по комутация
11. ¬E от 10. по симплификация
12. E от 3. и 9. по модус поненс – противоречие с 11.
13. A от 4. – 12. по свеждане до противоречие

В 4. сме допуснали истинността на „¬А“. Това е само допускане – не знаем дали твърдението е истинно, или не; нещо повече, идеята ни е да докажем, че не е истинно. Поради това въпросното твърдение, както и всички зависими от него твърдения (тези, изведени с негова помощ), са изместени надясно. Когато пишем едно твърдение надясно, под допускането, с това указваме, че то е зависимо от него и може да не е истинно. Твърденията под допускането се използват единствено и само за целите на доказателството чрез свеждане до противоречие. 5. е зависимо от допускането, тъй като е изведено от него. 6. следва от 5. и по този начин зависимостта от допускането се предава и на него. Същото важи за 7., което следва от 6. и 1. и т.н. Така, чрез поредица от зависими от допускането изводи, в 12. сме стигнали до противоречие. Доказателството чрез свеждане до противоречие ни дава основание да сме сигурни в истинността на обратното на допуснатото твърдение „¬А“, а именно А, поради което сме го утвърдили в 13. Това твърдение вече не е написано надясно, под допускането, защото истинността му е сигурна (при истинност на предпоставките). Основанието за утвърждаването на 13. е цялата поредица изнесени надясно твърдения, започваща от допускането и свършваща с противоречието. Поради това като основание за извеждането на 13. сме написали „от 4. – 12. по свеждане до противоречие“.

В горния пример твърдението, което изведохме посредством доказателство чрез свеждане до противоречие, беше крайното твърдение, до което искаме да стигне. Бихме могли обаче да използваме доказателство чрез свеждане до противоречие, за да изведем твърдение, което не е крайното заключение, но което може да бъде използвано, за да се стигне до него. В този случай е важно, след като сме завършили дадено доказателство, в което е използвано допускане, да не използваме повече твърденията, записани под допускането, тъй като те обслужват само процедурата на индиректното доказателство и може да не са истинни. Ето един пример, при който в рамките на едно доказателство два пъти е използвано доказателство чрез свеждане до противоречие:

1. A→(C∨¬B)
2. (BC)→(AD)
3. B / AC
4. ¬(AC) допускане
5. A∧¬C от 4. по мат. импликация
6. A от 5. по симплификация
7. C∨¬B от 1. и 6. по модус поненс
8. ¬C от 5. по симплификациякомутация)
9. ¬B от 7. и 8. по дизюнктивен силогизъм – противоречие с 3.
10. AC от 4. – 9. по свеждане до противоречие
11. ¬(CA) допускане
12. C∧¬A от 11. по мат. импликация
13. C от 12. по симплификация
14. BC от 3. и 13. по конюнкция
15. AD от 2. и 14. по модус поненс
16. A от 15. по симплификация
17. ¬A от 12. по симплификациякомутация) – противоречие с 16.
18. CA от 11. – 17. по свеждане до противоречие
19. (AC)∧(CA) от 10. и 18. по конюнкция
20. AC от 19. по мат. еквивалентност

Тъй като целта е да се докаже твърдението „AC“, идеята е първо да се докажат двете импликации „AC“ и „CA“, от които след това по схемата еквивалентност „α↔β“ ⇔ „(α→β)∧(β→α)“ да се получи търсеният извод. Импликациите се извеждат чрез две индиректни доказателства. В 4. сме допуснали отрицанието на „AC“ и чрез поредица от изводи в 9. сме стигнали до противоречие, което ни е дава основани в 10. да изведем „АC“ (обратното на допускането твърдение). Това твърдение вече не е зависимо от допускането и съответно стои наляво от него. Когато един път сме приключили с едно доказателство чрез свеждане до противоречие, повече нямаме право да се отнасяме до твърденията, използвани в него (тези под допускането). От тук нататък в доказателството може да използваме като предпоставки за изводи твърдението в 10. („АC“) и твърденията преди 4., но не и тези от 4. до 9. По-нататък в 11. сме допуснали отрицанието на „CA“ и с поредица от изводи сме стигнали до противоречие, след което сме извели като сигурен извод „CA“, който поради това е записан отляво. От тук нататък нямаме право да използваме твърденията от 11. до 17. Изобщо правилото при използване на допускания е следното: докато сме в рамките на едно доказателство чрез допускане (доказателство чрез свеждане до противоречие в дадения случай), имаме право да се отнасяме както към зависимите от допускането твърдения (тези отдясно), така и към тези, които не са зависими от допускането (тези отляво). Приключим ли обаче един път доказателството чрез допускане, повече нямаме право да се отнасяме към зависимите от допускането твърдения. Тъй като вече имаме изведени „АC“ и „CA“, доказателството продължава, като ги свързваме в конюнкция и чрез схемата еквивалентност материална еквивалентност извеждаме търсеното заключение „АС“.

По-горе, за да изведем дадено твърдение α, допускахме неговото отрицание „¬α“ и, стигайки до противоречие, извеждахме α. Ясно е обаче, че бихме могли да направим и обратното – да допуснем α и, стигайки до противоречие, да изведем „¬α“. Това може да се схване като същото, но с едно допълнително прилагане на двойно отрицание: тръгваме от „α“, но поради схемата еквивалентност двойно отрицание все едно сме тръгнали от „¬¬α“. Съответно, ако стигнем до противоречие, можем да изведем „¬α“.

Един друг вид доказателство, в което се използва допускане, е условното доказателство. При него, също както при доказателството чрез свеждане до противоречие, се допуска истинността на някакво твърдение, за да се изведе истинността на друго твърдение. Допуснато твърдение може и да не е истинно, затова го изнасяме надясно и пишем зависимите от него твърдения под него, с което си напомняме, че след като условното доказателство е завършено, тези твърдения вече не могат да се използват. Истинността на твърдението, което извеждаме чрез условното доказателство като цяло, обаче е сигурна (стига началните предпоставки да са истинни).

Условното доказателство се състои в следното. Ако допуснем, че някакво твърдение α е истинно, и в резултат на това успеем да изведем логически някакво твърдение β, с това сме показали, че ако α е истинно, то и β е истинно, с други думи показали сме, че импликацията „Ако α, то β“ (символно „α→β“) е истинна, въпреки че самите твърдения α и β може и да не са истинни.

Да разгледаме следния пример:

1. PQ)→¬S
2. (ST)∨(QP) / ¬P→¬Q
3. ¬P допускане
4. ¬PQ от 3. по добавяне
5. ¬S от 1. и 4. по модус поненс
6. ¬S∨¬T от 5. по добавяне
7. ¬(ST) от 6. по Де Морган
8. QP от 2. и 7. по дизюнктивен силогизъм
9. ¬Q от 8. и 3. по модус толенс
10. ¬P→¬Q от 3. – 9. по условно доказателство

В 3. сме допуснали, че твърдението „¬P“ е истинно. Това е само допускане – не знаем дали е истинно. Затова то заедно със следващите твърдения, които го предпоставят (от 3. до 9. включително), са изнесени надясно. В 10. е заключението на условното доказателство: „¬P→¬Q“. За него сме сигурни, че е истинно, защото може да бъде перифразирано с „Ако ‚¬P‘ е истинно, то и ‚¬Q‘ е истинно“. Веригата от изводи от 3. до 9. е доказателство за истинността на това твърдение, защото тя демонстрира, че „¬Q“ логически следва от „¬P“ (тръгвайки от „¬P“, с поредица от логически валидни изводи сме стигнали до „¬Q“), и значи ако „¬P“ е истинно, то и „¬Q“ е истинно.

Нека обобщим, в рамките на метода на естествената дедукция можем да използваме условно доказателство по следния начин. Винаги можем да допуснем произволно твърдение α. Подчертаваме, че това е само допускане, като го пишем отдясно. Правим някакви изводи, като за предпоставки използваме както твърденията, зависими от допускането (тези отдясно), така и сигурните твърдения (тези отляво). По всяко време можем да решим да завършим условното доказателство. Ако твърдението, до което сме стигнали, е β, като извод на условното доказателство на следващия ред и отляво пишем твърдението „α→β“. Истинността на това твърдение е сигурна (при истинност на предпоставките). Оттук нататък повече нямаме право да използваме зависимите от допускането твърдения (тези отдясно) – те обслужват само условното доказателство и не са част от цялостното доказателство с естествена дедукция.

В едно и също доказателство с естествена дедукция можем да използваме както доказателство чрез свеждане до противоречие, така и условно доказателство. Освен това можем да използваме доказателство чрез допускане в рамките на другo доказателство чрез допускане. Ето един пример за използване на условно доказателство в рамките на условно доказателство (същото нещо можем да правим и при доказателството чрез свеждане до противоречие):

1. (MN)→[(OP)→R] / M→(OR)
2. M допускане
3. MN от 2. по добавяне
4. (OP)→R от 3. и 1. по модус поненс
5. O допускане
6. OP от 5. по добавяне
7. R от 4. и 6. по модус поненс
8. OR от 5. – 7. по условно доказателство
9. M→(OR) от 2. – 8. по условно доказателство

В случаи като този се ръководим отново от правилото, че докато сме в рамките на едно доказателство чрез допускане, можем да използваме като предпоставки за правене на изводи твърдения, които са зависими от допускането, но приключим ли с доказателството чрез допускане, повече нямаме право да ги използваме. В съответствие с това, при допускане в допускането, докато сме в рамките на вътрешното допускане, т.е. когато никое от двете доказателства чрез допускане все още не е завършено (в примера това са редове от 5. до 7.), можем да използваме като предпоставки за изводи всички твърдения преди това. Когато сме приключили с вътрешното доказателство чрез допускане, но все още не сме приключили с външното, повече не можем да използваме твърденията от вътрешното доказателство (твърденията, изместени най-надясно). Когато приключим и с външното доказателство, можем да използваме само твърдения, които не са зависими от допускания (твърденията, разположените най-отляво, на нивото на предпоставките).

Посредством доказателството чрез свеждане до противоречие и условното доказателство може да бъде доказвано, че някакви твърдения са тавтологии. По принцип едно твърдение е тавтология, ако е невъзможно да бъде неистинно. Затова, тъй като истинността на тавтологиите не зависи от истинността на други твърдения, те могат да бъде доказани, без да се изхожда от каквито и да е предпоставки. Това обаче може да стане само чрез използване на доказателство чрез свеждане до противоречие или условно доказателство. Ето един пример, при който посредством доказателство чрез свеждане до противоречие се доказва, че твърдението „[¬C∧(DC)]→D“ е тавтология. За целта се допуска, че е неистинно (т.е., че отрицанието му е истинно), което води до противоречие. Това показва, че твърдението е истинно по необходимост (т.е., че е тавтология).

1. ¬{[¬C∧(DC)]→D} допускане
2. C∧(DC)]∧¬D от 1. по мат. импликация
3. ¬C∧(DC) от 2. по симплификация
4. ¬D от 2. по симплификациякомутация)
5. DC от 3. по симплификациякомутация)
6. C от 5. и 4. по дизюнктивен силогизъм
7. ¬C от 3. по симплификация – противоречие с 6.
8. C∧(DC)]→D от 1. – 7. по свеждане до противоречие

Освен за всяка тавтология, по този начин също и за всяко противоречие може да бъде доказано, че са такава. Тъй като за израз с формата на противоречие не е възможно да е истинен, за да докажем, че е противоречие, допускаме, че е истинен самият той, а не отрицанието му, както правим, когато доказваме, че даден израз е тавтология (горния пример).

Формално погледнато ни е нужен само единият от двата вида доказателства чрез допускане, които въведохме. Причината е, че всичко, което може да бъде доказано с условно доказателство, може да бъде доказано и с доказателство чрез свеждане до противоречие, и обратно. За удобство обаче въведохме и двата вида доказателства. Като цяло доказателството чрез свеждане до противоречие и условното доказателство много улесняват доказателствата. Те често ги правят по-кратки, но по-важното е, че дори и да не ги правят по-кратки, ги правят по-лесни за откриване, тъй като обикновено позволяват прилагането на по-прости и естествени схеми за извод, като симплификация, модус поненс, модус толенс, дизюнктивен силогизъм и т.н., като по този начин се избягва нуждата от използването на изкуствени доказателствени конструкции – с други думи двата прийома правят естествената дедукция естествена в по-голяма степен.

Ще завършим темата за естествената дедукция с пример за едно мета-доказателство (доказателство за доказателствата). Ще покажем, че всичко, което може да бъде доказано с условно доказателство, може да бъде доказано и с доказателство чрез свеждане до противоречие. За целта приемаме, че с условно доказателство е изведено произволно твърдение „α→β“:

α допускане
... изводи, които водят от α до β
β
α→β по условно доказателство

Тогава същото твърдение „α→β“ може да бъде изведено и посредством доказателство чрез свеждане до противоречие по следния начин:

¬(α→β) допускане
α∧¬β по мат. импликация
α по симплификация
... същите изводи, които водят от α до β по-горе
β
¬β по симплификациякомутация) – противоречие
α→β по свеждане до противоречие

Задачи

(Изтеглете задачите като pdf.)
(1) Докажете валидността на следните изводи с естествена дедукция:
1) 1. AC
2. D∨(AB)
3. ¬D / C
2) 1. IJ
2. J∨(IK)
3. JM
4. ¬M
5. K→¬N / ¬N
3) 1. AC
2. C→(AB)
3. ¬B
4. ¬D→[D∨¬(AB)]
5. DB / ¬A∧¬B
4) 1. AB
2. (AB)→(¬¬C∧¬D)
3. ¬E→¬C
4. A
5. ¬¬EF / F∨(¬A↔¬B)
5) 1. FG
2. ¬(FG)∧L
3. (GH)→(IJ)
4. F∨(KG)
5. ¬KL / IH
6) 1. (AB)∧C
2. AD
3. BE
4. EF / DF
7) 1. Q→(VR)
2. T→¬U
3. ¬V
4. TQ
5. ¬UV / R
8) 1. ¬S→(NO)
2. (NU)∧(PT)
3. (OT)∧(PN)
4. ¬U
5. SU / T
9) 1. AB
2. ¬B
3. [(¬A∧¬B)∨C]→(BD) / D∨¬E
10) 1. (QR)→[(SL)→¬T]
2. (SU)→Q
3. S∧¬U
4. TK / K
(2) За всяка от стъпките в следните доказателства с естествена дедукция определете от кои редове и по кое правило са получени:
1) 1. А∨¬B
2. ¬C→¬A / BC
3. ¬BA
4. BA
5. AC
6. BC
2) 1. P→¬P
2. (PQ)∨(RS) / R
3. ¬P∨¬P
4. ¬P
5. ¬P∨¬Q
6. ¬(PQ)
7. RS
8. R
3) 1. A→(BC)
2. C∨¬D)∨F
3. ¬E→(D∧¬F) / A→(BE)
4. (AB)→C
5. ¬(CD)∨F
6. (CD)→F
7. C→(DF)
8. (AB)→(DF)
9. ¬(D∧¬F)→¬¬E
10. ¬(D∧¬F)→E
11. D∨¬¬F)→E
12. DF)→E
13. (DF)→E
14. (AB)→E
15. A→(BE)
4) 1. KL
2. ML
3. N→[K∨(KM)]
4. N / L
5. K∨(KM)
6. (KK)∨M
7. KM
8. (KL)∧(ML)
9. LL
10. L
5) 1. PR
2. (T→¬S)→¬R / PT
3. ¬¬R→¬(T→¬S)
4. R→¬(T→¬S)
5. ¬R∨¬(T→¬S)
6. ¬R∨¬(¬T∨¬S)
7. ¬R∨(¬¬T∧¬¬S)
8. ¬R∨(T∧¬¬S)
9. ¬R∨(TS)
10. RT)∧(¬RS)
11. ¬RT
12. RT
13. PT
6) 1. [O→(PQ)]∧[R→(PS)]
2. [(T→¬O)∧U]→X
3. (UX)→(TR) / QS
4. (T→¬O)→(UX)
5. (T→¬O)→(TR)
6. ¬(T→¬O)∨(TR)
7. ¬(¬T∨¬O)∨(TR)
8. (¬¬T∧¬¬O)∨(TR)
9. (TO)∨(TR)
10. T∧(OR)
11. (OR)∧T
12. OR
13. (PQ)∨(PS)
14. P∧(QS)
15. (QS)∧P
16. QS
7) 1. P↔¬Q
2. (PS)∧(SP)
3. SQ / Q
4. (P→¬Q)∧(¬QP)
5. P→¬Q
6. ¬¬Q→¬P
7. Q→¬P
8. S→¬P
9. PS
10. P→¬P
11. ¬P∨¬P
12. ¬P
13. QP)∧(P→¬Q)
14. ¬QP
15. ¬¬Q
16. Q
8) 1. А→(C∨¬B)
2. (BC)→(AD)
3. B / AC
4. А→(¬BC)
5. А→(BC)
6. (АB)→C
7. (BA)→C
8. B→(AC)
9. AC
10. B→[C→(AD)]
11. C→(AD)
12. ¬C ∨(AD)
13. CA)∧(¬CD)
14. ¬CA
15. CA
16. (AC)∧(CA)
17. AC
(3) Докажете валидността на следните изводи с естествена дедукция:
1) 1. WM
2. ¬WE / ME
2) 1. (RS)∧(PQ)
2. (SQ)→O
3. ¬O / ¬R∨¬P
3) 1. (AB)→(CD)
2. CE
3. ¬E / ¬A
4) 1. KL
2. KM / (¬L∨¬M)→¬K
5) 1. (LM)→N
2. (L∧¬M)→¬N / L→(MN)
6) 1. SL / S→(LW)
7) 1. AB
2. C→¬B / A→¬C
8) 1. E→(FG)
2. (FH )→I / EI
9) 1. (AB)→(CD) / ¬AC
10) 1. M∨(NO)
2. MO / O
(4) Решете отново примерите от предишната задача този път като използвате доказателство чрез свеждане до противоречие или условно доказателство.
(5) Докажете валидността на следните аргументи чрез естествена дедукция, като за символното представяне на простите твърдения в тях използвате дадените в скобите букви. Опитайте се да ги решите по два начина – един път без да използвате условно доказателство или доказателство чрез свеждане до противоречие и втори път като използвате някое от тях.2
1) Ако започна новата работа (N), ще трябва да си купя кола (K), а ако отида на море (M), ще изхарча половината от спестяванията си (S). Но ако си купя кола и изхарча половината от спестявания, ще трябва да живея с 10 лева на ден (L). Аз обаче не мога да живея с толкова. Значи или няма да си купя кола, или няма да отида на море.
2) Ако нашият представител се кандидатира за президент (P), то ако направи позитивна кампания (K), ще стигне до балотаж (B). Ако стигне до балотаж и спечели изборите (S), той няма да бъде преизбран след четири години (C). Ако обаче подкрепи смъртното наказание (N), ще спечели изборите и ще бъде преизбран след четири години. Следователно, ако нашият представител се кандидатира за президент, ако направи позитивна кампания, той няма да подкрепи смъртното наказание.
3) Ако лекарят инжектира антителата (L), пациентът ще получи алергична реакция (A), а ако получи алергична реакция, черният му дроб ще спре да функционира (C). Но ако лекарят не инжектира антителата, вирусът ще се разпространи в кръвоносната му система (V). Черният дроб на пациента ще спре да функционира, ако вирусът се разпространи в кръвоносната му система. Ако черният дроб на пациента спре да функционира, той няма да доживее до сутринта (S). Лекарят ще инжектира или няма да инжектира антителата, така че пациентът със сигурност няма да доживее до сутринта.
4) Ако е Нова година (N), Иван пие червено вино (R). Ако празнува с приятели (P), Иван пие бира (B). Следователно, ако празнува Нова година с приятели, Иван пие червено вино и бира.
5) Ако Иван запише старогръцки (S), той ще запише и латински (L). Ако запише старогръцки, то ако запише латински, той ще запише и логика (O). Ако Иван запише старогръцки, ако запише логика, той ще запише и математика (M). Следователно, ако запише старогръцки, Иван ще запише и математика.
6) Ако има икономическа криза (I) или възникнат международни конфликти (K), то ако правителството бездейства (B) или взима неадекватни мерки (M), няма да има нито икономически растеж (R), нито политическа стабилност (P). Ако няма икономически растеж или данъците се повишат (D), ще има протести (N). Следователно, ако има икономическа криза, то ако правителството бездейства, ще има протести.
7) Ако Петър е срещнал Мария (P), той ѝ е казал новината (Z), в случай че я е знаел (K). Но Петър е срещнал Мария и не ѝ е казал новината. Значи не я е знаел.
8) Ако започна собствен бизнес (S), ще стана богат (B), а ако започна научна кариера (K), ще имам свободно време (V). Или ще започна собствен бизнес, или ще започна научна кариера. Ако обаче започна собствен бизнес, няма да имам свободно време, докато ако започна научна кариера, няма да съм богат. Следователно ще имам свободно време, ако и само ако не съм богат.
9) Ако отида на приема (P), ще трябва да си купя фрак (F). Но ако си купя фрак, няма да мога да си платя наема за месеца (N) и да погася лихвите по заема си (Z). Ако не си платя наема, ще трябва да се крия цял месец от хазяина (K), а аз не мога да направя това. Освен това ще трябва да погася лихвите по заема си. Следователно няма да отида на приема.
10) Ако данъците бяха увеличени (D), щеше да се увеличи безработицата (B), а ако чуждите инвестиции бяха намалели (I), щеше да се намали растежа (R). Но ако се беше увеличила безработицата или инвестициите бяха намалели, потреблението щеше да спадне (P). Потреблението обаче не е спаднало. Следователно нито данъците са увеличени, нито чуждите инвестиции са намалели.
11) Ако Иван е бил до късно с приятели (K), на другия ден той е махмурлия (S). Ако любимият му отбор е паднал (L), на другия ден той е раздразнителен (R). Следователно, ако Иван е бил до късно с приятели или любимият му отбор е паднал, на другия ден той е махмурлия или е раздразнителен.
12) Ако в началото на годината Юпитер е бил под влиянието на Марс (M), през годината ще има война (V) или вътрешни размирици (R). Ако пък тогава Юпитер е бил под влиянието на Сатурн (S), то или годината ще е гладна (G), или ще има война. Война обаче със сигурност няма да има. Следователно, ако годината не е нито гладна, нито има вътрешни размирици, Юпитер не е бил под влиянието нито на Марс, нито на Сатурн.
(6) Използвайте естествена дедукция, за да отговорите на следните въпроси:
1) Вие сте в ролята на детектив. Разполагате със следната информация. Има 4-ма заподозрени – да ги наречем „P“, „Q“, „R“ и „S“. Ако P е невинен, тогава и S е невинен, но вината на R би била несъмнена. Ако S е невинен, тогава Q e сред извършителите на престъплението. Ако S е виновен, тогава е виновен и R. R обаче има сигурно алиби. Кои са виновни и кои – невинни?
2) Както предишното, но този път информацията е следната. P е виновен, ако и само ако Q е невинен. R е невинен, ако и само ако S е виновен. Ако S е сред извършителите, то и P е сред тях, и обратно. Ако S е виновен, тогава и Q е виновен.
3) В един ресторант един клиент казал на сервитьора следното: „Аз ям картофи или ориз, но не и двете заедно. Ако ям картофи, тогава не ям хляб. Ако ям хляб или не ям картофи, тогава не ям ориз.“ Какво трябва да сервира сервитьорът на клиента?

1. Вариантът на естествена дедукция за пропозиционалната логика, който е изложен, почти напълно съвпада с този в (Copi, 1998). 2. Повечето от примерите са от задача (2) от задачите към „1.7 Бърза проверка за логическо следване“ . Там валидността на аргументите трябваше да бъде доказана с бърза проверка. Може да сравните двата метода.