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