Теорема об аналоге СДНФ в Pk

Теорема: Каждую функцию $k$-значной логики можно представить в виде

$f(x_1, x_2, \dots , x_n) = \large {\bigvee\limits_{(\sigma_{1}, \sigma_{2}, \dots ,\sigma_{n}) \in \mathbb{E}_{k}^n}} \normalsize I_{\sigma_{1}}(x_1) \wedge I_{\sigma_{2}}(x_2) \wedge \dots \wedge I_{\sigma_{n}}(x_n) \wedge f(\sigma_{1}, \sigma_{2}, \dots, \sigma_{n})$,

Доказательство: Подставим вместо переменных $x_1,\dots, x_n$ любые конкретные значения $a_1,\dots, a_n \in \mathbb{E}_{k}$.

Тогда в левой части равенства получим $f(a_1,\dots, a_n)$, в правой $\large {\bigvee\limits_{(\sigma_{1}, \sigma_{2}, \dots ,\sigma_{n})}} \normalsize I_{\sigma_{1}}(a_1) \wedge I_{\sigma_{2}}(a_2) \wedge \dots \wedge I_{\sigma_{n}}(a_n) \wedge f(\sigma_{1}, \sigma_{2}, \dots, \sigma_{n}) = \bigvee {0, \dots, 0,f(a_1,\dots, a_n), 0,\dots,0} = f(a_1,\dots, a_n)$, так как $I_{\sigma_{i}}(a_i) = 0$, если $a_i\neq \sigma_i$ и $I_{\sigma_{i}}(a_i) = k-1$, если $a_i = \sigma_i$, а $k-1 \geq f(a_1,\dots, a_n) \geq 0$ при любых $a_1,\dots, a_n$, соответственно, левая и правая часть равны. $\Box$