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

Введем обозначение: ={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. XX2(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}.

© 2011-2024 Контрольные работы по математике и другим предметам!