Критерий полноты системы функций
Классы функций
- [math]\displaystyle{ T_0 }[/math] — функции, сохраняющие ноль,
- [math]\displaystyle{ T_1 }[/math] — функции, сохраняющие единицу,
- [math]\displaystyle{ S }[/math] — самодвойственные функции,
- [math]\displaystyle{ M }[/math] — монотонные функции,
- [math]\displaystyle{ L }[/math] — линейные функции.
ни в одном из классов [math]\displaystyle{ T_0 }[/math], [math]\displaystyle{ T_1 }[/math], [math]\displaystyle{ S }[/math], [math]\displaystyle{ M }[/math], [math]\displaystyle{ L }[/math]:
[math]\displaystyle{ \mathcal P\not \subseteq T_0 }[/math], [math]\displaystyle{ \mathcal P\not \subseteq T_1 }[/math], [math]\displaystyle{ \mathcal P\not \subseteq S }[/math], [math]\displaystyle{ \mathcal P\not \subseteq M }[/math], [math]\displaystyle{ \mathcal P\not \subseteq L }[/math].Необходимость. Если система функций [math]\displaystyle{ \mathcal P }[/math] лежит полностью в одном из классов [math]\displaystyle{ R\in\{T_0, T_1, S, M, L\} }[/math], то, поскольку все эти классы замкнуты и не совпадают с [math]\displaystyle{ P_2 }[/math], [math]\displaystyle{ [\mathcal P]\subseteq [R]\neq P_2 }[/math]. Тогда система [math]\displaystyle{ \mathcal P }[/math] — не является полной.
Достаточность. Пусть [math]\displaystyle{ f_0, f_1, f_S, f_M, f_L\in\mathcal P }[/math] такие функции, что [math]\displaystyle{ f_0\notin T_0 }[/math], [math]\displaystyle{ f_1\notin T_1 }[/math], [math]\displaystyle{ f_S\notin S }[/math], [math]\displaystyle{ f_M\notin M }[/math], [math]\displaystyle{ f_L\notin L }[/math] (некоторые из функций могут совпадать). Проведем доказательство в несколько этапов.
1. Покажем, что с помощью [math]\displaystyle{ f_0 }[/math], [math]\displaystyle{ f_1 }[/math], [math]\displaystyle{ f_S }[/math] можно получить 0 и 1.
1.1. Пусть [math]\displaystyle{ f_0(1,...,1)=1 }[/math]. Пусть [math]\displaystyle{ \varphi(x) = f_0(x,...,x) }[/math]. Тогда [math]\displaystyle{ \varphi(0) = \varphi(1) = 1 }[/math]. Значит [math]\displaystyle{ \varphi(x) = 1 }[/math] и, имея единицу, можно получить вторую константу [math]\displaystyle{ 0=f_1(1,...,1) }[/math].
1.2. Пусть теперь [math]\displaystyle{ f_0(1,...,1)=0 }[/math]. Тогда [math]\displaystyle{ \varphi(x) = f_0(x,...,x) = \overline x }[/math]. Подставляя в [math]\displaystyle{ f_S }[/math] [math]\displaystyle{ x }[/math] и [math]\displaystyle{ \overline x }[/math] по лемме о несамодвойственной функции получаем константу [math]\displaystyle{ 0 }[/math] или [math]\displaystyle{ 1 }[/math] и с помощью [math]\displaystyle{ \overline x }[/math] получаем вторую константу.
2. По лемме о немонотонной функции, подставляя константы в [math]\displaystyle{ f_M }[/math] можно получить [math]\displaystyle{ \neg x }[/math].
3. Используя [math]\displaystyle{ f_L }[/math], константы и [math]\displaystyle{ \neg x }[/math], по лемме о нелинейной функции можно получить [math]\displaystyle{ x\wedge y }[/math].
Так как [math]\displaystyle{ \{\neg, \wedge\} }[/math] — полная система функций, то и система [math]\displaystyle{ \mathcal P }[/math] — полная.
Рассмотрим принадлежность функций [math]\displaystyle{ \mathcal P }[/math] классам [math]\displaystyle{ T_0 }[/math], [math]\displaystyle{ T_1 }[/math], [math]\displaystyle{ S }[/math], [math]\displaystyle{ M }[/math], [math]\displaystyle{ L }[/math] и заполним таблицу.
[math]\displaystyle{ \begin{array}{|c|c|c|c|c|c|} \hline & T_0 & T_1 & S & M & L\\ \hline 0 & + & - & - & + & + \\ \hline 1 & - & + & - & + & + \\ \hline x y & + & + & - & + & - \\ \hline x\oplus y \oplus z & + & + & + & - & + \\ \hline \end{array} }[/math]
Рассмотрим, например, проверку функции [math]\displaystyle{ x\oplus y \oplus z }[/math]:
a) [math]\displaystyle{ 0\oplus 0 \oplus 0 = 0 }[/math] [math]\displaystyle{ \Rightarrow }[/math] [math]\displaystyle{ x\oplus y \oplus z\in T_0 }[/math];
b) [math]\displaystyle{ 1\oplus 1 \oplus 1 = 1 }[/math] [math]\displaystyle{ \Rightarrow }[/math] [math]\displaystyle{ x\oplus y \oplus z\in T_1 }[/math];
c) [math]\displaystyle{ \overline{\overline x \oplus \overline y \oplus \overline z} = 1 \oplus (1\oplus x) \oplus (1\oplus y) \oplus (1 \oplus z) = x\oplus y \oplus z }[/math] [math]\displaystyle{ \Rightarrow }[/math] [math]\displaystyle{ x\oplus y \oplus z\in S }[/math];
d) [math]\displaystyle{ (1,0,0)\prec (1,1,0) }[/math], но [math]\displaystyle{ 1 = 1\oplus 0 \oplus 0 \gt 1\oplus 1 \oplus 0 = 0 }[/math] [math]\displaystyle{ \Rightarrow }[/math] [math]\displaystyle{ x\oplus y \oplus z\notin M }[/math];
e) Очевидно, функция является линейной: [math]\displaystyle{ x\oplus y \oplus z\in L }[/math].
Теперь, заполнив и проанализировав таблицу, можно убедиться, что система функций [math]\displaystyle{ \mathcal P }[/math] является полной, так как в каждом столбце, соответствующем одному из классов присутствует хотя бы один минус.
В то же время ни одно подмножество [math]\displaystyle{ \mathcal P }[/math] полной системой не является, поскольку,
если вычеркнуть в таблице хотя бы одну строку, появится столбец не имеющий минуса.
Пусть [math]\displaystyle{ \mathcal B\subseteq \mathfrak M }[/math]. [math]\displaystyle{ \mathcal B }[/math] называется базисом класса [math]\displaystyle{ \mathfrak M }[/math], если
- [math]\displaystyle{ [\mathcal B] = \mathfrak M }[/math];
- [math]\displaystyle{ \forall f\in \mathcal B \Rightarrow [\mathcal B\setminus \{f\}]\neq \mathfrak M }[/math].
Базисом [math]\displaystyle{ P_2 }[/math] будет ее подсистема [math]\displaystyle{ \{1, xy, x\oplus y\} }[/math].
[math]\displaystyle{ \begin{array}{|c|c|c|c|c|c|} \hline & T_0 & T_1 & S & M & L\\ \hline 0 & + & - & - & + & + \\ \hline 1 & - & + & - & + & + \\ \hline x y & + & + & - & + & - \\ \hline x\oplus y & + & - & - & - & + \\ \hline \end{array} }[/math]