3.1. Элементарные функции многозначных логик. Представление функций формулами специального вида
Будем
рассматривать число значений истинности
k>2,
k
N. Множество
всех значений истинности обозначим
че-рез Ek
=
{0,1,...,k-1}.
Произведением Enk
называется мно-жество всех наборов вида
,
где все
.
Определение.
Функция
называется функцией
многозначной (k-значной)
логики,
еслихnEnk,
f(хn)Enk
.
Множество
всех функций
k
- значной логики обозна-чается
.
Определения существенных и фиктивных перемен-ных, формул, операций суперпозиции и замыкания, полно-ты имеют тот же вид, что и в алгебре логики.
Основные способы задания функций k - значной ло-гики - с помощью таблиц истинности и выражение через элементарные функции. В таблицах истинности наборы значений переменных располагаются в лексикографическом порядке, при котором векторам х n соответствуют числа от 0 до k n - 1 в системе счисления с основанием k .
В качестве элементарных выделены следующие функ-ции:
1.Константы. Принимают значения от 0 до k -1 , являются функциями произвольного числа переменных, принимаю-щими постоянные значения на всех наборах.
2.Отрицание Поста: х 1(mod k). Обозначается .
3.Отрицание
Лукасевича:
.
Обозначается N(x)
или
х.
4.Характеристическая
функция 1-го рода
:
164
5.Характеристическая
функция 2-го рода
:
6.Минимум : min (x,y).
7.Максимум : max (x,y).
8.Сумма по mod k : x y.
9.Произведение по mod k : xy (mod k).
10.Усеченная разность:
0 , x < y,
x
y
=
x-y, x y.
11.Импликация:
12.Функция Вебба:
V k(x,y)=max(x,y) 1.
13. Разность по mod k :
Для функций из существуют формульные выраже-ния, аналогичные нормальным формам и полиному Жегал-кина в алгебре логики.
Определение.
Первой
формой
функции
яв-ляется её представление в виде:
где максимум берется по всем наборам значений перемен-ных х n.
165
Определение. Второй формой функции является её представление в виде:
где сумма берется по всем наборам значений х n.
Замечание. При представлении функций в первой и второй формах построение производится непосредственно по наборам переменных и значениям функции. При этом наборы, на которых f = 0, можно опускать, поскольку внут-ренние функции форм на них обращаются в нуль.
Определение. Многочленом по модулю k называется выражение вида:
Q(x n)=a0 a1X1 ... a mXm,
где
а X
j
- произведения переменных
.
Поскольку умножение ассоциативно, то величина про-изведения хх...х не зависит от порядка выполнения эле-ментарных умножений и его будем обозначать в виде степени хs , где s- число сомножителей в произведении.
Определение.
Функция
f
(x
n)
Pk
реализуется
мно-гочленом
Q(x
n)
по
,
если Q(x
n)
= f
(x
n)
при всех
.
В первой и второй формах функции в представимы всегда. В форме многочлена Q(x n) по модулю k все функ-ции в представимы только тогда, когда k - простое чис-ло. Возможность представления любой функции в виде многочлена при простом k следует из того, что все степе-ни переменной хs при s = 0 ,..., k - 1 будут являться по-парно различными функциями. В Q(x n) общее число по-парно различных (с точностью до перестановки сомножи-телей) произведений, содержащих степени переменных из x n от 0 до k-1, равно числу kn всех возможных наборов переменных. Для построения Q(xn ) можно использовать
166
метод неопределенных коэффициентов. При составном k степени переменных хs при s = 0, ... , k-1 не будут различ-ными функциями, поэтому представление многочленами возможно не для всех функций.
Пример 1 . Представить функцию f = x y 2 при k =3 в первой и второй формах.
Решение. Таблица истинности функции f = x y 2 имеет сле-дующий вид:
N |
x |
y |
f |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
2 |
0 |
2 |
0 |
3 |
1 |
0 |
0 |
4 |
1 |
1 |
1 |
5 |
1 |
2 |
1 |
6 |
2 |
0 |
0 |
7 |
2 |
1 |
2 |
8 |
2 |
2 |
2 |
Обе формы получаем путём подстановки значений перемен-ных и функции в общие форму-лы.
Первая форма принимает вид:
f=max{min(1,J1(x),J1(y)),min(1,J1(x),J2(y)),min(2,J2(x),J1(y)),
min(2,J2(x),J2(y))}.
Вторая форма:
f =j1(x) j1(y) j1(x) j2(y) 2 j2(x) j1(y) 2 j2(x) j2(y).
Пример 2 . Представить функцию f = x y 2 при k =3 в виде многочлена по модулю 3.
Решение.
Таблица истинности функции f = x y 2 приведена ниже. В общем виде многочлен от двух переменных х, у , степени которых не превышают 2 ( 2=3-1), имеет вид:
Q = 0 1 х 2 y 3 хy 4 x 2 5 y 2 6 x 2y 7 y 2x 8x 2y 2.
167
N |
x |
y |
f |
0 |
0 |
0 |
2 |
1 |
0 |
1 |
2 |
2 |
0 |
2 |
2 |
3 |
1 |
0 |
1 |
4 |
1 |
1 |
2 |
5 |
1 |
2 |
2 |
6 |
2 |
0 |
0 |
7 |
2 |
1 |
1 |
8 |
2 |
2 |
2 |
0. х=0, у=0. Q = 0 =2, 0 =2.
1. х=0, у=1. Q = 2 2 1 + 5 1=2, 2 5 =0.
2. х=0, у=2. Q = 2 2 2 5 1=2, 22 5 =0. Из 1 и 2 следует: 2 = 0, 5 = 0.
3. х=1, у=0. Q = 2 1 1 4 1=1 1 4 =1-2=2.
4. х=1, у=1. Q=2 1 1 3 1 4 1 6 1 7 1 81=2. 1 3 4 6 7 8 =0.
5. х=1,у=2. Q=2 1 1 3 2 4 1 6 2 7 1 81=2.1 3 4 26 7 8 =0.
6. х=2, у=0. Q = 2 1 2 4 1=0 21 4 =0 - 2=1.
Из 3 и 6 следует: 1 = 2, 4 = 0.
7. х=2,у=1. Q=2 22 3 2 6 1 7 2 81=1. 23 6 2 7 8 =1.
8. х=2,у=2. Q=2 22 3 1 6 2 7 2 81=2. 3 2 6 2 7 8 =2.
Подставив в 4 и 5 1 = 2, 4 = 0 и объединив полученные уравнения с 7 и 8, получим следующую систему из четырёх уравнений относительно 3 , 6 , 7 , 8 :
а) 3 6 7 8 =1.
б) 23 2 6 7 8 =1.
в) 23 6 2 7 8 =1.
г) 3 2 6 2 7 8 =2.
Сложив б) - г),получим : 23 2 6 2 7 =1.
Отсюда : 3 6 7 =2.Вычитая полученное уравнение из а), получим: 8 =2.
168
Подставляя 8 =2 в б)-г) и вычитая их из уравнения 23 2 6 2 7 =1, получим: 7=2, 6 =2, 3 =1.
В итоге искомый многочлен примет вид:
f=2 2 х ху 2 x y 2 2x 2y 2x 2y 2.
Задачи.
1.Найти выражения функций в первой форме:
а)
f = x
y, k = 3,4;
б)
в) f = max(x,y), k = 3; г) f = xy, k = 4; д) f = (x y), k = 3; е) f = x 2y 2, k = 4; ж) f = max(x,y), k = 3.
2.Найти выражение функций во второй форме:
а) f = min(xy , x y), k = 3; б) f = min(x, y 2), k = 4;
в) f = max(x,y), k = 3; г) f = xy, k = 4; д) f = (x y), k = 3; е) f = x 2y 2, k = 4; ж) f = max(x,y), k = 3.
3.Разложить функции в многочлен по модулю k:
а) f = min(x , j 2(y) ), k = 3,5; б) f = min(x , y 2), k = 3,5; в) f = x y, k = 3; г) f = x 2y 2, k = 3; д) f = x y 3, k = 3.