Истинност на формулите

Ако имаме няколко прости съждения, които сме съставили във формула, можем да се опитаме да решим дали цялата формула е вярна, или невярна.

Истинност на съждение

Първо ще уточним какво е истинностна стойност на съждение. Ако имаме съждение p, трябва да можем да решим дали е вярно, или невярно. Вярното съждение има истинностна стойност 1, а невярното – 0.

Оценка на истинността е правило e, което на дадено съждение приписва или 0, или 1. Ако напишем e(p), искаме да разберем истинността на съждението p. Ако p е съждението „два по два е четири“, то e(p) = 1, защото става дума за вярно съждение. Ако q е съждението „Стефан Стефанов е жена“, то e(q) = 0, защото Стефан не е жена. Така e е функция, която ни връща дали съждението е вярно.

Тук трябва да си дадем сметка, че e не е някаква магическа функция, която знае всичко на света. Тя се държи така, както ѝ кажем. Тя не знае дали Стефан Стефанов е мъж, или жена. В началото на изчислението ние трябва да зададем как да се държи оценяващата функция. Ако ѝ кажем, че Стефан Стефанов е жена, тя ще ни върне e(q) = 1.

Истинност на логическите връзки

За да определим истинността на една формула, трябва да знаем как се оценява истинността на логическите връзки. Тоест ако знаем оценките e(p) и e(q), каква ще е истинностната стойност на формулите p ∧ q, p ⇒ q и т.н.

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

Истинност на конюнкцията

Конюнкцията се означава p ∧ q и се чете „p и същевременно q“. За пример да вземем формулата „България се намира в Югоизточна Европа и същевременно столицата ѝ е София“. Кога цялото това изречение е вярно?

За определянето на истинността ни помага вече самата връзка „и същевременно“. Тя изрично ни казва, че иска и двете съждения отляво и отдясно да са верни. Ако и двете съждения p и q са верни, тоест e(p) = 1 и e(q) = 1, то е вярна и цялата конюнкция. В противен случай, когато едното от съжденията е невярно или и двете са неверни, цялата формула е невярна.

Пример за конюнкция, която не е вярна, може да бъде: „Дунав е река и същевременно Дунав тече през Русия“. Вярно е, че Дунав е река, но не е вярно, че тече в Русия, така че цялата конюнкция не е вярна.

Прегледно това се записва в следната таблица:

$$\begin{array}{ccc}p& q& p\wedge q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 0\end{array}$$

В първите две колони са истинностните стойности на съжденията p и q, а в третата е истинностната стойност на формулата p ∧ q.

Истинност на дизюнкцията

Дизюнкцията се означава p ∨ q и се чете „p или q“. Пример: „Русия лежи в Европа или в Азия.“ Кога цялото изречение е вярно?

При дизюнкцията ни стига поне една от възможностите да е вярна. Връзката „или“ ни дава избор, достатъчно е лявата или дясната част да е вярна. Единствената малка разлика спрямо обикновената реч е, че логическото „или“ е вярно и когато са изпълнени и двете съждения едновременно. Това не е обичайно, често в говоримия език използваме „или“ в изключващ смисъл, тоест „или …, или …“

За това има класическа шега: семейство избира нова кола в автокъща. Таткото казва на продавача: „решихме да вземем синя или червена кола“. Продавачът им продаде и двете коли. Това илюстрира разликата между логическото и говоримото „или“: таткото вероятно е имал предвид, че ще изберат точно една от колите, а продавачът е сметнал за допустимо да им продаде и двете.

Предишното изречение за Русия е вярно, защото и двете съждения са верни. Изречението „числото 7 се дели на 3 или числото 7 е просто“ е вярно, защото седем е просто число. Вярно е, че не се дели на три, но това вече не ни пречи. Таблица на истинностните стойности:

