Функции k-значной логики. Элементарные функции. Лемма об аналоге правила де Моргана

Аналогичным функциям алгебры двузначной логики, можно определить функции $k$-значной логики. Значения переменных и самих функций берутся из множества $\mathbb { E } _ { k } = \ { 0,1,\dots, k~—~1\ } , k \geq 3$. Множество всех таких функций обозначается через $\mathbb { P } _ { k } $. Как и булевы функции, каждую функцию $f(x_1,\dots, x_n)$ из $\mathbb { P } _ { k } $ можно задать таблицей.

$$ \begin{array} { | c c c || c | } \hline x_1 & \dots & x_n & f(x_1,\dots,x_n) \\ \hline 0 & \dots & 0 & f(x_1,\dots,x_n) \\ & \dots & & \dots \\ \sigma_1 & \dots & \sigma_n & f(\sigma_1,\dots,\sigma_n) \\ & \dots & & \dots \\ k~-~1 & \dots & k~-~1 & f(k~-~1,\dots,k~-~1) \\ \hline \end{array} $$

В таблице приведены значения некоторых элементарных функций при $k = 3$

$$ \begin{array} { | c | c | c | c | c | c | c | c | c | c | } \hline x & y & max(x,y) & min(x,y) & x+y(mod~3) & xy(mod~3)
& x\perp y & x\rightarrow y & x - y & V_3 { (x,y) } \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 1\\ \hline 0 & 1 & 1 & 0 & 1 & 0 & 0 & 2 & 2 & 2\\ \hline 0 & 2 & 2 & 0 & 2 & 0 & 0 & 2 & 1 & 0\\ \hline 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 2\\ \hline 1 & 1 & 1 & 1 & 2 & 1 & 0 & 2 & 0 & 2\\ \hline 1 & 2 & 2 & 1 & 0 & 2 & 0 & 2 & 2 & 0\\ \hline 2 & 0 & 2 & 0 & 2 & 0 & 2 & 0 & 2 & 0\\ \hline 2 & 1 & 2 & 1 & 0 & 2 & 1 & 1 & 1 & 1\\ \hline 2 & 2 & 2 & 2 & 1 & 1 & 0 & 2 & 0 & 2\\ \hline \end{array} $$

Пусть $p_k(n)$ — число всех функций $f(x_1,\dots, x_n)$ из $\mathbb { P } _ { k } $. Количество различных наборов значений переменных равно $k^n$. На каждом из этих наборов функции $f(x_1,\dots, x_n)$ может принимать любое из $k^n$ значений. Следовательно, всего таких функций будет $p_k(n) = k^ { k^n } $. Это число очень быстро растет, например уже в $\mathbb { P } _ { 3 } $ число функций от переменных $x_1$ и $x_2$ равно $p_3(2) = 19683$. Все основные понятия, такие, как формула над множеством функций, значение формулы на наборе значений переменных, функция, реализуемая формулой, существенная и несущественная переменные и др., вводится точно так же, как и в двузначной логике { определения почти дословно повторяются } , и мы не будем их воспроизводить. Однако не следует забывать, что переменные и функции принимают уже не два значения, а больше. В частности, если известно значение $x$ из то нельзя определить значение $y$ из $\mathbb { E } _ { k } $ только на основе соотношения $y\neq x~( k \geq 3)$. Это приводит к принципиальным отличиям $\mathbb { P } _ { k } ,~k \geq 3$, от $\mathbb { P } _ { 2 } $ .

Известно, что при подстановке одной булевой функции в другую сохраняется существенная зависимость от переменных. Покажем, что для функций $k$-значной логики при $k \geq 3$ аналогичное утверждение неверно.

Рассмотрим функцию $\varphi(x_1, x_2)$, заданную табл.

$$ \begin{array} { | c | c c c | } \hline x_1 & 0 & 1 & 2 \\ \hline 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 2 & 0 & 0 & 1 \\ \hline \end{array} $$

Функция $\varphi$ принадлежит $\mathbb { P } _ { 3 } $ и принимает ненулевое значение только на наборе $(2,2)$. Поэтому функция $\varphi(x, \varphi(y,z))$ — константа 0, поскольку для любых $\beta$, $\gamma \in \mathbb { E } _ { 3 } $ выполняется неравенство $\varphi(\beta, \gamma)~\neq~2$

Рассмотрим следующие "элементарные" функции $k$-значной логики.

