2015-06-26
1385
СПЕЦИАЛЬНЫЕ КЛАССЫ БУЛЕВСКИХ
ФУНКЦИЙ
ОПРЕДЕЛЕНИЕ
Множество функций B 
называется замкнутым классом, если [ B ] = B.
Например, множество { x, 
} является замкнутым классом. Рассмотрим пять специальных классов булевских функций, свойства которых будут использованы при нахождении простых необходимых и достаточных условий полноты произвольных систем функций в P 2.
ФУНКЦИИ, СОХРАНЯЮЩИЕ НОЛЬ
Обозначим как Т 0 множество всех таких булевских функций, которые на нулевом наборе значений переменных принимают значение 0.
О таких функциях говорят, что они сохраняют 0, т.е. множество б.ф., сохраняющих ноль, это:
Т 0 = { f (x 1,..., x n) ½ f (0,..., 0) = 0 }.
Сформулируем простейшие свойства класса T 0.
1. Класс T 0 является замкнутым классом функций.
Для проверки справедливости последнего утверждения достаточно проверить, что всякая формула U (f 1,..., f p), составленная с помощью функций f 1,..., f p, сохраняющих ноль, представляет функцию f U, которая также сохраняет ноль.
Проведем обоснование этого свойства в соответствии с определением понятия формулы над классом функций.
1.1. Если U = f (x 1,..., x n), где f (x 1,..., x n)Î T 0, то
f (0,..., 0) = 0 и f U = f.
1.2. Если U = f (U 1,..., U n), где f (x 1,..., x n) Î T 0, а
U 1,..., U n - это или символы переменных или подформулы формулы U, составленные с помощью функций из T 0 и символов переменных. Заметим, что поскольку обозначение переменной представляет тождественную функцию I (x) = x, то U 1,..., U n можно рассматривать как подформулы, представляющие некоторые функции 
из класса T 0. Тогда функция f (
) также принадлежит классу T 0.
Действительно, f (g 1(0,..., 0),..., g n (0,... ,0))= f (0,... ,0)= 0.
2. Определим число различных функций переменных
x 1,..., xn, которые содержатся в T 0.
Поскольку функции из T 0 на всех наборах значений переменных, отличных от нулевого набора, принимают произвольные значения, и таких ненулевых наборов 2 n-1, то в T 0 содержится ровно 
различных булевских функций n переменных.
