1.10.4. Монотонность. Класс м

Определение. Булев векторⁿ предшествует векторуⁿ, если для всех их компонент i (1  i n ) выполняется условие:  _i   _i . Обозначают предшествование как: ⁿ  ⁿ. Функцию f(хⁿ) называют монотонной, если на всех предшествующих наборах ее переменных ⁿ и ⁿ (ⁿ ⁿ ) предшествование сохраняется и для значений функции, т.е. выполняется условие: f ( ⁿ )  f ( ⁿ ).

Свойство предшествования вводит на множестве n — мерных булевых векторов E₂ⁿ бинарное отношение нестрогого порядка, поскольку оно удовлетворяет аксиомам рефлексивности, антисимметричности и транзитивности. При n >1 данное отношение вводит на E₂ⁿ частичный порядок, так как есть не сравнимые между собой наборы – например (01) и (10), (011) и (110) и др.

Множество монотонных функций n переменных обозначается Мⁿ, все множество монотонных функций алгебры логики — М. Оно является предполным классом в Р₂. Если функция f  М, то ее называют немонотонной. Выяснить монотонность любой функции можно непосредственной проверкой всех предшествующих наборов по таблице истинности.

Замечание. Если функция на некотором набореⁿ равна 0, то ее значения на всех последующих наборахⁿ, сравнимых сⁿ ( ⁿ   ⁿ), можно не проверять, поскольку значение f ( ⁿ )= 0 предшествует любому значению f ( ⁿ ). Аналогично, если функция на некотором наборе ⁿ равна 1, то ей предшествуют любые значения на всех предшествующих наборах ⁿ, сравнимых с ⁿ ( ⁿ  ⁿ).

Пример. Проверить монотонность функций: а) х , б) х  у , в) (00101011).

Решение. Задачу решаем с учетом Замечания путем проверки сохранения функциями свойства предшествования на всех парах сравнимых наборов переменных в таблице истинности.

х	
0	1
1	0

х	У	z	f
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

х	у	
0	0	0
0	1	1
1	0	1
1	1	1

а) Функция х принимает значение 1 на наборе х=(0). Он является предшествующим набору х=(1): (0)  (1). Сравнивая значения функции: f(0)=1 > f(1)=0, получим нарушение предшествования. Следовательно, отрицание не монотонно.

б) Первое единичное значение функции — на наборе (х,у) =(0,1). С ним сравним набор (1,1). Для данной пары наборов: f(0,1)=1 = f(1,1)=1 — отношение предшествования сохраняется. Аналогично для следующего набора (х,у)=(1,0) с единичным значением функции сравнимым является набор (1,1). В этом случае: f(1,0)=1 = f(1,1)=1 — отношение также сохраняется. Поскольку все сравнимые наборы проверены, то функция логического сложения является монотонной.

в) Рассмотрим первое единичное значение функции — на наборе (х,у,z)=(0,1,0). С ним сравнимы наборы (0,1,1), (1,1,0) и (1,1,1). Проверка набора (0,1,1) дает: f(0,1,0)=1 > f(0,1,1)=0 — нарушение отношения предшествования. Следовательно, данная функция не монотонна.

Ответ: функции а) х и в) (00101011) не монотонны, функция б) ху — монотонна.

Монотонными являются элементарные функции 0, 1, х, , . Для немонотонных функций (не входящих в М) справедлива

Лемма о немонотонной функции

Если f (х ⁿ)  М, то из нее путем подстановки констант 0, 1 и тождественной функции х всегда можно получить функцию отрицаниях .

Доказательство. Из f (х ⁿ)  М следует, что существуют наборы и такие, что  , а f ( )  f ( ). При этом f( ) =1, f ( ) = 0. Так как   , то для компонент этих векторов c одинаковыми номерами возможны только три варианта: 1)  _i =  _i = 0; 2)  _i =  _i = 1; 3)  _i = 0,  _i = 1.

Третий вариант присутствует всегда, иначе наборы и полностью совпадут.

Выполним следующие подстановки в f (х ⁿ). В первом случае (_I = _i = 0) вместо соответствующих переменных подставим тождественный 0, во втором случае (_i = _i = 1) — тождественную единицу, а в третьем (_i = 0,  _i = 1) — тождественную функцию х. В итоге получим функцию одной переменной F(x), у которой F( 0 ) = f ( ) = 1, F( 1 ) = f ( ) = 0. Следовательно, функция F(х)эквивалентна отрицанию х.

ЗАДАЧИ

1. Проверить монотонность функций: а) ху  yz  xz ; б) х у  у z ; в) ху х у ; г) х у ; д) (01100111) ; е) (00100011).

2. Доказать, что если f  Т₀ и f  М , то f  1.

3. Доказать, что если f  Т₁ и f  М , то f  0.

4. Доказать замкнутость класса М .

5. Доказать предполноту класса М (например, с использованием леммы о немонотонной функции и сведением дополненной системы к {f} = { , , }).