§ 18. Полнота системы функций. Теорема Поста

Среди рассмотренных вопросов важными являлись вопросы о представимости булевых функций с помощью связок ¬ , &, ∨, либо ¬ , &, либо ¬ , ∨, и т.п. Всякий раз фактически речь шла о возможности представить булевы функции с помощью только некоторых функций и суперпозиции последних. Иначе можно сказать, что из всевозможных булевых функций были выделены некоторые функции ϕ1,ϕ2,..., ϕk, а затем выяснялось, можно ли любую булеву функцию представить как суперпозицию функций ϕ1,ϕ2,...,ϕk

Система функций Ф=$\{ϕ_1, ϕ_2,..., ϕ_n\}$ называется функционально полной, если всякая булева функция представима посредством суперпозиции функций из системы Ф.

Из теоремы 3.14 или 3.15 следует, что любую булеву функцию можно представить с помощью формулы, содержащей только связки ¬ , &, ∨. Следовательно, система функций ϕ1(А)=¬ x, ϕ2(x,y)=x&y, ϕ3(x,y)=x∨y является функционально полной системой функций. Эта полная система состоит из трех функций (одной одноместной и двух двуместных функций).

Из теорем 3.14 и 3.6 следует, что каждая из функций ϕ(x,y)=x¬ y и ψ(x,y)=x↓ y образует полные системы, состоящие только из одной функции.

Из теоремы 3.7 следует, что других полных систем функций, состоящих только из одной двуместной функции, нет.

Из теорем 3.14 и 3.4 следует полнота каждой из систем функций:

$\{¬ x, x\&y\} ; \{¬ x, x∨y\} ; \{¬ x, x⇒y\}$

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

$\{x\&y, ¬(x≡y), x∨¬ x\}$

Система булевых функций $\{ϕ_1, ϕ_2,..., ϕ_n\}$ называется базисом, если она является полной системой функций, но никакая ее собственная часть не образует полную систему функций.

Примерами базиса будут системы $\{¬ , \&\}, \{|\}$ , но $\{¬ , \&, ∨\}$ - не базис, ибо ее подсистема ¬ , & - полна.

Естественно выяснить, есть ли критерии полноты системы функций, т.е. можно ли выяснить, когда (при каких условиях) та или иная система функций полна. И если есть такие критерии, то в чем они состоят. Ответом является теорема Поста. Но прежде чем ее сформулировать, введем некоторые новые понятия.

1. Функции, сохраняющие нуль (единицу). Булева функция $f(x_1,x_2, ...,x_n)$ называется сохраняющей нуль (единицу), если f(0,0,...,0)=0 (f(1,1,...,1)=1).

Например, функция x&y, очевидно, сохраняет 0, а функция ¬ x∨¬ y∨z сохраняет 1. Функция x⇒ y не сохраняет 0, а x≡¬ y не сохраняет единицу. Таким образом, есть функции, сохраняющие 0, функции, сохраняющие 1, а также есть функции, не сохраняющие 0 и функции, не сохраняющие 1.

Теорема 3.20. Суперпозиция булевых функций, сохраняющих нуль (единицу), есть снова булева функция, сохраняющая нуль (единицу).

Доказательство. Пусть даны булевы функции, сохраняющие нуль:

$f(x_1,x_2, ...,x_n), ϕ_1(y_{11},y_{12},...,y_{1(m1))}, ϕ_2(y_{21},y_{22},...,y_{2(m2))},…, ϕ_n(y_{n1},y_{n2}, ...,y_{n(mn))}$

Подставляя функции $ ϕ_1,ϕ_2,...,ϕ_n$ вместо аргументов$x_1,x_2,...,x_n$, получаем новую функцию

$F(y_{11},y_{12}, ...,y_{1(m1)};...; y_{n1},y_{n2}, ...,y_{n(mn))}= f(ϕ_1, ϕ_2,..., ϕ_n)$

Найдем значение функции F на нулевом наборе, полагая все yij=0. Так как каждая из функций ϕi сохраняет нуль и, следовательно, равна нулю при нулевых значениях аргументов уij, а также f(0,0,...,0)=0, то получим, что F(0,0,...,0;.........;0,0,...,0)=0.

Для функций, сохраняющих единицу, доказательство проводится аналогично.

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

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

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

Действительно, в противном случае нельзя получить функцию, не сохраняющую единицу, например, x≡¬ y.

2. Самодвойственные функции. Булева функция $f(x_1,x_2, ...,x_n)$называется самодвойственной, если

$¬ f(x1,x2, ...,xn) = f(¬ x1,¬ x2, ...,¬ xn)$

Легко убедиться, что функция f(x) = ¬ x самодвойственная, а f(x,y) = x&y не является самодвойственной.

Нетрудно доказать следующую теорему.

Теорема 3.21. Суперпозиция самодвойственных функций есть снова самодвойственная функция.

Следствие 3.7. В полной системе функций должна содержаться хотя бы одна не самодвойственная функция.

Действительно, в противном случае нельзя получить несамодвойственную функцию, например, x&y.