$$\begin{array}{ccc}p& q& p\vee q\\ 1& 1& 1\\ 1& 0& 1\\ 0& 1& 1\\ 0& 0& 0\end{array}$$

Истинност на импликацията

Импликацията се означава p ⇒ q и се чете „ако p, то q“. Пример за импликация е изречението „ако изпием много водка, ще повърнем“. Кога е вярно изречението?

Логическата импликация е най-коварната от всички връзки и дори в обикновената реч често не се разбира правилно и се бърка с еквивалентността. Да се опитаме да отговорим на въпроса дали е вярна и обратната импликация: q ⇒ p.

Знаем, че ако изпием много водка, ще повърнем. Вярно ли е също така, че ако повръщаме, значи сме изпили много водка? Със сигурност не, може да сме пили съвсем друг алкохол и пак да ни е лошо или да ни е лошо от нещо съвсем различно. Обратната импликация съвсем не е задължително да е вярна. Ако са верни p ⇒ q и същевременно q ⇒ p, става дума за еквивалентност, вж. по-нататък.

Друг пример: „ако утре вали, Георги ще вземе чадър“. А сега ти казвам, че Георги е взел чадър. Въпросът е: валяло ли е този ден? Много хора са склонни да кажат, че разбира се да, нали Георги е взел чадър, щом е трябвало да вали. Само че първоначалното изречение не е построено така!

Всъщност Георги може да е взел чадър по друга причина, за която нямаме представа. Може би Георги винаги взема чадър, когато отива на гости на тъщата си, за да може да ѝ избоде окото. Или е решил да си купи нов чадър, а стария иска да изхвърли. Всичко това са напълно допустими причини Георги да е взел чадър, въпреки че не е било задължително да вали.

Сега вече можем да отговорим на въпроса кога импликацията е вярна. Когато и двете съждения са верни, импликацията със сигурност е вярна: „ако 42 е естествено число, то е положително“. И двете съждения са верни, така че цялата импликация е вярна. Друг пример е импликацията „ако 42 е естествено число, то е отрицателно“. Тази импликация не е вярна, защото се опитваме от истина да изведем нещо, което не е истина.

Накрая остават случаите, когато първото съждение е невярно. Тогава истинността на второто съждение вече не ни интересува. Ако тръгваме от неистина, можем нататък да дърдорим каквото си искаме. Това са изречения от рода на „ако 1 е отрицателно число, то ние сме китайският бог на шегите“ или „ако Витоша е известна строителна фирма, то слънцето е синьо“. В такива случаи импликацията автоматично е вярна, защото просто тръгва от неистина. Таблица:

$$\begin{array}{ccc}p& q& p\Rightarrow q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 0& 1\end{array}$$

Истинност на еквивалентността

Еквивалентността се записва p ⇔ q и се чете „p тогава и само тогава, когато q“. Пример за еквивалентност е „числото x се дели на две тогава и само тогава, когато е четно“. Кога цялото изречение е вярно?

При еквивалентността очакваме двете съждения да са в такава симбиоза, че или са верни и двете, или не е вярно нито едно. Така или числото x е четно и същевременно се дели на две, или не е нито едното, нито другото. Не може да се случи x да е четно, но да не се дели на две.

Пример: „Георги чете книга тогава и само тогава, когато седи в тоалетната.“ За да е изпълнена еквивалентността, винаги когато Георги седи в тоалетната, той трябва да чете книга. И същевременно винаги когато чете книга, трябва да седи в тоалетната. Не може да се случи да чете книга например в леглото.

Еквивалентността можем да изразим с две импликации. Така p ⇔ q можем да препишем като p ⇒ q и същевременно q ⇒ p. Таблица:

$$\begin{array}{ccc}p& q& p\iff q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}$$

Отрицание

Отрицанието е унарна операция, записваме го или с щрих p', или с този символ: ¬p. Отрицанието отрича първоначалното твърдение. Ако имаме съждението „Мария е певица“, то отрицанието му е съждението „Не е вярно, че Мария е певица“ или накратко „Мария не е певица“. На практика винаги можем да образуваме отрицание, като пред съждението поставим „Не е вярно, че…“

