Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій

Проблема вирішення в логіці висловлювань розглядається як відповідь на питання, чи існує алгоритм, який за скінченне число кроків дає змогу визначити тип будь-якої формули алгебри висловлювань. В алгебрі висловлювань ця проблема розв’язується позитивно. Зокрема можна запропонувати способи: 1) Складанням таблиць істинності формул; 2) Застосуванням методу міркувань від супротивного; 3) Зведенням формул до нормальних форм.

Зрозуміло, що таблиця істинності для будь-якої формули від n висловлюваних змінних може бути побудована за скінченне число кроків і визначить тип формули. Але число рядків таблиці (2ⁿ) може виявитися завеликим при значній кількості атомів, що становлять формулу. Тому на практиці в такому разі краще застосувати метод 2 або 3.

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

А. Якщо припустимо, що для деякого набору значень атомів формула α(A₁, A₂, …, A_n) набуває значення “ Хибність ”, а після аналізу формули прийдемо до суперечності, то відносно формули α робимо висновок, що вона є тавтологією.

Б. Якщо припустимо, що для деякого набору значень атомів формула α(A₁, A₂,…, A_n) набуває значення “Істина” і прийдемо до суперечності, то є суперечною.

В. Якщо не одержимо суперечності ні при припущенні А), ні при припущенні Б), то робимо висновок, що формула α є нейтральною.

Приклад 1.5.1. Визначити тип формули

α = ((A Þ B) ÞA) ÞA.

Розв’язання. Припустимо, що α не є тотожно істинною формулою. Тоді повинен існувати такий набір значень атомів, на якому вона набуває значення “ Хибність ”. Формула α є імплікацією. Значення “ Хибність ” можливе лише за умови, що (AÞB)ÞA набуває на цьому наборі значення “ Істина ”, а А – “ Хибність ”. Тоді випливає, що AÞB повинне набувати значення “ Хибність ”, що неможливо, оскільки А – “ Хибність ”. Отже, α є тавтологією.

Перед тим як розв’язувати проблему вирішення, інколи корисно спочатку перетворити формулу логіки висловлювань за допомогою рівносильних перетворень до деякої стандартної форми. Такими формами є диз’юнктивна нормальна форма (ДНФ) та кон’юнктивна нормальна форма (КНФ).

Зафіксуємо деяку множину Х логічних змінних.

Означення 1.5.1. Елементарною кон’юнкцією (диз’юнкцією) називається кон’юнкція (диз’юнкція) скінченного числа попарно різних логічних змінних, узятих із запереченням або без нього.

Наприклад, є елементарними кон’юнкціями, є елементарними диз’юнкціями, а або вже такими не будуть.

Означення 1.5.2. Елементарні кон’юнкції, що містять усі змінні з Х, будемо називати конституентами одиниці над Х, а елементарні диз’юнкції, які задовольняють подібну властивість, – конституентами нуля над Х.

Неважко бачити, що кожна конституента одиниці (відповідно, конституента нуля) лише на одному, єдиному для неї наборів атомів набуває значення “Істина” (відпо-

відно значення “Хибність”).

Означення 1.5.3. Диз’юнктивною (кон’юнк-тивною) нормальною формою називається диз’юнкція (кон’юнкція) скінченного числа попарно різних елементарних кон’юнкцій (диз’юнкцій).

Наприклад, є ДНФ, – КНФ. Надалі елементарні кон’юнкції в ДНФ будемо називати доданками, а елементарні диз’юнкції в КНФ – множниками.

Означення 1.5.4. ДНФ (КНФ)називається досконалою, якщо всі її доданки (множники) є конституентами одиниці (нуля) над множиною всіх її атомів.

Досконалі форми будемо відповідно позначати ДДНФ та ДКНФ.

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

1. Усунути логічні зв’язки “Імплікація” та “Еквіваленція” за формулами .

2. Використати закон подвійного заперечення та закони де Моргана для перенесення знака заперечення безпосередньо до атомів.

3. Використати відповідні закони дистрибутивності.

Приклад 1.5.2. Шляхом перетворень одержати для формули α = А В рівносильні їй ДНФ та КНФ.

Розв’язання.. - КНФ.

- ДНФ.

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

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

Теорема 1.5.1. Кожна із множин операцій { , , }, { , }, { , }, { , Þ} є функціонально повною.

Доведення. Оскільки для довільних формул α і β алгебри висловлювань характерні рівносильності:

,

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

Формально це вже доведено, оскільки за алгоритмом ми зможемо перетворити будь-яку формулу алгебри висловлювань у ДНФ чи КНФ (див. приклад 1.5.2), для сполучення атомів у яких застосовуються лише операції з множини { , , }. Застосуємо інше доведення, використовуючи таблиці істинності і тим самим заодно доведемо ще одну теорему.

Теорема 1.5.2. Кожна функція логіки висловлювань є функцією істинності деякої ДНФ (КНФ).

Доведення. Нехай задана функція логіки висловлювань подана таблицею істинності з рядками, де кожен рядок містить деякий розподіл значень істинності для набору змінних. У кожному рядку і = , , …, таблиці істинності атоми і сама може набувати значення X або I. На наборах атомів в і-му рядку, що надають функції значення І, складемо елементарну кон’юнкцію X_i1ÙX_i2Ù…ÙX_in, де X_ij = A_ij, якщо A_ij є І, , якщо A_ij є Х. З’єднаємо всі елементарні кон’юнкції операцією диз’юнкції.

Покажемо, що одержана конструкція є шуканою ДНФ.

За означенням 1.5.2 кожна конституента одиниці лише на одному, єдиному для неї наборі атомів набуває значення І, тобто тільки для наборів і-го рядка, а на всіх інших рядках вона набуває значення Х. Тому кожний кон’юнктивний одночлен у побудованій ДНФ надасть значення І лише в своєму рядку. Отже, побудована таким чином ДНФ є рівносильною до функції поданою таблицею істинності і теорему 1.5.2 доведено, а одночасно доведено і теорему 1.5.1. Для побудови КНФ дії аналогічні.

Приклад 1.5.3. Утворити ДНФ та КНФ для функції логіки висловлювань, що подана таблицею істинності.

А1	А2	f
X	X	I
X	I	I
I	X	I
I	I	X

Розв’язання. Для рядків таблиці зі значенням І для f записуємо елементарні кон’юнкції А₁ Ù А₂ , А₁ Ù А₂ , А₁ Ù А₂ , які зв’язуємо між собою диз’юнкцією. Одержимо ДНФ:

f = (ØА₁ÙА₂)Ú(А₁ÙØА₂) Ú (ØА₁ÙØА₂).

КНФ для даної функції - f = А₁ Ú А₂.