1.3 Таблици за истинност

Синтаксис на пропозиционалната логика

Логическата символика, чрез която представяме символно твърденията от естествения език, може да се разглежда също като един език. Всеки език има синтактични правила, които определят как от простите знаци (думите) се образуват все по-сложни съставни изрази (изреченията). Определяйки това, синтактичните правила разграничават правилно образуваните (граматически смислените) изрази от неправилно образуваните (граматически безсмислените) възможни поредици от думи. Синтаксисът на един език се определя от неговите синтактични правила. Разглеждайки синтаксиса на езика се абстрахираме от значението на изразите му и техните истинностни стойности – това което ни интересува е единствено да можем да определяме дали дадена поредица от думи е граматически правилна, или не, без значение какво означава и дали (ако е изречение) е истинна. Със значението на изразите на езика се занимава неговата семантика. Така че, насочвайки се към синтаксиса на езика на пропозиционалната логиката, нека точно формулираме кои са елементите, които изграждат изреченията му, и посредством какви синтактични правила става това.

„Думите“, от които се образуват изреченията на езика на пропозиционалната логика, са следните:

• неограничен брой букви за твърдения: „p“, „q“, „r“, „s“ …
• логическите съюзи на отрицанието („¬“), конюнкцията („∧“), дизюнкцията („∨“), импликацията („→“) и еквивалентността („↔“)
• спомагателните символи на скобите: „(“ и „)“

Синтактичните правила на езика на пропозиционалната логика са следните:

• Всяка буква за твърдение е правилно-образуван израз (формула).
• Ако α е правилно-образуван израз, то и ¬α¹ е правилно-образуван израз.
• Ако α и β са правилно-образувани изрази, то и (α∧β) е правилно-образуван израз.
• Ако α и β са правилно-образувани изрази, то и (α∨β) е правилно-образуван израз.
• Ако α и β са правилно-образувани изрази, то и (α→β) е правилно-образуван израз.
• Ако α и β са правилно-образувани изрази, то и (α↔β) е правилно-образуван израз.
• Правилно-образувани изрази са тези и само тези последователности от символи, за които може да бъде показано, че са такива въз основа на синтактичните правила i)-vi).

Взети заедно, тези седем синтактични правила точно определят (дават дефиниция на) понятието за правилно-образуван израз (или накратко формула) на пропозиционалната логика. Такива дефиниции се наричат рекурсивни. Особеното при тях е, че дефинираният термин („правилно-образуван израз“ или „формула“ в нашия случай) се използва в самата дефиниция. Рекурсивните дефиниции обаче не са кръгови, както би била например дефиницията на термина „красиво“ посредством израза „нещо, което е красиво“. Всяка дефиниция на общ термин (израз, под който попадат някакви неща) трябва да е такава, че да определя точно кои са нещата, които попадат под него. Това обикновено става като се дава критерий (необходимо и достатъчно условие) за попадане под термина. Проблемът на кръговите дефиниции не е, че даваният критерий не е необходимо и достатъчно условие (нещо да е красиво е необходимо и достатъчно условие за това, да е красиво), а че чрез него е принципно невъзможно да се определи за каквото и да било дали попада под термина, или не, тъй като, като го приложим, се завъртаме в кръг. За да разберем, например, дали даден предмет е красив на базата на горната кръгова дефиниция, трябва да разберем дали е красив, но за да разберем това, трябва да разберем дали е красив … и т.н. до безкрайност. Въпреки че използва термина, който дефинира, горната рекурсивна дефиниция на „правилно-образуван израз“ („формула“) определя точно и некръгово за всеки израз дали е правилно-образуван, или не поради следното. Първо в нея се определя кои са атомарните формули, т.е. простите (несъставени от други) правилно-образувани изрази. Това става в правило i). Правила от ii) до vi) определят по какъв начин, тръгвайки от атомарни формули и използвайки логическите съюзи, можем да образуваме все по-сложни правилно-образувани изрази. Накрая правило vii) изключва от правилно-образуваните изрази всички поредици от символи, които не са образувани в съгласие с предишните правила. Дефиницията по същество ни казва, че даден израз е правилно-образуван, ако и само ако е бил построен от елементите на определено множество от елементарни символи (което посочва) чрез използването на определени правила (които посочва). Като резултат, въпреки че съществуват безкрайно много правилно-образувани и неправилно образувани изрази, за всеки един конкретен израз може бъде проверено ефективно (за краен брой стъпки) дали е правилно-образуван, или не – нещо невъзможно при посочената кръгова дефиниция за красиво.²

