Логічне слідування на базі алгебри висловлень

Разом з відношенням рівносильності на множині формул алгебри висловлень, яке є відношенням еквівалентності, розглядають також

деякі інші відношення, що являють собою інтерес для логіки та її застосувань. Серед останніх виділимо відношення логічного слідування,

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

Нехай A(p1,p2,...,pn) і B(p1,p2,...,pn) - дві формули алгебри висловлень. Будемо говорити, що формула B(p1,p2,...,pn) є логічним

слідуванням формули A(p1,p2,...,pn), якщо B приймає значення 1 для всіх тих наборів значень пропозиційних змінних, для яких формула A істинна (тобто приймає значення 1); позначатимемо це A(B.

Це означає, що множина наборів значень змінних, для яких істинна формула A, є підмножиною множини наборів значень змінних, для яких істинна формула B, що є логічним слідуванням формули A.

Приклад 5.1. Формула B(x,y,z)=(xÚz) є логічним слідуванням формули A(x,y,z)=((xÚy)Ùz), що випливає з відповідних таблиць істинності

Очевидно, що дві формули A і B є рівносильними тоді і тільки тоді, коли кожна з них є логічним слідуванням іншої, тобто A=B тоді і тільки тоді, коли AÞB і BÞA.

З означення випливає також, що будь-яка формула є логічним слідуванням тотожно хибної формули, а тотожно істинна формула (тавтологія) є логічним слідуванням довільної формули.

Проблема перевірки чи є формула B логічним слідуванням іншої заданої формули A також може бути зведена до проблеми розв’язності для певної формули алгебри висловлень

Теорема 2. Формула B(p1,p2,...,pn) є логічним слідуванням формули A(p1,p2,...,pn) тоді і тільки тоді, коли тотожно істинною є формула (A®B).

8. Проблема розв’язуванності в алгебрі висловлень.

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

Метод, що описаний за допомогою системи вказівок, які необхідно виконати у певній послідовності для одержання з умови задачі за скінчене число кроків її розв’язку, називають алгоритмом. Задача знаходження алгоритму для розв’язку даного класу задач отримала назву проблеми розв’язуваності даного класу задач.

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

Прикладом проблеми розв’язуваності може бути задача побудови алгоритму, який дає змогу для кожної формули з’ясувати, чи є вона здійсненною (чи не є вона ТІ або ТХ), тобто чи виражає дана формула деякий логічний закон чи ні. Проблема розв’язуваності для даної задачі розв’язувана.

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

Наведений алгоритм, звичайно, дає принципове вирішення проблеми розв’язуваності. Проте, за умови великої кількості змінних він практично не здійснений через величезне число можливих наборів значень змінних (2ⁿ).

Існує інший алгоритм, що ґрунтується на зведенні формул до нормальної форми. Якщо у процесі такого зведення формула не перетворилася на ТІ або ТХ, то це свідчить про її здійсненність.

У якості нормальних форм використовуються досконалі диз’юнктивні (ДДНФ) та кон’юнктивні (ДКНФ) нормальні форми.