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

Доказательство: Пусть f(x₁, x₂,…,x_n) немонотонная функция тогда любые наборы a=(a₁, a₂,…,a_n), b = (b₁, b₂,…,b_n) для которых a ≤ b, но f(a) > f(b). Пусть i₁, i₂,…,i_k есть все те номера аргументов, для которых a_ip < b_ip, p=1,2..k. На остальных аргументных местах j имеем a_j = b_j. В выражении f(a₁, a₂,…,a_n) заменим нули на местах i₁, i₂,…,i_k на x. В результате получим функцию g(x), для которой g(0) = f(a) = 1 и g(1) = f(b) =0, то есть для g(x) является отрицанием.

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

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

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