Например „((p∧q)→(¬r∧¬s))“ е правилно-образуван израз (формула) на пропозиционалната логика според горната дефиниция поради следното. „p“ и „q“ са правилно-образувани въз основа на i). Следователно въз основа на iii) „(p∧q)“ също е правилно-образуван. От друга страна „r“ и „s“ са правилно-образувани въз основа на i). Следователно въз основа на ii) „¬r“ и „¬s“ също са правилно-образувани, от което въз основа на iii) следва, че също и „(¬r∧¬s)“ е правилно-образуван. След като „(p∧q)“ и „(¬r∧¬s)“ са правилно-образувани, въз основа на v) „((p∧q)→(¬r∧¬s))“ също е правилно-образуван.

Съгласно синтактичните правила от iii) до vi), винаги когато образуваме конюнкции, дизюнкции, импликации или еквивалентности трябва да ги заграждаме със скоби. Причината е, че след това те могат да участват като подформули в други формули, а тогава трябва да са в скоби. Например от „r“ и „s“ въз основа на iii) можем да образуваме „(r∧s)“, a не „r∧s“, защото, ако след това например свържем получения израз чрез импликация с „p“, в първия случай ще получим „p→(r∧s)“, а във втория – „p→r∧s“. Последният израз обаче е двусмислен – не е ясно дали е импликация (между „p“ и „r∧s“) или конюнкция (между „p→r“ и „s“).

Заграждането със скоби на образуваните по правила от iii) до vi) изрази има като резултат, че съставни изрази, които не са части от други изрази, се оказват заградени със скоби. Така например формулата, която получихме в примера по-горе, беше „((p∧q)→(¬r∧¬s))“, а не „(p∧q)→(¬r∧¬s)“. Изпускането на скобите около самостоятелни изрази се прави по конвенция за по-лесно четене. Пишем „(p∧q)→(¬r∧¬s)“, но всъщност този израз е съкращение за израза „((p∧q)→(¬r∧¬s))“.

Съгласно правило ii), когато от някакъв израз α се образува неговото отрицание ¬α, последният израз не се загражда в скоби (за разлика от конюнкциите, дизюнкциите, импликациите и еквивалентностите). В резултат на това например правилно-образуван израз е „¬¬¬p“, а не „¬(¬(¬p))“. Когато след знака за отрицание няма отваряща скоба, отрицанието се отнася до първото възможно изречение след него. Например третото (от ляво на дясно) отрицание в „¬¬¬p“ се отнася към „p“; второто – към „¬p“; първото – към „¬¬p“. По същия начин „¬“ в „¬p∧q“ се отнася до „p“, което е първото възможно изречение след отрицанието, а не към „p∧q“ – за да се отнася към „p∧q“, последното трябва да е заградено в скоби: „¬(p∧q)“.

Въпреки че съгласно синтактичните правила единствените скоби, които можем да използваме, са „(“ и „)“, за по-лесно четене ще се разберем (ако желаем) да използваме и друг вид скоби. Например ще разглеждаме „{[¬p→(q∧¬r)]∨p}↔(r∧s)“ като правилно-образуван израз, който не се различава от израза „((¬p→(q∧¬r))∨p)↔(r∧s)“.

Синтактичната структура на всеки правилно-образуван израз може да се визуализира посредством така нареченото синтактично дърво, което показва „историята“ на образуването на израза посредством синтактичните правила. Формулата „(p∧q)→(¬r∧¬s)“ например има следното синтактично дърво:

То има формата на обърнато надолу дърво, в най-крайните клони на което (най-отдолу) стоят букви за твърдения. В нашия случай това са „p“, „q“, „r“ и „s“. Такива, съставени от една единствена буква формули, се наричат атомарни формули. Историята на образуването на формулата е дадена в посока отдолу нагоре. Формулата „(p∧q)“ е образувана въз основа на правило iii) от „p“ и „q“; „¬r“ и „¬s“ – въз основа на правило ii) от „r“ и „s“; … и т.н., докато накрая се стигне до цялата формула най-отгоре на дървото. Последната стъпка, при която се получава цялата формула, показва кой е нейният главен логически съюз, т.е. каква е формата на израза като цяло. В нашия случай главният логически съюз (както и формулата като цяло) е импликация, защото в последната стъпка целият израз се получава от свързването посредством импликация на „(p∧q)“ и „(¬r∧¬s)“.