3. Монотонные функции. Рассмотрим различные наборы значений переменных x1,x2,...,xn, когда каждое xi принимает значение 0 либо 1.

Если значение каждого аргумента одного набора больше или равно значению того же аргумента второго набора, то говорят, что первый набор не меньше второго. Если же некоторые из значений аргументов первого набора больше или равны, а другие меньше значений второго набора, то такие наборы называются несравнимыми.

Например, имеем, что (1,0,1) ≥ (1,0,0), так как значения аргументов х1 и х2 совпадают, а значение аргумента х3 на первом наборе больше, чем на втором. Аналогично имеем, что (0,0,1,1,1) ≥ (0,0,1,0,1); (1,0,1,1) ≥ (1,0,0,0). Очевидно, что любой набор не меньше набора, состоящего только из нулей.

Наборы (1,0) и (0,1) несравнимы, ибо значение аргумента x1 больше на первом наборе, а аргумента x2 - на втором.

Булева функция $f(x_1,x_2, ...,x_n)$называется монотонной, если для любых наборов значений ее аргументов $(а_1,а_2, ...,а_n)$ и $(b_1,b_2, ...,b_n)$ таких, что $(а_1,а_2, ...,а_n)$ ≥ $(b_1,b_2, ...,b_n)$, имеет место $f(а_1,а_2, ...,а_n)$ ≥$f(b_1,b_2, ...,b_n)$.

Например, учитывая, что наборы (0,1), и (1,0) несравнимы, легко установить, что функция $x\&y∨¬ x\&y$ монотонна.

Функция ¬ (x⇒y) не является монотонной, так как на наборе (1,0) равна единице, а на большом наборе (1,1) - нулю.

Нетрудно убедиться, что имеет место приведенная далее теорема и следствие из этой теоремы.

Теорема 3.22. При суперпозиции монотонных функций получается монотонная функция.

Следствие 3.8. В полной системе функций должна содержаться хотя бы одна немонотонная функция.

4. Линейные функции. Функция $f(x_1,x_2, ...,x_n)$ называется линейной, если

$f(x_1,x_2, ...,x_n) = c_0+c_1\&x_1+c_2\&x_2+…+c_n\&x_n$

где ci - константы (единица или нуль), 0≤ i≤ n.

Примеры линейных функций. Линейными являются следующие двухаргументные функции: тождественно равная нулю $(f(x,y)=0)$ тождественно равная единице $(f(x,y)=1)$ , а также $f(x,y)=x, f(x,y)=1+x, f(x,y)=y, f(x,y)=1+y, f(x,y)=x+ y, f(x,y)=1+ x+ y$ . Других двухаргументных линейных функций нет. Например, функция $f(x,y)=x\&y$ является нелинейной.

Легко доказать следующую теорему.

Теорема 3.23. Суперпозиция линейных функций является линейной функцией.

Следствие 3.9. В полной системе булевых функций должна содержаться хотя бы одна нелинейная булева функция.

Действительно, в противном случае нельзя получить нелинейную функцию, например, x&y.

Пусть $P_0$ - класс функций, сохраняющих нуль

$P_1$ - класс функций, сохраняющих единицу

S - класс самодвойственных функций

М - класс монотонных функций

L - класс линейных функций.

Теорема 3.24. (Теорема Поста). Для полноты системы функций $Ф={ϕ_1,ϕ_2,..., ϕ_n}$ необходимо и достаточно, чтобы для каждого из классов $Р_0, Р_1, S, М, L$ в $Ф$ нашлась функция ϕi, ему (классу) не принадлежащая.

Необходимость условий теоремы вытекает из следствий 3.5-3.9. Доказательство достаточности не приводим.

Отметим, что полная система функций может содержать всего одну функцию. Например, полна система $Ф={ϕ_1}, где ϕ_1=ϕ_1(x,y)=x| y$. Это означает, что функция $ϕ_1(x,y)=x| y$ не принадлежит ни одному из классов функций $Р_0, Р_1, S, М, L$ в $Ф$.

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

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

Доказательство. Пусть $G={f_1, f_2,..., f_n}$ - полная система функций. Согласно теоремы 3.24 в G найдутся функции $f_i∉ Р0, f_j∉Р1, f_s∉S , f_m∉М и f_l∉L$ Тогда система $G_1={f_i, f_j, f_m, f_s, f_l }$ - полная система. Может быть, что в G₁ некоторые функции совпадают, но все равно их не более пяти. Имеем $f_i∉Р_0$следовательно, $ f_i(0,...,0)=1$. Если $f_i(1,...,1)=0$, то f_i не монотонная функция и тогда $\{(f_i, f_j, f_s, f_l)\}$ - полная система. Если $f_i(1,...,1)=1, то f_i(¬ 0,...,¬ 0)=1, а ¬f_i(0,...,0)=0, $ следовательно, fi не самодвойственная функция и тогда $\{(f_i, f_j, f_m, f_l)\}$ полная система. Таким образом, всегда можно выделить полную подсистему, содержащую не более четырех функций.