Рівносильність формул алгебри висловлень

Дві формули A і B алгебри висловлень називаються рівносильними, якщо їм відповідає та сама функція істинності. Рівносильність формул A і B позначають за допомогою знака = (º або «): записують A=B (AºB або A«B).

Очевидно, що відношення рівносильності на множині формул є відношенням еквівалентності, тому часто це відношення називають еквівалентністю.

Наведемо приклади пар рівносильних формул:

(A®B)=((ØA)ÚB), (Ø(AÚB))=((ØA)Ù(ØB)), (Ø(AÙB))=((ØA)Ú(ØB)),

(AÙ(BÚC))=((AÙB)Ú(AÙC)), (AÚ(BÙC))=((AÚB)Ù(AÚC))

тощо.

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

Цей простий метод може бути застосований для перевірки рівносильності або нерівносильності будь-яких формул 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).

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

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

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

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

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

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

Булеві функції. Питання функціональної повноти.

Булева функція (або логічна функція, або функція алгебри логіки) від n змінних - в дискретної математики відображення B n → B, де B = {0,1} - булево безліч. Елементи булева безлічі 1 і 0 зазвичай інтерпретують як логічні значення "істинно" і "помилково", хоча в загальному випадку вони розглядаються як формальні символи, що не несуть певного сенсу. Невід'ємне ціле число n називають арністю або місцевістю функції, в разі n = 0 булева функція перетворюється в булеву константу. Елементи декартова твори B n називають булевими векторами. Безліч всіх булевих функцій від будь-якого числа змінних часто позначається P 2, а від n змінних - P 2 (n). Булеві функції названі так за прізвищем математика Джорджа Буля. Кожна булева функція арності n повністю визначається завданням своїх значень на своїй області визначення, тобто на всіх булевих векторах довжини n. Число таких векторів дорівнює 2 n. Оскільки на кожному векторі булева функція може приймати значення або 0, або 1, то кількість всіх n-арних булевих функцій дорівнює 2 лютого n. Тому в цьому розділі розглядаються тільки найпростіші і найважливіші булеві функції. Те, що кожна булева функція задається кінцевим масивом даних, дозволяє представляти їх у вигляді таблиць. 1.1. Нульарние функції

При n = 0 кількість булевих функцій зводиться до двох 2 2 0 = 2 1 = 2, перша з них тотожно дорівнює 0, а друга 1. Їх називають булевими константами - тотожний нуль і тотожна одиниця.

1.2. Унарні функції

При n = 1 число булевих функцій дорівнює 2 2 1 = 2 2 = 4. Визначення цих функцій міститься в наступній таблиці.

Таблиця значень булевих функцій від однієї змінної: x 0 x̅ x 1

0 0 1 0 1

1 0 0 1 1

Назви булевих функцій від однієї змінної: Позначення Назва

0 тотожний нуль, тотожна брехня, тотожне "НІ"

x̅, x, x ' заперечення, логічне "НІ", "НЕ", "НІ", "NOT" (англ.), "NO" (англ.)

x тотожна функція, логічне "ТАК", "YES" (англ.)

1 тотожна одиниця, тотожна істина, тотожне "ТАК", тавтологія.

Функціональна повнота

Визначення. Множина функцій алгебри логіки А називається повною системою (в Р₂), якщо будь-яку функцію алгебри логіки можна виразити формулою над А.

Теорема 1[1, ст.6]. Система А={ } є повною.

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

Лема 1[1, ст.6]. Якщо система А – повна, і будь-яка функція може бути виражена формулою над іншою системою В, то В – теж повна система.

Доведення. Розглянемо довільну функцію алгебри логіки і дві системи функцій А={g₁, g₂,…} і B={h₁, h₂,…}. Оскільки система А повна, функція може бути виражена у вигляді формули над нею , де , тобто функція представляється у вигляді , що означає що вона може бути представлена формулою над В. Перебираючи таким чином всі функції алгебри логіки, отримаємо, що система В також повна. Лема доведена.

Теорема 2[1, ст.6]. Такі системи є повними в Р₂

1. ;

2. ;

3. ;

4.

Доведення.

1. Відомо (теорема 1), що система А= повна. Покажемо, що система В= повна. З закону де Моргана отримуємо, що , тобто кон’юнкція виражається через диз’юнкцію і заперечення, і всі функції системи А виражаються формулами над системою В. Система В повна (лема 1).

2. Аналогічно пункту 1: = із леми 1 випливає, що вираз пункту 2 є правильний.

3. згідно леми 1 система повна.

4. згідно леми 1 система повна.

5.