Цей простий метод може бути застосований для перевірки рівносильності або нерівносильності будь-яких формул A і B довільної складності. Відтак, на перший погляд може здатися, що проблема встановлення рівносильності або нерівносильності формул алгебри висловлень є розв’язаною і до того ж найпростішим чином і отже, всі подальші дослідження у цьому напрямку є непотрібними.
Наведемо лише два міркування, які демонструють, що перше враження є обманливим.
Перше міркування пов’язане з тим, що коли кількість пропозиційних змінних у досліджуваних формулах є значною, то застосування зазначеного простого методу може стати практично нездійсненним. Адже, вже для 30 змінних необхідно випробувати по більш ніж 109 наборів значень змінних для кожної формули. Це тільки кількість кроків загальної процедури, а крім того, слід врахувати трудомісткість обчислення значень функцій інстинності даних формул на кожному з наборів.
По-друге, - і це міркування, певно, є важливішим, - в алгебрі висловлень у більшості випадків цікавляться не рівносильністю двох будь-яких заданих формул, а рівносильністю нескінченної множини пар формул. Потрібні твердження, згідно яких усі формули певного типу є рівносильними відповідно формулам певного іншого типу. Якщо множини формул обох цих типів є нескінченними, то подібні твердження, очевидно, не можуть бути встановлені жодним методом, що спирається на побудову таблиць інстинності, а потребують загальних міркувань.
Зокрема, однією з основних проблем алгебри висловлень є проблема опису класу всіх тавтологій (тобто тотожно істинних формул), яка носить назву проблеми розв’язності. Простішим варіантом цієї проблеми є така: вказати правило перевірки скінченним числом дій тотожної істинності певної формули.
Проблема розв’язності займає важливе місце в математичній логіці. До проблеми розв’язності зводиться багато різних задач математичної логіки.
Наприклад, до проблеми розв’язності може бути зведена обговорювана вище проблема перевірки рівносильності заданих формул A і B.
Легко довести таку теорему.
Теорема 1. Формули алгебри висловлень A і B рівносильні тоді і тільки тоді, коли формула ((A®B)Ù(B®A)) є тавтологією.
З метою скорочення запису формул, подібних до формули з наведеної теореми, до сигнатури алгебри висловлень вводять додаткову операцію, що позначається ~ і означається так: (A~B) є скороченим записом формули ((A®B)Ù(B®A)).
Отже, останню теорему можна сформулювати так.
Формули A і B рівносильні тоді і тільки тоді, коли формула (A~B) є тотожно істинною.
Разом з відношенням рівносильності на множині формул алгебри висловлень, яке є, як зазначалось, відношенням еквівалентності, розглядають також деякі інші відношення, що являють собою інтерес для логіки та її застосувань. Серед останніх виділимо відношення логічного слідування, яке є відношенням часткового порядку на множині формул алгебри висловлень.
Нехай 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) , що випливає з відповідних таблиць істинності (див.табл.4).
Таблиця 4
| xyz | AB |
| 0 0 00 0 10 1 00 1 1 1 0 0 1 0 1 1 1 01 1 1 | 0 00 10 01 10 11 10 11 1 |
Очевидно, що дві формули A і B є рівносильними тоді і тільки тоді, коли кожна з них є логічним слідуванням іншої, тобто A=B тоді і тільки тоді, коли AÞB і BÞA.
З означення випливає також, що будь-яка формула є логічним слідуванням тотожно хибної формули, а тотожно істинна формула (тавтологія) є логічним слідуванням довільної формули.
Проблема перевірки чи є формула B логічним слідуванням іншої заданої формули A також може бути зведена до проблеми розв’язності для певної формули алгебри висловлень.
Теорема 2. Формула B(p1,p2,...,pn) є логічним слідуванням формули A(p1,p2,...,pn) тоді і тільки тоді, коли тотожно істинною є формула (A®B).
Відзначимо, що алгебра висловлень, або, як її іноді називають, логіка висловлень є надто бідною теорією для опису логічного апарату математичних міркувань. Типи логічних міркувань, основаних на тотожно істинних формулах алгебри висловлень, далеко не вичерпують логічних законів, які використовуються математикою, не кажучи вже про логічні міркування в інших науках.
При побудові алгебри висловлень вихідними об’єктами були елементарні висловлення, що мали певне значення істинності: 1 або 0. Нові об’єкти - складені висловлення, що також мали певне значення істинності, - будувались за чітко визначеними правилами утворення формул. При цьому значення істинності або хибності складеного висловлення визначалось за таблицями істинності відповідних операцій алгебри висловлень. Означені згодом поняття рівносильності і логічного слідування формул були введені змістовно, тобто з використанням значень істинності формул залежно від значень їхніх змінних. Така побудова логічного числення або теорії називається змістовно-алгоритмічною, або табличною.
Iншим методом побудови логічного числення є описаний вище формально-аксіоматичний метод. Саме за допомогою цього методу побудовано так зване числення висловлень.