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