2.3. Основные формы функций k – значных логик

Любую функцию f (x , …, x ) из P можно представить в так называемой первой основной форме, являющейся аналогом СДНФ для функций двузначной логики

f ( x , …, x ) = max { min [ f (s , …, s ), J (x ), J (x ), …, J (x ) ] }, (2.4)

s

где максимум берется по всем наборам s = (s , …, s ) значений переменных

x , …, x .

Пример. Представить в первой форме при k = 3 следующую функцию:

f ( x, y ) = max { j (x) ∙ j (y), x ∙ [ j (y) + 2 · j (y) ] }.

Обозначим через f = j (x) · j (y), f = j (y) + 2 · j (y) .

Составим таблицу заданной функции.

Таблица 2.8

x	y	j (x)	J (y)	f	j (y)	j (y)	2j (y)	f	x·f	f(x,y)
0	0	1	1	1	0	0	0	0	0	1
0	1	1	0	0	1	0	0	1	0	0
0	2	1	0	0	0	1	2	2	0	0
1	0	0	1	0	0	0	0	0	0	0
1	1	0	0	0	1	0	0	1	1	1
1	2	0	0	0	0	1	2	2	2	2
2	0	0	1	0	0	0	0	0	0	0
2	1	0	0	0	1	0	0	1	2	2
2	2	0	0	0	0	1	2	2	1	1

По первым двум и последнему столбцам табл.2.8 записываем правую часть выражения (2.4). Тогда получим:

f ( x, y ) = max { min [ 1, J (x), J (y)], min [ 0, J (x), J (y)], min [ 0, J (x), J (y)],

min [ 0, J (x), J (y)], min [ 1, J (x), J (y)], min [ 2, J (x), J (y)], min [ 0, J (x), J (y)],

min [ 2, J (x), J (y)], min [ 1, J (x), J (y)] }.

Правую часть этого выражения можно упростить т.к. “слагаемые” в фигурных скобках для которых значения функции f(x,y) равны нулю будут равны нулю. Таких слагамых четыре. Кроме того, “слагаемые “ для которых значения функции равны двум

можно записать без 2. Произведя эти упрощения, получим искомую первую форму данной функции:

f ( x, y ) = max { min [1, J (x), J (y)], min [ 1, J (x), J (y)], min [ J (x), J (y)],

min [ J (x), J (y)], min [ 1, J (x), J (y)] }.

Справедливо еще одно представление для функции k – значной логики, назы-

ваемое второй основной формой:

f ( x , …, x ) = f ( s ) · j (x ) …j (x ), (2.5)

где суммирование ведется по всем наборам s = (s , …, s ) значений переменных

x , …, x , причем сумма и произведение берутся по mod k.

Пример. Представить во второй форме функцию, заданную в предыдущем примере.

Подставляя в правую часть выражения (2.5), значения первого, второго и пос-леднего столбцов табл. 2.5, получим:

f ( x, y ) = 1·j (x) j (y) + 0·j (x) j (y) + 0·j (x) j (y) + 0·j (x) j (y) + 1·j (x) j (y) +

+ 2·j (x) j (y) + 0·j (x) j (y) + 2·j (x) j (y) + 1·j (x) j (y) =

= j (x) j (y) + j (x) j (y) + 2·j (x) j (y) + 2·j (x) j (y) + j (x) j (y).

Последнее выражение и является второй формой для данной функции.

Третьей основной формой функции n переменных, являющейся аналогом СКНФ для функции двузначной логики, называется следующее выражение:

f ( x , …, x ) = min { max [ f (s , …, s ), ~ J (x ), ~ J (x ), …, ~ J (x ) ] } (2.6)

s

где минимум берется по всем наборам s = (s , …, s ) значений переменных x , …, x .

Пример. Представить в форме (2.6) функцию предыдущего примера.

Подставляя в правую часть выражения (2.6) значения первого, второго и последнего столбцов табл.2.8, получим:

f ( x, y ) = min { max [ 1, ~J (x), ~J (y)], max [ 0, ~J (x), ~J (y)], max [ 0, ~J (x), ~J (y)],

max [ 0, ~J (x), ~J (y)], max [ 1, ~J (x), ~J (y)], max [ 2, ~J (x), ~J (y)],

max [ 0, ~J (x), ~J (y)], max [ 2, ~J (x), ~J (y)], max [ 1, ~J (x), ~J (y)]}

Убирая из правой части этого выражения, шестое и восьмое “слагаемые” и значения функции равные нулю, получим искомую форму данной функции:

f ( x, y ) = min { max [1, ~J (x), ~J (y)], max [ ~J (x), ~J (y)], max [ ~J (x), ~J (y)],

max [ ~J (x), ~J (y)], max [ 1, ~J (x), ~J (y)], max [ ~J (x)], ~J (y)],

max [ 1,~J (x),~J (y)] }.