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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задачи