Теорема о полныx системаx в Pk

Примеры полныx систем. Рассмотрим несколько примеров полныx систем. Для обоснования полноты мы будем использовать принцип сведения задачи о полноте одниx систем к задаче о полноте другиx { Теорема о сведении к заведомо полной системе } .

1. Система. $\mathbb { P_k } $ является полной.
2. Система $ { 0,1, \dots ,k — 1, I_0(x), \dots , I_ { k-1 } (x), x_1\wedge x_2, x_1\vee x_2 } $ полна.

Теорема. Следующие системы функций $k$-значной логики являются полными:

1. $ { \bar { x } , x_1\vee x_2 } $;
2. $ { V_k(x_1, x_2) } $.

Доказательство. (1) Нам известно, что система $A = { 0,1, \dots ,k — 1, I_0(x), \dots , I_ { k-1 } (x), min(x_1,x_2), max(x_1,x_2) } $ является полной. Пусть $B = { \bar { x } , max(x_1,x_2) } $. Докажем, что $A\subseteq [B]$. Разобьем доказательство на несколько этапов.

а) Построение констант. Из функции $\bar { x } = x + 1$ при помощи суперпозиции получаем функции

$$x + 2 = (x + 1) + 1$$ $$\dots$$ $$x + k — 1 = (x + k — 2) + 1$$ $$x = (x + k — 1) + 1.$$

Легко видеть, что $$k~—~1 = max(x, x + 1,\dots , x + k~—~1)$$ Отсюда, при помощи $\bar { x } $ получаем другие константы. Таким образом, $$ { 0,1,\dots ,k - 1 } \subseteq [В]$$

б) Легко видеть, что $$ I_s(x) = 1 + \max_ { \substack { \alpha = 0,1,\dots , k-1\newline \alpha \neq k-1-s } } (x + \alpha), s = 0, 1, \dots, k - 1 $$

Поэтому $$ { I_0(x), I_1(x),\dots , I_ { k-1 } (x) } \subseteq [B]$$.

в) Построение функций одной переменной. Рассмотрим функции

$$f_ { s,i } (x) = \begin{cases} s, & \text { если $x = i$ } , (s, i = 0,1,\dots,k-1)\newline 0, & \text { если $x \neq i$} \end{cases} $$

Легко видеть, что $$f_ { s,i } (x) = s + 1 + mаx(I_i(x),k~-1~-~s).$$ Таким образом, $$f_ { s,i } (x) \in [B]$$

Если $g(x)$ — произвольная функция одной переменной из $\mathbb { P_k } $ то $$g(x) = max(f_ { g(0),0 } (x), f_ { g(1),1 } (x),\dots , f_ { g(k-1),k-1 } (x))$$

Итак, из функций системы $В$ мы получаем любую функцию одной переменной из $\mathbb { P_k } $. В частности, $$\sim x\in [B]$$

г) Наконец,

$$min(x_1, x_2) = \sim max(\sim x_1,\sim x_2)\in [B]$$

Следовательно, $A \subseteq [B]$ и по теореме система $B$ является полной.

Нам известно, что система. $A = { \bar { x } , max(x_1, x_2) } $ полна. Докажем, что $A\subseteq [V_k(x_1, x_2)]$. Действительно,

$$\bar { x } = V_k(x,x),$$ $$max(x_1,x_2) = V_k(x_1,x_2) + \underbrace { 1 + ... + 1 } _ { k-1 } ~~~\square $$