Табличні методи у сучасній логіці

У логіці висловлювань для визначення типу чи статусу форму­ли, а також перевірки правильності чи коректності міркування, на­явності відношення логічного випливання між його засновками і висновком, яке полягає в тому, що висновок не може бути хибним, якщо усі засновки істинні, широко використовують метод таблиць істинності та метод аналітичних таблиць.

Таблиця істинності в логіці висловлювань - це табличний метод, за допомогою якого з'ясовується значення істинності складної формули логіки висловлювань на підставі табличних визначень логічних сполучників.

Алгоритм побудови таблиці істинності для визначення складної формули логіки висловлювань:

1. Скласти без повторів список пропозиційних змінних, що входять до складу формули.

2. Кожна пропозиційна змінна повинна розпочинати новий стовпчик таблиці.

3. Для кожної підформули у тій послідовності, в якій вони вхо­дять до складу формули, має бути побудований відповідний стовп­чик таблиці.

4. Кількість рядків у таблиці істинності обчислюється за формулою 2ⁿ, де 2 означає кількість логічних значень, які припису­ються пропозиційним змінним, - «істину» або «хибу», а n - кіль­кість пропозиційних змінних, що входять до складу формули; кож­ний набір значень повинен відрізнятися від інших.

5. Потрібно визначити головний логічний сполучник у формулі.

6. Останній стовпчик таблиці істинності повинен бути побу­дований для головного логічного сполучника, який відповідає зна­ченню усієї формули.

Якщо в результаті побудови таблиці істинності для деякого складного описового висловлювання, записаного складною формулою, з’ясується, що воно набуває значення «істина», не­залежно від того, яких логічних значень набувають його склад­ники, тоді таке складне описове висловлювання є логічним за­коном. У цьому випадку в останньому стовпчику таблиці по­винні бути лише істинні значення.

Якщо ж з’ясується, що воно набуває значення «хиба», неза­лежно від того, яких логічних значень набувають його склад­ники, тоді таке складне описове висловлювання є логічним протиріччям. У цьому випадку в останньому стовпчику табли­ці повинні бути лише хибні значення.

Нарешті, якщо з’ясується, що воно змінює своє логічне зна­чення, залежно від того, яких логічних значень набувають його складники, тоді таке складне описове висловлювання буде вико­нуваним висловлюванням. У цьому випадку в останньому стовп­чику таблиці можуть бути як істинні, так й хибні значення.

Побудуємо таблицю істинності для формули p→(q→p)

На підставі наведеної таблиці визначаємо, що у досліджуваній формулі ((p → ~ q) л p) → ~ q наявне відношення логічного ви­пливання.

Аналітична таблиця в логіці висловлювань - це табличний метод, за допомогою якого з’ясовується значення істинності складної формули логіки висловлювань на підставі правил за­міни логічних сполучників та їх заперечень, шляхом доведення від протилежного.

Правила заміни логічних сполучників і їх заперечень, або пра­вила редукції чи аналітичні правила, отримують із табличних ви­значень логічних сполучників.

Визначення правил заміни в логіці висловлювань:

Правило заміни кон’юнкції: якщо формула має вигляд А л В, тоді в тій же галузці дерева формули вона продовжується і замі­нюється на формули А і В. Схема правила:

де символ Г, що читається як «гамма», позначає формули реш­ти частини рядка, які знаходяться зліва від редукованої формули, а символ ∆, що читається як «дельта», позначає формули решти час­тини рядка, що знаходять справа від редукованої формули, форму­ли зліва і справа можуть бути й відсутніми.

Правило заміни диз’юнкції: якщо формула має вигляд А v В, тоді дерево формули розгалужується на дві нові альтернативні підтаблиці, в одній з яких вихідна формула замінюється на форму­лу А, в іншій - на формулу В.

Схема правила:

де вертикальна риска фіксує факт розгалуження дерева форму­ли на дві нові альтернативні галузки чи підтаблиці.

Правило заміни імплікації: якщо формула має вигляд А → В, тоді дерево формули розгалужується на дві нові альтернативні підтаблиці, в одній з яких вихідна формула замінюється на форму­лу ~А, в іншій на формулу В.

