Нормальні форми висловлень

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

Закони (2) стверджують асоціативність зв'язок кон'юнкції. Звідси формула вигляду ((…((A ₁Ù A ₂)Ù A ₃)Ù…)Ù A_n) має еквівалентний запис A ₁Ù A ₂Ù A ₃Ù…Ù A_n. Формула в такому записі називається кон'юнкцією формул A ₁, A ₂, A ₃, …, A_n.

Означення. Елементарною кон'юнкцією називається кон'юнкція формул, кожна з яких є або пропозиційною змінною, або запереченням такої. Наприклад, A ₁ÙØ A ₂Ù A ₃.

Означення. Диз'юнктивною нормальною формою (скорочено ДНФ) називається диз'юнкція елементарних кон'юнкцій. Наприклад, формула A Ù B Ú B Ù C Ú D. Зауважимо, що її структуру краще видно в записі A × B Ú B × C Ú D або в записі .

Будь-яка формула може бути перетворена до ДНФ. Ми не будемо доводити це твердження, а лише опишемо потрібні рівносильні перетворення. Застосуванням законів (13) і (12) можна позбутися зв'язок «і ®, тобто перетворити формулу до рівносильної, у якій є лише зв'язки Ø, Ú і Ù. Далі, якщо у формулі є заперечення диз'юнкцій чи кон'юнкцій, то вони "спускаються" до пропозиційних змінних застосуванням законів Де Моргана (6). Далі, якщо у формулі є множники-диз'юнкції, то їх можна позбутися застосуванням першого з законів дистрибутивності (3). В результаті всі множники у кон'юнкціях формули є елементарними, і вона являє собою ДНФ. Застосування законів (1), (2), (4), (5), (7)-(10) може скоротити цей процес.

Приклад. Розглянемо перетворення (A ® B)«(C ® B). Після знаків º у дужках указано номери законів, застосованих при черговому перетворенні:

(A ® B)«(B ® C) º^{(13, 12)}

º(Ø(Ø A Ú B)Ú(Ø C Ú B))×(Ø(Ø C Ú B)Ú(Ø A Ú B)) º^{(6, 7, 2)}

º (A ×Ø B ÚØ C Ú B)×(Ø B × C ÚØ A Ú B) º⁽³⁾

º A ×Ø B ×Ø B × C Ú A ×Ø B ×Ø A Ú A ×Ø B × B ÚØ C ×Ø B × C ÚØ C ×Ø A ÚØ C × B Ú

Ú B ×Ø B × C Ú B ×Ø A Ú B × B º^{(1, 4, 9, 8)}

º A ×Ø B × C ÚØ A ×Ø C Ú B ×Ø C Ú B ×Ø A Ú B º⁽⁵⁾

º A ×Ø B × C ÚØ A ×Ø C Ú B

За законами (2) зв'язки диз'юнкції також асоціативні, звідки формули ((…((A ₁Ú A ₂)Ú A ₃)Ú …)Ú A_n) і A ₁Ú A ₂Ú A ₃Ú…Ú A_n також є еквівалентними. Остання з них називається диз'юнкцією формул A ₁, A ₂, A ₃, …, A_n.

Означення. Елементарною диз'юнкцією називається диз'юнкція формул, кожна з яких є або пропозиційною змінною, або запереченням такої. Наприклад, A ₁ÚØ A ₂Ú A ₃.

Означення. Кон'юнктивною нормальною формою (скорочено КНФ) називається кон'юнкція елементарних диз'юнкцій. Наприклад, формула (A Ú B)Ù(Ø B Ú C ÚØ D), яку можна подати також у вигляді .

Будь-яка формула перетворюється до рівносильної їй КНФ з використанням тих самих законів, тільки замість першого з законів дистрибутивності (3) вживається другий: A Ú(B Ù C) º (A Ú B)Ù(A Ú C).

Приклад. Розглянемо перетворення формули (A ® B)«(C ® B) після одержання формули (A ×Ø B ÚØ C Ú B)×(Ø B × C ÚØ A Ú B):