2.2.3.3. Монотонные функции

Определение. Если a = (a1, …, an) и b = (b1, …, bn) - наборы длины n из 0 и 1, то a £ b, если a1 £ b1, …, an £ bn.

Пример 47.

Наборы ( 0, 1, 0) и (1, 1, 0) сравнимы, причем ( 0, 1, 0) £ (1, 1, 0).

Наборы (0, 1) и (1, 0) несравнимы. Также несравнимы наборы (0, 1) и ( 1, 1, 0).

Определение. Функция f(x1, x2, …, xn) называется монотонной, если для всяких наборов a = (a1, …, an) и b = (b1, …, bn) условие a £ b влечет f(a) £ f(b).

Утверждение. Функция монотонна тогда и только тогда, когда ее сокращенная ДНФ не содержит отрицаний.

Следствие. Функция монотонна тогда и только тогда, когда ее МДНФ не содержит отрицаний.

Пример 48.

Выяснить, являются ли функции монотонными: f = 00100110; f = 00110111.

Решение.

1. Сокращенная ДНФ для функции f = 00100110 имеет вид Поскольку сокращенная ДНФ содержит отрицания, то функция не является монотонной.

2. Сокращенная ДНФ для функции f = 00110111 имеет вид Поскольку сокращенная ДНФ не содержит отрицаний, то функция является монотонной.

Теорема. Класс M = {f | a£ b ? f(a)£ f(b)} монотонных функций замкнут относительно суперпозиций.

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 2.2.3.3. Монотонные функции:

  1. 2.2.1 Алгоритм обратного распространения ошибки
  2. 5.3. ЗАДАЧА УПРАВЛЕНИЯ
  3. Частотный диапазон сигнала и способы его определения
  4. §8. Энергия связи и эффективная масса в пределе Майера в сильном магнитном поле
  5. Понятие о Шумпетере
  6. § 11. Функция одного переменного
  7. § 23. Про и ав одная обратной функции
  8. § 33. Условия возрастания и убывания функций
  9. § 35. Схема исследования функции на экстремум
  10. 10. Неопределенность и высшая категория «нечто» (то ті)
  11. КАК НУЖНО РАССУЖДАТЬ КОМПЬЮТЕРУ [†††††]