Тофтул Логіка (2002)
5. Логічний вивід і проблема розв'язання
Поняття логічного виводу
Термін «логічний вивід» використовується у широкому і вузькому значеннях. У широкому значенні поняття «логічний вивід» ототожнюється з поняттям умовиводу [69], до якого включають і власне вивід (логічний). Так, один з найновіших словників з логіки дає таке визначення: «Вивід логічний — міркування, в ході якого з яких-небудь суджень — засновків — з допомогою логічних правил одержують висновок — нове судження» [18]. Це визначення повністю збігається з визначенням умовиводу. Про це свідчить і приклад, яким ілюструється цитоване визначення: «Всі люди смертні. Кай — людина. Кай смертний».
Часте ототожнення виводу з умовиводом пояснюється їх подібністю. І умовивід, і логічний вивід є міркуваннями, будуються вони відповідно до певних логічних правил, містять засновки і висновки, дають змогу одержувати так зване вивідне знання. Проте між ними існує й істотна відмінність. Якщо умовивід — це справжнє, змістовне міркування, то логічний вивід нагадує своєрідну гру «...з символами, коли можна комбінувати символи у відповідності з правилами, з'єднувати їх, роз'єднувати тощо» [36]. Правила, відповідно до яких будується логічний вивід, є строго однозначно визначеними, що не завжди можна сказати про правила умовиводів. Засновками і висновком умовиводу є судження, виражені засобами природної мови, а засновками і висновком виводу є безструктурні, позначені символами прості висловлювання, формули і навіть схеми формул (до речі, висновок тут називається вивідною формулою). Назвати вивідну формулу знанням можна хіба що умовно, оскільки вона набуває смислу тільки після відповідної інтерпретації.
ВИВІД — послідовність висловлювань, формул або схем формул, яка утворюється з аксіом, засновків і теорем (раніше доведених формул), остання формула якої (послідовності) виведена з попередніх формул за правилами відповідної формально-логічної теорії.
Логічний вивід у логіці висловлювань є одним з видів числення. Оскільки кожна формальна система має власні аксіоми і правила виводу, то в кожній з них вивід носить специфічний характер. Особливо ефективними є виводи в системі логіки висловлювань, насамперед в системі натурального виводу. Процес міркування, одержання істинних висновків у них ґрунтується не на застосуванні конкретних за змістом засновків і навіть не на зв'язках між обсягами термінів у середині простих суджень (між суб'єктом і предикатом) та обсягами термінів різних простих суджень (як у силогізмі), а на характері логічних зв'язків між висловлюваннями, врахуванні лише логічного значення (істинності чи хибності) останніх та коректному застосуванні до них правил виводу.
Формалізувавши (в даному випадку — переклавши на мову логіки висловлювань) вихідні судження, суд-ження-засновки, можна алгоритмізувати процес виведення із засновків необхідного й істинного висновку, який, будучи перекладеним на природну мову, фігуруватиме як розв'язання відповідної задачі (про формалізацію див. на с 13 цього посібника).
Найважливішими характеристиками виводу логіки висловлювань є, по-перше, сумісність його засновків і висновку, їх несуперечливість, а по-друге, та обставина, що кожен закон («завжди істинне» висловлювання) в цій формальній системі піддається обґрунтуванню. 'Натуральним цей вивід називають тому, що він будується способом, близьким до того, яким ми звичайно користуємось у неформальних доведеннях.
Мова1 й основні правила виводу логіки висловлювань
Правило виводу — своєрідний трафарет, шаблон, припис, що визначає перехід від засновків до висновку-наслідку, вказуючи, яким чином висловлювання, істинність яких відома, можна видозмінювати, щоб одержати нові істинні висловлювання.
Пропонують і таке формулювання правил виводу: «Правила виводу — це способи логічного переходу від засновків до висновку, які задають правила введення і усунення логічних сполучників» [14].
Правило введення кон'юнкції (ВК):
А
А,АА0Л...АА
1 Z П
Згідно з цим правилом істинні висловлювання завжди можна з'єднувати знаком кон'юнкції. У найпростішому випадку це правило записується так:-— ,що
АлВ означає: якщо висловлювання А, В поодинці істинні,
то істинна і їх кон'юнкція — АлВ. Наприклад: Тарас Шевченко2 — геніальний поет (А). Тарас Шевченко — талановитий живописець (В).
Тарас Шевченко — геніальний поет і (він же) талановитий живописець (АлВ).
Одержаний висновок є істинним, чого не скажеш, наприклад, про складне висловлювання (кон'юнк-цію)«Тарас Шевченко — геніальний поет і живописець», оскільки ознака геніальності в цьому висловлюванні стосується Шевченка і як живописця.
Цей приклад не можна вважати типовим, оскільки суб'єктами простих суджень (кон'юнктів) далеко не завжди виступає одне й те ж поняття. Приклад, як правило, адресується буденній свідомості, здоровому глузду. Тому «типовіші» приклади, що ілюструють правила введення кон'юнкції, здадуться непереконливими для здорового глузду. Скажімо, «"Сім" — просте число, і Київ — столиця України» (АлВ).
Правило усунення кон'юнкції (УК):
А,/А9л...лА
А>
Це правило дозволяє з кон'юнкції висловлювань виводити будь-яке висловлювання, що є її кон'юнк-том.
Наприклад:
У скоєнні цього злочину брали участь А і В (АлВ). У скоєнні цього злочину брав участь А(А).
Правило введення диз'юнкції (ВД): A,vA,v...vA
12 п
Це правило дозволяє до істинного висловлювання приєднувати з допомогою диз'юнкції (нестрогої) інші висловлення. Оскільки ж нестрога диз'юнкція є істинною за умови істинності принаймні одного диз'юнкта, то звідси випливає висновок, що логічне значення приєднуваних диз'юнктів не впливає на утворену диз'юнкцію: вона завжди буде істинною.
Наприклад:
О. Пушкін — геніальний поет.
0. Пушкін — геніальний поет або живописець.
Правила усунення диз'юнкції (УД)
1. Правило усунення строгої диз'юнкції:
A,vA,v...vA
1— 2— — п
A,v...vA А,
Усунення строгої диз'юнкції з двома диз'юнктами здійснюється так:
АуВ ■ АуВ АуВ АуВ
А . В . А . В
В ' А В ' А
2. Правило усунення нестрогої диз'юнкції:
A,vA.v...vA„ A,vA„v...vA
12 п 12 п
А9Л...ЛА„ A,v...vA
А, > А,
Логічний вивід і проблема розв'язання
Усунення нестрого! диз'юнкції з двома диз'юнктами здійснюється так:
AvB AvB А . В
В ' А
У традиційній логіці правило усунення диз'юнкції відповідає схемі розділово-категоричного умовиводу (див. с 195).
Правило введення імплікації (ВІ):
А В-+А
Згідно з таблицею істинності імплікації за умови істинності консеквента вона завжди є істинною. Дати переконливу змістовну інтерпретацію цього правила, мабуть, неможливо.
Правило дедукції є одним із різновидів введення імплікації:
Г, АУ-В Г\-(А->В) '
Читається це правило так: «Якщо з гамми засновків Г і формули А можна вивести формулу В, то із засновків Г випливає формула А-+В.
Правило усунення імплікації (УІ):
А-+В А->В
А В~
1. (Modus ponens); 2. —=—(Modus tollens).
Це правило дозволяє за наявності істинного антецедента виводити відповідний консеквент, а за наявності заперечення консеквента — переходити до заперечення антецедента.
Правило введення еквіваленції (BE): А->В В-+А АВ '
Імплікація А-+В означає, що А є достатньою, але не необхідною підставою стосовно В, а В є необхідною, проте недостатньою умовою істинності А. Аналогічно можна охарактеризувати й імплікацію В->А, орієнтуючись на її складові (антецедент і консеквент), а не на буквене їх позначення. За умови істинності А—>В і В—> —>А з цих даних можна вивести еквіваленцію АВ, в якій виражається взаємна необхідність і достатність А і В.
Наприклад:
Якщо трикутник рівносторонній, то він рівнокутний (А->Б).
Якщо трикутник рівнокутний, то він рівносторон-
ній (В—>А).
Трикутник є рівностороннім тоді і тільки тоді, коли він рівнокутний (АВ).
Правило усунення еквіваленції (УЕ):
1 АВ
А . В . А . В .
В А В~ А
Про правильність перелічених висновків свідчить таблиця істинності еквіваленції, згідно з якою логічне значення її правої і лівої частин збігається: іі; х--х.
Існують й інші правила виводу, котрі часто виділяють в окрему групу: «...в логіці висловлювань існують також правила перетворення суджень, які задаються відповідними рівносильностями (їх ще називають правилами еквівалентної заміни). Знак «=», що з'єднує дві частини кожної формули, які наводяться нижче, означає логічну тотожність цих частин за будь-яких значень пропозиційних змінних (що можна перевірити, склавши для них таблиці істинності). Ці рівносильності служать алгоритмами правомірної трансформації структури логічних виразів, а також правилами переходу до виразів з іншими логічними сполучниками» [15].
Поняття «рівносильність» (=) тотожне поняттю «еквівалентність» (В) = (AvB): «Якщо цей предмет металевий, то він електропровідний» і «Цей предмет не є металевим або він електропровідний».
Приклад рівносильності 14— (АлВ) = (AvB ):«Рошб
має рівні і попарно паралельні сторони» і «Хибно, що
в ромба сторони не є рівними або не попарно паралель
ними». _ _
Приклад рівносильності 15 — (AvB) = (АлВ): «Цей кут є прямим або тупим» і «Хибно, що цей кут не є ні прямим, ні тупим».
Рівносильність 18 — (AvB)л(AvB) = В — називається законом виключення; рівносильності 19 і 20 — Ал(АВ) = А; Av(AлB) =А — законами поглинання; рівносильності 21 і 22_— (А\?)л(В\?)=_(А\?)л(В\? v(AvB); (AAC)V (ВЛС) = (АлС (BлC)v(AлB) — законами виявлення.
Рівносильності 23—27 є похідними від перерахованих рівносильностей 1—22.
Вдаючись до рівносильностей 1—27 і правил заміни, виводять рівносильності 28—34.
Особливе місце належить у системі виводу рівносильним формулам, до складу яких входять «завжди істинні» або «завжди хибні» підформули. Зрозуміло, що всі «завжди істинні» формули рівносильні одна одній. Це стосується і «завжди хибних» формул: вони теж рівносильні між собою. Згідно з таблицею істинності заперечення, заперечення «завжди істинної» формули є «завжди хибною» формулою, і навпаки. Так, оскільки формула А \/ІГ« завжди істинна», то формула AvA є «завжди хибною» (або: оскільки формула АлА «завжди хибна», то її заперечення АлА є «завжди істинною» формулою).
Позначивши буквою «і» «завжди істинну» формулу, а буквою «х» «завжди хибну», одержують рівно-сильності 43—50'.
Логічний вивід будується на таких засадах. На будь-якому кроці побудови виводу можна дописати до послідовності формул:
1) будь-яку частину наявної формули (підформулу) або її заперечення як припущення;
2) формулу, що випливає із записаних вище формул послідовності за одним із правил логічного виводу або рівносильну якійсь із записаних вище;
3) раніше доведену формулу.
Якщо засновки є повними, тобто достатніми для одержання однозначного висновку, і несу переч ливими, то одне із суперечних припущень призведе до суперечності (що дає підставу вважати його неспроможним), а друге — до несуперечливого шуканого висновку. Якщо ж засновки суперечливі, то в обох випадках ми прийдемо до суперечності, що буде достатньою підставою для того, щоб вважати хибними принаймні деякі засновки. І, нарешті, коли засновки є несуперечливи-ми, але неповними, то з обох суперечних припущень будуть випливати різні висновки, які разом з тим не ведуть до суперечливості сам вивід.
Розглянемо названі ситуації на прикладах.
Дано чотири засновки, з яких потрібно вивести висновок:
1. А-В.
2V C->A.
3. АуС.
4. АВ.
Перший хід міркування:
5. А (припущення).
6. В (усунення імплікації: 1; 5).
7. С (усунення строгої диз'юнкції: 3; 5).
8. В (усунення еквіваленції: 4; 5) — суперечність: 6; 8.
9. А (усунення імплікації 1; 8) — суперечність: 5; 9. 10. АлВлСлВлА (введення кон'юнкції: 5; 6; 7; 8; 9).
Другий хід міркування:
5. А (припущення).
6. С (усунення імплікації: 2; 5).
7. С (усунення строгої диз'юнкції: 3; 5) — супереч-ність: 6; 7.
8. Б (усунення еквіваленції: 4; 5).
9. АлСлСлВ (введення кон'юнкції: 5; 6; 7; 8).
Як бачимо, з обох суперечних припущень одержані суперечливі наслідки, що свідчить про суперечність засновків.
Розглянемо іншу ситуацію. Дано чотири засновки, з яких потрібно зробити висновок:
1. А-С.
2. AvB.
3. С-В.
4. CvA.
Перший хід міркування:
5. А (припущення).
6. С (усунення імплікації: 1; 5).
7. В (усунення строгої диз'юнкції: 2; 5).
8. С (усунення імплікації: 3; 7).
9. А (усунення нестрогої диз'юнкції: 4; 8).
10. АлСлВлСлА (введення кон'юнкції: 5; 6; 7; 8; 9). Другий хід міркування:
5. А (припущення).
6. В (усунення строгої диз'юнкції: 2; 5).
7. С (усунення нестрогої диз'юнкції: 4; 5).
8. А (усунення імплікації: 1; 7).
9. В (усунення імплікації: 3; 7).
Ю. АлВлСлАлВ (введення кон'юнкції).
Оскільки жодне із суперечних припущень не призвело до суперечності міркування, то звідси випливає висновок: засновки потребують доповнення.
До припущень вдаються не завжди, а лише тоді, коли без них не можна зробити черговий крок логічного виводу (іноді припущення дає можливість скоротити шлях розв'язання задачі). Якщо нам дано засновки:
1. А->В.
2. CvA.
3. B->D.
4. CAD,
то немає потреби вдаватися до припущення, оскільки четвертий засновок містить пряму інформацію про С і D.
5. Q (усунення кон'юнкції: 4);
6. j=) (усунення кон'юнкції: 4);
7. А (усунення нестрогої диз'юнкції: 2; 5);
8. В (усунення імплікації: 3; 6);
9. В (усунення імплікації: 1; 7);
10. CADAAABAB (введення кон'юнкції: 5; 6; 7; 8; 9).
11. CADAAABAB (усунення подвійного заперечен
ня — УПЗ).
12. CADAAAB (згідно із законом ідемпотентності).
А якщо без припущення не можна обійтися, то яку
ж змінну треба вибирати як припущення? Ту, з якої можна вивести якомога більше наслідків. Так, маючи засновки
1. С-*А.
2. В->С-
3. AvB,
з яких потрібно зробити висновки, ми змушені брати за припущення С, оскільки саме воно дає можливість вивести найбільше висновків. Інші припущення тут неефективні: припущення В дає можливість одержати лише один висновок —С , а припущення А — жодного:
4. С (припущення).
5. А (усунення імплікації: 1; 5).
6. S (усунення імплікації: 2; 5).
7. А (усунення нестрогої диз'юнкції: 3; 6).
Щоб застосувати теорію логічного виводу у розв'язанні практичних задач, потрібно послідовно здійснити кілька операцій. Наприклад, у нас є такі дані:
Коло підозрюваних у скоєнні злочину обмежується чотирма особами: Івановим, Петровим, Сидоровим, Федотовим.
1. Іванов міг брати участь у скоєнні злочину тоді і тільки тоді, коли до цього злочину причетний і Петров.
2. Якщо до цього злочину не причетний Сидоров, то в ньому брав участь Федотов.
3. Відомо, що один і тільки один із підозрюваних Іванов або Сидоров — причетні до цього злочину.
4. Федотов довів своє алібі.
Насамперед потрібно виділити прості судження з цього тексту і позначити їх пропозиційними змінними. Ось ці судження:
1. Іванов брав участь у скоєнні злочину (А).
2. Петров брав участь у скоєнні злочину (В).
3. Сидоров брав участь у скоєнні злочину (С).
4. Федотов брав участь у скоєнні злочину (£>). Після цього слід виділити логічні зв'язки, які є в
цьому тексті (і відповідно їх розставити): , у.
Поєднавши пропозиційні змінні (А, В, С, D) відповідними логічними термінами (зв'язками), одержимо такі висловлювання:
1. АВ.
2. С->£».
3. АуС;
4. D
Оскільки в нас є пряма інформація про алібі Федотова — D, то немає потреби вдаватися до припущення. Далі вивід будуємо так:
5. С (усунення імплікації: 2; 4).
6. А (усунення строгої диз'юнкції: 3; 5).
7. В (усунення еквіваленції: 1; 6).
8. БлСлАлВ (введення кон'юнкції: 4; 5; 6; 7). Залишається лише зробити переклад одержаного
висновку на природну мову: «Ні Федотов, ні Іванов, ні Петров не причетні до скоєння злочину. Злочин скоїв Сидоров».
Проблема розв'язання і розв'язуючі процедури
Оскільки висновок виводу (останнє у відповідній послідовності, вивідне висловлювання) не завжди з необхідністю випливає із засновків, то доводиться вдаватися до різних процедур, щоб довести, що логічне слідування справді має місце в тому чи іншому виводі. Так, щоб довести, що проголошена нами формула В (теза) є справді істинною, треба підібрати такі фор-мули-аргументи А1лА2л...лАп, з яких за відповідною процедурою можна вивести формулу, що збігається з проголошеною (з тезою), проте на відміну від останньої є достовірною.
Для позначення логічного слідування в логіці застосовують знак «І— » (або« f=»). Вираз «А\—В» читається так: «з А логічно випливає В».
Із формули А випливає формула В тоді, коли імплікація «А—їВ» є законом логіки («завжди істинною» формулою). Ось чому (і не тільки тому) знаходження процедури, що дає змогу визначити, до якого класу формул логіки висловлювань («завжди істинних», «завжди хибних» чи виконуваних) належить будь-яка формула, є винятково важливою проблемою логіки висловлювань.
Побудова відповідних таблиць істинності є ефективною лише за умови, коли до розглядуваних формул входить невелике число змінних. В іншому разі вона буде громіздкою, оскільки кількість рядків у таблиці стрімко зростає із збільшенням числа змінних, які входять до формули. Так, якщо формула містить три пропозиційні змінні, то рядків у таблиці буде 8, чотири — 16, п'ять — 32, десять — 1024. До того ж існують інші, менш громіздкі, зручніші процедури, з допомогою яких розв'язуються ці задачі. Йдеться про зведення формул до нормальної форми.
Нормальні форми формул логіки висловлювань
Формула логіки висловлювань має нормальну форму, якщо вона, по-перше, не містить у собі знаків -», , у, а по-друге, знаки заперечення стоять у ній лише при змінних.
Будь-яку формулу, що не має нормальної форми, можна скінченним числом застосувань правил заміни перетворити у формулу, яка має нормальну форму. Ця процедура називається процесом зведення формули до нормальної форми.
Щоб звести формулу до нормальної форми, необхідно зробити в ній такі рівносильні заміни:
1) кожну підформулу типу (А—>В) замінити згідно з рівносильністю 13 формулою (AvB);
2) кожну підформулу типу (АВ) замінити згідно з рівносильністю 16 формулою (AVB)A(BVA);
3) кожну підформулу типу (AvB) замінити згідно з рівносильністю 17 формулою (АУВ)Л(АУВ);
4) кожну підформулу типу (АлВ) замінити згідно з рівносильністю 10 формулою (AvB);
5) кожну підформулу типу (AvB) замінити згідно з рівносильністю 11 формулою (АлВ);
6) кожну підформулу типуіГ замінити згідно з рівносильністю 1 формулою А.
Якщо ж перелічені процедури не можна застосувати до формули, то вона вже має нормальну форму.
Наприклад, дано формулу (pq), яку треба звести до нормальної форми. Згідно з рівносильністю 16 одержимо формулу(p~vq)л(qvp). 3 цієї формули згідно з рівносильністю 10 одержимо формулу(pvq)v(qvp), де підформулі (pvq) відповідає підформула рівносильності А , виражена засобами метамови, а підформулі (FVQ) — В. Вдавшись до рівносильності 11 і застосувавши її до кожного з диз'юнктів одержаної формули, дістанемо формулу (pAq~)v(c[Ap). І нарешті згідно з рівносильністю 1 одержимо формулу (pAq)v(q~Xp).
До нормальних форм формул логіки висловлювань належать передусім кон'юнктивна нормальна форма (КНФ) і диз'юнктивна нормальна форма (ДНФ). Причому кожна з них має свій специфічний спосіб утворення (зведення) і дає змогу розв'язувати відповідні задачі.
Проблема розв'язання
Є три класи формул логіки висловлювань («завжди істинні», «завжди хибні» і невизначені, або виконувані). Завдання, що полягає у відшуканні процедури, котра дає змогу визначити, до якого з перелічених класів належить будь-яка формула, називається семантичною проблемою розв'язання для формул логіки висловлювань. А процедура, що дає змогу скінченним числом простих дій вирішувати проблему розв'язання, називається розв'язуючою процедурою.
Для того щоб одержати розв'язуючу процедуру, достатньо знайти спосіб відрізняти «завжди істинні» Формули від усіх інших. Якщо в результаті застосування такої процедури до формули А виявиться, що вона «завжди істинна», то проблема розв'язання вирішена. Коли ж ця формула виявиться не «завжди істинною», то цю процедуру треба застосувати до фор-мулиА Якщо буде встановлено, що ця формула є «завжди істинною», то звідси випливає висновок: формула А є «завжди хибною». Коли ж буде встановлено, що і формула А не є «завжди істинною», то це свідчить, що формула А є виконуваною, тобто при одних логічних значеннях змінних вона є істинною, а при інших — хибною.
Існує формальна процедура, з допомогою якої, не вдаючись до побудови відповідних таблиць істинності, можна визначати, до якого класу належить будь-яка формула логіки висловлювань — до «завжди істинних», «завжди хибних» чи виконуваних.
Пропозиційна змінна входить до складу формули, зведеної до нормальної форми, регулярно, якщо вона (змінна) входить до складу цієї форми одночасно як із запереченням, так і без заперечення. Якщо ж змінна входить до складу формули, зведеної до нормальної форми, тільки із запереченням або тільки без заперечення, то вона входить до складу формули нерегулярно.
Розв'язуюча процедура передбачає такі дії:
1) зведення формули до нормальної форми;
2) у зведеній до нормальної форми формулі виділення змінних, які входять до неї нерегулярно;
3) замість усіх змінних і заперечень змінних, які входять до формули нерегулярно, слід підставити на всіх місцях, де вони трапляються в нормальній формі, букву х (тобто логічне значення «хиба»);
4) застосування правил заміни згідно з рівносиль-ностями 48, 48', 50 і 50' до всіх підформул одержуваної формули, доки є приводи для його застосування. В результаті такої процедури довжина формули буде скорочуватись, і можуть з'явитися нові змінні, що нерегулярно входять до формули. З ними чинять аналогічно, тобто згідно з пунктами 3 і 4. Передбачувані в пунктах 2—4 перетворення слід повторювати, доки не одержимо формулу, яка не містить у собі змінних, що входять до неї нерегулярно;
5) розгляд наступних двох формул, одержаних з формули, яка не містить змінних, що входять до неї нерегулярно, якщо:
а) замість однієї змінної, яка регулярно входить до формули, в усіх місцях слід підставити і (логічне значення ■— «істина») і застосовувати правило рівносильної заміни згідно з рівносильностями 43, 47—50;
б) замість тієї ж змінної на всіх місцях підставити букву х (логічне значення — «хиба») і застосовувати правило рівносильної заміни згідно з рівносильностями 44, 47—50.
До формул а і б, якщо це можливо, знову застосовують пункти 2—4, а потім, згідно з пунктом 5, з формул а і б одержують відповідно формули аа, аб, ба і бб тощо, доки не вичерпані можливості застосування пунктів 2—5.
Якщо в результаті застосування цієї процедури до будь-якої формули А всі заключні формули набудуть значення і («істина»), то формула А є «завжди істинною», а якщо хоча б одна заключна формула набуде значення х («хиба»), то формула А не є «завжди істинною»
Кон'юнктивна нормальна форма
Кон'юнктивна нормальна форма формул логіки висловлювань є кон'юнкцією елементарних диз'юнкцій.
Елементарною диз'юнкцією є формула, що має такий вигляд: A1vA2v...vAn, де п>1, а кожна з формул Ар А2, ..А є змінною або запереченням змінної. Так, формула (pvqvrvs) є елементарною диз'юнкцією, чого не можна сказати про формулу (pvqv(pAr)vs), оскільки третій її диз'юнкт (рлг) не є ні змінною, ні запереченням змінної.
Елементарна диз'юнкція є «завжди істинною» тоді і лише тоді, коли в ній міститься принаймні одна пара диз'юнктів, з яких один є якоюсь змінною, а другий — її запереченням. У цьому неважко переконатися, побудувавши відповідну таблицю істинності: пара названих диз'юнктів забезпечить наявність «і» (істина) в кожному рядку цієї таблиці, що є достатньою підставою для визнання подібної Диз'юнкції «завжди істинною» формулою, тобто законом логіки.
Формула логіки висловлювань має кон'юнктивну нормальну форму тоді, коли вона має такий вигляд: В,лВгл...лВт, де Вг В2,...Вп_ — елементарні диз'юнкції і
т>1. Так, формула pA(qvr)A(qvp) має кон'юнктивну нормальну форму (кон'юнкт р слід розглядати як вироджену диз'юнкцію з одним диз'юнктом).
Будь-яку формулу логіки висловлювань з допомогою ряду рівносильних замін можна звести до кон'юнктивної нормальної форми. Формулу, що є рівносильною даній і має кон'юнктивну нормальну форму, називають кон'юнктивною нормальною формою даної формули.
Щоб звести формулу до кон'юнктивної нормальної форми, треба насамперед з допомогою відповідної процедури звести її до нормальної форми. А потім кожну підформулу, що має вигляд (pv(qAr)) згідно з рівно-сильністю 6 і кожну підформулу типу ((qA.r)vp) згідно з рівносильністю 6' замінити формулою ((pvq)A A(pvr)). Річ у тім, що формула має кон'юнктивну нормальну форму лише за умови, що вона, по-перше, має нормальну форму, а по-друге, не містить у собі під-формул типу (pv(qAr)) і ((qAr)vp).
Розглянемо зведення формули до кон'юнктивної нормальної форми на такому прикладі: (р—хі)—>(р~А~г).
1. Застосувавши до цієї формули правило усунення імплікації (при цьому підформулу (р—щ) будемо розглядати як антецедент (А), а підформулу (рХг) — як консеквент (В) імплікації А—>В, одержимо: (p-q)v v(pAq).
2. Застосувавши правило усунення імплікації, яка є в першому диз'юнкті цієї формули (при цьому як антецедент виступає р, а як консеквент — q), одержимо:
(pVq)v(pAT).
3. Вдавшись до рівносильності 11 (другого закону де Моргана) і зробивши відповідну заміну першого диз'юнкта цієї формули, одержимо: (p=Aq~)v(pAr).
4. Застосувавши рівносильність 10 (перший закон де Моргана) до другого диз'юнкта формули, одержимо: (p=Aq~)v(pvr).
5. Звернувшись до першої рівносильності, правила усунення подвійного заперечення, одержимо: (pAq)v(pvr).
6. Остання заміна згідно з рівносильністю 6' ((BAC)VA): (pvpvT)A(qvpvr).
Далеко не всі формули мають лише одну кон'юнктивну нормальну форму.
Формула логіки висловлювань в КНФ є «завжди істинною» тоді, коли кожен її кон'юнкт, тобто кожна елементарна диз'юнкція, містить у собі принаймні одну змінну одночасно зі знаком заперечення і без нього. В тому, що формула, зведена до КНФ, є «завжди істинною», можна переконатися за її зовнішнім виглядом. Так, оскільки кожен кон'юнкт формули (pvqvp)A(pvqvq~)A(pvrvqvr) містить змінну зі знаком заперечення і без нього, то вона є «завжди істинною».
З допомогою КНФ визначають, є дана формула «завжди істинною» чи ні, а також чи є формула В логічним наслідком із формул Ар А2,..Лп.
Щоб перевірити, чи є довільна формула В наслідком із формул А[ГА2, ~Ап, треба приєднати В через імплікацію до формул Аг А2, ~Ап, і одержаний вираз звести до КНФ. Якщо одержана КНФ буде «завжди істинною», то це засвідчить, що В випливає з_А;, А,..., Ап.
Перевіримо, чи випливає В з формул В —>А, А як засновків. Поєднаємо ці засновки кон'юнкцією і приєднаємо до них В з допомогою імплікації: ((В—>А)лА)—>В.
Одержану формулу зведемо до КНФ:
1. Застосувавши рівносильність 13, одержимо ((B->A)AA)VB.
2. Вдавшись до рівносильності 10, одержимо ((BA)vA)vB.
3. Використавши рівносильність 13, одержимо ((BvA)vA)vB.
4. Застосувавши рівносильність 10, одержимо ((BAA)VA)VB.
5 Вдавшись до рівносильності 6', одержимо ((AVB)A(AVA))VB.
6. Застосувавши першу рівносильність, одержимо ((AVB)A(AVA))VB.
7. Усунувши JCOH'IOHKT, ЯКИЙ містить змінну та її заперечення (AvA), одержимо AvBvB. Оскільки ця формула є елементарною диз'юнкцією, яка містить змінну (В) і її заперечення (В), то це означає, що вихідна формула є «завжди істинною». Тому формула В є наслідком із формул В—*А і А.
Розрізняють ще досконалу кон'юнктивну нормальну форму (ДКНФ) і скорочену кон'юнктивну нормальну форму (СДНФ), з допомогою яких розв'язують задачі на знаходження всіх логічних наслідків з даної формули.
Диз'юнктивна нормальна форма
Диз'юнктивна нормальна форма формул логіки висловлювань є диз'юнкцією елементарних кон'юнкцій.
Елементарною кон'юнкцією є формула, що має такий вигляд: А1лА2л...лА , де п>1, а кожна з формул Ар А2, ..., Ап є змінною, або запереченням змінної. Так, формула (рлс[лглд) є елементарною кон'юнкцією, чого не можна сказати про формулу (дл(дуг)лрлг), оскільки другий її кон'юнкт не є ні змінною, ні запереченням змінної.
Елементарна кон'юнкція є «завжди хибною» тоді й тільки тоді, коли до її складу входить принаймні одна пара кон'юнктів, з яких один є якоюсь змінною, а другий — її запереченням.
Формула логіки висловлювань має диз'юнктивну нормальну форму тоді, коли вона має такий вигляд: В vB2v...vBm, де Вр В2..„ Вт є елементарними кон'юнк-щями, а т>1. Наприклад: (pXqAr)vp~v(qAr).
Будь-яку формулу логіки висловлювань з допомогою відповідних рівносильних замін можна звести до диз'юнктивної нормальної форми. Формулу, що є рівносильною даній і має диз'юнктивну нормальну форму, називають диз'юнктивною нормальною формулою даної формули. Щоб звести формулу до ДНФ, необхідно насамперед звести її до нормальної форми, а потім кожну під-формулу типу (AA(BVCJ) згідно з рівносильністю 7 і кожну підформулу типу ((BVC)AA) згідно з рівносильністю Т замінити формулою ((AAB)V(AAC)).
Розглянемо процедуру зведення формули до диз'юнктивної нормальної форми на такому прикладі:
1. Застосувавши до цієї формули правило усунення імплікації (при цьому підформулу р будемо розглядати як антецедент, а підформулу ((p—>q)—>q) — як кон-секвент), одержимо: pv((p—>q)—>q).
2. Знову вдавшись до правила усунення імплікації (на цей раз роль антецедента виконує підформула (р—щ), а консеквента — q, одержимо: pv((p—>q)vq)-
3. Застосувавши правило усунення імплікації (антецедент — р, а консеквент — q), одержимо: pv((pq)vq).
4. Використавши другий закон де Моргана, одержимо: pv((pAq)vq).
5. Залишається лише усунути подвійне заперечення і зайві дужки: p~v(pAq)vq.
Формула може мати не одну ДНФ.
З допомогою ДНФ з'ясовують, по-перше, є дана формула «завжди хибною» чи ні, а по-друге, чи є та чи інша формула наслідком з відповідних засновків.
Формула, що має ДНФ, є «завжди хибною» тоді й тільки тоді, коли «завжди хибними» є всі її диз'юнкти, тобто коли кожна елементарна кон'юнкція містить у собі принаймні одну пару кон'юнктів, один з яких є якоюсь змінною, а другий — її запереченням. Таким чином, за виглядом елементарної кон'юнкції можна робити висновок, є вона «завжди хибною» чи ні. Так, формула ((pAqAp)v(qAq)v(pAqArAr)) є «завжди хибною», оскільки загалом вона є диз'юнкцією, кожен диз'юнкт якої (елементарна кон'юнкція) є «завжди хибним».
Розрізняють ще досконалу диз'юнктивну нормальну форму (ДДНФ) і скорочену диз'юнктивну нормальну форму (СДНФ), кожна з яких дає змогу розв'язувати відповідні задачі.
Термін «логічний вивід» використовується у широкому і вузькому значеннях. У широкому значенні поняття «логічний вивід» ототожнюється з поняттям умовиводу [69], до якого включають і власне вивід (логічний). Так, один з найновіших словників з логіки дає таке визначення: «Вивід логічний — міркування, в ході якого з яких-небудь суджень — засновків — з допомогою логічних правил одержують висновок — нове судження» [18]. Це визначення повністю збігається з визначенням умовиводу. Про це свідчить і приклад, яким ілюструється цитоване визначення: «Всі люди смертні. Кай — людина. Кай смертний».
Часте ототожнення виводу з умовиводом пояснюється їх подібністю. І умовивід, і логічний вивід є міркуваннями, будуються вони відповідно до певних логічних правил, містять засновки і висновки, дають змогу одержувати так зване вивідне знання. Проте між ними існує й істотна відмінність. Якщо умовивід — це справжнє, змістовне міркування, то логічний вивід нагадує своєрідну гру «...з символами, коли можна комбінувати символи у відповідності з правилами, з'єднувати їх, роз'єднувати тощо» [36]. Правила, відповідно до яких будується логічний вивід, є строго однозначно визначеними, що не завжди можна сказати про правила умовиводів. Засновками і висновком умовиводу є судження, виражені засобами природної мови, а засновками і висновком виводу є безструктурні, позначені символами прості висловлювання, формули і навіть схеми формул (до речі, висновок тут називається вивідною формулою). Назвати вивідну формулу знанням можна хіба що умовно, оскільки вона набуває смислу тільки після відповідної інтерпретації.
ВИВІД — послідовність висловлювань, формул або схем формул, яка утворюється з аксіом, засновків і теорем (раніше доведених формул), остання формула якої (послідовності) виведена з попередніх формул за правилами відповідної формально-логічної теорії.
Логічний вивід у логіці висловлювань є одним з видів числення. Оскільки кожна формальна система має власні аксіоми і правила виводу, то в кожній з них вивід носить специфічний характер. Особливо ефективними є виводи в системі логіки висловлювань, насамперед в системі натурального виводу. Процес міркування, одержання істинних висновків у них ґрунтується не на застосуванні конкретних за змістом засновків і навіть не на зв'язках між обсягами термінів у середині простих суджень (між суб'єктом і предикатом) та обсягами термінів різних простих суджень (як у силогізмі), а на характері логічних зв'язків між висловлюваннями, врахуванні лише логічного значення (істинності чи хибності) останніх та коректному застосуванні до них правил виводу.
Формалізувавши (в даному випадку — переклавши на мову логіки висловлювань) вихідні судження, суд-ження-засновки, можна алгоритмізувати процес виведення із засновків необхідного й істинного висновку, який, будучи перекладеним на природну мову, фігуруватиме як розв'язання відповідної задачі (про формалізацію див. на с 13 цього посібника).
Найважливішими характеристиками виводу логіки висловлювань є, по-перше, сумісність його засновків і висновку, їх несуперечливість, а по-друге, та обставина, що кожен закон («завжди істинне» висловлювання) в цій формальній системі піддається обґрунтуванню. 'Натуральним цей вивід називають тому, що він будується способом, близьким до того, яким ми звичайно користуємось у неформальних доведеннях.
Мова1 й основні правила виводу логіки висловлювань
Правило виводу — своєрідний трафарет, шаблон, припис, що визначає перехід від засновків до висновку-наслідку, вказуючи, яким чином висловлювання, істинність яких відома, можна видозмінювати, щоб одержати нові істинні висловлювання.
Пропонують і таке формулювання правил виводу: «Правила виводу — це способи логічного переходу від засновків до висновку, які задають правила введення і усунення логічних сполучників» [14].
А
А,АА0Л...АА
1 Z П
Згідно з цим правилом істинні висловлювання завжди можна з'єднувати знаком кон'юнкції. У найпростішому випадку це правило записується так:-— ,що
АлВ означає: якщо висловлювання А, В поодинці істинні,
то істинна і їх кон'юнкція — АлВ. Наприклад: Тарас Шевченко2 — геніальний поет (А). Тарас Шевченко — талановитий живописець (В).
Тарас Шевченко — геніальний поет і (він же) талановитий живописець (АлВ).
Одержаний висновок є істинним, чого не скажеш, наприклад, про складне висловлювання (кон'юнк-цію)«Тарас Шевченко — геніальний поет і живописець», оскільки ознака геніальності в цьому висловлюванні стосується Шевченка і як живописця.
Цей приклад не можна вважати типовим, оскільки суб'єктами простих суджень (кон'юнктів) далеко не завжди виступає одне й те ж поняття. Приклад, як правило, адресується буденній свідомості, здоровому глузду. Тому «типовіші» приклади, що ілюструють правила введення кон'юнкції, здадуться непереконливими для здорового глузду. Скажімо, «"Сім" — просте число, і Київ — столиця України» (АлВ).
Правило усунення кон'юнкції (УК):
А,/А9л...лА
А>
Це правило дозволяє з кон'юнкції висловлювань виводити будь-яке висловлювання, що є її кон'юнк-том.
Наприклад:
Правило введення диз'юнкції (ВД): A,vA,v...vA
12 п
Це правило дозволяє до істинного висловлювання приєднувати з допомогою диз'юнкції (нестрогої) інші висловлення. Оскільки ж нестрога диз'юнкція є істинною за умови істинності принаймні одного диз'юнкта, то звідси випливає висновок, що логічне значення приєднуваних диз'юнктів не впливає на утворену диз'юнкцію: вона завжди буде істинною.
Наприклад:
О. Пушкін — геніальний поет.
0. Пушкін — геніальний поет або живописець.
Правила усунення диз'юнкції (УД)
1. Правило усунення строгої диз'юнкції:
A,vA,v...vA
1— 2— — п
A,v...vA А,
Усунення строгої диз'юнкції з двома диз'юнктами здійснюється так:
АуВ ■ АуВ АуВ АуВ
А . В . А . В
В ' А В ' А
2. Правило усунення нестрогої диз'юнкції:
A,vA.v...vA„ A,vA„v...vA
12 п 12 п
А9Л...ЛА„ A,v...vA
Логічний вивід і проблема розв'язання
Усунення нестрого! диз'юнкції з двома диз'юнктами здійснюється так:
AvB AvB А . В
В ' А
У традиційній логіці правило усунення диз'юнкції відповідає схемі розділово-категоричного умовиводу (див. с 195).
Правило введення імплікації (ВІ):
А В-+А
Згідно з таблицею істинності імплікації за умови істинності консеквента вона завжди є істинною. Дати переконливу змістовну інтерпретацію цього правила, мабуть, неможливо.
Правило дедукції є одним із різновидів введення імплікації:
Г, АУ-В Г\-(А->В) '
Читається це правило так: «Якщо з гамми засновків Г і формули А можна вивести формулу В, то із засновків Г випливає формула А-+В.
Правило усунення імплікації (УІ):
А-+В А->В
А В~
1. (Modus ponens); 2. —=—(Modus tollens).
Це правило дозволяє за наявності істинного антецедента виводити відповідний консеквент, а за наявності заперечення консеквента — переходити до заперечення антецедента.
Правило введення еквіваленції (BE): А->В В-+А АВ '
Імплікація А-+В означає, що А є достатньою, але не необхідною підставою стосовно В, а В є необхідною, проте недостатньою умовою істинності А. Аналогічно можна охарактеризувати й імплікацію В->А, орієнтуючись на її складові (антецедент і консеквент), а не на буквене їх позначення. За умови істинності А—>В і В—> —>А з цих даних можна вивести еквіваленцію АВ, в якій виражається взаємна необхідність і достатність А і В.
Наприклад:
Якщо трикутник рівносторонній, то він рівнокутний (А->Б).
Якщо трикутник рівнокутний, то він рівносторон-
ній (В—>А).
Трикутник є рівностороннім тоді і тільки тоді, коли він рівнокутний (АВ).
Правило усунення еквіваленції (УЕ):
1 АВ
А . В . А . В .
В А В~ А
Про правильність перелічених висновків свідчить таблиця істинності еквіваленції, згідно з якою логічне значення її правої і лівої частин збігається: іі; х--х.
Існують й інші правила виводу, котрі часто виділяють в окрему групу: «...в логіці висловлювань існують також правила перетворення суджень, які задаються відповідними рівносильностями (їх ще називають правилами еквівалентної заміни). Знак «=», що з'єднує дві частини кожної формули, які наводяться нижче, означає логічну тотожність цих частин за будь-яких значень пропозиційних змінних (що можна перевірити, склавши для них таблиці істинності). Ці рівносильності служать алгоритмами правомірної трансформації структури логічних виразів, а також правилами переходу до виразів з іншими логічними сполучниками» [15].
Поняття «рівносильність» (=) тотожне поняттю «еквівалентність» (В) = (AvB): «Якщо цей предмет металевий, то він електропровідний» і «Цей предмет не є металевим або він електропровідний».
Приклад рівносильності 14— (АлВ) = (AvB ):«Рошб
має рівні і попарно паралельні сторони» і «Хибно, що
в ромба сторони не є рівними або не попарно паралель
ними». _ _
Приклад рівносильності 15 — (AvB) = (АлВ): «Цей кут є прямим або тупим» і «Хибно, що цей кут не є ні прямим, ні тупим».
Рівносильність 18 — (AvB)л(AvB) = В — називається законом виключення; рівносильності 19 і 20 — Ал(АВ) = А; Av(AлB) =А — законами поглинання; рівносильності 21 і 22_— (А\?)л(В\?)=_(А\?)л(В\? v(AvB); (AAC)V (ВЛС) = (АлС (BлC)v(AлB) — законами виявлення.
Рівносильності 23—27 є похідними від перерахованих рівносильностей 1—22.
Вдаючись до рівносильностей 1—27 і правил заміни, виводять рівносильності 28—34.
Особливе місце належить у системі виводу рівносильним формулам, до складу яких входять «завжди істинні» або «завжди хибні» підформули. Зрозуміло, що всі «завжди істинні» формули рівносильні одна одній. Це стосується і «завжди хибних» формул: вони теж рівносильні між собою. Згідно з таблицею істинності заперечення, заперечення «завжди істинної» формули є «завжди хибною» формулою, і навпаки. Так, оскільки формула А \/ІГ« завжди істинна», то формула AvA є «завжди хибною» (або: оскільки формула АлА «завжди хибна», то її заперечення АлА є «завжди істинною» формулою).
Позначивши буквою «і» «завжди істинну» формулу, а буквою «х» «завжди хибну», одержують рівно-сильності 43—50'.
Логічний вивід будується на таких засадах. На будь-якому кроці побудови виводу можна дописати до послідовності формул:
1) будь-яку частину наявної формули (підформулу) або її заперечення як припущення;
2) формулу, що випливає із записаних вище формул послідовності за одним із правил логічного виводу або рівносильну якійсь із записаних вище;
3) раніше доведену формулу.
Якщо засновки є повними, тобто достатніми для одержання однозначного висновку, і несу переч ливими, то одне із суперечних припущень призведе до суперечності (що дає підставу вважати його неспроможним), а друге — до несуперечливого шуканого висновку. Якщо ж засновки суперечливі, то в обох випадках ми прийдемо до суперечності, що буде достатньою підставою для того, щоб вважати хибними принаймні деякі засновки. І, нарешті, коли засновки є несуперечливи-ми, але неповними, то з обох суперечних припущень будуть випливати різні висновки, які разом з тим не ведуть до суперечливості сам вивід.
Розглянемо названі ситуації на прикладах.
Дано чотири засновки, з яких потрібно вивести висновок:
1. А-В.
2V C->A.
3. АуС.
4. АВ.
Перший хід міркування:
5. А (припущення).
6. В (усунення імплікації: 1; 5).
7. С (усунення строгої диз'юнкції: 3; 5).
8. В (усунення еквіваленції: 4; 5) — суперечність: 6; 8.
9. А (усунення імплікації 1; 8) — суперечність: 5; 9. 10. АлВлСлВлА (введення кон'юнкції: 5; 6; 7; 8; 9).
Другий хід міркування:
5. А (припущення).
6. С (усунення імплікації: 2; 5).
7. С (усунення строгої диз'юнкції: 3; 5) — супереч-ність: 6; 7.
8. Б (усунення еквіваленції: 4; 5).
9. АлСлСлВ (введення кон'юнкції: 5; 6; 7; 8).
Як бачимо, з обох суперечних припущень одержані суперечливі наслідки, що свідчить про суперечність засновків.
Розглянемо іншу ситуацію. Дано чотири засновки, з яких потрібно зробити висновок:
1. А-С.
2. AvB.
3. С-В.
4. CvA.
Перший хід міркування:
5. А (припущення).
6. С (усунення імплікації: 1; 5).
7. В (усунення строгої диз'юнкції: 2; 5).
8. С (усунення імплікації: 3; 7).
9. А (усунення нестрогої диз'юнкції: 4; 8).
10. АлСлВлСлА (введення кон'юнкції: 5; 6; 7; 8; 9). Другий хід міркування:
5. А (припущення).
6. В (усунення строгої диз'юнкції: 2; 5).
7. С (усунення нестрогої диз'юнкції: 4; 5).
8. А (усунення імплікації: 1; 7).
9. В (усунення імплікації: 3; 7).
Ю. АлВлСлАлВ (введення кон'юнкції).
Оскільки жодне із суперечних припущень не призвело до суперечності міркування, то звідси випливає висновок: засновки потребують доповнення.
До припущень вдаються не завжди, а лише тоді, коли без них не можна зробити черговий крок логічного виводу (іноді припущення дає можливість скоротити шлях розв'язання задачі). Якщо нам дано засновки:
1. А->В.
2. CvA.
3. B->D.
4. CAD,
то немає потреби вдаватися до припущення, оскільки четвертий засновок містить пряму інформацію про С і D.
5. Q (усунення кон'юнкції: 4);
6. j=) (усунення кон'юнкції: 4);
7. А (усунення нестрогої диз'юнкції: 2; 5);
8. В (усунення імплікації: 3; 6);
9. В (усунення імплікації: 1; 7);
10. CADAAABAB (введення кон'юнкції: 5; 6; 7; 8; 9).
11. CADAAABAB (усунення подвійного заперечен
ня — УПЗ).
12. CADAAAB (згідно із законом ідемпотентності).
А якщо без припущення не можна обійтися, то яку
ж змінну треба вибирати як припущення? Ту, з якої можна вивести якомога більше наслідків. Так, маючи засновки
1. С-*А.
2. В->С-
3. AvB,
з яких потрібно зробити висновки, ми змушені брати за припущення С, оскільки саме воно дає можливість вивести найбільше висновків. Інші припущення тут неефективні: припущення В дає можливість одержати лише один висновок —С , а припущення А — жодного:
4. С (припущення).
5. А (усунення імплікації: 1; 5).
6. S (усунення імплікації: 2; 5).
7. А (усунення нестрогої диз'юнкції: 3; 6).
Щоб застосувати теорію логічного виводу у розв'язанні практичних задач, потрібно послідовно здійснити кілька операцій. Наприклад, у нас є такі дані:
Коло підозрюваних у скоєнні злочину обмежується чотирма особами: Івановим, Петровим, Сидоровим, Федотовим.
1. Іванов міг брати участь у скоєнні злочину тоді і тільки тоді, коли до цього злочину причетний і Петров.
2. Якщо до цього злочину не причетний Сидоров, то в ньому брав участь Федотов.
3. Відомо, що один і тільки один із підозрюваних Іванов або Сидоров — причетні до цього злочину.
4. Федотов довів своє алібі.
Насамперед потрібно виділити прості судження з цього тексту і позначити їх пропозиційними змінними. Ось ці судження:
1. Іванов брав участь у скоєнні злочину (А).
2. Петров брав участь у скоєнні злочину (В).
3. Сидоров брав участь у скоєнні злочину (С).
4. Федотов брав участь у скоєнні злочину (£>). Після цього слід виділити логічні зв'язки, які є в
цьому тексті (і відповідно їх розставити): , у.
Поєднавши пропозиційні змінні (А, В, С, D) відповідними логічними термінами (зв'язками), одержимо такі висловлювання:
1. АВ.
2. С->£».
3. АуС;
4. D
Оскільки в нас є пряма інформація про алібі Федотова — D, то немає потреби вдаватися до припущення. Далі вивід будуємо так:
5. С (усунення імплікації: 2; 4).
6. А (усунення строгої диз'юнкції: 3; 5).
7. В (усунення еквіваленції: 1; 6).
8. БлСлАлВ (введення кон'юнкції: 4; 5; 6; 7). Залишається лише зробити переклад одержаного
висновку на природну мову: «Ні Федотов, ні Іванов, ні Петров не причетні до скоєння злочину. Злочин скоїв Сидоров».
Проблема розв'язання і розв'язуючі процедури
Оскільки висновок виводу (останнє у відповідній послідовності, вивідне висловлювання) не завжди з необхідністю випливає із засновків, то доводиться вдаватися до різних процедур, щоб довести, що логічне слідування справді має місце в тому чи іншому виводі. Так, щоб довести, що проголошена нами формула В (теза) є справді істинною, треба підібрати такі фор-мули-аргументи А1лА2л...лАп, з яких за відповідною процедурою можна вивести формулу, що збігається з проголошеною (з тезою), проте на відміну від останньої є достовірною.
Для позначення логічного слідування в логіці застосовують знак «І— » (або« f=»). Вираз «А\—В» читається так: «з А логічно випливає В».
Із формули А випливає формула В тоді, коли імплікація «А—їВ» є законом логіки («завжди істинною» формулою). Ось чому (і не тільки тому) знаходження процедури, що дає змогу визначити, до якого класу формул логіки висловлювань («завжди істинних», «завжди хибних» чи виконуваних) належить будь-яка формула, є винятково важливою проблемою логіки висловлювань.
Побудова відповідних таблиць істинності є ефективною лише за умови, коли до розглядуваних формул входить невелике число змінних. В іншому разі вона буде громіздкою, оскільки кількість рядків у таблиці стрімко зростає із збільшенням числа змінних, які входять до формули. Так, якщо формула містить три пропозиційні змінні, то рядків у таблиці буде 8, чотири — 16, п'ять — 32, десять — 1024. До того ж існують інші, менш громіздкі, зручніші процедури, з допомогою яких розв'язуються ці задачі. Йдеться про зведення формул до нормальної форми.
Нормальні форми формул логіки висловлювань
Формула логіки висловлювань має нормальну форму, якщо вона, по-перше, не містить у собі знаків -», , у, а по-друге, знаки заперечення стоять у ній лише при змінних.
Будь-яку формулу, що не має нормальної форми, можна скінченним числом застосувань правил заміни перетворити у формулу, яка має нормальну форму. Ця процедура називається процесом зведення формули до нормальної форми.
Щоб звести формулу до нормальної форми, необхідно зробити в ній такі рівносильні заміни:
1) кожну підформулу типу (А—>В) замінити згідно з рівносильністю 13 формулою (AvB);
2) кожну підформулу типу (АВ) замінити згідно з рівносильністю 16 формулою (AVB)A(BVA);
3) кожну підформулу типу (AvB) замінити згідно з рівносильністю 17 формулою (АУВ)Л(АУВ);
4) кожну підформулу типу (АлВ) замінити згідно з рівносильністю 10 формулою (AvB);
5) кожну підформулу типу (AvB) замінити згідно з рівносильністю 11 формулою (АлВ);
6) кожну підформулу типуіГ замінити згідно з рівносильністю 1 формулою А.
Якщо ж перелічені процедури не можна застосувати до формули, то вона вже має нормальну форму.
Наприклад, дано формулу (pq), яку треба звести до нормальної форми. Згідно з рівносильністю 16 одержимо формулу(p~vq)л(qvp). 3 цієї формули згідно з рівносильністю 10 одержимо формулу(pvq)v(qvp), де підформулі (pvq) відповідає підформула рівносильності А , виражена засобами метамови, а підформулі (FVQ) — В. Вдавшись до рівносильності 11 і застосувавши її до кожного з диз'юнктів одержаної формули, дістанемо формулу (pAq~)v(c[Ap). І нарешті згідно з рівносильністю 1 одержимо формулу (pAq)v(q~Xp).
До нормальних форм формул логіки висловлювань належать передусім кон'юнктивна нормальна форма (КНФ) і диз'юнктивна нормальна форма (ДНФ). Причому кожна з них має свій специфічний спосіб утворення (зведення) і дає змогу розв'язувати відповідні задачі.
Проблема розв'язання
Є три класи формул логіки висловлювань («завжди істинні», «завжди хибні» і невизначені, або виконувані). Завдання, що полягає у відшуканні процедури, котра дає змогу визначити, до якого з перелічених класів належить будь-яка формула, називається семантичною проблемою розв'язання для формул логіки висловлювань. А процедура, що дає змогу скінченним числом простих дій вирішувати проблему розв'язання, називається розв'язуючою процедурою.
Для того щоб одержати розв'язуючу процедуру, достатньо знайти спосіб відрізняти «завжди істинні» Формули від усіх інших. Якщо в результаті застосування такої процедури до формули А виявиться, що вона «завжди істинна», то проблема розв'язання вирішена. Коли ж ця формула виявиться не «завжди істинною», то цю процедуру треба застосувати до фор-мулиА Якщо буде встановлено, що ця формула є «завжди істинною», то звідси випливає висновок: формула А є «завжди хибною». Коли ж буде встановлено, що і формула А не є «завжди істинною», то це свідчить, що формула А є виконуваною, тобто при одних логічних значеннях змінних вона є істинною, а при інших — хибною.
Існує формальна процедура, з допомогою якої, не вдаючись до побудови відповідних таблиць істинності, можна визначати, до якого класу належить будь-яка формула логіки висловлювань — до «завжди істинних», «завжди хибних» чи виконуваних.
Пропозиційна змінна входить до складу формули, зведеної до нормальної форми, регулярно, якщо вона (змінна) входить до складу цієї форми одночасно як із запереченням, так і без заперечення. Якщо ж змінна входить до складу формули, зведеної до нормальної форми, тільки із запереченням або тільки без заперечення, то вона входить до складу формули нерегулярно.
Розв'язуюча процедура передбачає такі дії:
1) зведення формули до нормальної форми;
2) у зведеній до нормальної форми формулі виділення змінних, які входять до неї нерегулярно;
3) замість усіх змінних і заперечень змінних, які входять до формули нерегулярно, слід підставити на всіх місцях, де вони трапляються в нормальній формі, букву х (тобто логічне значення «хиба»);
4) застосування правил заміни згідно з рівносиль-ностями 48, 48', 50 і 50' до всіх підформул одержуваної формули, доки є приводи для його застосування. В результаті такої процедури довжина формули буде скорочуватись, і можуть з'явитися нові змінні, що нерегулярно входять до формули. З ними чинять аналогічно, тобто згідно з пунктами 3 і 4. Передбачувані в пунктах 2—4 перетворення слід повторювати, доки не одержимо формулу, яка не містить у собі змінних, що входять до неї нерегулярно;
5) розгляд наступних двох формул, одержаних з формули, яка не містить змінних, що входять до неї нерегулярно, якщо:
а) замість однієї змінної, яка регулярно входить до формули, в усіх місцях слід підставити і (логічне значення ■— «істина») і застосовувати правило рівносильної заміни згідно з рівносильностями 43, 47—50;
б) замість тієї ж змінної на всіх місцях підставити букву х (логічне значення — «хиба») і застосовувати правило рівносильної заміни згідно з рівносильностями 44, 47—50.
До формул а і б, якщо це можливо, знову застосовують пункти 2—4, а потім, згідно з пунктом 5, з формул а і б одержують відповідно формули аа, аб, ба і бб тощо, доки не вичерпані можливості застосування пунктів 2—5.
Якщо в результаті застосування цієї процедури до будь-якої формули А всі заключні формули набудуть значення і («істина»), то формула А є «завжди істинною», а якщо хоча б одна заключна формула набуде значення х («хиба»), то формула А не є «завжди істинною»
Кон'юнктивна нормальна форма
Кон'юнктивна нормальна форма формул логіки висловлювань є кон'юнкцією елементарних диз'юнкцій.
Елементарною диз'юнкцією є формула, що має такий вигляд: A1vA2v...vAn, де п>1, а кожна з формул Ар А2, ..А є змінною або запереченням змінної. Так, формула (pvqvrvs) є елементарною диз'юнкцією, чого не можна сказати про формулу (pvqv(pAr)vs), оскільки третій її диз'юнкт (рлг) не є ні змінною, ні запереченням змінної.
Елементарна диз'юнкція є «завжди істинною» тоді і лише тоді, коли в ній міститься принаймні одна пара диз'юнктів, з яких один є якоюсь змінною, а другий — її запереченням. У цьому неважко переконатися, побудувавши відповідну таблицю істинності: пара названих диз'юнктів забезпечить наявність «і» (істина) в кожному рядку цієї таблиці, що є достатньою підставою для визнання подібної Диз'юнкції «завжди істинною» формулою, тобто законом логіки.
Формула логіки висловлювань має кон'юнктивну нормальну форму тоді, коли вона має такий вигляд: В,лВгл...лВт, де Вг В2,...Вп_ — елементарні диз'юнкції і
т>1. Так, формула pA(qvr)A(qvp) має кон'юнктивну нормальну форму (кон'юнкт р слід розглядати як вироджену диз'юнкцію з одним диз'юнктом).
Будь-яку формулу логіки висловлювань з допомогою ряду рівносильних замін можна звести до кон'юнктивної нормальної форми. Формулу, що є рівносильною даній і має кон'юнктивну нормальну форму, називають кон'юнктивною нормальною формою даної формули.
Щоб звести формулу до кон'юнктивної нормальної форми, треба насамперед з допомогою відповідної процедури звести її до нормальної форми. А потім кожну підформулу, що має вигляд (pv(qAr)) згідно з рівно-сильністю 6 і кожну підформулу типу ((qA.r)vp) згідно з рівносильністю 6' замінити формулою ((pvq)A A(pvr)). Річ у тім, що формула має кон'юнктивну нормальну форму лише за умови, що вона, по-перше, має нормальну форму, а по-друге, не містить у собі під-формул типу (pv(qAr)) і ((qAr)vp).
Розглянемо зведення формули до кон'юнктивної нормальної форми на такому прикладі: (р—хі)—>(р~А~г).
1. Застосувавши до цієї формули правило усунення імплікації (при цьому підформулу (р—щ) будемо розглядати як антецедент (А), а підформулу (рХг) — як консеквент (В) імплікації А—>В, одержимо: (p-q)v v(pAq).
2. Застосувавши правило усунення імплікації, яка є в першому диз'юнкті цієї формули (при цьому як антецедент виступає р, а як консеквент — q), одержимо:
(pVq)v(pAT).
3. Вдавшись до рівносильності 11 (другого закону де Моргана) і зробивши відповідну заміну першого диз'юнкта цієї формули, одержимо: (p=Aq~)v(pAr).
4. Застосувавши рівносильність 10 (перший закон де Моргана) до другого диз'юнкта формули, одержимо: (p=Aq~)v(pvr).
5. Звернувшись до першої рівносильності, правила усунення подвійного заперечення, одержимо: (pAq)v(pvr).
6. Остання заміна згідно з рівносильністю 6' ((BAC)VA): (pvpvT)A(qvpvr).
Далеко не всі формули мають лише одну кон'юнктивну нормальну форму.
Формула логіки висловлювань в КНФ є «завжди істинною» тоді, коли кожен її кон'юнкт, тобто кожна елементарна диз'юнкція, містить у собі принаймні одну змінну одночасно зі знаком заперечення і без нього. В тому, що формула, зведена до КНФ, є «завжди істинною», можна переконатися за її зовнішнім виглядом. Так, оскільки кожен кон'юнкт формули (pvqvp)A(pvqvq~)A(pvrvqvr) містить змінну зі знаком заперечення і без нього, то вона є «завжди істинною».
З допомогою КНФ визначають, є дана формула «завжди істинною» чи ні, а також чи є формула В логічним наслідком із формул Ар А2,..Лп.
Щоб перевірити, чи є довільна формула В наслідком із формул А[ГА2, ~Ап, треба приєднати В через імплікацію до формул Аг А2, ~Ап, і одержаний вираз звести до КНФ. Якщо одержана КНФ буде «завжди істинною», то це засвідчить, що В випливає з_А;, А,..., Ап.
Перевіримо, чи випливає В з формул В —>А, А як засновків. Поєднаємо ці засновки кон'юнкцією і приєднаємо до них В з допомогою імплікації: ((В—>А)лА)—>В.
Одержану формулу зведемо до КНФ:
1. Застосувавши рівносильність 13, одержимо ((B->A)AA)VB.
2. Вдавшись до рівносильності 10, одержимо ((BA)vA)vB.
3. Використавши рівносильність 13, одержимо ((BvA)vA)vB.
4. Застосувавши рівносильність 10, одержимо ((BAA)VA)VB.
5 Вдавшись до рівносильності 6', одержимо ((AVB)A(AVA))VB.
6. Застосувавши першу рівносильність, одержимо ((AVB)A(AVA))VB.
7. Усунувши JCOH'IOHKT, ЯКИЙ містить змінну та її заперечення (AvA), одержимо AvBvB. Оскільки ця формула є елементарною диз'юнкцією, яка містить змінну (В) і її заперечення (В), то це означає, що вихідна формула є «завжди істинною». Тому формула В є наслідком із формул В—*А і А.
Розрізняють ще досконалу кон'юнктивну нормальну форму (ДКНФ) і скорочену кон'юнктивну нормальну форму (СДНФ), з допомогою яких розв'язують задачі на знаходження всіх логічних наслідків з даної формули.
Диз'юнктивна нормальна форма
Диз'юнктивна нормальна форма формул логіки висловлювань є диз'юнкцією елементарних кон'юнкцій.
Елементарною кон'юнкцією є формула, що має такий вигляд: А1лА2л...лА , де п>1, а кожна з формул Ар А2, ..., Ап є змінною, або запереченням змінної. Так, формула (рлс[лглд) є елементарною кон'юнкцією, чого не можна сказати про формулу (дл(дуг)лрлг), оскільки другий її кон'юнкт не є ні змінною, ні запереченням змінної.
Елементарна кон'юнкція є «завжди хибною» тоді й тільки тоді, коли до її складу входить принаймні одна пара кон'юнктів, з яких один є якоюсь змінною, а другий — її запереченням.
Формула логіки висловлювань має диз'юнктивну нормальну форму тоді, коли вона має такий вигляд: В vB2v...vBm, де Вр В2..„ Вт є елементарними кон'юнк-щями, а т>1. Наприклад: (pXqAr)vp~v(qAr).
Будь-яку формулу логіки висловлювань з допомогою відповідних рівносильних замін можна звести до диз'юнктивної нормальної форми. Формулу, що є рівносильною даній і має диз'юнктивну нормальну форму, називають диз'юнктивною нормальною формулою даної формули. Щоб звести формулу до ДНФ, необхідно насамперед звести її до нормальної форми, а потім кожну під-формулу типу (AA(BVCJ) згідно з рівносильністю 7 і кожну підформулу типу ((BVC)AA) згідно з рівносильністю Т замінити формулою ((AAB)V(AAC)).
Розглянемо процедуру зведення формули до диз'юнктивної нормальної форми на такому прикладі:
1. Застосувавши до цієї формули правило усунення імплікації (при цьому підформулу р будемо розглядати як антецедент, а підформулу ((p—>q)—>q) — як кон-секвент), одержимо: pv((p—>q)—>q).
2. Знову вдавшись до правила усунення імплікації (на цей раз роль антецедента виконує підформула (р—щ), а консеквента — q, одержимо: pv((p—>q)vq)-
3. Застосувавши правило усунення імплікації (антецедент — р, а консеквент — q), одержимо: pv((pq)vq).
4. Використавши другий закон де Моргана, одержимо: pv((pAq)vq).
5. Залишається лише усунути подвійне заперечення і зайві дужки: p~v(pAq)vq.
Формула може мати не одну ДНФ.
З допомогою ДНФ з'ясовують, по-перше, є дана формула «завжди хибною» чи ні, а по-друге, чи є та чи інша формула наслідком з відповідних засновків.
Формула, що має ДНФ, є «завжди хибною» тоді й тільки тоді, коли «завжди хибними» є всі її диз'юнкти, тобто коли кожна елементарна кон'юнкція містить у собі принаймні одну пару кон'юнктів, один з яких є якоюсь змінною, а другий — її запереченням. Таким чином, за виглядом елементарної кон'юнкції можна робити висновок, є вона «завжди хибною» чи ні. Так, формула ((pAqAp)v(qAq)v(pAqArAr)) є «завжди хибною», оскільки загалом вона є диз'юнкцією, кожен диз'юнкт якої (елементарна кон'юнкція) є «завжди хибним».
Розрізняють ще досконалу диз'юнктивну нормальну форму (ДДНФ) і скорочену диз'юнктивну нормальну форму (СДНФ), кожна з яких дає змогу розв'язувати відповідні задачі.
