Тернарные функции

При n = 3 число булевых функций равно 2^2³ = 2⁸ = 256. Некоторые из них определены в следующей таблице:

x	y	z	x↓y↓z	≥2(x,y,z)	x≠y≠z	x|y|z	min(x,y,z)	x=y=z	x ⊕ y ⊕ z	≥2(x,y,z)	f1	f2	max(x,y,z)
0	0	0	1	1	0	1	0	1	0	0	0	0	0
0	0	1	0	1	1	1	0	0	1	0	0	0	1
0	1	0	0	1	1	1	0	0	1	0	0	0	1
0	1	1	0	0	1	1	0	0	0	1	1	1	1
1	0	0	0	1	1	1	0	0	1	0	1	0	1
1	0	1	0	0	1	1	0	0	0	1	0	1	1
1	1	0	0	0	1	1	0	0	0	1	1	1	1
1	1	1	0	0	0	0	1	1	1	1	1	1	1

Названия булевых функций трех переменных:

Обозначения	Названия
x y z =  (x,y,z) = Webb2(x,y,z)	3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса
	Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией
x≠y≠z = [≠(x,y,z)] = NE(x,y,z,v)	Неравенство
x y z =  (x,y,z)	3-И-НЕ, штрих Шеффера
x&y&z = &(x,y,z) = (x AND y AND z) = AND(x,y,z) = (x И y И z) = И(x,y,z) = min(x,y,z)	3-И, минимум
(x=y=z) = [=(x,y,z)] = EQV(x,y,z,v)	Равенство
x⊕2y⊕2z = x+2y+2z = ⊕2(x,y,z) = +2(x,y,z)	Тернарное сложение по модулю 2
[>=2(x,y,z)] = (x И y) ИЛИ (y И z) ИЛИ (z И x)	переключатель по большинству, 3-ППБ, мажоритарный клапан
f1	Разряд займа при тернарном вычитании
f2	Разряд переноса при тернарном сложении
(x+y+z) = +(x,y,z) = max(x,y,z) = (x OR y OR z) = OR(x,y,z) = (x ИЛИ y ИЛИ z) = ИЛИ(x,y,z)	3-ИЛИ, максимум

[Править]Полные системы булевых функций Суперпозиция и замкнутые классы функций

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

x	y	z		f(x,y,z)
0	0	0		1
1	0	0		0
0	1	0		1
1	1	0		1
0	0	1		0
1	0	1		0
0	1	1		1
1	1	1		0

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

В качестве простейших примеров замкнутых классов булевых функций можно назвать множество {x}, состоящее из одной тождественной функции, или множество {0}, все функции из которого тождественно равны нулю вне зависимости от своих аргументов. Замкнуты также множество функций   и множество всех унарных функций. А вотобъединение замкнутых классов может таковым уже не являться. Например, объединив классы {0} и  , мы с помощью суперпозиции   сможем получить константу 1, которая в исходных классах отсутствовала.

Разумеется, множество P₂ всех возможных булевых функций тоже является замкнутым.