Схема правила:

Правило заміни еквіваленції: якщо формула має вигляд А θ В, тоді дерево формули розгалужується на дві нові альтер­нативні підтаблиці, в одній з яких вихідна формула замінюється на формули А і В, в іншій на формули ~А і ~В.

Схема правила:

Правило заміни заперечення кон’юнкції: якщо формула має вигляд ~ (А ^ В), тоді дерево формули розгалужується на дві нові альтернативні підтаблиці, в одній з яких вихідна формула заміню­ється на формулу ~ А, в іншій на формулу ~ В.

Схема правила:

Правило заміни заперечення диз’юнкції: якщо формула має вигляд ~ (А V В), тоді в тій же галузці дерева формули вона продо­вжується і замінюється на формули ~ А та ~ В.

Схема правила:

Правило заміни заперечення імплікації: якщо формула має вигляд ~ (А→В), тоді в тій же галузці дерева формули вона продо­вжується і замінюється на формули А та ~ В.

Схема правила:

Правило заміни заперечення еквіваленції: якщо формула має вигляд ~ тоді дерево формули розгалужується на дві

нові альтернативні підтаблиці, в одній з яких вихідна формула за­мінюється на формули А і ~В, в іншій - на формули ~ А і В.

Схема правила:

Правило заміни заперечення заперечення: якщо формула має вигляд — А, тоді в тій же галузці дерева формули, вона про­довжується і замінюється на формулу А.

Схема правила:

Правила заміни логіки висловлювань не є детермінованими. Вони повідомляють, що може бути зроблено, а не що повинно бути зроблено. При побудові аналітичної таблиці в логіці висловлювань вибирають формулу на галузці дерева формули і застосовують до неї правило. Оскільки порядок вибору правил редукції довільний, то може існувати декілька аналітичних таблиць для однієї форму­ли. Існують певні пріоритети, які накладаються на застосування правил, але їх не можна розглядати як загальний принцип.

Аналітична таблиця в логіці предикатів - це табличний метод, за допомогою якого з’ясовується значення істинності складної формули логіки предикатів на підставі правил заміни логічних сполучників, кванторів та їх заперечень, шляхом до­ведення від протилежного.

У логіці предикатів до правил редукції логіки висловлювань додаються кванторні правила. Визначення кванторних правил в ло­гіці предикатів:

Правило заміни квантора спільності: якщо формула ∀ α А(а) містить квантор спільності, то він замінюється на будь-яку пред­метну константу t чи будь-яку предметно-істиннісну функцію А(ї), яка виступає елементом розширення предикатів формули ∀α А(а) з умовою, що кожна зв’язана предметна змінна α і далі залишається зв’язаною.

Схема правила:

де A(t) - результат заміни всіх вільних входжень α в А на дові­льний терм t.

Правило заміни квантора існування: кожний квантор існу­вання 3 α A(α), який не знаходиться в області дії квантора спіль­ності ∀ α A(α), замінюється новою предметною константою k, яка раніше не входила у формулу А.

Схема правила:

де A(k) - результат заміни всіх вільних входжень α в А на предметну константу k, яка ще не зустрічалася в аналітичній таб­лиці.

Правило заміни заперечення квантора спільності: якщо формула ~∀ α А(а) містить вільні входження α у формулу А, то останні замінюються послідовно на нові предметні константи k, які раніше не входили у формулу А.

Зазначимо, що константа k повинна відрізнятися від уже вико­ристаних констант у списку формул, щоб виключити можливість появи пари формул А(к) і ~А(к).

Схема правила:

Правило заміни заперечення квантора існування: кожний заперечений квантор існування ~ 3 α А(а), який знаходиться в об­ласті дії запереченого квантора спільності ~∀ α А(а), замінюється новою предметно-істиннісною функцією ~А0), яка раніше не вхо­дила у формулу А.

Схема правила:

де A(t) - результат заміни всіх вільних входжень α в А на до­вільний терм t.

