Дискретная математика

( ) и отрицание (¬).
Булева алгебра – это множество

Формулы, представляющие одну и ту же функцию называются равносильными (эквивалентными).

с точностью до порядка элементарных конъюнкций и порядка элементов в

и равносильные формулы.

Тогда существует последовательность

и равносильны, то они

последовательность преобразований, переводящих

булевой формулой.
Доказательство: У каждой функции существует СДНФ – булева формула.