8.2. ПЕРЕКЛЮЧАТЕЛЬНЫЕ ФУНКЦИИ И ИХ СВОЙСТВА
Рассмотрим множество из двух элементов В2 = {0,1} и определим совокупность переменных x1,
x2, ..., xn таких, что каждая переменная может принимать
значения только из В2. Совокупность таких переменных назовем вектором
двоичных переменных и обозначим символом 
: = (x1, x2, ..., xn). Каждый компонент
вектора может принимать одно из двух значений: 0 или 1.
Назовем последовательность нулей и единиц, получающуюся из после замены переменных их значениями, двоичным набором. Любой такой набор можно рассматривать
как совокупность цифр двоичного числа. Условимся называть десятичный эквивалент этого числа номером набора. Если обозначить произвольный двоичный набор символом 
, а номер этого набора j( 
), то для заданного его номер вычисляется следующим образом:
Например,номер набора (0, 1, 0, 1, 0, 1): j = 24 + 22 + 20 = 21. Наборы из n компонентов нумеруются числами от 0 до 2n - 1. Следовательно, всего имеется 2n различных двоичных наборов.
Двоичный набор ( j )полностью
определяется своим номером j и числом компонентов n. Например, для j = 12 и n = 6 имеем (12) = (0, 0, 1, 1, 0, 0).
Таблица 2.1
x1
x2
x3
j ( x1, x2, x3)
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
Далее введем функции, зависящие от вектора аргументов ,
которые обозначим: φ() или
φ(x1, x2, ..., xn) и условимся, что такие функции могут принимать
значения только из множества В2 и называются переключательными функциями.
Или, другими словами,функция φ(x1, x2, ..., xn) ,
зависящая от переменных x1,x2,..., xn, каждая из которых может быть 0 или 1 и принимающая значение 0
или 1, называется переключательной функцией.
Областью определения переключательной функции от n переменных является множество из 2n двоичных наборов. Для того чтобы задать переключательную функцию, нужно указать соответствие между этими наборами и значениями функции. Такое
соответствие проще всего описать с помощью таблицы, число строк в которой определяется числом наборов, а число столбцов на единицу больше числа переменных. Пример такой формы задания функции приведен в табл. 2.1. Обозначим множество переключательных
функций, зависящих от n аргументов: Pn = {φi(x1, x2, ..., xn )} и найдем число элементов этого множества |P(n)|, т. е. число различных переключательных функций от n аргументов. В случае табличного задания столбцы значений различных функций должны иметь различие хотя бы в одной строке. Следовательно, для того чтобы найти число различных функций n переменных, нужно подсчитать какое количество различных столбцов значений может быть в таблице, имеющей 2n строк. Если каждую позицию в столбце считать двоичной переменной, то задача сводится к определению числа наборов для 2n переменных.Исходя из этого, получаем, что
Зависимость числа переключательных функций от числа переменных показана в табл. 2.2:
Таблица 2.2
n
|Pn|
1
4
2
16
3
256
4
65536
5
4,3. 103
Из табл. 2.2 видно, что число переключательных функций очень быстро растет при незначительном увеличении числа переменных.