Нормальні форми логічних формул

Попередньою формою логічної формули називається формула, яка рівносильна даній і містить лише знаки кон’юнкції, диз’юнкції та заперечення, причому останнє відноситься лише до однієї простої змінної.

Теорема. Будь-яку логічну формулу можна звести до попередньої форми.

Справді, імплікації та еквіваленції в логічній формулі можна позбутися, використовуючи такі рівносильності:

AÞB º

.

Позбутися знаків заперечення, що відносяться до декількох простих змінних, зв’язаних знаками кон’юнкції та диз’юнкції, можна, скориставшись законами де Моргана:

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

Проілюструємо на прикладі:

Попробуйте самостійно звести до попередньої форми такі логічні формули:

Елементарною кон’юнкцією називається кон’юнкція простих висловлень чи їх заперечень, причому кожне просте висловлення зустрічається лише один раз.

Наприклад: - елементарні кон’юнкції,

- не елементарні кон’юнкції.

Логічна формула, рівносильна даній, яка є диз’юнкцією елементарних кон’юнкцій називається диз’юнктивною нормальною формою (ДНФ) даної логічної формули.

Теорема. Будь-яку не тотожно хибну логічну формулу можна звести до ДНФ.

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

Проілюструємо:

Зауважимо, що одна і та ж логічна формула може мати декілька різних ДНФ. Розглянемо і які обидві є ДНФ формули .

Для уніфікації ДНФ використовують досконалу диз’юнктивну нормальну форму.

Конституентою одиниці від простих висловлень Х₁, Х₂, … Х_n називається елементарна кон’юнкція, яка містить всі ці прості висловлення або їх заперечення.

Завдання. Доведіть, що конституента одиниці приймає значення істинності рівне одиниці лише при одному наборі істинності простих висловлень.

Завдання. Запишіть всі конституенти одиниці від трьох простих висловлень. Яка кількість різних конституент одиниці від n простих висловлень?

 

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

Теорема. Будь-яку не тотожньо хибну логічну формулу можна звести до ДДНФ.

Доведення. Згідно з попередньою теоремою будь-яку не тотожньо хибну логічну формулу можна звести до ДНФ. Нехай одержана ДНФ є формулою від простих висловлень Х₁, Х₂, … Х_n. Якщо якась із елементарних кон’юнкцій не містить Х_і, то, скориставшись рівносильними перетвореннями:

,

отримаємо елементарні кон’юнкції, в яких зустрічаються всі прості висловлення Х₁, Х₂, … Х_n.

Скориставшись індемпотентністю диз’юнкції, позбудемося однакових доданків (часто формули, які утворюють диз’юнкцію називають доданками, як, до речі, і складові кон’юнкції називають множниками). В результаті цих дій отримаємо ДДНФ даної формули.

Проілюструємо на прикладі.

Нехай логічна формула звелась до попередньої форми, що задається формулою:

Знайдемо її ДНФ. Для цього скористаємось дистрибутивним законом кон’юнкції по відношенню до диз’юнкції, законами протиріччя, поглинання. Маємо: