Теорема об аналоге СДНФ в 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$