В типичной современной цифровой вычислительной машине цифрами являются 0 и 1. Следовательно, команды, которые выполняет процессор, суть булевы функции. Ниже будет показано, что любая булева функция реализуется через конъюнкцию, дизъюнкцию и отрицание. Следовательно, можно построить нужный процессор, имея в распоряжении элементы, реализующие конъюнкцию, дизъюнкцию и отрицание. Этот раздел посвящен ответу на вопрос: существуют ли (и если существуют, то какие) другие системы булевых функций, обладающих тем свойством, что с их помощью можно выразить все другие функции.
Введем в рассмотрение ряд классов функций:
1. Класс функций, сохраняющих константу 0, т.е. таких функций y=f(x1,x2 … xn), что f(0,0 … 0)=0. Например, xvy(¬x).
2. Класс функций, сохраняющих константу 1, т.е. таких функций y=f(x1,x2 … xn), что f(1,1 … 1)=1. Например, xv¬(yx).
3. Класс самодвойственных функций, т.е. таких функций y=f(x1,x2 … xn), что f(x1,x2 … xn)=¬(f(¬x1,¬x2 … ¬xn)).
4. Класс линейных функций, т.е. таких функций y=f(x1,x2 … xn), которые могут быть представлены в виде f(x1,x2 … xn)=c0⊕c1x1⊕c2x2⊕…⊕cnxn, где c0, c1, c2 — коэффициенты, которые могут принимать значение 0 или 1.
5. Класс монотонных функций. На множестве наборов из нулей и единиц Bn={(x1,x2 … xn):xi∈{0,1},i=1,2…n} введем частичный порядок следующим образом: (a1,a2…an)=(b1,b2…bn) тогда и только тогда когда a1=b1, a2=b2 … an=bn. Функция f(x1,x2 … xn) называется монотонной, если для любых двух элементов из Bn таких, что (a1,a2 … an)=(b1,b2 … bn) следует, что f(a1,a2 … an)=f(b1,b2 … bn).
Система 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)