2.2. Основные свойства элементарных функций

Опираясь на определение эквивалентности функций, можно доказать сле-

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

Свойства для функций: min(x , x ), max(x , x ), x ·x (md k), x + x (mod k)

Обозначим любую из этих функций через x o x . Тогда для этих функций

справедливы следующие свойства.

1. Коммутативность: x o x = x o x .

2. Ассоциативность: (x o x ) o x = x o (x o x ).

3. Дистрибутивность умножения относительно сложения:

(x + x ) x = x x + x x

Перечисленные свойства легко проверить самостоятельно.

Принимая во внимание ассоциативность умножения по mod k, произведение

x x …x (n сомножителей) записывают часто в виде степени xⁿ .

Функция min ( x , x ) считается старше функции max ( x , x ), т.е. она выполняяется раньше, если нет скобок. Поэтому в формулах некоторые скобки можно не писать.

Свойства для функций : 0, 1, …, k-1, J (x), …, J (x), min(x , x ), max(x , x ).

1). Дистрибутивность функции max относительно функции min :

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

2). Дистрибутивность функции min относительно функции max :

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

3). Идемпотентность функции max и min (аналог законов де Моргана в Р ):

min( ~x , ~x ) = ~max( x , x ); max( ~x , ~x ) = ~min( x , x ).

4). Правила упрощений:

a) min [ J (x), J (x) ] =

b) min [ (k-1), x ] = x, min ( 0, x ) = 0;

c) max [ (k-1), x ] = k-1, max ( 0, x ) = x.

5). max [ J (x), …, J (x) ] = k-1.

6). Правило введения переменной:

x = min { x , max [ J (x ), …, J (x ) ] }.

Докажем это свойство, используя свойства 4b) и 5):

min{ x , max [ J (x ), …, J (x ) ] } = min [ x , (k-1) ] = x .

7). Правило исключения ” чистых “ вхождений переменной:

x = max { min [ 1, J (x) ], min [ 2, J (x) ], …, min [ (k-1), J (x) ] }

8).Правило спуска символа J “ вглубь“ формулы:

a) J [ J (x)] =

2. J [ min (x, y) ] = max { min [ J (x), max ( J (y), …, J (y) ) ],

min [ J (y), max ( J (x), …, J (x) ) ] };

2. J [ max (x, y)] = max { min [ J (x), max ( J (y), …, J (y) ],

min [ J (y), max (J (x), …, J (x) ] }.

Представленные свойства элементарных функций можно проверить следующим образом. Проверим свойства 5 и 7 при k = 4. В этом случае эти свойства запишутся так:

5). max [ J (x), J (x), J (x), J (x) ] = 3,

7) x = max { min [1, J (x)], min [ 2, J (x) ], min [ 3, J (x) ] }.

Обозначив через f = min [1, J (x)], f = min [2, J (x)], f = min [3, J (x)],

f – левая часть равенства 5, F – правая часть равенства 7, составим следующую таблицу.

Таблица 2.3

Из таблицы видно, что все значения шестого столбца равны 3, т.к. k-1 = 3. Следовательно, свойство 5 подтверждается. Соответствующие значения первого и последнего столбцов совпадают, что подтверждает правильность свойства 7.

По табл.2.3 легко проверить свойство 4а). Например, для i = 1, j = 2, пользуясь

данной таблицей видно, что: min [ J (x), J (x)] = 0, min [ J (x), J (x)] = J (x).

Проверим справедливость свойства 8а), которое при k = 3 и m = 1 запишется

cледующим образом:

J [ J (x) ] =

Для проверки этого свойства составим следующую таблицу.

Таблица 2.4

x	J (x)	J (x)	J (x)	J (J )	J (J )	J (J )	max(J , J )
0	2	0	0	2	0	0	2
1	0	2	0	0	0	2	0
2	0	0	2	2	0	0	2

Из табл.2.4 видно, что значения пятого столбца совпадают с соответ-

ствующими значениями последнего столбца. Это означает, что при n = 0 выполня-

ется следующее равенство:

J [ J (x) ] = max [ J (x), J (x) ].

Все значения шестого столбца табл.2.4 равны нулю. Это означает, что при n = 1 выполняется равенство:

J [ J (x) ] = 0.

Значения третьего столбца равны соответствующим значениям предпоследнего столбца. Это означает, что при n = 2 выполняется равенство:

J [ J (x) ] = J (x).

Проверим свойство 8b), которое при k = 3 будет иметь следующий вид:

J [ min (x, y) ] = max{ min [ J (x), max ( J (y), …, J (y) ) ], (2.1)

min [ J (y), max ( J (x), …, J (x) ) ] }

при n = 0, 1, 2.

При n = 0 это соотношение упрощается и имеет следующий вид:

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

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

Применяя свойство 5 к правой части этого соотношения, получим:

J [ min(x,y) ] = max { min [ J (x), 2 ], min [ J (y), 2 ] } = max [ J (x), J (y) ].

Обозначим правую часть этого равенства через f, а min (x, y) через f .

Тогда это равенство запишется так:

J ( f ) = f. (2.2)

При n = 2 равенство (2.1) запишется в виде:

J [ min(x, y) ] = max { min [ J (x), J (y) ], min [ J (y), J (x)] } = min [J2(x), J2(y)].

Обозначим правую часть этого равенства через F. Тогда это равенство запишет-

ся так:

J ( f ) = F. (2.3)

Для проверки справедливости равенств (2.2) и (2.3) составим следующую таблицу.

Таблица 2.5

x	y	f	J (f )	J (x)	J (y)	f	J (f )	J (x)	J (y)	F
0	0	0	2	2	2	2	0	0	0	0
0	1	0	2	2	0	2	0	0	0	0
0	2	0	2	2	0	2	0	0	2	0
1	0	0	2	0	2	2	0	0	0	0
1	1	1	0	0	0	0	0	0	0	0
1	2	1	0	0	0	0	0	0	2	0
2	0	0	2	0	2	2	0	2	0	0
2	1	1	0	0	0	0	0	2	0	0
2	2	2	0	0	0	0	2	2	2	2

Из табл.2.5 видно, что значения четвертого столбца совпадают с соответствую-щими значениями седьмого столбца, что означает справедливость равенства (2.2). Ра-венство восьмого столбца и последнего означает справедливость равенства (2.3).

Проверку справедливости данного свойства при n = 1 рекомендуется проделать

самостоятельно.

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

Пример. Показать справедливость следующих утверждений:

~ ( ~ x ) = x, но ≠ x.

Справедливость этого видна из следующей таблицы.

Таблица 2.6

x	~x	~(~x)
0	2	0	1	2
1	1	1	2	0
2	0	2	0	1

Пример. Показать справедливость следующих утверждений;

~ min ( x,y ) = max ( ~x, ~y ), но ≠ max ( , ).

Обозначим эти соотношения следующим образом: f = f и f ≠ f .

Тогда справедливость этих соотношений при k = 3 видна из следующей таблицы.

Таблица 2.7

X	y	min(x,y)	F	~x	~y	f	f			f
0	0	0	2	2	2	2	1	1	1	1
0	1	0	2	2	1	2	1	1	2	2
0	2	0	2	2	0	2	1	1	0	1
1	0	0	2	1	2	2	1	2	1	2
1	1	1	1	1	1	1	2	2	2	2
1	2	1	1	1	0	1	2	2	0	2
2	0	0	2	0	2	2	1	0	1	1
2	1	1	1	0	1	1	2	0	2	2
2	2	2	0	0	0	0	0	0	0	0