x Ú 1 = 1;

x Ú x = x ;

x Ú y =y Ú x ;

x Ú= 1.

Таблица истинности функции f₆ (x,y) совпадает с таблицей сложения двух одноразрядных двоичных чисел по модулю два. Можно ввести функцию n аргументов, соответствующую сумме по модулю два n одноразрядных двоичных чисел. Такая переключательная функция определяется следующим условием: она равна единице, если число аргументов, равных единице, нечетно, и равна нулю, если число таких аргументов четно. Приведем некоторые соотношения для суммы по модулю два:

x Å 0 = x ;

x Å 1 = ;

x Å x = 0;

x Å x Å x = x ;

x Å y = y Å x .

Рассмотренные шестнадцать функций двух аргументов (будем называть их элементарными) позволяют строить новые переключательные функции следующим образом:

· путем перенумерации аргументов;

· путем подстановки в функцию новых функций вместо аргументов.

Функцию, полученную из функций f ₁ , f ₂ , …, f_k путем применения (возможно многократного) этих двух правил, будем называть суперпозицией функций f ₁ , f ₂ , …, f_k . Например, имея элементарные функции инверсии, конъюнкции, дизъюнкции, импликации, запрета, сложения по модулю два, можно составить новую переключательную функцию:

f ( x , y , z ) = (( Ú y ) D z ) Å (( y ® z ) × x ).

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

Пример 1. Представить в виде таблицы функцию

f ( x , y , z ) = (( Ú y ) D z ) Å (( y ® z ) × x ).

Решение. Функцию f (x,y,z) будем представлять последовательно, записывая в столбцы табл. 1.5 промежуточные результаты, получаемые после выполнения каждой операции:

Таблица 3

Таблица истинности функции f ( x , y , z ) = (( Ú y ) D z ) Å (( y ® z ) × x ).

x	y	z		( Ú y)	( Ú y) D z)	(y ® z)	(y ® z) × x	(( Ú y) D z) Å ((y ® z) × x)
0	0	0	1	1	1	1	0	1
0	0	1	1	1	0	0	0	0
0	1	0	1	1	1	1	0	1
0	1	1	1	1	0	1	0	0
1	0	0	0	0	0	1	1	1
1	0	1	0	0	0	0	0	0
1	1	0	0	1	1	1	1	0
1	1	1	0	1	0	1	1	1

3. Представление переключательной функции в виде многочленов.

1. Конституенты. В п. 2 был рассмотрен один из возможных способов представления переключательной функции – задание ее в виде таблицы истинности. В этом разделе будем решать обратную задачу, а именно представление переключательной функции, заданной таблицей истинности, через элементарные функции, образующие базис.

Рассмотрим переключательные функции, называемые конституентами.

Определение 1. Конституентой единицы называют переключательную функцию n аргументов, которая принимает значение, равное единице на одном единственном наборе аргументов.

Из определения следует, что число различных конституент единицы среди функций n аргументов равно 2ⁿ . Конституенты единицы обозначаются так: K_i (x₁ , …, x_n ) , где i – номер набора, на котором конституента равна единице. Например, запись K₇ (x₁ , x₂ , x₃ , x₄ ) означает функцию четырех аргументов, равную единице на наборе (0111).

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

K ₇ ( x ₁ , x ₂ , x ₃ , x ₄ ) = .

Чтобы записать в виде произведения конституенту K_i ( x ₁ , …, x_n ), можно воспользоваться следующим правилом: записать n -разрядное двоичное число (n – число аргументов), равное i , и конъюнкцию n переменных; над переменными, места которых совпадают с позициями нулей в двоичном числе i , поставить знак отрицания.

Пример 2. Записать конституенту, равную единице на двенадцатом наборе для функции пяти переменных.