Формулите, които участват в една формула, се наричат нейни подформули. Това са формулите във всеки от възлите на синтактичното дърво. В примера подформулите на „(p∧q)→(¬r∧¬s)“ по нарастваща сложност са „p“, „q“, „r“, „s“, „¬r“, „¬s“, „p∧q“, „¬r∧¬s“ както и самата „(p∧q)→(¬r∧¬s)“, която се разглежда като подформула на самата себе си.

Семантика на пропозиционалната логика. Таблици за истинност

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

Семантичните правила на пропозиционалната логика са следните:

• (При някаква интерпретация) атомарните формули (буквите за твърдения) имат стойност И или стойност Н.
• ¬α има стойност И, ако α има стойност Н, и стойност Н, ако α има стойност И.
• α∧β има стойност И, ако α и β имат стойност И, и стойност Н във всички останали случаи.
• α∨β има стойност Н, ако α и β имат стойност Н, и стойност И във всички останали случаи.
• α→β има стойност Н, ако α има стойност И, а β стойност Н, и стойност И във всички останали случаи.
• α↔β има стойност И, ако α и β има еднакви истинностни стойности, и стойност Н, ако имат различни истинностни стойности.

Следват, обединени в две, таблиците за истинност на всички логически съюзи, които въведохме по-рано:

Тези таблици се основават на семантичните правила, а не обратното. Таблиците са начин за онагледяване на правилата.

Въз основа на семантичните правила, при всяка интерпретация на буквите за твърдения, всяка съставна формула (независимо от сложността ѝ) получава определена истинностна стойност. Буквите за твърдения се интерпретират с някакви конкретни твърдения от естествения език. Тъй като всяко такова твърдение е или истинно, или неистинно, при всяка една интерпретация използваните букви за твърдения приемат определена истинностна стойност – И или Н. Това отговаря на семантичното правило I). На базата на тези истинностни стойности, въз основа на останалите семантични правила всяка следваща по сложност подформула на формулата също получава истинностна стойност, докато накрая цялата формула получи истинностна стойност. Този процес на детерминиране на истинностните стойности на съставните формули от истинностните стойност на буквите за твърдения, които се съдържат в тях, се извършва в посока отдолу нагоре в синтактичното дърво и е възможен, защото на всяко синтактично правило отговаря семантично правило. Да вземем за пример формулата „(p∧q)→(¬r∧¬s)“, която използвахме по-горе, и приемем произволно, че интерпретацията на буквите за твърдения е такава, че „p“ и „q“ приемат стойност Н, а „r“ и „s“ стойност И. Взимайки предвид семантичните правила и структурата на формулата, така както се показва от нейното синтактично дърво, виждаме, че подформулите ѝ и накрая тя самата получават следните истинностни стойности:

Диаграмата показва как истинностните стойности на „p“, „q“, „r“ и „s“ определят (отдолу нагоре) истинностните стойности първо на подформулите на „(p∧q)→(¬r∧¬s)“ и накрая на самата нея. Подформулата ѝ „p∧q“ има стойност Н, защото „p“ и „q“ имат стойност Н (за да е истинна една конюнкция, двата ѝ конюнкта трябва да са истинни). „¬r“ има стойност Н, защото „r“ има стойност И (истинностната стойност на отрицанието на една формула е обратна на нейната) и т.н. В крайна сметка цялата формула получава стойност И при тези стойности на буквите в нея.

Вместо с горната диаграма начинът, по който истинностната стойност на формулата се определя от истинностните стойности на буквите ѝ за твърдения, може да се види и с таблица. За целта в първия ред на таблицата разполагаме от ляво на дясно подформулите и накрая самата формула по реда на нарастване на сложността им, след което определяме, пак от ляво надясно, истинностните им стойности:

