2.1. Элементарные функции

В k- значной логике значения аргументов и значения функции могут принимать любые значения из следующего множества {0, 1, …, к-1}.

Функция f(x , …, x ) будет полностью определена, если задана ее таблица, т.е. заданы ее значения для всех наборов значений переменных.

Например, для некоторой функции двух переменных при k = 3 это может быть следующая таблица

Таблица 2.1

x	0	0	0	1	1	1	2	2	2
x	0	1	2	0	1	2	0	1	2
f(x , x )	0	0	1	2	0	2	1	0	1

Совокупность всех функций k– значной логики, зависящих от n переменных обозначается Р . Их число равно Р = k .

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

Понятия фиктивной и существенной переменных, эквивалентных функций, фор-мулы, операций суперпозиции и замыкания, замкнутого класса, базиса и другие в k –значной логике определяются так же, как соответствующие понятия в двузначной логи-

ке. Поэтому в дальнейшем приводятся определения только таких понятий, которые чем

то существенным отличаются от аналогичных понятий в Р .

Следующие функции k – значной логики называются элементарными.

1). Константы: 0, 1, …, k-1.

Эти функции рассматриваются как функции, зависящие от произвольного конечного числа переменных (включая и нуль переменных).

2). Отрицание Поста: = x + 1 (mod k).

Здесь представляет обобщение отрицания в смысле “ циклического “ сдвига значений.

3). Отрицание Лукашевича: ~x = (k-1) – x.

Оно представляет другое обобщение отрицания в смысле “зеркального“

отображения значений. Другое обозначение: Nx.

4). Характеристическая функция первого рода значения i:

j (x) = i = 0, 1, …, k-1.

5). Характеристическая функция второго рода значения i:

J (x) = i = 0,1, …, k-1.

6). Минимум x и y: min ( x,y ).

Эта функция представляет обобщение конъюнкции. Другое ее обозначение:

x&y или x∙y.

7). Максимум x и y: max ( x,y ).

Эта функция представляет обобщение дизъюнкции. Другое ее обозначение: x y.

8) Сумма по модулю k: x + y (mod k).

9). Произведение по модулю k: x∙y (mod k).

10). Усеченная разность :

x ÷ y =

11). Импликация : x y =

12). Функция Вебба : V (x,y) = max ( x,y ) + 1 (mod k).

Эта функция представляет собой аналог функции Шеффера.

13). Разность по модулю k: x – y =

14). –x =

В табл 2.2 приведены значения некоторых элементарных функций при k = 3.

Таблица 2.2

Следующие равенства вводятся по определению (при n > 2):

max ( x , …, x , x ) = max [ max ( x , …, x ), x ],

min( x , …, x ) = min [ min ( x , …, x ), x ].