Лемма о немонотонной функции. Критерий монотонности по сокращенной ДНФ


Лемма: (о немонотонной функции).
Суперпозицией констант 0 и 1 и немонотонной функции можно получить отрицание.

Доказательство: Пусть f(x1, x2,…,xn) немонотонная функция тогда любые наборы a=(a1, a2,…,an), b = (b1, b2,…,bn) для которых a ≤ b, но f(a) > f(b). Пусть i1, i2,…,ik есть все те номера аргументов, для которых aip < bip, p=1,2..k. На остальных аргументных местах j имеем aj = bj. В выражении f(a1, a2,…,an) заменим нули на местах i1, i2,…,ik на x. В результате получим функцию g(x), для которой g(0) = f(a) = 1 и g(1) = f(b) =0, то есть для g(x) является отрицанием.

Лемма: функция монотонна ⇔ ее сокращенная ДНФ не содержит отрицания.

Следствие: Функция f монотонна ⇔ минимальная ДНФ не содержит отрицаний переменных.


Комментарии запрещены.




Статистика