Аналог СДНФ в к-значной логике. Доказательство полноты мн-ва

[YgolovnicK]

Доброго времени суток. Столкнулся с доказательством полноты системы $B=\{0,1,...,k-1, I_{0}(x),...,I_{k-1}(x),\min(x_{1},x_{2}),\max(x_{1},x_{2})\}$
Само доказательство так же приведено (здесь я его приводить не буду). В доказательстве используется формула - аналог СДНФ в к-значной логике:

$f(x_{1},x_{2},...,x{n})=$ $\vee$ $I_{$ $\sigma$ $_{1}}(x_{1})$ $\wedge$ $...$ $\wedge$ $I_{$ $\sigma$ $_{n}}(x_{n})$ $\wedge$ $f($ $\sigma_{1}$ ,..., $\sigma$ $_{n})$ Где дизъюнкция осуществляется по ($\sigma_{1}$,..., $\sigma$ $_{n})$. (Извиняюсь, не сумел изобразить эту скобку под дизъюнкцией, эта формула изображает дизъюнкцию коньюнкций по всем сигма).
Вопрос в следующем: полнота доказывается для системы с константами, где в этой формуле константы?
Помогите, пожалуйста, разобраться.
А еще нужно доказать, что с помощью этой формулы можно представить любую функцию.
Нигде не встретил доказательства (пока что, занимаюсь поиском).

[AKM]

YgolovnicK в сообщении #671884 писал(а):

не сумел изобразить эту скобку под дизъюнкцией

http://dxdy.ru/post1100.html#p1100 писал(а):

$$\bigvee\limits_{(\sigma_1,\ldots,\sigma_n)}\ldots$$

Так, что ли?

[YgolovnicK]

да, благодарю. Получается следующее:

$$f(x_1,x_2,...,x_n)=\bigvee\limits_{(\sigma_1,\ldots,\sigma_n)} I_{\sigma_{1}}(x_1)\wedge...\wedge I_{\sigma_{n}}(x_n)\wedge f(\sigma_1,...,\sigma_n)$$

Доказательство обнаружил на просторах интернета, осталось лишь разобраться, где в формуле константы...

[Xaositect]

YgolovnicK в сообщении #671931 писал(а):

где в формуле константы...

Вот же они: $f(\sigma_1,\dots,\sigma_n)$

[YgolovnicK]

т.е. константы это сигмы? И в остальной формуле? а $I$ - характеристическая система такая, что $I=1$ только тогда, когда сигма и $x$ равны? так?

[Xaositect]

Константы - это не сигмы, а $f(\sigma_1,\dots,\sigma_n)$.
Давайте так: запишите в этой форме функцию, заданную таблицей: $\begin{tabular}{cc}$x_1$ & $f(x_1)$\\ $0$& $2$\\ $1$ & $0$ \\ $2$ & $1$\end{tabular}$

[YgolovnicK]

Xaositect в сообщении #671951 писал(а):

Константы - это не сигмы, а $f(\sigma_1,\dots,\sigma_n)$.
Давайте так: запишите в этой форме функцию, заданную таблицей: $\begin{tabular}{cc}$x_1$ & $f(x_1)$\\ $0$& $2$\\ $1$ & $0$ \\ $2$ & $1$\end{tabular}$

вы меня в тупик поставили
никогда в к-значной логике не делал этого и не объясняли нам...простите неуча и просветите, как надо?

[Xaositect]

YgolovnicK в сообщении #672036 писал(а):

никогда в к-значной логике не делал этого и не объясняли нам...простите неуча и просветите, как надо?

Очевидно, нужно взять формулу и подставить туда нашу функцию. Ладно, давайте я покажу.
Итак, пусть у нас в трехзначной логике функция $f(x_1) = (x_1 - 1) \operatorname{mod} 3$.
Берем формулу $f(x_1,\dots,x_n) = \bigvee\limits_{(\sigma_1,\dots,\sigma_n)\in E_k^n} I_{\sigma_1}(x_1)\wedge\dots\wedge I_n(\sigma_n)\wedge f(\sigma_1,\dots,\sigma_n)$ и подставляем туда нашу $f$. Получаем максимум ($\bigvee$) по всем $\sigma_1$, которая в трехзначной логике может быть $0$, $1$ или $2$.

$$f(x_1) = (I_0(x_1)\wedge f(0)) \vee (I_1(x_1)\wedge f(1)) \vee (I_2(x_1)\wedge f(2)) = (I_0(x_1)\wedge 2) \vee (I_1(x_1) \wedge 0) \vee (I_2(x_1) \wedge 1)$$

-- Вт янв 15, 2013 21:18:29 --

Справа явно видны константы.

[YgolovnicK]

Благодарю за разъяснение. Стало куда понятнее, чем было
Это мне, возможно понадобиться в ближайшее время.
У меня была формула общего вида СКНФ и СДНФ для алгебры логики - я и там не особо понимал, как подставлять, но там объяснили что куда, как по таблице истинности строить.
Здесь же только от Вас узнал. Благодарю за помощь.