Функции 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$ видна из следующей таблицы.