ТЕОРЕМА 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 можно представить в виде .

Дата добавления: 2014-11-15; просмотров: 278; Нарушение авторских прав

Мы поможем в написании ваших работ!