Теорема о полны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$$