1. Константы $0,1,\dots, k~—~1$.
2. Тождественная функция $x$.
3. Отрицания: Функции $f (x) = \bar { x } = x + 1 (mod~k)$ — отрицание Поста или циклический сдвиг, $f (x) = \sim N(x) = k - 1 - x$ — отрицание Лукасевича; Эти функции являются обобщениями отрицания в $\mathbb { P } _ { 2 } $. Функция $N(x)$ является "зеркальным" отражением $x$. Она обозначается также $\sim x$
4. Характеристическая функция { 2-го рода } $I_i(x)$: $$I_i(x) = \begin{cases} k-1, & \text { если $x = i$ } \newline 0, & \text { если $x \neq i$ } \end{cases} $$
5. Характеристическая функция { 1-го рода } $j_i(x) = 0, 1, \dots ,k — 1$: $$j_i(x) = \begin{cases} 1, & \text { если $x = i$ } \newline 0, & \text { если $x \neq i$ } \end{cases} $$ Эти функции являются аналогами функции $x^\sigma$ в $\mathbb { P } _ { 2 } $;
6. Минимум: Функции $min(x_1,x_2)$ и $x_1x_2 (mod~k)$. Эти функции являются обобщением конъюнкции. Функция $min(x_1,x_2)$ обозначается также $x_1\wedge x_2$;
7. Максимум: Функция $max(x_1,x_2)$. Она является аналогом дизъюнкции в $\mathbb { P } _ { 2 } $ и обозначается также $x_1\vee x_2$;
8. Сложение по модулю $k$: $f(x, y) = x_1 + x_2~(mod~k)$;
9. Умножение по модулю $k$: $f (x, y) = xy~(mod~k)$;
10. Разность по модулю $k$: $$(x-y)mod~k = \begin{cases} k-(y-x), & \text { если $0 \leq x < y \leq k-1$ } \newline x-y, & \text { если $0 \leq y \leq x \leq k-1$ } \end{cases} $$
11. Усеченная разность $x\perp y$: $$x\perp y = \begin{cases} 0, & \text { если $0 \leq x < y \leq k-1$ } \newline x-y, & \text { если $0 \leq y \leq x \leq k-1$ } \end{cases} $$
12. Импликация $x\supset y$: $$x\supset y = \begin{cases} k-1, & \text { если $0 \leq x < y \leq k-1$ } \newline (k-1)-x+y, & \text { если $0 \leq y \leq x \leq k-1$ } \end{cases} $$
13. Функция Веба: $ \nu_k(x,y)=(max(x,y)+1)mod~k$:
14. Транспортизация чисел $i$ и $j: t_ { ij } (x),i,j\in \ { 0,1,\dots ,k-1\ } , i\neq j$ $$t_ { ij } (x) = \begin{cases} x, & \text { если $x\in\ { i,j\ } ,$ } \newline j, & \text { если $x = i$ } \newline i, & \text { если $x = j$ } \end{cases} $$

Теорема: Об аналоге правила де Моргана

$\sim (x_1\vee x_2) = (\sim x_1)\wedge (\sim x_2)$ $\sim (x_1\wedge x_2) = (\sim x_1)\vee (\sim x_2)$

Докажем $\sim (x_1\vee x_2) = (\sim x_1)\wedge (\sim x_2)$. 2 случая для $x_1, x_2\in E_k$

1. $x_1\geq x_2;~x_1\vee x_2=x_1$ $\sim (x_1\vee x_2) = k-1-x_1$ $\sim x_1 = k-1-x_1$ $\sim x_2 = k-1-x_2$ $(\sim x_1)\wedge (\sim x_2) = k-1-x_1$

2. $x_1 < x_2;~\sim (x_1\vee x_2) = k-1-x_2$ $(\sim x_1)\wedge (\sim x_2) = k-1-x_2$

Пример: Показать справедливость следующих утверждений;

$\sim min ( x,y ) = max ( \sim x, \sim y )$, но $\overline { min(x, y) } \neq max(\bar { x } ,\bar { y } )$.

Обозначим эти соотношения следующим образом: $f_1=f_2$ и $f_3 \neq f_4$. Тогда справедливость этих соотношений при $k=3$ видна из следующей таблицы.

$x$	$y$	$min(x,y)$	$f_1$	$\sim x$	$\sim y$	$f_2$	$f_3$	$\bar x$	$\bar y$	$f_4$
0	0	0	2	2	2	2	1	1	1	1
0	1	0	2	2	1	2	1	1	2	2
0	2	0	2	2	0	2	1	1	0	1
1	0	0	2	1	2	2	1	2	1	2
1	1	1	1	1	1	1	2	2	2	2
1	2	1	1	1	0	1	2	2	0	2
2	0	0	2	0	2	2	1	0	1	1
2	1	1	1	0	1	1	2	0	2	2
2	2	2	0	0	0	0	0	0	0	0