загрузка...
 
§ 10. Закони логіки, таблиці істинності та логічні сполучники
Повернутись до змісту
Пропозиційна функція — це вираз, що містить змінний символ х. Щоб такий вираз набув змісту, замість х треба підставити щось більш певне, наприклад: «Іван», «100», «зелене» тощо. Так, пропозиційною функцією може бути вираз «х вміє грати в покер». Якщо замість х підставити ім'я «Хома», то матимемо висловлення, сповнене цілком конкретним змістом (істинне чи ложне).
Крім заміни змінних символів на постійні, є ще один спосіб, за допомогою якого з пропозиційних функцій одержують висловлення. Розглянемо таку алгебраїчну формулу:
(х + у)2 = х2 + 2ху + у2.
Говорячи мовою логіки, це пропозиційна функція, що містить змінні х і у, які задовольняють довільні пари чисел. Таким чином, для всіх чисел, символічно позначених х і у, істинною буде вищенаведена формула.
Розглянемо пропозиційну функцію вигляду
х> у.
Якщо замість х підставити 10, а замість у — 9, то висловлення буде істинним. А якщо замість х підставити | 12, а замість у — 13, матимемо ложне висловлення. Отже, формулу х > у не може задовольняти будь-яка пара чисел, тому стосовно неї говорять так: «Для деяких чисел х і у вірно, що х > у», або: «Існують числа х і у такі, що х > у».
Вирази типу «для всіх х, у, ...» або «існують х, у, ... такі, що ...» називаються кванторами (лат. quantum — кількість; quantify — визначати кількість).
Квантори (логічні оператори) вказують на кількісну характеристику значень тієї чи іншої змінної, для якої відповідне висловлення істинне.
У даному випадку є два квантори — універсальний, або квантор загальності («для всіх х, у, ...»), та екзистенціальний, або квантор існування («існують х, у, ... такі, що ...»).
Висловлення, що містять змінні, — це загальна форма багатьох логічних висловлень, яку називають логічною формулою. Якщо підстановка якогось значення змінної в логічну формулу перетворює її на істинне висловлення, то говорять, що дане висловлення «істинне для всіх значень х». Позначається це так: V х, де V — символ квантора загальності. Цей символ є аналогом слова «всі» і являє собою перевернуту літеру А, що нагадує про німецьке слово «alle» або англійське «all» (усі).
Якщо лише деякі значення змінної перетворюють логічну формулу в істинне висловлення, то говорять, що висловлення «істинне для деяких значень х». Позначається це так: 3 х, де 3 — символ квантора існування. Цей символ є аналогом слова «існувати» і являє собою звернену в протилежний бік літеру Е, яка нагадує про німецьке слово «existieren» або англійське «to exist» (існувати).
Хоч у буденній мові змінні й квантори не використовуються, у природних мовах існують їхні еквіваленти. Наприклад, в українській мові близькими за своїми функціями до кванторів є слова «усі», «усякий», «будь-який», «ніякий», «деякий» тощо. Так, висловлення «Деякі люди хитрі» має приблизно той самий зміст, що й вираз «Існує х такий, що х є людиною і хитрою».
Завдяки кванторам пропозиційні функції автоматично перетворюються на висловлення, а змінні втрачають свою свободу, тобто стають зв'язаними. Там, де квантори відсутні, справу мають лише з пропозиційною функцією, а змінні називаються вільними, або незв'язаними.
Змінним і кванторам належить винятково важлива роль У формулюванні математичних теорем. Стосовно змінних також впевнено можна сказати: їх винайдення стало поворотним пунктом в історії математики й логіки.
У логіці висловлень розрізняють двозначну та многозначну логіку. Двозначна логіка оперує лише двома значеннями, які умовно іменують «істина» і «лож», або ж інакше: «біле — чорне», «гарне — потворне», «1 — 0», «0 — 1» тощо.
Слід пам'ятати, що в логіці священне для філософів слово «істина» вживається лише для умовного позначення логічної властивості «або істинне, або ложне» («або ввімкнено, або вимкнено», «або любити, або не любити» тощо). Якщо висловлення логічно істинне, воно має значення «істина» («так», «1» тощо). Якщо ж висловлення логічно ложне, воно має значення істинності «ложність». Хоч останнє речення звучить незвично, це своєрідна логічна термінологія. До речі, свого часу відомий німецький математик і логік Е. Шредер (1841— 1902), намагаючись уникнути сторонніх психологічних асоціацій, пов'язаних з уживанням слів «істина» і «ложність», запропонував використовувати нуль («0») для позначення ложного висловлення.
З позиції математичної логіки кожне ложне висловлення трактується не як помилкове відображення дійсності, а ототожнюється з порожньою множиною. Відповідно кожне істинне висловлення ототожнюється з непорожньою множиною елементів, чия фізична природа не береться до уваги.
У математичній логіці щодо змісту висловлень потрібні знання, визначені поняттями теорії множин, тобто знання про умовну істинність (непорожню множину) або ложність (порожню множину) цих висловлень.
Більшість істинних тверджень, що стосуються буденного життя, є відносно істинними. У логіці така «відносність» не прийнятна, оскільки перевага надається «абсолютним» істинам. «Істинне» і «ложне» логіки вживають у розумінні можливої логічної оцінки суджень (висловлень), що уявляються як носії певного смислового змісту, вміщеного у знакову форму, точніше, у форму висловлення. У логіці висловлень смисловий зміст висловлень жорстко обмежується тим, що називають істиннісним значенням, не вкладаючи в це поняття філософського смислу.
Замість «висловлення р істинне» або «висловлення q ложне» можна сказати: «висловлення р має істиннісне значення «істина» (або «висловлення р має істинне значення істинності»); «висловлення дмає істиннісне значення «ложність» (або «висловлення q має ложне значення істинності»). Для позначення істиннісного значення (значення істинності) «істина» вживають українську літеру «і» (або математичний символ «1»), а для істиннісного значення (значення істинності) «ложність» — літеру «л» (або математичний символ «0»).
Логіка висловлень вимагає, щоб для кожного висловлення виконувалася умова його істинності або ложності.
Щоб охопити загальною схемою всі різновиди простих одиничних висловлень (висловлень про одиничне), які вказують на окремі предмети за допомогою відповідних одиничних імен, вводиться форма F(x), де х - змінна для одиничного імені, a F — символічне позначення властивостей даного індивіда. Отже, F(x) — це функція висловлення (пропозиційна функція), яка включає змінну; в разі підстановки на її місце постійного значення одержують власне висловлення. Наприклад, якщо*— яблуко, a F — смачне, маємо висловлення типу «яблуко смачне».
Висловлення форми F(x) дає змогу виражати безліч конкретно значущих висловлень. Можливість стає дійсністю тоді, коли замість змінної х підставляються конкретні значення типу а, Ь, с, ..., у результаті чого маємо F(a), F{b), F(c) тощо. Наприклад, якщо по черзі підставляти у форму F(x) замість х імена різних людей, а замість F — їхні властивості, дістанемо відповідні висловлення природною мовою:
• Шерлок Холмс живе в Лондоні;
• Доктор Ватсон — друг відомого англійського детектива;
• Хома Брут — видатний київський філософ.
Кожну формулу логіки висловлень можна розглядати як зображення певної функції.
У логіці всі окремі малі літери (р, q, r, ...), які символізують змінні, а також їх комбінації, що являють собою форму висловлень, є булевими функціями висловлень.
Запис цих функцій називають формулою. Інакше кажучи, булевою функцією висловлень буде вираз, одержаний У результаті скінченного числа кроків, записаних у символах булевої алгебри висловлень.
Цей погляд на формули логіки висловлень узгоджується з законами елементарної алгебри. Різниця полягає лише в тому, що в елементарній алгебрі розглядаються числові функції, а в логіці висловлень — логічні (булеві), Де змінні й пропозиційні функції набувають лише одного 3 двох значень — «істина» («1») чи «ложність» («0»).
Булева функція висловлень виражає логічний закон тОЦі, коли вона набуває істинного значення за усіх можли-вих комбінацій значень змінних. Перевірку того, чи виражає дана функція логічний закон, здійснюють за допомогою так званих таблиць (матриць) істинності.
Табличний метод перевірки формул логіки висловлень звільняє дослідників від необхідності будувати аксіоматичні системи, в яких теореми обґрунтовуються шляхом виведення їх із системи аксіом.
Є ряд формул, які набувають значення «істина» за будь-яких значень істинності змінних, що входять до них. Ці формули називають тотожно істинними формулами, або тавтологіями числення висловлень. Крім того, такі формули є логічними законами.
Формули, які набувають значення «ложність» за всіх значень змінних, що входять до них, називають тотожно ложними. Тотожно ложні формули — це суперечності, або, інакше, суперечності — це формули логіки висловлень, які за будь-якого набору значень своїх пропози-ційних змінних набувають значення «ложність». Усі фор- і мули логіки висловлень, що не є суперечностями, вважа- І ють виконуваними.
Тотожно істинні й тотожно ложні формули являють і собою постійні б у л є в і функції, які набува- J ють тільки одного значення, оскільки воно не залежить від змінних, що входять до формули.
На відміну від тотожно істинних, виконуваних, тотож-1 но ложні формули невиконувані.
Для більш конструктивної характеристики виконува-ності можна сказати: виконуваними формулами є такі, яка хоча б за одного розподілу значень істинності пропозиційних змінних, що входять до них, набувають значення «істина». • Якщо цієї умови не дотримано, говорять, що формули! невиконувані, тобто ложні. Кожна виконувана множина формул несуперечна.
Спосіб, за яким щодо будь-якої формули можна визначити, до якого виду формул вона належить, називають розв'язувальною процедурою. Проблема вирішення полягає в тому, щоб відшукати такий спосіб. Для логіки висловлень ним є побудова таблиць істинності, а також перебудова досліджуваної формули в одну з так званих нормальних форм.
У зв'язку з посиланнями на табличний метод перевірки логічних формул наводимо більш детальну характеристику логічних сполучників.
Логічні сполучники найзручніше характеризувати за допомогою таблиць істинності, де міститься відповідь на запитання про те, коли складне висловлення істинне, а коли ложне.
Якщо, припустімо, просте висловлення істинне тоді й тільки тоді, коли воно стверджує існування певного факту, що дійсно має місце (наприклад: «Земля обертається навколо Сонця»), то відповідь на запитання про істинність складного висловлення потребує не лише врахування фактів, а й розгляду смислу логічної зв'язки, за допомогою якої це висловлення було утворене (наприклад: «Якщо Земля обертається навколо Сонця, то навколо Сонця обертається й Марс»). З урахуванням цього необхідно розглянути всі логічні зв'язки (сполучники), використання яких визначає назву складних висловлень.
У природній мові складне речення, складові частини якого з'єднано зворотом «якщо..., то...», називається складнопідрядним реченням з підрядним умовним, а в логіці — імплікацією (лат. implicatio — сплетення, переплетення), або умовним висловленням.
Частина висловлення, яка пов'язана зі словом «якщо», у логіці називається антецедент (попередній), друга частина, що починається зі слова «то», — консеквент (наступний).
Оскільки логіки прагнуть уникати провокаційних аналогій, двозначності й психологізму, вони пропонують розглядати імплікацію як цілком осмислене висловлення навіть тоді, коли не існує ніякого змістового зв'язку між двома простими висловленнями, що утворюють одне складне. Наприклад: «Якщо птахи восени швидко-швидко летять на південь, то Волга повільно-повільно впадає в Каспійське море». Тут, як і у випадку обертання планет навколо Сонця, граматичний зворот «якщо..., то...» провокує на «філософське» розв'язування позалогічних проблем (наприклад: «Чи залежить обертання Марса або Юпітера навколо Сонця від обертання Землі навколо Сонця?», «Чи залежить те, що Волга впадає в Каспійське море, від осіннього перельоту птахів?»). Іноді логіки вдаються до крайніх заходів і формулюють питання про імплікацію приблизно так: «Якщо 2 + 2 = 4, то чи живуть на Марсі кирпаті марсіани?» Можливі й інші неприйнятні для буденної свідомості приклади. Таким чином логіки хочуть підкреслити, що в логіці висловлень зміст висловлень не має ніякого значення (!). У зв'язку з цим розрізняють м а т ер і а л ь н у (н є с т р о г у) і формальну (строгу) імплікації. Перше поняття є ширшим, оскільки кожна істинна формальна імплікація є водночас істинною матеріальною імплікацією, але не навпаки.
Граматичний зворот «якщо..., то...» часто вживають у мові науки. Найбільш уживаний він у математиці: математичні теореми тяжіють за формою до імплікацій.
Логічну операцію імплікації звичайно позначають функтором —> (так у мові математичної логіки називають про-позиційну зв'язку). Символічне зображення імплікації, що і складається з двох простих висловлень р і q, буде таким: р —> q. У зв'язку з тим, що це логічне висловлення не І завжди збігається за змістом з виразом природної мови типу «якщо..., то...», його доцільно читати не як «якщо р, то q», а так: «р імплікує q» («p містить q»; «завжди, якщо р, то q»), і розуміти дану операцію лише під кутом зору відповідної таблиці істинності. Перш ніж розбиратися з ] таблицями істинності, зокрема з таблицею для імплікації, слід зрозуміти таке.
В умовиводах буденного життя і в науці користуються тільки такими імплікаціями, в яких попередній (антецедент) і наступний (консеквент) члени пов'язані за змістом і за формою. Наприклад: «Якщо йде дощ, то, виходячи на вулицю, бери парасольку»; «Якщо експеримент буде вдалим, то гіпотеза підтвердиться». Імплікації, в яких немає цього зв'язку, зазвичай не становлять для логіків інтересу, крім спеціалістів з психічних захворювань. Логіки ж, намагаючись прояснити логічні характеристики зв'язок (логічних сполучників), значно спрощують і відхиляються від змісту висловлень. А втім, вони не лінуються заглядати у зміст висловлень природної мови, особливо якщо йдеться про перші кроки у навчанні тонкому логічному мистецтву.
Розглянемо такий приклад: «Якщо пиво відпускається тільки членам профспілки, то решта громадян задовольняються квасом».
Припустімо, що все відбувається саме так, тоді імплікація істинна. Якщо ж пиво, всупереч розпорядженню, відпускається не лише членам профспілки, то висновок ложний. Однак за відсутності пива й квасу в продажу, коли всі з насолодою п'ють воду, взагалі немає жодних порушень розпорядження. Отже, розпорядження діє, хоч і не виконується через об'єктивні
Розглянутий приклад з імплікаціями демонструє один з можливих типів логічних зв'язків між висловленнями. Знання цих зв'язків потрібне, якщо для розв'язання різних теоретико-пізнавальних і науково-практичних задач прагнуть урізноманітнювати дослідницький інструмент.
Запропонована таблиця істинності є прикладом матеріальної імплікації, під якою зазвичай розуміють функтор -».
Оскільки матеріальна імплікація протиставляється формальній, то матеріальна імплікація трактується як умовне висловлення, а формальна — як умовна функція висловлення.
Відомо, що матеріальна імплікація істинна, якщо істинний її консеквент або ложний її антецедент, а також якщо вони ложні одночасно. Труднощі виникають тоді, коли читають функтор імплікації як «якщо..., то...». Це зумовлює різке розходження між логічними умовами істинності імплікації й фактичними умовами істинності змістовного умовного висловлення. Наприклад, з логічного погляду імплікація «якщо сніг білий, то 2 + 2 = 4» є істинною щодо таблиці істинності, а з буденного мислення така умовне висловлення звучить безглуздо. Адже якщо випаде чорний сніг, як наслідок нерозумної промислової діяльності людини, це не може впливати на закони математики таким чином, щоб 2 + 2 давало у сумі 5. Щоб уникнути подібних нісенітниць імплікації, відомий логік Кларенс Ірвінг Льюїс (1883— 1964) увів функтор так званої строгої] імплікації, який мав до певної міри відповідати ролі умов-j ного сполучника в буденній мові. Це можливо за додер-і жання двох умов. По-перше, слід оперувати не екстен-j сіональними, а інтенсіональними функціями висловлень.! Тоді істинність або ложність строгої імплікації залежатиме не лише від істинності чи ложності висловлень, що складають її, а також і від різниці їхнього змісту. По-друге, використовуючи інтенсіональний підхід до імплікації, слід відмовитися від двозначної логіки на користь многознач-ної.
Стосовно термінів «екстенсіонал» і «інтенсіонал» слід зазначити таке: числення висловлень у межах математичної логіки охоплює не всі способи побудови складних! висловлень, а лише так звані екстенсіональні зв'язки, тобто зв'язки, в яких логічне значення цілого залежить не] від різниці у змісті простих висловлень, а виключно від] їхнього логічного значення. Такі значення обчислюються за допомогою таблиць істинності, а не інтуїтивно схоплюються людським розумом. Подібні функції висловленьназивають істиннісними.
Крім екстенсіональних складних висловлень є ше; інтенсіональні складні висловлення. Сьогодні логіки активно обговорюють питання щодо можливості зводити] останніх до екстенсіональних. Дехто з вчених вважає, що 'зробити це неможливо, бо значення істинності інтенсіонального складного висловлення залежить не тільки від] значень істинності висловлень, які входять до його складу, а й від інших факторів, що не піддаються оцінці з екстен-] сіонального погляду.
Зауважимо, що імплікація Льюїса строга не своїми обмеженнями форми висловлень, а своїми уточненнями логічної ролі умовного сполучника «якщо..., то...», запозиченого з буденної мови.
Розглянемо характерну логічну операцію — операцію диз'юнкції (лат. disjunctio — роз'єднання, розділення), яку застосовують, зокрема, до єднально-роз'єднувальних висловлень.
Операція диз'юнкції позначається функтором v (від першої літери латинського слова «vel»), який має свій аналог у природній мові — сполучник «чи».
У природній мові речення із сполучником «чи» вказує на можливість двох подій, одна з яких цілком імовірна. Наприклад, «Остап Бендер поїде до Ріо-де-Жанейро мільйонером чи залишиться в Одесі кербудом». Іноді замість виразу «чи» вживається вираз «або» у тому самому розділовому значенні, що й слово «чи». У логіці ж виразові «або» надають дещо іншого значення.
Сполучник «чи» у багатьох європейських мовах має два різні значення — виключне і невиключне. Так, якщо існують два ложні висловлення р і q, то складне висловлення типу «р чи q» слід вважати ложним. Якщо р істинне, a q ложне, то «р чи q» слід розглядати як істинне висловлення, що цілком відповідає значенню слова «чи» в українській мові. Проблема виникає, коли обидва прості висловлення істинні. У зв'язку з цим у логічній літературі іноді трапляються формулювання типу «р чи/і q» та «р чи (також) q». Це означає, що складне диз'юнктивне висловлення буде істинним і тоді, коли обидва прості висловлення є одночасно істинними. Однак іноді здійснення однієї з можливостей виключає здійснення іншої. Тоді вживається формулювання вигляду «або р, або q». Подібне складне висловлення є строгою (сильною) розділовою Диз'юнкцією, функтор якої виражається символом v. Іноді говорять, що в даному випадку йдеться про виключно-Роз'єднувальне (розділове) висловлення, або виключну (сильну, строгу) диз'юнкцію.
Зовсім інший вигляд має таблиця істинності для виключної (сильної, строгої) диз'юнкції (табл. 3), з якої видно, що сильна диз'юнкція істинна тоді й тільки тоді, коли прості висловлення мають різні значення істинності.
Розглянемо операцію кон'юнкції, яку застосовують до j складних висловлень, що містять два й більше простих висловлень, з'єднаних зв'язкою, еквівалентною сполучникові «і» у природній мові. Ця логічна зв'язка позначається символом & (або л). Вираз р & q читається так: «р і <7» (табл. 4).
Сформулюємо таке твердження, яке виконується, наприклад, для подій, описаних простими висловленнями, що утворюють складне висловлення: «Васисуалій Лохан-кін постійно думав про значення російської інтелігенції й часто забував вимикати світло в комунальній вбиральні».
Логіки віддають перевагу виразові «невірно, що», оскільки саме так підкреслюється заперечення усього висловлення. Заперечивши істинне висловлення, логіки вказують на те, що одержане в результаті заперечення висловлення є ложним. Наприклад: «Невірно, що Арістотель — грецький філософ». Якщо ж висловлення ложне з самого початку, то його заперечення дає істинне висловлення. Наприклад: «Невірно, що Волга не впадає в Каспійське море». Або: «Невірно, що Волга впадає в Чорне море».
Функтор операції заперечення часто позначається символом ->.
За означенням, якщо р — будь-яке просте висловлення, то його заперечення -> р (не-р) буде складним висловленням, що підкреслюється зворотом «невірно, що».
Логічну операцію заперечення можна зобразити у вигляді таблиці істинності (табл. 5).
Висловлення, яке два або чотири рази (тобто парну кількість разів) заперечується, має те саме значення істинності, що й відповідне незаперечне, а те, яке заперечується непарну кількість разів, наприклад тричі, має те саме значення істинності, що й висловлення, яке заперечується один раз.
Операції заперечення (інверсії), кон'юнкції (логічного множення) і диз'юнкції (логічного додавання) називаються булевими операціями. їх застосовують в електроніці, автоматиці, теорії обчислювальних пристроїв тощо.
Ще однією важливою логічною операцією є операція еквіваленції (еквівалентності), функтор якої відповідає виразові «тоді й тільки тоді, коли» або «якщо й тільки якщо» і позначається символом <-».
Еквівалентність висловлень передбачає, що кожне з Двох простих висловлень є необхідною й достатньою умовою для іншого, тобто операція еквіваленції використовується, коли бажають виразити взаємну зумовленість простих висловлень, що належать до складного. Наприклад: «Великий комбінатор може знову заволодіти автомобілем Козлевича тоді й тільки тоді (якщо й тільки якщо), коли Доведе Козлевичу медичний факт відсутності Бога». У Даному випадку стверджується таке: якщо довести відсутбажаним автомобілем. Більш того, повернення автомобіля і його водія можливе лише за умови здійснення вказаного доведення.
Еквівалентність, що містить висловлення р і q, символічно зобразимо як р <эг^ q. Вибір символу <-> зумовлений тим, що операція еквіваленті' близька у певному розумінні до операції імплікації, яка позначається символом ->.
Схарактеризуємо за допомогою таблиці істинності операцію еквіваленції (табл. 6), попередньо скориставшись таким висловленням: «Пиво можна одержати тоді й тільки тоді, коли станеш членом профспілки».
Якщо будь-який любитель пива став членом профспілки, то очевидно, що висловлення щодо нього є істинним. Якщо ж І любитель пива не став членом профспілки й не одержав належну кінву пива, то жодної претензії до міських властей у нього бути не може. Якщо пропоноване пиво член профспілки не і випив через те, що воно йому не смакує, то знову ж таки ніяких претензій до вищих інстанцій бути не може.
Нарешті, якщо пиво випив нечлен профспілки, то твердження ложне. Очевидно, що висловлення також є ложним, якщо обіцяне пиво не випив його любитель, який є членом профспілки.
Таким чином видно, що еквівалентність двох простих висловлень істинна тільки тоді, коли обидва ці висловлення або одночасно істинні, або одночасно ложні. Коли ж одне з простих висловлень істинне, а інше — ложне, еквівалентність є ложною.
Звороти «тоді й тільки тоді, коли» і «якщо й тільки якщо» часто вживаються при формулюванні наукових означень, для чого в науці усталилися відповідні правила.
Дуже часто в застосуваннях логіки висловлень до електротехніки користуються формулами, що мають лише три символи логічних операцій, а саме: &, у, гхі Пояснюється це тим, що деякі логічні операції можна виразити за допомогою інших. Наприклад, операція еквіваленції виражається через імплікацію й кон'юнкцію, а імплікація і кон'юнкція — через заперечення й диз'юнкцію. Диз'юнкцію ж можна виразити за допомогою кон'юнкції й заперечення:
Те, що одні логічні формули можна виразити через інші, передбачає оцінку формул логіки висловлень на їх рівносильність. Дві формули логіки висловлень, що зображають одну й ту саму булеву функцію, вважаються рівносильними, якщо їхні значення істинності за будь-якого набору значень змінних, котрі входять до них, збігаються. Рівносильність формул записується так: -і-і р з р, де = — символ рівносильності.
Як уже стверджувалося, для логіки висловлень процедурою вирішення є не лише побудова таблиць істинності, а й перетворення досліджуваного виразу в так звану нормальну форму, за допомогою якої можна встановити, чи є Цей вираз загальнозначущим, чи ні; чи виконуваний він, чи ні.
Нормальна форма виразу, що досліджується, має задовольняти такі умови: 1) бути рівносильною вихідному виразові; 2) зі зв'язок логіки висловлень містити тільки символи заперечення, кон'юнкції й диз'юнкції; 3) символи заперечення мають стосуватися тільки пропозиційних змінних, а не складних виразів.
Зауважимо, що загальнозначущими вважають такі вирази логіки висловлень, які за кожного значення пронозиційних змінних, що трапляються в них, набувають значення «істина». Вирази у нормальній формі можуть містити тільки заперечення, кон'юнкцію та диз'юнкцію, а решта логічних констант має бути зведена до них.
Розглянемо перетворення імплікації в диз'юнкцію. Імплікація р —> q може бути перетворена в диз'юнкцію р v q, оскільки обидві вони мають однаковий порядок значень істинності (табл. 7).
Рівносильність формул логіки висловлень аналогічна тотожностям елементарної алгебри. Наприклад:
{х + у)2 = х2 + 2ху + у2.
У цьому випадку два різні за формою формульні вирази тотожно рівні, бо вони завжди набувають однакових числових значень, хоч би які числа підставлялися замість змінних л: і у.
Щоб з'ясувати, до якого класу виразів належить певний вираз логіки висловлень, його спочатку зводять до нормальної форми. Для цього у виразі -і (р v -> q) -?, -»(->/?& q) спочатку позбуваються імплікації, а потім — символів заперечення над дужками.
Діє загальне правило перетворення будь-якої імплікації 6 диз'юнкцію: імплікація перетворюється в диз'юнкцію з таким самим порядком значень істинності, якщо її антецедент заперечується, константа імплікації замінюється на константу диз'юнкції, а консеквент береться без змін. Наприклад:
Вираз логіки висловлень є загальнозначущим, якщо у кожній диз'юнкції його кон'юнктивної форми будь-яка пропозиційна змінна одного разу трапляється з запереченням, а іншого разу — без заперечення. Якщо цього немає хоча б в одній диз'юнкції, то вираз не буде загальнозначущим.



загрузка...