Исказна логика¶

Основни појам исказне логике је исказ. То је тврдња која може бити тачна или нетачна. На пример, „Београд је главни град Републике Србије“ је тачан исказ, а „7 је паран број“ је нетачан исказ.

У реалности постоје и тврдње које могу бити истините у некој мери, попут исказа „напољу је данас топло“, који зависи од субјективног осећаjа, контекста (доба године) и слично. Ми се нећемо бавити таквом оценом, већ ћемо разматрати само класичну логику у којој је сваки исказ или потпуно тачан или потпуно нетачан.

Сложене исказе добијамо тако што једноставне исказе повезујемо логичким везницима.

На пример, исказ „број 6 није прост“ је негација (логичко не) исказа „број 6 је прост“. Пошто је други исказ нетачан, први исказ (негација) је тачан. Негацију исказа \(p\) означавамо са \(\neg p\) и њена истинитосна вредност је супротна од истинитосне вредности полазног исказа.

Исказ „7 је непаран прост број“ у себи крије конјункцију (логичко „и“) исказа „7 је непаран број“ и „7 је прост број“. Сва ова три исказа су тачна. Конјункција исказа је тачна ако и само ако су тачна оба исказа.

Конјункција исказа \(p\) и \(q\) обележава се са \(p \wedge q\). Истинитосна вредност тог исказа у зависности од истинитосне вредности исказа \(p\) и истиитосне вредности исказа \(q\) одређена је следећом таблицом (0 означава да је исказ нетачан, а 1 да је тачан).

Купац добија попуст ако је тачан исказ „купац је премијум купац или му је рачун већи од 1000 динара“. Тај исказ је дисјункција (логичко „или“) исказа „Купац је премијум купац“ и исказа „рачун је већи од 1000 динара“. Дисјункција је тачна када је било који од та два исказа тачан, тј. када је тачан бар један од њих. Могуће је да се деси и да су оба исказа тачна и њихова дисјункција ће бити тачна (ако премијум купац направи рачун већи од 1000 динара, исказ ће бити тачан и он ће добити попуст). Таква дисјункција се назива инклузивна дисјункција. У математици се подразумева да је дисјункција инклузивна осим ако се другачије не нагласи.

Постоји и ексклузивна дисјункција која је тачна када је тачно један од два исказа тачан. На пример, „киша или пада или не пада“ је исказ који је увек тачан јер је увек тачно један од два дата исказа тачан (ако киша пада, тачан је само први, а ако не пада тачан је само други исказ). Још један, пример исказа који у себи садржи дисјункцију се може протумачити као ексклузивна је ако особа која води рачуна о својој линији каже да ће ићи у посластичарницу „или ако имам пуно пара или ако сам јако гладна“. Наиме, ако су оба услова испуњена, та особа неће отићи у посластичарницу, јер се боји да ће се пуно угојити ако јако гладна и са пуно пара оде у посластичарницу. Ексклузивност дисјункције обично у говорном језику наглашавамо коришћењем везника „или-или“.

Размотримо исказ „ако добијем лото-премију, частићу вас летовањем“. Ово је пример импликације (ако-онда). Размислимо када је овај исказ тачан тј. када особа која ово каже говори истину, а када лаже тј. даје лажно обећање пријатељима.

• Ако особа добије премију и части пријатеље летовањем, очигледно је рекла истину.

• Ако особа добије премију, а онда не части пријатеље летовањем, јасно је да је слагала.

• Ако особа не добије премију и не части пријатеље, поново је јасно да није ништа слагала.

• Донекле збуњујућ случај је ако особа не добије лото-премију, а ипак части пријатеље летовањем (вероватно, јер је на неки други начин дошла до новца). Ни у овом случају не можемо рећи да је особа лагала. Наиме, особа у свом исказу није рекла ништа о томе шта ће се десити ако не добије премију, па шта год да се у том случају догоди, она није слагала своје пријатеље.

Дакле, импликација је нетачна једино када је претпоставка испуњена а закључак није (особа је добила премију, а није частила пријатеље). Импликација је тачна у свим осталим случајевима. Ако претпоставка није испуњена, импликација је тачна (ако особа не добије премију, сигурно није дала лажно обећање). Такође, ако је закључак тачан, импликација је тачна (ако особа части пријатеље летовањем, сигурно није дала лажно обећање).

