12.Дизъюнктивные нормальные формы.

РАЗЛОЖЕНИЕ БУЛЕВСКИХ ФУНКЦИЙ ПО ПЕРЕМЕННЫМ

Рассмотрим вопрос о нахождении способа представления произвольных функции из P₂ с помощью формул над множеством элементарных функций.

Решение этого вопроса практически важно, поскольку делает возможным не только прямой переход от формульных представлений булевских функций к их табличному заданию, но и обратный: от табличного задания функций к их формульному представлению. Кроме того, формульное представление функций из P₂ может оказаться более компактным по сравнению с табличным заданием.

Введем в рассмотрение специальную функцию двух переменных

Данная функция имеет следующее табличное задание:

x 	x^
0 0	1
0 1	0
1 0	0
1 1	1

Из этого следует, что x^ = 1 тогда и только тогда, когда x = .

ОПРЕДЕЛЕНИЕ

Конъюнкцией ранга r называется всякая формула K, имеющая вид: .

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

Очевидно, что K = принимает значение 1 на единственном наборе значений своих переменных, для которого выполнены условия: . Поэтому для всякого конкретного набора значений переменных x₁,..., x_n однозначно определяется конъюнкция ранга n, принимающая значение 1 только на этом наборе. Например, для набора (0, 0, 1, 0, 1) значений переменных x₁,...,x₅ соответствующая конъюнкция имеет вид

. (1)

Тогда, если булевская функция f(x₁,..., x_n) принимает значение 1 лишь на двух наборах значений переменных (₁,...,_n) и (₁,...,_n), то справедливо равенство: f (x₁, . . . , x_n) =  . (2)

Подобным образом можно выписать формулу, представляющую произвольную булевскую функции f, если заданы все наборы, на которых она равна 1.

Приведенные два примера (1) и (2) представлений булевских функций формулами являются частными случаями следующей общей теоремы.

ТЕОРЕМА

(О разложении булевских функций по переменным)

Пусть f (x₁ ,..., x_n )  P₂ и 1  m  n.

Тогда справедливо следующее тождество:

f(x₁ , . . . , x_n ) = . (1)

Замечание. Здесь запись означает дизъюнкцию конъюнкций ранга n, составленных для всех возможных двоичных наборов (₁, . . . , _n) значений переменных x₁, . . . , x_n.

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

Покажем, что для каждого набора (₁, . . . , _n) значений переменных функции f значения, принимаемые функциями в левой и правой частях равенства (1), совпадают.

Значение, принимаемое функцией слева, равно f .

Рассмотрим правую часть равенства (1). Подставив в него выбранные значения переменных, получим запись:

.

Учитывая, что = 1 тогда и только тогда, когда  i = 1, . . . , m (_i = _i), из полученного выражения можно удалить все элементы дизъюнкции, которые принимают значение равное нулю, и получить выражение: .

Так как = 1, то последнее выражение равно: . То есть значения, принимаемые левой и правой частями равенства (1) на наборе значений переменных (₁, . . . , _n), равны.

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

Такое представление булевой функции называется совершенной дизъюнктивной нормальной формой этой функции или СДНФ для f.

СЛЕДСТВИЕ. Всякая булевская функция представима формулой над множеством B = { }.

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