Теорема:Всякая булева формула, не содержащая отрицаний, представляет монотонную функцию, отличную от

и

;
Док-во: Пусть дана булева формула, без отрицаний. Применим к ней процедуру приведения к ДНФ. Получим невырожденную ДНФ также не содержащую отрицаний. Пусть на наборе

. Тогда

содержит конъюнкцию (без отрицаний!)

, равную

на этом наборе. Следовательно,

. Рассмотрим любой набор

, больший чем

. В нем обязательно

, поэтому

обратится в

и

; Таким образом, условие монотонности для

выполнено и функция

, представляемая ДНФ

(а значит, и исходной формулой), монотонна.
Кто-нибудь, пожалуйста, объясните этот момент: ....Тогда

содержит конъюнкцию (без отрицаний!)

, равную

на этом наборе. Следовательно,

....здесь

это элементы конъюнкции? То есть есть

, а что тогда означает: Следовательно,

. Что это за набор, что он означает?