Честа забуна је да људи мешају импликацију и еквиваленцију, тј. исказ „ако будеш учио, добићеш добру оцену“ схватају као исказ „добићеш добру цену ако и само ако будеш учио“, што, између осталог, значи да ако ученик не буде учио он сигурно неће добити добру оцену. Еквиваленција је тачна једино када два исказа имају исту истинитосну вредност (или су оба нетачна или су оба тачна).

Применом ових логичких везника кренувши од елементарних исказа и евентуално логичких константи \(\top\) и \(\bot\), градимо сложене исказе, тј. исказне формуле. На пример, \(p \vee \neg q \Leftrightarrow (p \wedge (\neg q \Rightarrow p))\). Подразумевамо да у овако записаним формулама приоритет има оператор \(\neg\), затим \(\wedge\), па \(\vee\), затим \(\Rightarrow\) и на крају \(\Leftrightarrow\).

Обратимо пажњу на то да смо за истинитосне вредности формуле одабрали вредности 0 и 1, а не логичке констане \(\bot\) и \(\top\). Наиме, пожељно је да се чим видимо нешто написано зна да ли је то што је написано логичка формула или њена истинитосна вредност. Гледајући из перспективе програмирања, тип логичке формуле и тип истинитосне вредности није исти тип и стога није добро да постоје објекти који би истовремено били представници оба типа. У приступу који смо одабрали када напишемо \(\top\) или bot одмах знамо да су у питању логичке формуле, а када напишемо 0 или 1 одмах знамо да су у питању истинитосне вредности. За скуп истинитосних вредности могли смо да уместо скпа \(\{0, 1\}\) одаберемо и неки други двочлан скуп (нпр. \(\{\mathit{true}, \mathit{false}\}\)), али треба избегавати да то буде скуп \(\{\top, \bot\}\)).

Синтакса исказне логике дефинише како се граде исправно записане формуле. Прецизна дефиниција синтаксе формуле је одређена контекстно слободном граматиком:

\[\begin{split}\begin{eqnarray*} \mathit{formula} &\rightarrow& promenljiva\\ \mathit{formula} &\rightarrow& \top\\ \mathit{formula} &\rightarrow& \bot\\ \mathit{formula} &\rightarrow& \neg \mathit{formula}\\ \mathit{formula} &\rightarrow& \mathit{formula} \wedge \mathit{formula}\\ \mathit{formula} &\rightarrow& \mathit{formula} \vee \mathit{formula}\\ \mathit{formula} &\rightarrow& \mathit{formula} \Rightarrow \mathit{formula}\\ \mathit{formula} &\rightarrow& \mathit{formula} \Leftrightarrow \mathit{formula}\\ \mathit{formula} &\rightarrow& (\mathit{formula}) \end{eqnarray*}\end{split}\]

Семантика одређује истинитосну вредност формула. Валуација \(v\) је функција која пресликава скуп променљивих у скуп \(\{0, 1\}\) (променљиве које се сликају у 1 су тачне у тој валуацији, а оне које се сликају у 0 су нетачне у тој валуацији). Вредност формуле \(F\) у валуацији \(v\) обележавамо са \(I_v(F)\). Функцију \(I_v\) дефинишемо рекурзивно, на основу водећег везника у формули.

• \(I_v(\top) = 1\)

• \(I_v(\bot) = 0\)

• \(I_v(p) = v(p)\)

• \(I_v(\neg F) = 1 - I_v(F)\)

• \(I_v(F_1 \wedge F_2) = \min{(I_v(F_1), I_v(F_2))}\)

• \(I_v(F_1 \vee F_2) = \max{(I_v(F_1), I_v(F_2))}\)

• \(I_v(F_1 \Rightarrow F_2) = I_v(\neg F_1 \vee F_2)\)

• \(I_v(F_1 \Leftrightarrow F_2) = I_v((F_1 \Rightarrow F_2) \wedge (F_2 \Rightarrow F_1))\)

Кажемо да је формула \(F\) тачна у датој валуацији \(v\) ако и само ако је \(I_v(F) = 1\). Ово обележавамо и са \(v \vDash F\).

