2015-06-28
2558
Если f* = f, то функция f называется самодвойственной. Множество всех самодвойственных булевых функций обозначается через S. Функции х, Ø х самодвойственные. Функции Ù и Ú двойственны друг другу и поэтому несамодвойственные. Два набора из нулей и единиц называем их противоположными, если на соответствующих местах у них расположены противоположные элементы 0 и 1.
ТЕОРЕМА. Булева функция самодвойственная тогда и только тогда, когда на противоположных наборах значений переменных принимает противоположные значения.
Доказательство. f* = f Û Ø f (х 1,…, хn) = f (Ø x 1,…,Ø xn).
ТЕОРЕМА. Число всех различных n- местных самодвойственных булевых функций равно 
Доказательство. По предыдущей теореме оно равно числу всех возможностей для составления верхней половины таблицы, задающей n- местную булевую функцию.
ТЕОРЕМА. Класс S замкнут.
Доказательство. Пусть f 1, f 2 Î S Þ Ø f 1(х 1, …, хn) = f 1(Ø x 1, …, Ø xn), Ø f 2(х 1, …, хn) = f 2(Ø x 1, …, Ø xn); f = f 1(x 1, …, xn –1), f 2(y 1, …, ym)) Þ
|
|
|
f* = Ø f 1(Ø х 1, …,Ø хn –1, f 2(Ø y 1, …, Ø ym)) =
= Ø f 1(Ø x 1, …, Ø xn –1, Ø f 2(y 1, …, ym)) = f 1(х 1, …, хn -1, f 2(y 1,…, ym)) = f Þ f Î S.
Общий случай можно получить многократным повторением этого рассуждения. ■
