Функции 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