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

Проблема вирішення в логіці висловлювань розглядається як відповідь на питання, чи існує алгоритм, який за скінченне число кроків дає змогу визначити тип будь-якої формули алгебри висловлювань. В алгебрі висловлювань ця проблема розв’язується позитивно. Зокрема можна запропонувати способи : 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.Елементарною кон’юнкцією (диз’юнкцією) називається кон’юнкція ( диз’юнкція) скінченного числа попарно різних логічних змінних, узятих із запереченням або без нього.

Наприклад, Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru є елементарними кон’юнкціями, Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru є елементарними диз’юнкціями, а Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru або Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru вже такими не будуть.

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

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

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

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

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

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

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

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

1. Усунути логічні зв’язки “Імплікація” та “Еквіваленція” за формулами Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru .

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

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

Приклад 1.5.2.Шляхом перетворень одержати для формули α = А Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru В рівносильні їй ДНФ та КНФ.

Розв’язання. . Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru - КНФ.

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

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

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

Теорема 1.5.1. Кожна із множин операцій { Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru , Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru , Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru }, { Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru , Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru }, { Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru , Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru }, { Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru , Þ} є функціонально повною.

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

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

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

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

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

Доведення. Нехай задана функція логіки висловлювань подана таблицею істинності з Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru рядками, де кожен рядок містить деякий розподіл значень істинності для набору змінних. У кожному рядку і = Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru , Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru , … , Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru таблиці істинності атоми і сама Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru може набувати значення X або I. На наборах атомів в і-му рядку, що надають функції значення І, складемо елементарну кон’юнкцію Xi1ÙXi2Ù…ÙXin , де Xij = Aij, якщо Aij є І, Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru , якщо 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 записуємо елементарні кон’юнкції Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru А1 Ù Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru А2 , Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru А1 Ù А2 , А1 Ù Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru А2 , які зв’язуємо між собою диз’юнкцією. Одержимо ДНФ:

f = (ØА1ÙА2)Ú(А1ÙØА2) Ú (ØА1ÙØА2).

КНФ для даної функції - f = Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru А1 Ú Проблема вирішення в алгебрі висловлювань. Функціональна повнота множини логічних операцій - student2.ru А2 .

Наши рекомендации