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

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

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

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

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

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

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

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

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

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

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

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

(pq) → (¬r∧¬s)
pq ¬r ∧ ¬s
p q ¬r ¬s
r s

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

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

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

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

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

Съдържанието на семантичните правила, дадено под формата на таблици за истинност, е следното:

α β α ∧ β α ∨ β α → β α ↔ β
И И И И И И
И Н Н И Н Н
Н И Н И И Н
Н Н Н Н И И
α ¬α
И Н
Н И

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

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

(pq) → (¬r∧¬s)
И
pq ¬r ∧ ¬s
Н Н
p q ¬r ¬s
Н Н Н Н
r s
И И

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

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

p q r s pq ¬r ¬s ¬r∧¬s (pq)→(¬r∧¬s)
Н Н И И Н Н Н Н И

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

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

p q r s pq ¬r ¬s ¬r∧¬s (pq)→(¬r∧¬s)
Н Н И И Н Н Н Н И
И И И И И Н Н Н Н

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

Като пример нека разгледаме таблицата на „¬(pq)∨¬q“:

p q pq ¬(pq) ¬q ¬(pq)∨¬q
И И И Н Н Н
И Н Н И И И
Н И И Н Н Н
Н Н И Н И И

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

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

p ¬p p∨¬p (p∨¬p)→¬p
И Н И Н
Н И И И

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

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

И
Н

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

И И
И Н
Н И
Н Н

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

И И И
И И Н
И Н И
И Н Н
Н И И
Н И Н
Н Н И
Н Н Н

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

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

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

p q r ¬r q∨¬r ¬(q∨¬r) р→¬(q∨¬r)
И И И Н И Н Н
И И Н И И Н Н
И Н И Н Н И И
И Н Н И И Н Н
Н И И Н И Н И
Н И Н И И Н И
Н Н И Н Н И И
Н Н Н И И Н И

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

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

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

Пример за тавтология: „[(рq)→p]→p

p q рq (рq)→p [(рq)→p]→p
И И И И И
И Н Н И И
Н И И Н И
Н Н И Н И

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

p ¬p p∧¬p
И Н Н
Н И Н

Задачи

(Изтеглете задачите като pdf.)

(1) Определете дали следните изрази са правилно образувани, или не:

1) ¬(р∧¬q)

2) ¬(¬r)

3) [(qp)]→qr

4) [¬(pq)→p]→¬¬¬p

5) p→(¬r∧¬q)∨(q∧¬s)

6) q∧¬¬¬¬q

7) [¬(p)∧q]∨r

8) {[(ss)→s]→s}→s

9) (qq)→(rr)

10) q→(qr)→r

11) ¬¬[¬p→(rq)]

12) p∧(qr)∧s

(2) Избройте всички подформули на следните формули:

1)pr) ∨ (p↔¬q)

2) [p∧(q∨¬r)] ↔ [(pq)∨¬r]

3) (p∧¬p) ↔ (r→¬q)

4) [(p→¬q)→r] → (¬r∧¬p)

(3) За всяка от следните формули определете дали е елементарна формула, отрицание, конюнкция, дизюнкция, импликация или еквивалентност:

1) ¬[(qp)∧r]∧p

2) ¬rs

3) ¬(pq)∧¬(qp)

4) ¬¬[(pq)→(pq)]

5) q

6) (¬¬pq)∧(qp)

7) ¬q∨(pq)

8) ¬¬p∧¬¬r

9) ¬q∨¬(¬pq)

10) p∧¬[(pq)→r]

(4) Постройте таблици за истинност на следните формули и определете дали са тавтологии, противоречия или синтетични.

1) p → (qp)

2) ¬(pq) → (pq)

3) (p→¬q) → ¬p

4) [p→(¬qr)] ∨ (¬pq)

5)p∨¬q) → ¬(pq)

6) (pq) → (¬q→¬p)

7) (p∧¬q) ∨ (¬pq)

8)p∧¬q) ↔ (p↔¬q)

9) [(pq)∧¬(pq)] ↔ (p↔¬q)

10) (pq) → [(¬rp)→(r∧¬q)]

11) [(¬p∨¬q)∧¬r] → [(pq)↔r]

12) [(pq)→r] ↔ [p→(qr)]

(5) Като използвате таблици за истинност, докажете, че следните формули са тавтологии:

1) p ∨ ¬p

2) p → [q→(pq)]

3) {p∨[(¬qr)∧p]} → (p∨¬r)

4) [(p→¬q)∧q] → ¬p

5) [(pq)∧¬p] ↔ (¬pq)

6) [(pq)→r] → [p→(qr)]



1. Систематично използваме гръцките букви като обозначаващи произволни изрази. Съответно кавичките около изрази, в които участват гръцки букви, използваме за да изразят конкатенация, т.е. свързване на няколко израза в един чрез поставянето им един до друг, а не цитиране. Например „α∧β“ трябва да се разбира като „изразът, който се получава, когато след израза α (т.е. израза, който буквата „α“ обозначава) поставим знака за конюнкция, а след него поставим израза β“. (Ако кавичките се използваха за цитиране, „α∧β“ щеше да има значението на „изразът, който се получава, когато след първата буква от гръцката азбука поставим знака за конюнкция, а след него поставим втората буква от гръцката азбука“.) Съответно, когато някаква гръцка буква обозначава израз, който в дадения контекст не е част от друг израз, кавичките около нея в качеството им на знак за конкатенация се обезсмислят, поради което, когато са сами, около гръцките букви няма кавички. 2. Рекурсивните дефиниции имат този недостатък в сравнение с експлицитните (не-рекурсивните), че не дават израз, който е взаимнозаменяем с дефинирания. Например дефиницията на термина „човек“ посредством израза „разумно същество“ – като се абстрахираме от това, че е неясна и очевидно неправилна – е експлицитна дефиниция, защото ни дава възможност вместо „човек“ навсякъде да използваме „разумно същество“. Рекурсивните дефиниции не дават такъв взаимнозаменяем израз.