Истинностните стойности на буквите за твърдения в първите четири колони са каквито ги фиксирахме по условие – произволно приехме, че „p“ и „q“ са интерпретирани с някакви неистинни изречения, а „r“ и „s“ с някакви истинни изречения. Истинностната стойност на „p∧q“ в петата колона се получава от истинностните стойности на „p“ и „q“ в първата и втората колона по таблицата за истинност на конюнкцията. Истинностните стойности на „¬r“ и „¬s“ в шестата и седмата колона се получават от истинностните стойности съответно на „r“ и „s“ в третата и четвъртата колона по таблицата за истинност на отрицанието и т.н. По принцип истинностните стойности на всяка съставна формула в таблицата се получават от истинностните стойности на една или два формули, стоящи наляво от нея. По този начин, движейки се от ляво надясно, накрая стигаме до истинностната стойност на цялата формула в най-дясната колона.

Удобството на таблицата е, че може да бъде допълвана с нови редове за други комбинации от истинностни стойности на буквите ѝ за твърдения. Добавяйки например нов ред, отговарящ на случая, когато и четирите букви за твърдения имат стойност И, получаваме, че тогава цялата формула има стойност Н:

Като продължим да добавяме нови редове за други възможни комбинации от истинностни стойности на буквите за твърдения във формулата, накрая ще изчерпим всички възможни комбинации. В случая, когато това стане, таблицата ще има 16 реда, защото 16 е броят на всички възможни комбинации от истинностни стойности на четири букви за твърдения. Такава пълна таблица, съдържаща всяка комбинация от истинностни стойности на буквите за твърдения във формулата, се нарича нейна таблица за истинност. За всяка формула може да бъде направена такава таблица. Като пример отдолу е дадена таблицата за истинност на „¬(p→q)∨¬q“:

В „¬(p→q)∨¬q“ участват две букви за твърдения – „р“ и „q“, поради което има четири комбинации от истинностни стойности за тях: и двете да имат стойност И; „p“ да има стойност И, а „q“ стойност Н; обратното; и двете да имат стойност Н. На всяка от тези четири възможности отговаря ред от таблицата. Във всеки от редовете истинностната стойност на цялата формула в последната колона се определя като последователно се определят истинностните стойности на нейните подформули в посока отляво надясно (от по-простите към по-сложните). Истинностните стойности на „p→q“ в третата колона се определят от истинностните стойности на „р“ и „q“ в първата и втората колона въз основа на таблицата за истинност на импликацията. Истинностните стойности на „¬q“ в петата колона се определя от стойностите на „q“ във втората колона въз основа на таблицата за истинност на отрицанието (стойностите под „¬q“ са обратните на тези под „q“). Истинностните стойности на „¬(p→q)“ в четвъртата колона се определят по същия начин от истинностните стойности на „p→q“. Накрая истинностните стойности на цялата формула в последната колона се определят от истинностните стойности в предишните две колони по таблицата за истинност на дизюнкцията. Като цяло таблицата показва, че едно твърдение с формата на „¬(p→q)∨¬q“ е истинно или когато „p“ и „q“ са неистинни (последния ред), или когато „р“ е истинно, а „q“ е неистинно (втория ред), и че е неистинно в останалите два случая.

Когато в една формула участва само една буква за твърдение, таблицата ѝ има два реда, отговарящи съответно на случая, при който буквата има стойност И, и случая, при който има стойност Н. Такава е например таблицата на „(р∨¬р)→¬р“:

Истинностните стойност под „¬р“ са обратните на тези под „р“. Стойностите на „р∨¬р“ се получават от тези на „р“ и „¬р“ по таблицата за истинност на дизюнкцията. Стойностите на цялата формула в последната колона се получават от истинностните стойности в предишните две колони по таблицата на импликацията. За разлика от останалите логически съюзи при импликацията редът на твърденията е от значение. Затова при определянето на истинностните ѝ стойности е важно да гледаме първо стойностите на антецедента и после тези на консеквента, въпреки че, както е тук, редът им в таблицата може да е обратен – в примера стойностите на антецедента са в третата колона, а тези на консеквента във втората.

Когато една таблица за истинност има два реда (т.е. когато формулата ѝ има само една буква за твърдение), ще подреждаме истинностните стойности под тази буква, като първо пишем „И“, а после „Н“. Т.е. като правило таблицата за истинност на формула с една буква ще започва така:

