Нормальные формы

В алгебре высказываний используют две нормальные фор­мы: дизъюнктивную и конъюнктивную нормальные формы формулы (ДНФ и КНФ).

ДНФ формулы есть формула, равносильная исходной формуле логики высказыванийи записанная в виде дизъюнкции элементарных конъюнкций переменных, т.е.

F = K ₁Ú K ₂Ú K ₃Ú..., где K_i = A & B & C &....

КНФ формулы есть формула, равносильная исходной формуле логики высказываний и записанная в виде конъюнкции элементарных дизъюнкций переменных, т.е.

F = D ₁ & D ₂ & D ₃ &..., где D_i = A Ú B Ú C Ú....

Наибольшее распространение в логике высказываний по­лучили формулы вида КНФ, элементарные дизъюнкции которых D_i принято называть дизъюнктами, а члены каждого дизъюнкта A, B, C – атомами.

Пример 1.13.

Указать, в каких нормальных формах находятся следующие формулы логики высказываний.

a) A – ДНФ и КНФ

b) (A Ú B)& C – КНФ

c) A Ú Ø B Ú Ø C – ДНФ и КНФ

d) (A Ú B)&(Ø A Ú C) – КНФ

e) A Ú B & C – ДНФ

f) A & Ø B & Ø C – ДНФ и КНФ

g) A & B Ú Ø A & C – ДНФ

Для каждой формулы логики высказываний функции F имеется равносильная ей дизъюнктивная нормальная форма (ДНФ) и конъюнктивная нормальная форма (КНФ).

Алгоритм приведения формул логики высказываний к ДНФ (КНФ).

Шаг 1. Все подформулы F вида A É B (т.е. содержащие импликацию) заменяем на Ø A Ú B или на Ø(A &Ø B) (в соответствии с равносильностью 12 раздела 1.3).

Шаг 2. Все подформулы F вида A ~ B (т.е. содержащие эквивалентность) заменяем на (A & B) Ú (Ø A &Ø B) или на (A ÚØ B)&(Ø A Ú B) (в соответствии с равносильностью 13).

Шаг 3. Все отрицания, стоящие над сложными подформулами, опускаем по законам де Моргана (в соответствии с равносильностями 4, 19, 20).

Шаг 4. Устраняем все двойные отрицания над формулами (в соответствии с равносильностью 8).

Шаг 5. Осуществляем раскрытие всех скобок по закону дистрибутивности конъюнкции относительно дизъюнкции для ДНФ (в соответствии с равносильностями 3а и 17) или по закону дистрибутивности дизъюнкции относительно конъюнкции для КНФ (в соответствии с равносильностями 3б и 18).

Шаг 6. Для получения более простой формулы целесообразно использовать равносильности 5, 6, 7, 9, 10, 11.

Пример 1.14.

Дана формула F = Ø(A & B)&(A Ú B).

Привести формулу к виду ДНФ:

1) F = (Ø A ÚØ B)&(A Ú B);

2) F = (Ø A & A) Ú (Ø A & B) Ú (Ø B & A) Ú (Ø B & B);

3) F = (Ø A & B) Ú (Ø B & A).

Пример 1.15.

Дана формула F = (A É (B ÚØ C)) É D.

Привести формулу к виду КНФ:

1) F = (Ø A Ú(B ÚØ C)) É D;

2) F = Ø(Ø A Ú(B ÚØ C))Ú D;

3) F = (A &(Ø B)& C)Ú D;

4) F = (A Ú D)&(Ø B Ú D)&(C Ú D).

Если каждая элементарная конъюнкция (или элементарная дизъюнкция) формулы содержат символы всех переменных, то такая формула называется совершенной. Есть совершенные дизъюнктивные нормальные формы формулы (СДНФ) и совершенные конъюнктивные нормальные формы формулы (СКНФ).

Пример 1.16.

Указать, в каких нормальных формах находятся формулы логики высказываний трех переменных.

a) X&Y&Z – СДНФ и КНФ;

b) Ø X & Y&Z Ú X&Y &Ø Z – СДНФ;

c) X Ú Y Ú Z – СКНФ и ДНФ;

d) X & Z – ДНФ и КНФ;

e) (Ø X Ú Y Ú Z) & (X Ú Y ÚØ Z) – СКНФ;

f) X Ú Y Ú Z – СКНФ и ДНФ;

g) (X Ú Y)&(X ÚØ Z) – КНФ.

Каждая формула, не равная тождественно Л, может быть приведена к СДНФ, которая является единственной с точностью до перестановки дизъюнктивных членов.

