Критерий полноты [теорема Поста о функциональной полноте]

Теорема Поста: система функций из $P_2$ функционально полна $\Longleftrightarrow$ система содержит:

1. Функцию, не сохраняющую константу $0$.

2. Функцию, не сохраняющую константу $1$.

3. Несамодвойственную функцию

4. Немонотонную функцию

5. Нелинейную функцию

Доказательство $\Rightarrow$ { прямое } : Пусть система функций $F$ из $P_2$ полна { в $P_2$), допустим, что в системе $F$ нет одной из указанных функций, например немонотонной. Тогда все функции в $F$ монотонны, т.к. класс монотонных функций замкнут относительно суперпозиции, то мы не можем получить ни одной немонотонной функции. Потому система $F$ полной в $P_2$ не является. Противоречие с полнотой $F$. Следовательно, система $F$ содержит все $5$ указанных функций.

Доказательство $\Leftarrow$ { обратное } : Пусть $F$ содержит все $5$ функций: $f\_1(x\_1, x\_2,...,x\_n)$ – не сохраняет константу $0$, $f\_2(x\_1, x\_2,...,x\_n)$ – не сохраняет константу $1$, $f\_3(x\_1, x\_2,...,x\_n)$ – несамодвойственная функция, $f\_4(x\_1, x\_2,...,x\_n)$ – немонотонная функция, $f\_5(x\_1, x\_2,...,x\_n)$ – нелинейная функция.

Покажем, что суперпозицией функций системы $F$ можно получить полную систему $G { xy,\bar { x } }$

1. Пусть $g(x) = f\_1(x\_1, x\_2,...,x\_n)$, тогда $g(0) = f(0,...,0) = 1$ далее возможны два случая:

А } $g(1) = 1 \Rightarrow g(x) \equiv 1$. Функция $h(x) = f\_2(g\_1(x),g\_2(x),...,g\_n(x)) = f\_2(1,..,1) = 0$. Т.е. $h(x) \equiv 0$ получили константы $0$ и $1$.

Б } $g(1) =0 \Rightarrow g(x) = \bar { x }$. По лемме о несамодвойственной функции суперпозицией над $\ { f\_3,\bar { x } \ }$ можно получить одну из констант, например $0$. $f\_1(0,...,0) = 1$ есть другая константа. В обоих случаях получили обе константы.

2. По лемме о немонотонной функции суперпозицией над $\ { f\_4,0,1\ }$ можно получить отрицание $х$.

3. По лемме о нелинейной функции суперпозицией над $\ { f\_5,1,\bar { x } \ }$ можно получить конъюнкцию.

Функции системы $G$ найдены $\ { x\wedge y, \bar { x } \ }$ суперпозицией функций над системой $F$. Следовательно, $F$ – есть полная система в $P_2$. чтд.