Неке исказне формуле су тачне без обзира на истинитосну вредност полазних исказа од којих су изграђени. Такве формуле се називају таутологије. На пример, формула \(\neg (p \wedge q) \Leftrightarrow \neg p \vee \neg q\) је тачна без обзира на то да ли су \(p\) и \(q\) тачни (то је јасно ако разумемо да она говори о томе да је исто рећи да није тачно да су \(p\) и \(q\) оба тачни и рећи да бар један од њих није тачан).

Доделу истинитосних вредности променљивих називамо валуација (на пример, другом реду у претходној табели одговара валуација \(p\mapsto 0, q\mapsto 1\)). Таутологије су формуле које су тачне у свим валуацијама. Негације таутологија су незадовољиве, тј. нетачне у свим валуацијама. Формуле које су тачне бар у једној валуацији називамо задовољиве формуле, а формуле које нису таутологије, тј. које су нетачне бар у једној валуацији називамо порециве формуле.

Испитивање коректности закључивања се може свести на испитивање таутологичности неких формула. Закључивање се обично заснива на томе да се на основу тога што је познато да важи један или више исказа (претпоставке, тј. премисе) тврди да важи и неки додатни исказ (закључак, тј. конклузија). Закључак је исправан ако је он логичка последица претпоставки, тј. ако је тачан када год су све претпоставке тачне. Да би се испитало да ли је исказ \(q\) логичка последица претпоставки \(p_1, p_2, \ldots, p_n\) (што можемо записати као \(p_1, \ldots p_n \vDash q\)), довољно је испитати да ли је формула \(p_1 \wedge p_2 \wedge \ldots \wedge p_n \Rightarrow q\) таутологија. Дакле, логичке последице су у тесној вези са импликацијом, међутим, ово прво је семантички појам (укључује анализу тачности две формуле), а ово друго је синтаксички појам (само гради нову формулу од датих).

Испитивање таутологичности (али и задовољивости, незадовољивости и порецивости) формула може се извршити испитивањем свих валуација, тј. прављењем истинитосне таблице, а видећемо да постоје и ефикаснији и интуитивнији начини.

На пример, претпоставимо да знамо да су искази „Ако је Цеца победила онда је Марија била друга или је Сандра била трећа“ и „Сандра није била трећа“ тачни. Да ли је исправно из њих закључити да је исказ „Ако Марија није била друга, онда Цеца није победила“? Желимо да проверимо да ли је трећи исказ логичка последица прва два, тј. да ли је трећи исказ тачан у свим валуацијама у којима су прва два тачна. Да би се то проверило довољно је проверити да је формула \(I_1 \wedge I_2 \Rightarrow I_3\) таутологија, где су са \(I_1\) и \(I_2\) означени полазни искази, а са \(I_3\) исказ за који проверавамо да ли је њихова логичка последица. Ако са \(p\) означимо исказ „Цеца је победила“, са \(q\) исказ „Марија је била друга“ и са \(r\) исказ „Сандра је била трећа“, добијамо формулу:

\[(p \Rightarrow q \vee r) \wedge (\neg r) \Rightarrow (\neg q \Rightarrow \neg p)\]

Ова формула јесте таутологија, што доказујемо следећом истинитосном таблицом:

\[\begin{split}\begin{array}{ccccccccccccccccccc} (p & \Rightarrow &q & \vee& r) &\wedge& (\neg &r) &\Rightarrow &(\neg &q &\Rightarrow &\neg &p)\\ \hline {\bf 0} & 1 & {\bf 0} & 0 & {\bf 0} & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0\\ {\bf 0} & 1 & {\bf 0} & 1 & {\bf 1} & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0\\ {\bf 0} & 1 & {\bf 1} & 1 & {\bf 0} & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0\\ {\bf 0} & 1 & {\bf 1} & 1 & {\bf 1} & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0\\ {\bf 1} & 0 & {\bf 0} & 0 & {\bf 0} & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1\\ {\bf 1} & 1 & {\bf 0} & 1 & {\bf 1} & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1\\ {\bf 1} & 1 & {\bf 1} & 1 & {\bf 0} & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1\\ {\bf 1} & 1 & {\bf 1} & 1 & {\bf 1} & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1\\ \end{array}\end{split}\]

Приметимо да смо у претходној истинитосној таблици вредности променљивих писали испод њиховог назива, док смо испод сваког везника писали истинитосну вредност потформуле којој је тај везник водећи везник. Водећи везник у целој формули је импликација која повезује конјункцију прва два исказа и трећи исказ, па је истинитосна вредност целе формуле исписана испод тог везника. Видимо да су у тој колони све јединице, што значи да је формула увек тачна, без обзира на истинитосне вредности исказа \(p\), \(q\) и \(r\) и да је таутологија.

