Таблиците за истинност показват по какъв начин истинностната стойност на една формула се определя от истинностните стойности на буквите ѝ за твърдения. В частност те служат също за определяне на това, дали една формула е тавтология, противоречие или синтетична. Истинностно-функционалният анализ е алтернативен метод, който служи за същото, но има някои предимства.1
Ще използваме формулата „[p∧(¬q∨r)]∨(¬p∧q)“, за да видим в какво се състои този метод. Задаваме си въпроса какво следва за истинностната стойност на формулата, ако една от нейните букви за твърдения – да кажем „p“ – получи определена истинностна стойност. Каква следва например, ако „p“ получи стойност И? За да отговорим на този въпрос, заместваме във формулата „p“ с „И“:
| [p∧(¬q∨r)] ∨ (¬p∧q) |
| Случай 1 p: И |
| [И∧(¬q∨r)] ∨ (¬И∧q) |
Конюнкцията между някакво истинно твърдение и произволно друго твърдение винаги има истинностната стойност на другото твърдение, т.е. „И∧α“ има истинностната стойност на α. Това е така, защото ако α има стойност И, „И∧α“ ще има също стойност И (конюнкцията между две истинни твърдения е истинно твърдение), а ако α има стойност Н, „И∧α“ ще има стойност Н – същата като α (защото конюнкцията между едно истинно и едно неистинно твърдение е неистинно твърдение). Това ни дава право по принцип да заместваме израз от вида „И∧α“ със съдържащия се в него израз α. Така че в израза, до който стигнахме, можем да заместим „И∧(¬q∨r)“ с „(¬q∨r)“:
| [p∧(¬q∨r)] ∨ (¬p∧q) |
| Случай 1 p: И |
| [И∧(¬q∨r)] ∨ (¬И∧q) |
| (¬q∨r) ∨ (¬И∧q) |
Дотук получихме, че когато „p“ има стойност И, началната формула има същата истинностна стойност като тази на „(¬q∨r)∨(¬И∧q)“. Продължавайки нататък, в последната формула можем да заместим „¬И“, с „Н“, защото отрицанието на едно истинно твърдение е неистинно твърдение.
| [p∧(¬q∨r)] ∨ (¬p∧q) | |
| Случай 1 p: И | |
| [И∧(¬q∨r)] ∨ (¬И∧q) | |
| (¬q∨r) ∨ (¬И∧q) | |
| (¬q∨r) ∨ (Н∧q) |
От своя страна „Н∧q“ може да бъде заместено с „Н“, защото когато единият от членовете на една конюнкция е неистинен, тя е неистинна, независимо каква е истинностната стойност на другия член (конюнкцията е истинна само когато и двата ѝ конюнкта са истинни). Така че по принцип израз от вида „Н∧α“ може да бъде заместван с „Н“. В резултат на въпросното заместване в конкретния случай получаваме, че когато „p“ има стойност И, началната формула има същата истинностна стойност „(¬q∨r)∨Н“:
| [p∧(¬q∨r)] ∨ (¬p∧q) |
| Случай 1 p: И |
| [И∧(¬q∨r)] ∨ (¬И∧q) |
| (¬q∨r) ∨ (¬И∧q) |
| (¬q∨r) ∨ (Н∧q) |
| (¬q∨r) ∨ Н |
Последният израз е дизюнкция между едно неистинно и някакво друго твърдение. Такъв израз винаги има истинностната стойност на другото твърдение, т.е. „Н∨α“ (редът на членовете в дизюнкцията е без значение) има същата истинностна стойност като тази на α. Това е така, защото когато α има стойност И, „Н∨α“ също има стойност И (за да е истинна една дизюнкция, е достатъчно само единият от членове ѝ да е истинен), а когато α има стойност Н, същата стойност има и „Н∨α“ (дизюнкцията между две неистинни твърдения е неистинна). Така че по принцип израз с формата „Н∨α“ може да бъде заместван с α. В конкретния случай заместваме „(¬q∨r)∨Н“ с „¬q∨r“:
| [p∧(¬q∨r)] ∨ (¬p∧q) |
| Случай 1 p: И |
| [И∧(¬q∨r)] ∨ (¬И∧q) |
| (¬q∨r) ∨ (¬И∧q) |
| (¬q∨r) ∨ (Н∧q) |
| (¬q∨r) ∨ Н |
| ¬q∨r |
Получихме, че когато „p“ има стойност И, истинностната стойност на целия израз е същата като тази на „¬q∨r“. Последната обаче зависи от истинностните стойности на „q“ и на „r“. Затова избираме едната от двете букви за твърдения, да кажем „r“, и разглеждаме последователно случаите, когато „r“ е истинно и когато е неистинно. Първо, за случая когато „r“ е истинно, заместваме „r“ в „¬q∨r“ с „И“:
| [p∧(¬q∨r)] ∨ (¬p∧q) | ||
| Случай 1 p: И | ||
| [И∧(¬q∨r)] ∨ (¬И∧q) | ||
| (¬q∨r) ∨ (¬И∧q) | ||
| (¬q∨r) ∨ (Н∧q) | ||
| (¬q∨r) ∨ Н | ||
| ¬q∨r | ||
| r: И | ||
| ¬q∨И | ||
Когато единият от членовете на произволна дизюнкция е истинен, цялата дизюнкция също е истинна, без значение каква е истинностната стойност на другия ѝ член, т.е. израз с формата „И∨α“ има винаги стойност И. Това ни дава право да заменим „¬q∨И“ с „И“:
| [p∧(¬q∨r)] ∨ (¬p∧q) | ||
| Случай 1 p: И | ||
| [И∧(¬q∨r)] ∨ (¬И∧q) | ||
| (¬q∨r) ∨ (¬И∧q) | ||
| (¬q∨r) ∨ (Н∧q) | ||
| (¬q∨r) ∨ Н | ||
| ¬q∨r | ||
| r: И | ||
| ¬q∨И | ||
| И | ||
Получихме, че когато „p“ и „r“ имат стойност И, целият израз е истинен, независимо от истинностната стойност на „q“.
За другия възможен случай, когато „r“ има стойност Н, заместваме „r“ в „¬q∨r“ с „Н“. И тъй като вече видяхме, че „Н∨α“ има същата истинностна стойност като α, от „¬q∨Н“ получаваме „¬q“ (редът на членовете в дизюнкцията е без значение):
| [p∧(¬q∨r)] ∨ (¬p∧q) | ||
| Случай 1 p: И | ||
| [И∧(¬q∨r)] ∨ (¬И∧q) | ||
| (¬q∨r) ∨ (¬И∧q) | ||
| (¬q∨r) ∨ (Н∧q) | ||
| (¬q∨r) ∨ Н | ||
| ¬q∨r | ||
| r: И | r: Н | |
| ¬q∨И | ¬q∨Н | |
| И | ¬q | |
Значи, когато „p“ има стойност И, а „r“ – Н, целият израз има истинностната стойност на „¬q“, т.е. ако „q“ е И, целият израз е Н, и ако „q“ е Н, целият израз е И:
| [p∧(¬q∨r)] ∨ (¬p∧q) | ||
| Случай 1 p: И | ||
| [И∧(¬q∨r)] ∨ (¬И∧q) | ||
| (¬q∨r) ∨ (¬И∧q) | ||
| (¬q∨r) ∨ (Н∧q) | ||
| (¬q∨r) ∨ Н | ||
| ¬q∨r | ||
| r: И | r: Н | |
| ¬q∨И | ¬q∨Н | |
| И | ¬q | |
|
q: И |
||
|
Н |
||
До тук истинностно-функционалният анализ ни даде половината от информацията, която би се съдържала в таблицата за истинност на началния израз, т.е. какви са истинностните стойности на израза в случаите, когато „p“ има стойност И. Освен това вече е ясно, че изразът е синтетичен, и ако ни интересуваше само въпросът какъв е видът на формулата (дали е тавтология, противоречие или е синтетична), можехме да спрем дотук, без да правим останалата част от анализа. Това показва едно от предимствата на истинностно-функционалния анализ пред таблиците за истинност. Тъй като таблиците се правят колона по колона, а не ред по ред (иначе е по-трудно), за да разберем какъв е видът на израза (нещо, което се вижда едва от последната колона), трябва да направим цялата таблица, докато при истинностно-функционалния анализ можем да получим отговор и без анализът да е извършен докрай. Това което най-често ще ни интересува в бъдеще ще е въпросът, дали определен израз е тавтология. Когато, правейки истинностно-функционален анализ, стигнем до „Н“, можем да спрем с анализа, тъй като това дава отрицателен отговор на този въпрос.
Другата половина на анализа, отнасяща се до случая, когато „p“ има стойност Н, се получава аналогично:
| [p∧(¬q∨r)] ∨ (¬p∧q) | |
| Случай 2 p: Н | |
| [Н∧(¬q∨r)] ∨ (И∧q) | |
| Н ∨ (И∧q) | |
| И∧q | |
| q | |
| q: И | q: Н |
| И | Н |
Изразът на третия ред отдясно е получен чрез заместване на „p“ с „Н“ в началната формула. При заместването на второто участие на „p“ с „Н“, сме написали направо „И“, вместо да пишем „¬Н“ и след това „И“. Следващият ред е получен от предишния чрез заместване на „Н∧(¬q∨r)“ с „Н“. Основанието е, че (както видяхме по-горе) израз от вида „Н∧α“ може да бъде заместен само с „Н“. Петият ред е получен от предишния въз основа на използваното по-горе правило, според което „Н∨α“ може да бъде заменено с α. α в случая е „И∧q“. „И∧q“ след това е заменено с „q“ въз основа на въведеното по-горе правило, според което „И∧α“ може да бъде заместено с α. Като резултат получаваме, че когато „p“ има стойност Н, истинностната стойност на целия израз не зависи от истинностната стойност „r“, а е същата като тази на „q“. Това демонстрира другото предимство на истинностно-функционалния анализ пред таблиците за истинност – често той е по-къс, защото дава подобна „компресирана“ информация.
По-горе използвахме следните правила за заместване:
| Отрицание: |
| ¬И се замества с Н |
| ¬Н се замества с И |
| Конюнкция: |
| И∧α (α∧И) се замества с α |
| Н∧α (α∧Н) се замества с Н |
| Дизюнкция: |
| И∨α (α∨И) се замества с И |
| Н∨α (α∨Н) се замества с α |
Правилата, отнасящи се до импликацията, са следните (при импликацията, за разлика от конюнкцията, дизюнкцията и еквивалентността, редът на свързваните твърдения е от значение, затова тук имаме четири, а не две правила):
| Импликация: |
| Н→α се замества с И |
| α→И се замества с И |
| И→α се замества с α |
| α→Н се замества с ¬α |
От къде идват тези правила може да се види посредством таблицата за истинност на импликацията:
| α | β | α → β |
| И | И | И |
| И | Н | Н |
| Н | И | И |
| Н | Н | И |
Таблицата показва, че когато антецедентът на импликацията има стойност Н (последните два реда), импликацията има стойност И независимо от истинностната стойност на консеквента ѝ. Това ни дава право да заменяме „Н→α“ с „И“. Таблицата освен това показва, че когато консеквентът на импликацията има стойност И (първия и третия ред), импликацията има стойност И независимо от истинностната стойност на антецедента ѝ. Това ни дава право да заменяме „α→И“ с „И“. Основанието за третото правило е следното. Когато α има стойност „И“, „И→α“ също има стойност И, защото тогава импликацията свързва две истинни твърдения (първия ред от таблицата). Когато α има стойност Н, „И→α“ също има стойност Н, защото тогава импликация има истинен антецедент и неистинен консеквент (втория ред от таблицата). Следователно израз от вида „И→α“ винаги има същата истинностната стойност като α и значи може да бъде заместен с нея. Що се отнася до четвъртото правило, когато α има стойност И, „α→Н“ има стойност Н (втория ред от таблицата), а когато α има стойност Н, „α→Н“ има стойност И (последния ред от таблицата). Т.е. израз с формата „α→Н“ има винаги обратната на α истинностна стойност, поради което може да бъде заменен с „¬α“.
Правилата, отнасящи се до еквивалентността, са следните (те са две, тъй като редът на членовете при еквивалентността е без значение):
| Еквивалентност: |
| И↔α (α↔И) се замества с α |
| Н↔α (α↔Н) се замества с ¬α |
Ако α има стойност И, „α↔И“ също ще има стойност И (една еквивалентност е истинна, когато двете свързвани твърдения имат еднаква истинностна стойност). Ако α е Н, „α↔И“ също ще е Н, защото тогава истинностната стойност на двете свързвани твърдения ще е различна. Т.е. израз с формата „α↔И“ има винаги същата истинностна стойност като α и значи може да бъде заместен с α.
Що се отнася до второто правило, ако α има стойност И, „Н↔α“ ще има стойност Н (обратната), защото тогава истинностната стойност на свързваните от еквивалентността изрази ще е различна. Ако α има стойност Н, „Н↔α“ ще има стойност И (обратната), защото тогава истинностната стойност на свързваните изразите ще е еднаква. Получава се, че израз с формата „Н↔α“ има винаги обратната на α истинностна стойност и следователно може да бъде заместван с „¬α“.
Ето един пример на истинностно-функционален анализ, в който участват всички логически съюзи.
| [(p∧q)∨(¬p∧q)] → (q↔¬r) | |
| Случай 1 q: И | |
| [(p∧И)∨(¬p∧И)] → (И↔¬r) | |
| [p∨¬p] → ¬r | |
| И → ¬r | |
| ¬r | |
| r: И | r: Н |
| Н | И |
| Случай 2 q: Н | |
| [(p∧Н)∨(¬p∧Н)] → (Н↔¬r) | |
| [Н∨Н] → ¬¬r | |
| Н → r | |
| И | |
Този път сме избрали да започнем анализа с „q“, а не с „p“. Можем да започваме с която буква пожелаем, но като правило анализът е най-кратък, когато започваме с буквата, която се среща най-често. Затова тук сме избрали „q“. В третия ред на първото разклонение „[p∨¬p]→¬r“ е получено от „[(p∧И)∨(¬p∧И)]→(И↔¬r)“ като последователно сме приложили два пъти правилото за „И∧α“ и един път правилото за „И↔α“. След това „И→¬r“ е получено от „[p∨¬p]→¬r“ въз основа на това, че формулата „p∨¬p“ е очевидна тавтология и значи може да бъде заменена с И.
По принцип, когато стигнем до дизюнкция, свързваща израз и неговото отрицание, като „р∨¬р“, „q∨r∨¬q“, „[r→(q∧¬s)]∨¬r∨r“, „(p∧q)∨¬(p∧q)∨r“ и т.н., тъй като очевидно е тавтология, можем да я заменим с „И“. По същия начин (тъй като очевидно са тавтологии, т.е. винаги истинни) можем да заменяме с „И“ също импликации и еквивалентности, които свързват един и същ израз, като „р→р“, „¬(р∧r)→¬(р∧r)“, „q↔q“, „(q∨r)↔(q∨r)“ и т.н. Освен това можем да заместваме с „Н“ изрази, които са очевидни противоречия, като тези с формата „α∧¬α“, както и конюнкции, съдържащи израз и неговото отрицание заедно с други изрази, като „q∧¬q∧r“, „[r→(q∨¬s)]∧¬r∧r“, „(p∨q)∧¬(p∨q)∧r“ и т.н.
Връщайки се към примера, по-нататък „И→¬r“ е заменено с „¬r“ по едно от правилата за импликацията. Резултатът до тук е, че когато „q“ има стойност И, целият израз има обратната на „r“ истинностна стойност. Във второто разклонение, отговарящо на случая, когато „q“ има стойност Н, след като сме заместили „q“ с Н, на следващия ред два пъти сме приложили правилото, според което „Н∧α“ се замества с „Н“, и един път правилото, според което „Н↔α“ се замества с „¬α“. Резултатът е „[Н∨Н]→¬¬ r“. Изрази като „Н∨Н“, в които не участват букви за твърдения, а само истинностни стойности, се заместват със съответната истинностна стойност на базата на таблиците за истинност. „Н∨Н“ например се замества с „Н“ по таблицата за истинност на дизюнкцията, „И→Н“ – с „Н“ по таблицата за истинност на импликацията, и т.н. Освен това израз с формата „¬¬α“ може да бъде заменен с α, тъй като двата израза са очевидно еквивалентни. Така че, замествайки в „[Н∨Н]→¬¬r“ „Н∨Н“ с „Н“ и „¬¬r“ с „r“, получаваме „Н→r“, което след това заместваме с „И“ въз основа на едно от правилата за импликацията. Резултатът от второто разклонение на анализа е, че когато „q“ има стойност Н, целият израз има стойност И независимо от истинностните стойности на другите две букви за твърдения.
Макар и да не е задължително, за по-кратък анализ е добре да съблюдаваме правилото, да започваме ново разклонение (чрез заместване на буква за твърдение с истинностна стойност) само след като сме елиминирали всички участия на „И“ или „Н“ в разклонението, в което се намираме в момента. Например, ако сме стигнали до израза „(¬r∧q)→Н“, трябва първо да елиминираме „Н“-то в него, като го трансформираме в „¬(¬r∧q)“ със съответното правило за заместване, и чак след това да започнем нови разклонения, замествайки „r“ или „q“ първо с „И“ и след това с „Н“.
| (1) Определете с истинностно-функционален анализ дали следните формули са тавтологии, противоречия или синтетични: |
| 1) | p → (q→p) |
| 2) | ¬(p∨q) → (p∧q) |
| 3) | (¬p∨¬q) → ¬(p∧q) |
| 4) | [p→(¬q∨r)] ∨ (¬p∨q) |
| 5) | [(p→q)→r] ↔ [p→(q→r)] |
| 6) | (p→¬q) → ¬p |
| 7) | (p∧¬q) ∨ (¬p∧q) |
| 8) | (¬p∧¬q) ↔ (p↔¬q) |
| 9) | (p→q) → [(¬r∨p)→(r∧¬q)] |
| 10) | [(¬p∨¬q)∧¬r] → [(p∧q)↔r] |
| (2) Докажете с истинностно-функционален анализ, че следните формули са тавтологии: |
| 1) | ¬(p∨q) → ¬p |
| 2) | (p→q) → [(r∨p)→(r∨q)] |
| 3) | [p∨(q∧¬r)] → [(p∨q)∧(r→p)] |
| 4) | [(p→q)∧(r→s)] → [(p∨r)→(q∨s)] |
| 5) | ¬p → ¬(p∧q) |
| 6) | ¬p → [(p→q)∨q] |
| 7) | [p∧(q∨r)] → [(p∧q)∨(p∧r)] |
| 8) | [(p→q)∨r] → ¬[(p∧¬q)∧¬r] |