Функции k - значной логики

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

Функция k -значной логики, зависящая от n переменных, – это закон, отображающий . Множество функций k -значной логики обозначается как Р_k. Функция из Р_k полностью определена, если задана ее таблица истинности, т.е. заданы значения на всех наборах. Наборы можно рассматривать как записи в k -ичной системе счисления чисел от 0 до k –1, всего наборов kⁿ. Функций из Р_k, зависящих от n переменных, будет kⁿ. | P ₃(n)|, например, будет 3, если n = 2, то | P ₃(2)| = 3⁹ = 19683 (k =3, n =2).

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

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

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

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

3. J_i (x)={ k -1, x = i, I = 0, 1, 2,..., k –1}.

4. min (x ₁, x ₂) – обобщение конъюнкции;

5. x ₁× x ₂(mod k) – второе обобщение конъюнкции;

6. max (x ₁, x ₂) – обобщение дизъюнкции;

7. x ₁+ x ₂(mod k) – сумма по mod k.

Принято min (x ₁, x ₂) обозначать x ₁& x ₂, max (x ₁, x ₂) обозначать x ₁Ú x ₂.

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