2.3.6.2. Совершенная дизъюнктивная нормальная форма

Представление булевой функции f(x₁, ..., x_n) в виде

называется совершенной дизъюнктивной нормальной формой (СДНФ). Здесь дизъюнкция v означает, что берется дизъюнкция по тем наборам , на которых функция f равна единице.

СДНФ называется совершенной, потому что каждое слагаемое в дизъюнкции включает все переменные, дизъюнктивной, потому что главная операция – дизъюнкция.

Теорема: Всякая булева функция (кроме 0) имеет одну единственную СДНФ.

Доказательство. По следствию 2:

Ясно, что в дизъюшкции останутся только члены, для которых .

При f = 0 множество конъюнкций в правой части пусто.

Теорема: Всякая булева функция может быть выражена через дизъюнкцию, конъюнкцию и отрицание:

f = func F.

Доказательство: Если f = 0, то . Если , то см. предыдущую теорему.

Алгоритм преобразования формулы в СДНФ

Равенство (*) дает возможность находить СДНФ для функции по ее таблице истинности. Однако, если функция заданна формулой, то этот путь часто неудобен.

Разобьем построение СДНФ на два этапа:

I. Сначала по формулам построим ДНФ.

II. По найденному ДНФ построим СДНФ.

Будем пользоваться элементарными операциями, которыми являются преобразования формул, использующие аксиом 1÷10 и их простейшие следствия.

I.Построение ДНФ.

1). Преобразуем формулу так, чтобы в ней были только операции дизъюнкции, конъюнкции и отрицания, причем отрицание может стоять только над аргументами.

Такого рода преобразования мы уже делали (см. пример на стр. 139) - базисные операции .

Замечание. Формулы, являющиеся ДНФ, можно охарактеризовать, как формулы, содержащие только конъюнкцию, дизъюнкцию и отрицание. В них отрицания стоят только над аргументами и в начале выполняются все конъюнкции, а потом – дизъюнкции. Поэтому далее нужно

2). преобразовать формулу так, чтобы все конъюнкции выполнялись раньше, чем дизъюнкции. Это достигается с помощью дистрибутивного закона.

В результате формула приобретает вид дизъюнктивной формы:

v(A_i^...^A_j),

где А_i – либо переменная, либо отрицание переменной.

II. Теперь преобразуем ДНФ в СДНФ.

3). Если в ДНФ имеется несколько одинаковых элементарных конъюнкций, то мы оставляем только одну с помощью идемпотенции конъюнкции: x^x = x. Затем с помощью идемпотентности дизъюнкции удаляются повторные вхождения одинаковых конъюнкций в дизъюнкцию.

В результате этого шага формула не содержит «лишних» переменных и «лишних» конъюнктивных слагаемых.

При этом делаем все элементарные конъюнкции правильными, путем следующих двух преобразований:

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

б) если некоторая переменная входит в элементарную конъюнкцию несколько раз, при чем во всех случаях без отрицания или во всех случаях под знаком отрицания, то мы оставляем только одно вхождение, так как x^x = x.

Теперь нужно получить полные конъюнкции.

4). Если в некоторую конъюнкцию не входит переменная у, то нужно рассмотреть равносильное выражение , и вновь применим преобразование 2). Если недостающих членов несколько, то надо добавить несколько конъюктивных членов вида .

Напоминание: = 1, 1^x = х.

После применения преобразования 4) могут вновь появиться одинаковые конъюнкции. Поэтому нужно вновь применить преобразование 3).

На этом преобразование формулы в СДНФ заканчивается.

Мы не оговорили, что всюду, конечно, надо пользоваться коммутативностью и ассоциативностью конъюнкции и дизъюнкции.

Пример. Найти СДНФ: xvy^z.

2.3.6.3. Совершенные конъюнктивные нормальные формы.

Совершенно аналогично можно провести рассмотрение для конъюнктивных нормальных форм.

Определение 1. Формула вида называется элементарной дизъюнкцией.

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

Таким образом, формула F находится в конъюнктивной нормальной форме тогда и только тогда, когда F имеет вид:

F = F₁^...^F_n, n≥1, где каждая из F₁, ..., F_n есть элементарная дизъюнкция.

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

Определение 3. Элементарная дизъюнкция называется правильной, если в нее каждая переменная входит не более одного раза (включая ее вхождение под знак отрицания).

Определение 4. Правильная элементарная дизъюнкция называется полной относительно переменных (x₁, ..., x_n), если каждая из этих переменных входит в нее один и только один раз (быть может, под знаком отрицания).

Определение 5. Совершенной конъюнктивной нормальной формой (СКНФ) относительно переменных (x₁, ..., x_n) называется конъюнктивная нормальная форма, в которой нет одинаковых элементарных дизъюнкций и все элементарные дизъюнкции правильны и полны относительно переменных

(x₁, ..., x_n).

Теорема: Всякая булева функция (кроме 1) может быть единственным образом выражена в виде СКНФ:

.

Вместо можно потребовать, чтобы .