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

Пример.

Следствие.

Теорема.

Всякая булева формула, не содержащая отрицаний, представляет монотонную функцию, отличную от 0 и 1, и наоборот, для любой монотонной функции, отличной от 0 и 1, найдется представляющая её булева формула без отрицаний.

Сокращенная ДНФ монотонной функции является её минимальной ДНФ.

Определить, является ли функция монотонной.

Выразим через элементарные функции булевой алгебры:

.

Полученная формула булевой алгебры не содержит отрицаний, следовательно, функция является монотонной.

Замкнутые классы булевых функций

Рассмотрим понятия замыкания и замкнутого класса.

Пусть - некоторое подмножество функций из . Замыканием множества булевых функций называется множество , состоящее из функций, представимых в виде формул через функции множества .

Дата добавления: 2014-10-22