Функционально-полная система в математической логике

В типичной современной цифровой вычислительной машине цифрами являются 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, не самодвойственную, нелинейную и немонотонную.
В таблице приведены свойства, которыми обладают элементарные булевы функции (символ * - отмечает свойство, которым обладает данная функция).

Используя теорему Поста и данную таблицу можно строить базисы из элементарных функций по следующему правилу. Выбрав любую элементарную булеву функцию и дополнив ее при необходимости другими функциями так, чтобы все они вместе удовлетворяли теореме о функциональной полноте. Через функции этого базиса можно выразить все другие булевы функции.
Построим некоторые часто используемые в приложениях базисы.
1. Система функций S1={,&,v} образует базис. Для приведения булевой функции к виду, содержащему лишь связки из базиса S1 могут быть полезны следующие эквивалентности:
X→Y=XvY
X↔Y=(XvY)(XvY)
X⊕Y=XYvXY
X|Y=XvY
X↓Y=X&Y
2. Система S2={,&} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1, а затем использовать соотношение XvY=(X•Y).
3. Система S3={,v} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1, а затем использовать соотношение X•Y=(XvY).
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))•(XvY•ZvY•Z)