Елементи логіки

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

Розглянемо два різновиди формул, що мають певні структурні особливості. Саме структура цих формул зумовлює їх використання у таких важливих галузях застосування математичної логіки, як автоматизація доведення тверджень і логічне програмування.Закони (2) стверджують асоціативність зв'язок кон'юнкції. Звідси формула вигляду ((…((A1A2)A3)…)An) має еквівалентний запис A1A2A3…An. Формула в такому записі називається кон'юнкцією формул A1, A2, A3, …, An.

Означення. Елементарною кон'юнкцією називається кон'юнкція формул, кожна з яких є або пропозиційною змінною, або запереченням такої. Наприклад, A1A2A3.

Означення. Диз'юнктивною нормальною формою (скорочено ДНФ) називається диз'юнкція елементарних кон'юнкцій. Наприклад, формула 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) (3)

 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 (5)

 ABCACB

За законами (2) зв'язки диз'юнкції також асоціативні, звідки формули ((…((A1A2) A3) …)An) і A1A2A3…An також є еквівалентними. Остання з них називається диз'юнкцією формул A1, A2, A3, …, An.

Означення. Елементарною диз'юнкцією називається диз'юнкція формул, кожна з яких є або пропозиційною змінною, або запереченням такої. Наприклад, A1A2A3.

Означення. Кон'юнктивною нормальною формою (скорочено КНФ) називається кон'юнкція елементарних диз'юнкцій. Наприклад, формула (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):