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

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

За да докажем чрез допускане на противното, че дадена формула е тавтология, допускаме, че тя има стойност Н, след което въз основа на това допускане започваме да правим изводи за истинностните стойности на нейните подформули. Целта е да стигнем да противоречие. Противоречие ще има, ако за някаква подформула се окаже, че има едновременно стойност И и стойност Н. От противоречието следва, че допускането ни е невъзможно, т.е. за началната формула е невъзможно да приеме стойност Н, което значи, че приема само стойност И. С други думи формулата е тавтология.

Като пример ще покажем, че изразът „[(pq)∧¬q]→¬p“ е тавтология. Допускаме, че има стойност Н:

1. [(pq)∧¬q] → ¬p Н допускане

Една импликация е неистинна в един единствен случай – когато антецедентът й (в нашия случай „(pq)∧¬q“) е И, а консеквентът й („¬p“) е Н. Следователно от 1. можем да заключим следните две неща:

2. (pq)∧¬q И от 1.
3. ¬p Н от 1.

От дясната страна на всеки ред от доказателството посочваме номера на реда (или редовете, ако са повече от един), от който следва това което се твърди. Продължаваме по-нататък. Тъй като в 2. имаме истинна конюнкция, а една конюнкция е истинна, ако и само ако и двата ѝ конюнкта са истинни, значи „pq“ и „¬q“ трябва да са истинни:

4. pq И от 2.
5. ¬q И от 2.

Тъй като в 3. сме получили, че „¬р“ има стойност Н, значи „р“ има стойност И:

6. p И от 3.

По същата причина от 5. следва, че „q“ трябва да има стойност Н:

7. q Н от 5.

Тъй като в 6. сме получили, че „p“ трябва да има стойност И, а в 7. – че „q“ трябва да има стойност Н, от таблицата за истинност на импликацията следва, че импликацията между тях „pq“ трябва да има стойност Н:

8. pq Н от 6. и 7.

8. обаче противоречи на 4., според което „pq“ има стойност И. С това доказателството чрез допускане на противното е завършено. Заради противоречието допускането ни е невъзможно. „[(pq)∧¬q]→¬p“ не може да има стойност Н и значи е тавтология.

Доказателството с този метод, че дадена формула е противоречие, се различава от доказателството, че е тавтология, само в началното допускане, което вече не е, че формулата има стойност Н, а стойност И. Ако в резултат на това допускане стигнем до противоречие, ще следва, че за формулата е невъзможно да приеме стойност И, което значи, че е противоречие. Като пример ще докажем, че „¬[(р∧¬q)∨¬(¬qr)]∧(p∧¬r)“ е противоречие:

1. ¬[(р∧¬q)∨¬(¬qr)] ∧ (p∧¬r) И допускане
2. ¬[(р∧¬q)∨¬(¬qr)] И от 1.
3. p∧¬r И от 1.
4. p И от 3.
5. ¬r И от 3.
6. r Н от 5.
7. (р∧¬q)∨¬(¬qr) Н от 2.
8. р∧¬q Н от 7.
9. ¬(¬qr) Н от 7.
10. ¬qr И от 9.
11. ¬q Н от 4. и 8.
12. r И от 10. и 11. – противоречие с 6.

В 11. заключаваме, че „¬q“ е Н, защото в 8. имаме, че конюнкцията „р∧¬q“ е неистинна, а за да е неистинна една конюнкция, поне единият от конюнктите ѝ трябва да е неистинен, за „р“ обаче знаем, че е истинен от 4., и значи остава „¬q“ да е неистинен. В 12. заключаваме, че „r“ е И, защото в 10. имаме, че дизюнкцията „¬qr“ е И, а за да е истинна една дизюнкция, поне единият от дизюнктите ѝ трябва да е истинен, „¬q“ обаче е неистинен от 11. и значи остава „r“ да е истинен. Останалите изводи в доказателството са или изводи от истинна конюнкция, че и двата конюнкта са истинни (2., 3., 4. и 5.), или от неистинна дизюнкция, че и двата дизюнкта са неистинни (8. и 9.), или от истинностната стойност на някакво отрицание, че изразът без отрицание има обратната истинностна стойност (6., 7. и 10.).

По принцип определени изводи от истинностната стойност на една формула за истинностните стойности на подформулите ѝ можем да правим, когато формулата е или отрицание, или истинна конюнкция, или неистинна дизюнкция, или неистинна импликация, защото тогава има само една възможност за истинностните стойности на главните ѝ подформули. Напротив, например от една истинна импликация „α→β“ не може да направим определен извод за истинностните стойности на α или β, защото има три възможности: или и двете да са И, или и двете да са Н, или α да е Н, а β да е И; и значи и α, и β могат да бъдат както истинни, така и неистинни. Когато не може да се направи определен извод, трябва да се разглеждат различни случаи. Например от това, че „pq“ има стойност Н, можем да заключим, че или „p“, или „q“ имат стойност Н, но понеже не знаем кое от двете (или и двете), трябва да разгледаме два (не изключващи се) случая: когато „р“ е Н и когато „q“ е Н. Тогава, за да докажем, че началната формула е тавтология (противоречие), трябва да стигнем до противоречие и в двата случая. Тъй като разглеждането на различни случаи усложнява доказателството, ясно е, че трябва да се стремим да минем без него. Това обаче не винаги е възможно. Например, ако искаме да докажем, че даден израз с формата на еквивалентност е тавтология или противоречие, ще сме принудени да разгледаме два случая, защото както когато „α↔β“ е И, така и когато е Н, α и β могат да бъдат както И, така и Н (това се вижда от таблицата за истинност на еквивалентността).

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

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

Задачи

(Изтеглете задачите като pdf.)

(1) Докажете с допускане на противното, че следните формули са тавтологии:

1) ¬(pq) → ¬p

2) (pq) → [(rp)→(rq)]

3) [p∨(q∧¬r)] → [(pq)∧(rp)]

4) [(pq)∧(rs)] → [(pr)→(qs)]

5) ¬p → ¬(pq)

6) ¬p → [(pq)∨q]

7) [p∧(qr)] → [(pq)∨(pr)]

8) [(pq)∨r] → ¬[(p∧¬q)∧¬r]

(2) Докажете с допускане на противното, че следните формули са противоречия:

1)q→¬p) ∧ ¬(q∨¬p)

2) [(pq)∧(pr)] ∧ ¬[p→(qr)]

3) ¬[¬(pq)∨(¬qp)]

4) [(p∨¬q)∧r] ∧ ¬[¬(pr)→(¬qr)]