Правила редукції в логіці предикатів можна розділити на дві групи. До першої групи зараховують правила, застосуван­ня яких не збільшує кількості списків формул в наступному рядку таблиці. Це правила заміни кон’юнкції, заміни заперечення диз’юнкції, заміни заперечення імплікації, заміни заперечення за­перечення, заміни квантора спільності, заміни заперечення кван­тора спільності, заміни квантора існування і заміни зап еречення квантора існування. До другої групи зараховують правила, за­стосування яких збільшує кількість списків формул. Це пра­вила заміни заперечення кон’юнкції, заміни диз’юнкції і заміни імплікації. Побудова аналітичної таблиці в логіці предикатів зна­чно спроститься, якщо правила другої групи будуть використову­ватися тільки після того, як будуть використані усі можливі пр а­вила першої групи.

Серед правил першої групи спочатку слід використовувати пропозиційні правила - заміни кон’юнкції, заміни заперечення диз’юнкції, заміни заперечення імплікації і заміни заперечення за­перечення, і тільки після цього потрібно використовувати квантор­ні правила - заміни квантора спільності, заміни заперечення кван­тора спільності, заміни квантора існування і заміни заперечення квантора існування.

При редукції формул логіки предикатів за цими правилами можна порекомендувати спочатку застосовувати правило заміни заперечення квантора спільності та правило заміни квантора існу­вання, оскільки вони вимагають введення нових предметних кон­стант, а потім правило заміни квантора спільності та правило замі­ни заперечення квантора існування, які допускають заміну підкван - торної змінної на будь-який терм. При цьому доцільно заміняти їх на ті константи, які з’явились в результаті застосування правила заміни заперечення квантора спільності та правила заміни квантора існування.

Алгоритм побудови аналітичної таблиці для складної фор­мули логіки висловлювань та логіки предикатів:

1. Побудова аналітичної таблиці починається із припущення, що складна формула логіки висловлювань, або логіки предикатів, значення істинності якої необхідно визначати, є хибною, або на­слідок чи консеквент у відношенні логічного випливання між за­сновками і висновком міркування є хибним. Для цього визначають перший рядок аналітичної таблиці, застосовуючи заперечення для головного логічного сполучника, при дослідженні статусу форму­ли, або заперечення для консеквентна імплікації, при перевірці правильності міркування.

2. Далі визначають другий рядок аналітичної таблиці, замі­нюючи заперечення головного логічного сполучника, або запер е- чення консеквентна імплікації вихідної формули. При цьому спра­ва рядка аналітичної таблиці вказують знак правила редукції та підкреслюють формулу до якої воно застосовується.

3. Після цього визначають наступні рядки аналітичної табли­ці, послідовно замінюючи головні логічні сполучники вихідної фор­мули логіки висловлювань, або квантори спільності та існування, чи їх заперечення, вихідної формули логіки предикатів.

4. Головною метою побудови аналітичної таблиці є обґрунту­вання того, що вихідна формула є логічно істинною або загально- значущою. Способом досягнення цієї мети є доведення від проти­лежного. Тому при побудові аналітичної таблиці важливо керува­тися настановленням на отримання логічного протиріччя, коли вихідна формула буде розкладена на свої складники - атомарні формули та їх заперечення. У цьому випадку список формул вва­жається замкненим. Звичайно, логічне протиріччя в результаті численних спроб можна і не отримати, але це побічний результат, а не головна мета побудови аналітичної таблиці.

5. Якщо, послідовно застосовуючи правила заміни логічних сполучників та їх заперечень, чи правила заміни кванторів та їх заперечень, приходять до підсумкових таблиць, які містять тіль­ки атомарні формули та їх заперечення, тоді такі таблиці будуть замкненими, а вихідна формула - логічним законом або загально- значущою формулою, чи правильно або коректно побудованим мір­куванням. У протилежному випадку вихідна формула буде незага- льнозначущою формулою.

6. Замкнені списки позначаються символами N, N₁, N₂ і т. д. Якщо кожний список формул в останньому рядку аналітичної таблиці замкнений, тоді аналітична таблиця також вважається замкненою.

Розглянемо на прикладах як будується аналітична таблиця в логіці висловлювань.

Перевіримо на загальнозначущість формулу А → А. Визначає­мо перший рядок:

~ (А → А). Будуємо таблицю.