Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій
Проблема вирішення в логіці висловлювань розглядається як відповідь на питання, чи існує алгоритм, який за скінченне число кроків дає змогу визначити тип будь-якої формули алгебри висловлювань. В алгебрі висловлювань ця проблема розв’язується позитивно. Зокрема можна запропонувати способи : 1) Складанням таблиць істинності формул; 2) Застосуванням методу міркувань від супротивного; 3) Зведенням формул до нормальних форм.
Зрозуміло, що таблиця істинності для будь-якої формули від n висловлюваних змінних може бути побудована за скінченне число кроків і визначить тип формули. Але число рядків таблиці (2n) може виявитися завеликим при значній кількості атомів, що становлять формулу. Тому на практиці в такому разі краще застосувати метод 2 або 3.
Аналіз формул із застосуванням методу міркувань від супротивного базується на таких умовиводах:
А. Якщо припустимо, що для деякого набору значень атомів формула α(A1, A2, …, An) набуває значення “ Хибність ”, а після аналізу формули прийдемо до суперечності, то відносно формули α робимо висновок, що вона є тавтологією.
Б. Якщо припустимо, що для деякого набору значень атомів формула α(A1, A2,…, An) набуває значення “Істина” і прийдемо до суперечності, то є суперечною.
В. Якщо не одержимо суперечності ні при припущенні А) , ні при припущенні Б), то робимо висновок, що формула α є нейтральною.
Приклад 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. На наборах атомів в і-му рядку, що надають функції значення І, складемо елементарну кон’юнкцію Xi1ÙXi2Ù…ÙXin , де Xij = Aij, якщо Aij є І, 
, якщо Aij є Х. З’єднаємо всі елементарні кон’юнкції операцією диз’юнкції.
Покажемо, що одержана конструкція є шуканою ДНФ.
За означенням 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 записуємо елементарні кон’юнкції А1 Ù А2 , А1 Ù А2 , А1 Ù А2 , які зв’язуємо між собою диз’юнкцією. Одержимо ДНФ:
f = (ØА1ÙА2)Ú(А1ÙØА2) Ú (ØА1ÙØА2).
КНФ для даної функції - f = А1 Ú А2 .