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

Далее:

Вычисление тройного интеграла. Теорема о переходе от тройного интеграла к повторному

Определение криволинейного интеграла второго рода

Специальные векторные поля

Вычисление объёмов

Полином Жегалкина. Теорема о представлении в виде полинома Жегалкина

Вычисление поверхностного интеграла второго рода

Вычисление криволинейного интеграла первого рода. Примеры

Замена переменных в двойном интеграле. Двойной интеграл в полярных координатах

Поверхностный интеграл первого рода и его свойства

Несобственные интегралы по неограниченной области

Формулы. Равенство функций и эквивалентность формул. Основные эквивалентности

Вычисление поверхностного интеграла первого рода

Поток векторного поля через поверхность

Класс $L$. Теорема о замкнyтости класса $L$

Критерий полноты {формулировка}. Лемма о нелинейной функции

Огравление $\Rightarrow $