6.3. Система обчислень

Значення складного висловлювання залежить від значень простих висловлювань. Його, як і значення функцій алгебри логіки, можна обчислити за відповідною формулою (пропозиційною формою), використовуючи таблицю істинності. Для операцій логіки висловлювань таблиці істинності мають такий вигляд:

Приклад 6.4. Обчислимо на всіх можливих інтерпретаціях значення висловлювання, поданого формулою :

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

Визначення 6.4. Тавтологією (тотожно істинною) називають формулу, істинну на будь-якій інтерпретації. Суперечністю (тотожно хибною) називають формулу, хибну на будь-якій інтерпретації. Нейтральною називають формулу, яка на деяких інтерпретаціях істинна, а на деяких — хибна.

Формула, наведена в попередньому прикладі, є тавтологією.

Приклад 6.5. а) Формула є тавтологією. У цьому можна переконатися, обчислюючи її значення при і :

,

або використовуючи таблицю істинності:

б) Формула є суперечністю. Обчислимо її значення при і :

,

або скористаємося її таблицею істинності:

в) Формула є тавтологією (на цій формулі базується метод доведення теорем “від протилежного”). Обчислимо її значення на всіх можливих інтерпретаціях змінних А і В:

Приклад 6.6. Перевіримо, чи є тавтологіями формули і :

З таблиці істинності видно, що формула — тавтологія, а формула — не тавтологія.

Приклад 6.7. Покажемо, що формули “парадоксів матеріальної імплікації”: — “Якщо висловлювання А істинне, то воно випливає з будь-якого висловлювання” і — “Якщо висловлювання А хибне, то з нього випливає будь-яке висловлювання” є тавтологіями:

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

Приклад 6.8. Перевіримо, чи формула є тавтологією, не будуючи таблиці істинності, а шукаючи можливість спростувати це припущення. Будемо міркувати так. Відповідно до визначення операції імплікації значення Х імплікація дає тільки у випадку . Із останньої імплікації випливає, що змінна В обов’язково має набувати значення Х. Тоді має набувати значення І. Це можливо лише тоді, коли набуває значення Х. Отже, А має набувати значення І. Таким чином, на інтерпретації формула не є істинною — це спростовує припущення, що формула є тавтологією; ця формула нейтральна.

6.4. Еквівалентні перетворення формул

Визначення 6.5. Дві формули еквівалентні (рівносильні), якщо вони набувають тих самих значень на будь-якій інтерпретації.

Іншими словами: формули А і В еквівалентні тоді і тільки тоді, коли формула є тавтологією. При цьому формула — це еквівалентність.

Розглянемо закони еквівалентності алгебри висловлювань (вони аналогічні до законів алгебри логіки).

1. Закони комутативності (дають можливість переставляти операнди при використанні операцій , і ):

; ; .

2. Закони асоціативності (дають можливість нехтувати дужками, коли є послідовність операцій чи послідовність операцій ):

(також можна записати );

(також можна записати ).

3. Закони дистрибутивності (їх використовують при розкритті дужок):

;

.

4. Закони де Моргана (встановлюють взаємозв’язок між операціями заперечення, кон’юнкції, диз’юнкції):

; .

5. Закон заперечення: .

6. Закон виключення третього: .

7. Закон суперечності: .

8. Закон імплікації: .

9. Закон рівності: .

10. Закони спрощення:

; ;

; ;

; ;

; .

11. Закон тотожності: .

Довести, що подані закони є еквівалентностями, можна за допомогою таблиць істинності, які дадуть можливість переконатися, що на всіх інтерпретаціях закони істинні, тобто наведені формули є тавтологіями. Наприклад, закон спрощення має таку таблицю істинності:

Пояснимо суть закону виключення третього. Відповідно до цього закону або твердження А, або твердження має бути істинним — інакшого не може бути. Правда, в розмовній мові можна навести приклади, які суперечать цьому закону. Розглянемо висловлювання: “Це висловлювання хибне” — воно не може бути істинним, бо воно говорить, що воно хибне; воно не може бути хибним, бо тоді воно було б істинним. Це висловлювання не істинне і не хибне, а тому порушує закон виключенння третього. Парадокс виникає через те, що висловлювання посилається саме на себе, так само, як і всі решта парадоксальні твердження (наприклад: “Перукар стриже всіх мешканців села, крім тих, хто стриже себе сам”).

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

Правило підстановки . Нехай — еквівалентність, а — формула, записана як функція від змінної Р. Тоді і — теж еквівалентності.

Суть правила підстановки така: замість змінної можна скрізь, де вона входить у формулу, підставити будь-яку ту саму формулу чи іншу змінну.

Приклад 6.9. Наведемо приклад використання правила підстановки. Відповідно до закону імплікації формула є еквівалентністю. Розглянемо формулу . Нехай , . Тоді: , . Відповідно до закону підстановки, теж є еквівалентністю.

Правило транзитивності. Якщо і — еквівалентності, то теж еквівалентність і, отже, формула еквівалентна формулі .

Це правило можна подати формулою , яка є тавтологією.

Приклад 6.10. Покажемо, що є еквівалентністю. Послідовно застосовуючи закони еквівалентності (їх будемо вказувати в дужках), матимемо:

(закон імплікації);

(закон комутативності);

(закон заперечення);

(закон імплікації).

Відповідно до правила транзитивності маємо, що .

Зауважимо, що для спрощення запису викладок при переході до еквівалентної формули можна замість знака еквівалентності ( ) використовувати знак рівності ( ) і записувати все в один рядок. Тоді в нашому прикладі послідовність еквівалентних перетворень матиме такий вигляд:

.

Приклад 6.11. Доведемо, що є законом еквівалентності, використовуючи інші закони еквівалентності, а також правила підстановки (замість змінної А підставимо константу І) і транзитивності:

(закон виключення третього);

(закон де Моргана);

(закон заперечення);

(закон комутативності);

(закон суперечності).

Отже, .

Приклад 6.12. Доведемо закон суперечності , використовуючи інші закони:

(закон де Моргана);

(закон заперечення);

(закон комутативності);

(закон виключення третього);

(результат прикладу 6.11).

Отже, .

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

Використання закону імплікації (подання імплікації через диз’юнкцію) часто дає можливість спростити процес виведення еквівалентностей.

Приклад 6.13. Використовуючи закони еквівалентності, покажемо, що формула є тавтологією:

(закон імплікації);

(закон де Моргана);

(закон заперечення);

(закон асоціативності);

(закон імплікації);

(закон заперечення);

(закони асоціативності,

комутативності, спрощення);

(закон виключення третього);

(закон спрощення);

Отже, .