Page 59 - 4570

58

2. Використати закон подвійного заперечення та закони де Моргана для
перенесення знака заперечення безпосередньо до атомів.
3. Використати відповідні закони дистрибутивності.
Приклад 2.16. Шляхом перетворень одержати для формули α = А ~ В
рівносильні їй ДНФ та КНФ.
Розв’язання.
  (A  B )(B  A ) (A B  )(B  ) A – КНФ.

  (A B )(B  ) A  AB  BB  AA  BA  AB  AB – ДНФ.
Інший шлях перетворення будь-якої формули алгебри висловлювань до
нормальних форм – це побудова спочатку для даної формули таблиці
істинності, а потім за таблицею складаємо ДДНФ або ДКНФ.

3. Функціональна повнота множини логічних операцій
Означення 2.18. Деяка множина операцій алгебри висловлювань
називається функціонально повною, якщо довільна формула алгебри
висловлювань рівносильна формулі, в яку входять лише операції із цієї
системи.
Теорема 2.1. Кожна із множин операцій {, , }, {, }, {, }, {,

} є функціонально повною.
Доведення. Оскільки для довільних формул α і β алгебри висловлювань
характерні рівносильності:
      ,        ,         ,
то достатньо довести, що перша з означених множин у теоремі є функціонально
повною – {, , }, а всі інші автоматично стають функціонально повними за
рівносильностями.
Формально це вже доведено, оскільки за алгоритмом ми зможемо
перетворити будь-яку формулу алгебри висловлювань у ДНФ або КНФ, для
сполучення атомів у яких застосовуються лише операції з множини {, , }.
Застосуємо інше доведення, використовуючи таблиці істинності і тим самим
заодно доведемо ще одну теорему.

Теорема 2.2. Кожна функція логіки висловлювань є функцією істинності
деякої ДНФ (КНФ).
Доведення. Нехай задана функція логіки висловлювань подана таблицею
n
істинності з 2 рядками, де кожен рядок містить деякий розподіл значень
n
істинності для набору змінних. У кожному рядку і = 1, 2, . . ., 2 таблиці
істинності атоми і сама f може набувати значення T або F. На наборах атомів
i
в і-му рядку, що надають функції значення T, складемо елементарну

кон’юнкцію X i1X i2…X in, де X ij = A ij, якщо A ij є T, X  A , якщо A ij є F.
i j i j
З’єднаємо всі елементарні кон’юнкції операцією диз’юнкції. Покажемо, що
одержана конструкція є шуканою ДНФ.
За означенням кожна конституента одиниці лише на одному, єдиному для
неї наборі атомів набуває значення T, тобто тільки для наборів і-го рядка, а на
всіх інших рядках вона набуває значення F. Тому кожний кон’юнктивний