Проблем метода истинитосних таблица је то што је тај метод веома неефикасан. Наиме, за \(n\) исказних променљивих таблица има \(2^n\) врста, па већ формуле од педесетак променљивих није могуће обрадити на овакав начин, чак ни уз коришћење веома ефикасних савремених рачунара. Таутологичност можемо доказати и неким другим методама. Једна од популарнијих је и метода семантичких таблоа.

Покушавамо да пронађемо валуацију \(v\) у којој ће цела формула бити нетачна, тј.

\[I_v\left((p \Rightarrow q \vee r) \wedge (\neg r) \Rightarrow (\neg q \Rightarrow \neg p)\right) = 0\]

Пошто је у питању импликација, она ће бити нетачна ако и само ако су обе премисе тачне, а закључак нетачан. Дакле, потребно је да нађемо валуацију у којој важи:

\[\begin{split}I_v\left(p \Rightarrow q \vee r\right) = 1\\ I_v\left(\neg r\right) = 1\\ I_v\left(\neg q \Rightarrow \neg p\right) = 0\end{split}\]

Пошто формула \(\neg r\) мора бити тачна, у нашој траженој валуацији исказ \(r\) мора бити нетачан, а пошто импликација \(\neg q \Rightarrow \neg p\) мора бити нетачна, њена премиса мора бити тачна, а закључак нетачан. Тако долазимо до следећих услова:

\[\begin{split}I_v\left(p \Rightarrow q \vee r\right) = 1\\ I_v\left(r\right) = 0\\ I_v\left(\neg q\right) = 1\\ I_v\left(\neg p\right) = 0\end{split}\]

Пошто формула \(\neg q\) мора бити тачна, исказ \(q\) мора бити нетачан, а пошто формула \(\neg p\) мора бити нетачна, исказ \(p\) мора бити тачан.

\[\begin{split}I_v\left(p \Rightarrow q \vee r\right) = 1\\ I_v\left(r\right) = 0\\ I_v\left(q\right) = 0\\ I_v\left(p\right) = 1\end{split}\]

Међутим, ови услови су заједно неодрживи. Да би импликација \(p \Rightarrow q \vee r\) била тачна, потребно је или да је њена претпоставка \(p\) нетачна или да је њен закључак \(q \vee r\) тачан. Наш табло се зато грана на две могућности:

• Прва могућност је да важи \(I_v(p)=0\), међутим, то се коси са условом \(I_v(p)=1\) који је раније изведен.

• Друга могућност је да важи \(I_v(q \vee r)=1\). Да би ова импликација била тачна треба да важи или \(I_v(q)=1\) или да важи \(I_v(r)=1\). Наш табло се зато поново грана на две могућности, међутим, лако се види да су обе неодрживе.

  • Ако важи \(I_v(q)=1\), тада није могуће да важи и \(I_v(q)=0\), што је услов који смо већ раније извели.

  • Ако важи \(I_v(r)=1\), тада није могуће да важи и \(I_v(r)=0\), што је услов који смо већ раније извели.

Дакле, све гране нашег таблоа су контрадикторне и није могуће пронаћи валуацију у којој би наша формула била нетачна.

Често се у закључивању користи и чињеница да су две формуле логички еквивалентне, што значи да је прва тачна ако и само ако је друга тачна (логичка еквивалентност формула \(\phi_1\) и \(\phi_2\) се некада обележава са \(\phi_1 \equiv \phi_2\)). На пример, еквивалентно је да ли смо рекли ако је суво, онда није падала киша и ако је падала киша, онда није суво. Уопште, формуле \(p \Rightarrow q\) и \(\neg q \Rightarrow \neg p\) су логички еквивалентне (овај конкретан пример се назива контрапозиција). Да би се доказало да су \(\phi_1 \equiv \phi_2\) еквиваленција, довољно је доказати да је \(\phi_1 \Leftrightarrow \phi_2\) таутологија. Дакле, логичка еквиваленција је у тесној вези са еквиваленцијом, али ово прво је семантички појам (укључује анализу тачности формула), а ово друго је синтаксички појам (само гради нову формулу од две задате).