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

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

ПО ПЕРЕМЕННЫМ

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

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

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

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

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

ОПРЕДЕЛЕНИЕ

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

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

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

. (1)

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

Ú . (2)

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

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

ТЕОРЕМА 4.2

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

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

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

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

. (1)

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

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

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

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

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

.

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

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

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

Рассмотрим несколько специальных случаев доказанной теоремы.

1. Разложение по одной переменной (m = 1)

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

2. Разложение по всем переменным (m = n).

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

В случае, когда булевская функция f(x₁ , . . . , x_n ) отлична от тождественного нуля, разложение по всем переменным можно записать в виде:

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

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

СЛЕДСТВИЕ. Всякая булевская функция представима формулой над множествомB = {&, Ú, ` }.

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