Когато буквите за твърдения са две (например „p“ и „q“), на всеки от двата възможни случая за „p“ (които продължаваме да подреждаме по същия начин – първо „И“, после „Н“) отговарят по два случая за „q“. Затова удвояваме всяка от стойностите под „p“ и за всяка удвоена стойност подреждаме стойностите за „q“ по същия начин – първо „И“, после „Н“. Така че като правило таблицата за истинност на формула с две букви за твърдения ще започва така:

При подреждането на комбинациите в таблица за истинност на формула с три букви ще следваме същото правило: ще изхождаме от подреждането при две букви, т.е. „ИИ“, „ИН“, „НИ“, „НН“, като ще удвояваме всяка от тези четири комбинации заради третата буква (т.е. последователността в първите две колони става „ИИ“, „ИИ“, „ИН“, „ИН“, „НИ“, „НИ“, „НН“, „НН“), и за всяко такова удвояване за третата буква ще слагаме първо „И“, после „Н“. Така подреждането става следното:

Формулиран за произволен брой букви за твърдения начинът, по който ще подреждаме истинностните стойности в таблиците, е следният: при една буква пишем първо „И“, после „Н“; при две букви следваме същия ред, но удвояваме всеки от редовете и добавяме към първия от удвоените редове „И“, към втория „Н“; при три букви следваме същия ред както при две, но удвояваме редовете и добавяме към първия „И“, към втория „Н“; … и т.н.; при n букви за твърдения следваме същия ред както при n-1, но удвояваме редовете и добавяме към първия „И“, към втория „Н“.

От начина на подреждане на комбинациите от истинностни стойности се вижда, че всяко добавяне на буква за твърдение удвоява редовете на таблицата. При една буква таблицата има 2 реда; при две букви редовете стават 2.2 = 2² = 4 ; при три букви – 2.2.2 = 2³ = 8; … и т.н.; при n букви таблицата ще има 2ⁿ реда.

Като пример на таблица за истинност на формула с три букви нека построим таблицата на „р→¬(q∨¬r)“:

Построяването на таблицата не се различава от това на таблици на формули с една или с две букви – единствената разлика е, че редовете са повече. Стойностите под „¬r“ са обратните на тези под „r“; стойностите под „q∨¬r“ са получени от тези под „q“ и „¬r“ по таблицата за истинност на дизюнкцията; стойностите под „¬(q∨¬r)“ са обратните на тези в предишната колона; стойностите на целия израз в последната колона са получени от стойностите под „p“ и „¬(q∨¬r)“ (в този ред) по таблицата за истинност на импликацията.

В зависимост от таблицата си за истинност всяка формула попада в една от следните три групи:

• Формули, които имат само стойност И в последната колона на таблицата си; те се наричат тавтологии.
• Формули, които имат само стойност Н в последната колона на таблицата си; те се наричат противоречия.
• Формули, които имат както стойност И, така и стойност Н в последната колона на таблицата си; те се наричат синтетични.

Тавтологиите са формули, които получават винаги стойност И, независимо от истинностните стойности на буквите им за твърдения. Така ще наричаме също и изреченията от естествения език, които имат формата на тавтологии, т.е. които се представят символно с такива формули. Въпросните изречения се наричат още логически истинни. Те имат характерното свойство, че истинността им не зависи от фактите. Например не е нужно да правим някакви исторически проучвания, за да установим, че изречението „Сократ е имал или нямал по-малък брат“ („р∨¬р“) е истинно. Не е нужно да знаем дори кой е Сократ.

Пример за тавтология, която (за разлика от „р∨¬р“) не е очевидна, е „[(р→q)→p]→p“. Тавтологичността ѝ се вижда от следната таблица:

Противоречия наричаме формулите, които получават винаги стойност Н независимо от истинностните стойности на буквите им за твърдения. Така ще наричаме също и изреченията от естествения език, които се представят символно с такива формули. Въпросните изречения се наричат още логически неистинни. Както при логически истинните изречения при тях не е нужно да се обръщаме към действителността, за да определим дали са истинни, или не. Неистинността им са съдържа в самото им значение. Каквито и да са фактите, ясно е, че изречението „Сократ е имал и е нямал по-малък брат“ („p∧¬p“) е неистинно:

Задачи