Монотонность. Класс М
Определение. Булев вектор`an предшествует вектору`bn, если для всех их компонент i (1 £ i£ n ) выполняется условие: a i £b i . Обозначают предшествование как:`a n £`b n. Функцию f(`хn) называют монотонной, если на всех предшествующих наборах ее переменных`a n и`b n (`an £`bn ) предшествование сохраняется и для значений функции, т.е. выполняется условие: f (a n )£ f (b n ).
Свойство предшествования вводит на множестве n — мерных булевых векторов E2n бинарное отношение нестрогого порядка, поскольку оно удовлетворяет аксиомам рефлексивности, антисимметричности и транзитивности. При n >1 данное отношение вводит на E2n частичный порядок, так как есть не сравнимые между собой наборы – например (01) и (10), (011) и (110) и др.
Множество монотонных функций n переменных обозначается Мn, все множество монотонных функций алгебры логики — М. Оно является предполным классом в Р2. Если функция f ÏМ, то ее называют немонотонной. Выяснить монотонность любой функции можно непосредственной проверкой всех предшествующих наборов по таблице истинности.
Замечание. Если функция на некотором наборе`an равна 0, то ее значения на всех последующих наборах`bn, сравнимых с`an (`a n £ b n), можно не проверять, поскольку значение f (`a n )= 0предшествует любому значению f (`b n ). Аналогично, если функция на некотором наборе`b n равна 1, то ей предшествуют любые значения на всех предшествующих наборах`a n, сравнимых с`b n (`a n £`b n).
Пример. Проверить монотонность функций: а) Øх , б) х Ú у , в) (00101011).
Решение.Задачу решаемсучетом Замечания путем проверки сохранения функциями свойства предшествования на всех парах сравнимых наборов переменных в таблице истинности.
| х | Ø |
| х | У | z | f |
| х | у | Ú |
а) Функция Øх принимает значение 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, х, Ú, &. Для немонотонных функций (не входящих вМ) справедлива
Дата добавления: 2015-10-05; просмотров: 2137;