Отрицанието ни обръща истинностната стойност, тоест от 0 прави 1, а от 1 прави 0. Можем да запишем ¬0 = 1 и ¬1 = 0.

Внимавай за някои коварни неща. Нека имаме твърдението „варта е бяла“. Какво е отрицанието? Някой би могъл да се сети, че „варта е черна“, но това не е вярно! Когато използваме предишното правило, отрицанието ще е съждението „не е вярно, че варта е бяла“. Означава ли това задължително, че е черна? Не означава, може да е например розова.

Таблица на всички връзки

$$\begin{array}{cccccc}p& q& p\wedge q& p\vee q& p\Rightarrow q& p\iff q\\ 1& 1& 1& 1& 1& 1\\ 1& 0& 0& 1& 0& 0\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 1\end{array}$$

Истинност на цяла формула

Вече можем да оценим истинността на две съждения, свързани с логическа връзка. Цялата формула оценяваме напълно аналогично. Ако имаме формулата (p ⇒ q) ∧ r, то щом установим, че формулата (p ⇒ q) има например стойност 1, получаваме класическата конюнкция 1 ∧ r, която вече умеем да решаваме.

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

Табличен метод

Табличният метод се използва при оценяване на по-сложни формули. В първите n колони записваме n-те съждителни символа, с които работи формулата, а в следващите колони последователно поставяме частичните подформули, които формулата съдържа. На пример ще стане по-ясно:

Нека имаме формулата (p ∨ q) ∧ (q ⇒ p). В началото записваме в таблицата всички съждителни символи, тоест p и q, и всички комбинации от техните оценки:

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

След това добавяме колони за отделните подформули p ∨ q и q ⇒ p.

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Сега оценяваме тези формули и попълваме в колоните нули или единици. В таблицата имаме цялата необходима информация. Действаме така: когато оценяваме p ∨ q в първия ред, на мястото на p заместваме 1 и на мястото на q също 1. Така получаваме израза 1 ∨ 1. Стойността на този израз пак е 1, така че в таблицата записваме единица:

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Така последователно попълваме цялата таблица:

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1& 1\\ 1& 0& 1& 1\\ 0& 1& 1& 0\\ 0& 0& 0& 1\end{array}$$

Сега остава да оценим цялата формула. Нека я означим например φ = (p ∨ q) ∧ (q ⇒ p). Добавяме към таблицата колона с φ и я оценяваме, като вече използваме предишните две колони.

$$\begin{array}{ccccc}p& q& p\vee q& q\Rightarrow p& \phi \\ 1& 1& 1& 1& 1\\ 1& 0& 1& 1& 1\\ 0& 1& 1& 0& 0\\ 0& 0& 0& 1& 0\end{array}$$

Таблицата е готова и ни определя истинностната стойност на формулата при всички възможни оценки. Например ако e(p) = 1 и същевременно e(q) = 1, формулата е вярна. Когато e(p) = 0 и e(q) = 1, формулата не е вярна.

Забележи, че не можем да кажем „формулата е вярна“. Това изречение няма смисъл, защото за да кажем, че формулата е вярна, трябва да кажем при коя оценка е вярна. Можем да кажем, че „формулата φ е вярна при оценката e₁ и не е вярна при оценката e₂“.

Единственият случай, в който можем да кажем, че формулата е вярна, е когато е вярна при всички възможни оценки. Например формулата p ∨ ¬p е вярна при всички оценки, така че можем да кажем, че формулата е вярна. Аналогично за случая, когато формулата е невярна при всички оценки.

Такива формули имат свое специално название. Формула, която е вярна при всички оценки, се нарича тавтология. Формула, която не е изпълнена при нито една оценка, се нарича противоречие.