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

Введем в рассмотрение ряд классов функций:

1. Класс функций, сохраняющих константу 0, т.е. таких функций y=f(x₁,x₂ … x_n), что f(0,0 … 0)=0. Например, xvy(¬x).

2. Класс функций, сохраняющих константу 1, т.е. таких функций y=f(x₁,x₂ … x_n), что f(1,1 … 1)=1. Например, x_v¬(yx).

3. Класс самодвойственных функций, т.е. таких функций y=f(x₁,x₂ … x_n), что f(x₁,x₂ … x_n)=¬(f(¬x₁,¬x₂ … ¬x_n)).

4. Класс линейных функций, т.е. таких функций y=f(x₁,x₂ … x_n), которые могут быть представлены в виде f(x₁,x₂ … x_n)=c₀⊕c₁x₁⊕c₂x₂⊕…⊕c_nx_n, где c₀, c₁, c₂ — коэффициенты, которые могут принимать значение 0 или 1.

5. Класс монотонных функций. На множестве наборов из нулей и единиц Bⁿ={(x₁,x₂ … x_n):x_i∈{0,1},i=1,2…n} введем частичный порядок следующим образом: (a₁,a₂…a_n)=(b₁,b₂…b_n) тогда и только тогда когда a₁=b₁, a₂=b₂ … a_n=b_n. Функция f(x₁,x₂ … x_n) называется монотонной, если для любых двух элементов из Bⁿ таких, что (a₁,a₂ … a_n)=(b₁,b₂ … b_n) следует, что f(a₁,a₂ … a_n)=f(b₁,b₂ … b_n).

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

Критерий полноты (Теорема Поста): Система S булевых функций является полной тогда и только тогда, когда она включает хотя бы одну функцию: не сохраняющую константу 0, не сохраняющую константу 1, не самодвойственную, нелинейную и немонотонную.

В таблице приведены свойства, которыми обладают элементарные булевы функции (символ * — отмечает свойство, которым обладает данная функция).

Название	Обозначение	Не сохранимость константы 0	Не сохранимость константы 1	Не самодвойственность	Не линейность	Не монотонность
Конст. 0	0		*	*
Конст. 1	1	*		*
Отриц.	¬	*	*			*
Конъюн.	&			*	*
Дизъюн.	v			*	*
Имплик.	→	*		*	*	*
Эквивал.	∼	*		*		*
Сумма по мод. 2	⊕		*	*		*
Штрих Шеффера	|	*	*	*	*	*
Стрелка Пирса	↓	*	*	*	*	*

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

Построим некоторые часто используемые в приложениях базисы.

1. Система функций S1={¬,&,v} образует базис. Для приведения булевой функции к виду содержащему лишь связки из базиса S1 могут быть полезны следующие эквивалентности:

X→Y=¬XvY

X↔Y=(Xv¬Y)(¬XvY)

X⊕Y=¬XYvX¬Y

X|Y=¬Xv¬Y

X↓Y=¬X&¬Y

2. Система S2={¬,&} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1, а затем использовать соотношение XvY=¬(¬X•¬Y).

3. Система S3={¬,v} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1, а затем использовать соотношение X•Y=¬(¬Xv¬Y).

4. Система S4={1,&,⊕} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1 а затем использовать соотношения:

¬X=1⊕X

XvY=X⊕Y⊕X•Y

5. Система S5={|} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S2 а затем использовать соотношения:

X•Y=¬(¬X|¬Y)

¬X=X|X

6. Система S6={↓} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S3 а затем использовать соотношения:

XvY=¬(¬X|¬Y)

¬X=X↓X

7. Система S7={→,0} образует базис.

Пример: Записать функцию X↔(Y⊕Z) в базисе S1={¬,&,v}.

X↔(Y⊕Z)=(Xv¬(Y⊕Z))•(¬Xv(Y⊕Z))=(Xv¬(¬Y•ZvY•¬Z))•(¬Xv¬Y•ZvY•Z)