Каждая формула, не равная тождественно И, может быть приведена к СКНФ, которая является единственной с точностью до перестановки конъюнктивных членов.

Алгоритм приведения формулы булевой функции к СДНФ

Шаг 1. Используя алгоритм построения ДНФ, находим формулу F, являющуюся ДНФ данной формулы.

Шаг 2. Если в элементарную конъюнкцию K_i формулы F не входит ни переменная A, ни ее отрицание A, то на основании 1- го закона расщепления (равносильность 7а) заменяем K_i на (K_i & A) Ú (K_i &Ø A).

Шаг 3. В каждой элементарной конъюнкции переставляем конъюнктивные члены так, чтобы для каждого i (i = 1,..., n) на i -ом месте была либо переменная A_i, либо ее отрицание Ø A_i.

Шаг 6. Устраняем возможные повторения конъюнктивных членов согласно закону идемпотентности для дизъюнкции: K_i Ú K_i º K_i.

Пример 1.17.

F = A &Ø B Ú A &Ø C & D Ú A & B & C &Ø D.

Преобразовать формулу к виду СДНФ:

1) F = A &Ø B & C Ú A &Ø B &Ø C Ú A & B &Ø C & D Ú A &Ø B &Ø C & D Ú A & B & C &Ø D;

2) F = (A &Ø B & C & D)Ú(A &Ø B & C &Ø D)Ú(A &Ø B &Ø C & D)Ú(A &Ø B &Ø C &Ø D)Ú (A & B &Ø C & D)Ú (A &Ø B &Ø C & D)Ú (A & B & C &Ø D).

Алгоритм нахождения СКНФ полностью повторяет алгоритм нахождения СДНФ, если произвести двойственную замену & на Ú и Ú на &.

Пример 1.18.

F = (A Ú B)) &(Ø A ÚØ B Ú C Ú D).

Преобразовать формулу к виду СКНФ:

1) F = (A Ú B Ú C) &(A Ú B ÚØ C) &(Ø A ÚØ B Ú C Ú D);

2) F = (A Ú B Ú C Ú D)&(A Ú B Ú C ÚØ D)&(A Ú B ÚØ C Ú D) &(A Ú B ÚØ C ÚØ D) &(Ø A ÚØ B Ú C Ú D).

Совершенные нормальные формы удобно записывать, используя таблицы истинности, по значениям переменных и значению логической функции.

Алгоритм представления логической функции, заданной таблицей, формулой в СДНФ.

Шаг 1. Выбираем в таблице все наборы переменных A ₁, A ₂,..., A _n, для которых значение F равно И.

Шаг 2. Для каждого такого набора (строки таблицы) составляем конъюнкцию переменных, причем в эту конъюнкцию переменная A_i записывается без изменений (т. е A_i), если ее значение равно “И” и со знаком отрицания (т. е Ø A_i), если ее значение равно “Л”.

Шаг 3. Составляем дизъюнкцию всех полученных конъюнкций. В результате получится формула данной функции в СДНФ.

Для получения формулы в СКНФ следует воспользоваться следующим алгоритмом.

Алгоритм представления логической функции, заданной таблицей, формулой в СКНФ

Шаг 1. Выбираем в таблице все наборы переменных A ₁, A ₂,..., A _n, для которых значение F равно Л

Шаг 2. Для каждого такого набора (строки таблицы) составляем дизъюнкцию переменных, причем в эту дизъюнкцию переменная A_i записывается без изменений (т. е A_i), если ее значение равно “Л” и со знаком отрицания (т. е Ø A_i), если ее значение равно “И”.

Шаг 3. Составляем конъюнкцию всех полученных дизъюнкций. В результате получится формула данной функции в СКНФ.

Пример 1.19.

Записать СДНФ и СКНФ для функции, заданной таблицей истинности (таблица 1.6):

Таблица 1.6

a) Формула СДНФ:

F (A, B, C) = Ø А &Ø B &Ø C Ú Ø А & B &Ø C Ú А &Ø B &Ø C Ú А & B & C;

b) Формула СКНФ:

F (A, B, C) = (A Ú B ÚØ C) &(A ÚØ B Ú C) & (Ø A Ú B ÚØ C) &(Ø A ÚØ B Ú C).

Замечание. Т. к. всего строк в таблице функции 2 ⁿ, то, если число дизъюнктивных членов в СДНФ равно p, а число конъюнктивных членов в СКНФ равно q, то p + q =2 ⁿ.

Так, для функции, рассмотренной в примере 1.19, n = 3, p = 4, q = 4, p + q = 8 = 2³.