§5. Совершенные днф и кнф.

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

Пусть (x₁,...,х_n) — набор логических переменных, = - набор нулей и единиц.

Конституентой единицы набора называется конъюнкт .

Конституентой нуля набора называется дизъюнкт

Отметим, что тогда и только тогда, когда .

Пример 4.1 - Формула есть конституента единицы К¹ (1,0,1), формула есть конституента нуля К⁰(0,0,1).

Совершенной ДНФ называется дизъюнкция всех конституент единицы,

а совершенной КНФ называется конъюнкция всех конституент нуля, среди которых нет одинаковых.

Таким образом; СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждый конъюнкт (дизъюнкт) каждая переменная x_i из набора {x_i,..., х_n} входит ровно один раз, причем входит либо сама x_i ,либо ее отрицание .

Пример 4.2 формула - СДНФ,

формула - СКНФ,

а формула не является СДНФ.

Для решения задачи нахождения СДНФ и СКНФ, эквива­лентных исходной формуле , предварительно рассмотрим разложения булевой функции f{x₁,x₂,... ,х_n) по m переменным (для определенности по х₁, х₂, ..., х_m) - разложения Шеннона.

ТЕОРЕМА (О разложении булевой функции по переменным)

Где дизъюнкция берется по всем возможным наборам ( )

Доказательство.

ЗАМЕЧАНИЕ. Здесь доказывается, что некоторая формула реализует заданную функцию. Для этого до­статочно взять произвольный набор значений аргументов функции, вычислить на этом наборе значение формулы, и если оно окажется равным значению функции на этом на­боре аргументов, то из этого следует доказываемое утверждение.

СЛЕДСТВИЕ 1.

СЛЕДСТВИЕ 2.

Предельное представление (т.е. когда n=m ) булевой функции f(x₁ ,x₂ ,…, x_n ) в виде

называется совершенной дизъюнктивной нормальной формой (СДНФ).

ЗАМЕЧАНИЕ. СДНФ называется совершенной, потому что каждое слагаемое в дизъюнкции включает все переменные; дизъюнктивной, потому что главная операция — дизъюнкция, а почему она называется нормальной, объяснено в следующем отступлении.

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

Доказательство.

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

доказательство

ТЕОРЕМА. Всякая булева функция (кроме 1) может быть единственным образом выражена в виде совершенной конъюнктивной нормальной формы (СКНФ):

Доказательство.

По принципу двойственности из предыдущей теоремы.

Пример 4.2. Построим совершенные ДНФ и КНФ булевой функции f(x₁, х₂, х₃), заданной таблицей истинности (табл. 4.1).

Таблица 4.1

С

f(x₁, х₂, х₃) =

f(x₁, х₂, х₃) =

Описанный способ нахождения СДНФ и СКНФ по таблице истинности бывает часто более трудоемким, чем следующий ал­горитм.

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

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

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

б) если в конъюнкт одна и та же литера входит несколько раз, то удаляем все литеры , кроме одной;

в) если в некоторый конъюнкт не входит перемен­ная у, то этот конъюнкт заменяем на эквивалентную формулу и, применяя закон дистрибутивности, приво­дим полученную формулу к ДНФ; если недостающих перемен­ных несколько, то для каждой из них к конъюнкту добавляем соответствующую формулу вида ^;

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