Лекции::

Дополнительно:

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

Определение. Если 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.

Выяснить, являются ли функции монотонными:

  1. f = 00100110;
  2. f = 00110111.

Решение.

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

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

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

предыдущаяследующая