Критерий полноты системы функций - История изменений

St001214: Новая страница: «Классы функций * $T_0$ {{---}} функции, сохраняющие ноль, *
2021-12-10T12:35:10Z

Новая страница: «Классы функций * <math>T_0</math> {{---}} функции, сохраняющие ноль, * <ma...»

Новая страница
Классы функций
* <math>T_0</math> {{---}} [[Функции сохраняющие ноль|функции, сохраняющие ноль]],
* <math>T_1</math> {{---}} [[Функции сохраняющие единицу|функции, сохраняющие единицу]],
* <math>S</math> {{---}} [[Самодвойственные функции|самодвойственные функции]],
* <math>M</math> {{---}} [[Монотонные функции|монотонные функции]],
* <math>L</math> {{---}} [[Линейные функции|линейные функции]].

{{Теорема
|author= Теорема Поста
|statement= Для полноты системы функций <math>\mathcal P\subseteq P_2</math> необходимо и достаточно, чтобы <math>\mathcal P</math> не лежал полностью
ни в одном из классов <math>T_0</math>, <math>T_1</math>, <math>S</math>, <math>M</math>, <math>L</math>:
<math>\mathcal P\not \subseteq T_0</math>, <math>\mathcal P\not \subseteq T_1</math>, <math>\mathcal P\not \subseteq S</math>, <math>\mathcal P\not \subseteq M</math>, <math>\mathcal P\not \subseteq L</math>.

|proof= '''Необходимость.''' Если система функций <math>\mathcal P</math> лежит полностью
в одном из классов <math>R\in\{T_0, T_1, S, M, L\}</math>, то, поскольку все эти классы
замкнуты и не совпадают с <math>P_2</math>, <math>[\mathcal P]\subseteq [R]\neq P_2</math>. Тогда
система <math>\mathcal P</math> — не является полной.

'''Достаточность.'''
Пусть <math>f_0, f_1, f_S, f_M, f_L\in\mathcal P</math> такие функции, что
<math>f_0\notin T_0</math>,
<math>f_1\notin T_1</math>,
<math>f_S\notin S</math>,
<math>f_M\notin M</math>,
<math>f_L\notin L</math> (некоторые из функций могут совпадать).
Проведем доказательство в несколько этапов.

1. Покажем, что с помощью <math>f_0</math>, <math>f_1</math>, <math>f_S</math> можно получить 0 и 1.

1.1. Пусть <math>f_0(1,...,1)=1</math>.
Пусть <math>\varphi(x) = f_0(x,...,x)</math>. Тогда <math>\varphi(0) = \varphi(1) = 1</math>.
Значит <math>\varphi(x) = 1</math> и, имея единицу, можно получить вторую константу <math>0=f_1(1,...,1)</math>.

1.2. Пусть теперь <math>f_0(1,...,1)=0</math>.
Тогда <math>\varphi(x) = f_0(x,...,x) = \overline x</math>.
Подставляя в <math>f_S</math> <math>x</math> и <math>\overline x</math> по лемме о несамодвойственной функции
получаем константу <math>0</math> или <math>1</math> и с помощью <math>\overline x</math> получаем вторую константу.

2. По лемме о немонотонной функции, подставляя константы в <math>f_M</math> можно получить <math>\neg x</math>.

3. Используя <math>f_L</math>, константы и <math>\neg x</math>, по лемме о нелинейной функции можно
получить <math>x\wedge y</math>.

Так как <math>\{\neg, \wedge\}</math> — полная система функций, то и система <math>\mathcal P</math> — полная.
}}

{{Пример
|content=Требуется проверить на полноту систему функций <math>\mathcal P = \{0, 1, x y, x\oplus y\oplus z\}</math>.

Рассмотрим принадлежность функций <math>\mathcal P</math> классам <math>T_0</math>, <math>T_1</math>, <math>S</math>, <math>M</math>, <math>L</math> и заполним таблицу.

<math>
\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>x\oplus y \oplus z</math>:

a) <math>0\oplus 0 \oplus 0 = 0</math> <math>\Rightarrow</math> <math>x\oplus y \oplus z\in T_0</math>;

b) <math>1\oplus 1 \oplus 1 = 1</math> <math>\Rightarrow</math> <math>x\oplus y \oplus z\in T_1</math>;

c) <math>\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>\Rightarrow</math> <math>x\oplus y \oplus z\in S</math>;

d) <math>(1,0,0)\prec (1,1,0)</math>, но
<math>1 = 1\oplus 0 \oplus 0 \gt 1\oplus 1 \oplus 0 = 0</math>
<math>\Rightarrow</math> <math>x\oplus y \oplus z\notin M</math>;

e) Очевидно, функция является линейной: <math>x\oplus y \oplus z\in L</math>.

Теперь, заполнив и проанализировав таблицу, можно убедиться, что система функций
<math>\mathcal P</math> является полной, так как в каждом столбце, соответствующем одному
из классов присутствует хотя бы один минус.

В то же время ни одно подмножество <math>\mathcal P</math> полной системой не является, поскольку,
если вычеркнуть в таблице хотя бы одну строку, появится столбец не имеющий минуса.
}}

{{Определение
|definition= Пусть <math>\mathfrak M</math> — замкнутый класс функций.
Пусть <math>\mathcal B\subseteq \mathfrak M</math>.
<math>\mathcal B</math> называется базисом класса <math>\mathfrak M</math>, если
# <math>[\mathcal B] = \mathfrak M</math>;</li>
# <math>\forall f\in \mathcal B \Rightarrow [\mathcal B\setminus \{f\}]\neq \mathfrak M</math>.</li>
}}

{{Пример
|content= Система <math>\{0, 1, xy, x\oplus y\}</math> полная, но базисом <math>P_2</math> не является.
Базисом <math>P_2</math> будет ее подсистема <math>\{1, xy, x\oplus y\}</math>.

<math>
\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>
}}