Занятие 2. Нахождение дизъюнктивной и конъюнктивной нормальных форм

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 1.

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

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

1) F = () (A B);

2) F = ( A) ( B) ( A) ( B);

3) F = ( B) ( A).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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