2.7. Функции K - значной логики

Введем обозначение: Eк={0, 1, 2, ..., K–1}.

Функция K-значной логики, зависящая от N переменных, – это закон, отображающий . Множество функций K-значной логики обозначается как РK. Функция из РK полностью определена, если задана ее таблица истинности, т. е. заданы значения на всех наборах. Наборы можно рассматривать как записи в K-ичной системе счисления чисел от 0 до K–1, всего наборов KN. Функций из РK, зависящих от N переменных, будет KN. |P3(N)|, например, будет 3, если N = 2, то |P3(2)| = 39 = 19683 (K=3, N=2).

X1 X2 . . . Xn-1 Xn	F
0 0 . . . 0 0 0 0 . . . 0 1 . . . . . . . . . . . . . . . . . . . 0 0 . . . 0 K–1 0 0 . . . 1 0 . . . . . . . . . . . . . . . . . . . K–1 K–1 . . . K–1 K–1	. . . . . . .

В K - значной логике также есть функции, которые называются элементарными. Приведем некоторые из них, примеры будем приводить для K = 3 и N = 2.

1. Циклический сдвиг или отрицание Поста: = X+1(Mod K).

2. Зеркальное отображение или отрицание Лукосевича: NX = K–1–X.

Эти две функции являются обобщением отрицания.

3. Ji(X)={K-1, X = I, I = 0, 1, 2, ..., K–1}.

X1	X2	Nx	J0(X)	J1(X)	J2(X)
0 1 2	1 2 0	2 1 0	2 0 0	0 2 0	0 0 2

4. Min(X1,X2) – обобщение конъюнкции;

5. X1×X2(Mod K) – второе обобщение конъюнкции;

6. Max(X1,X2) – обобщение дизъюнкции;

7. X1+X2(Mod k) – сумма по mod K.

X1	X2	Min(X1,X2)	X1X2(Mod 3)	Max(X1X2)	X1+X2(Mod 3)
0 0 0 1 1 1 2 2 2	0 1 2 0 1 2 0 1 2	0 0 0 0 1 1 0 1 2	0 0 0 0 1 2 0 2 1	0 1 2 1 1 2 2 2 2	0 1 2 1 2 0 2 0 1

Принято Min(X1,X2) обозначать X1&X2, Max(X1,X2) обозначать X1ÚX2.

Как и в двузначной логике, можно ввести понятие формулы над множеством и ставить вопрос о полной в РK системе функций.

Теорема о полной в Рk системе функций

Cистема функций {Max(X1,X2), Min(X1,X2), 0, 1, ..., K–1, J0(X), J1(X), ..., JK-1(X)} является полной в Рk и любая функция F(X1, ..., Xn) Î Pk выражается формулой над этой системой следующим образом:

.

Эта формула есть своеобразный аналог СДНФ.

Доказательство. Покажем справедливость этой формулы на любом произвольном наборе (A1, ..., AN). Слева имеем F(A1, ..., AN). Справа имеем .

Если для какого-нибудь J из {1, 2, ..., N} IJ ¹ AJ, то (AJ) = 0 и Min[J (A1), (A2), …, (AN), F(I1,..,IN)] = 0. Рассмотрим набор (I1, ..., IN), где I1 = A1, I2 = A2, ..., In = AN, тогда J (A1) = K–1, J (A2) = K–1, .., J (AN) = K–1 и Min[J (A1), ... , J (AN) F(A1, …, AN).] = Min[(K–1), ..., (K–1), F(A1, …, AN).] = F(A1, …, AN), но тогда Так как набор (A1, ..., AN) произвольный и равенство на нем справедливо, то формула верна. В этой формуле использованы функции Ji(X), (I = 0, ..., K–1), Min(X1X2), Max(X1X2) и константы 0, ..., K–1, так как функция F(I1, ..., In) есть число из {0, 1, ..., K–1}.

< Предыдущая		Следующая >