Нормальные формы булевых функций

Конъюнктивной нормальной формой (КНФ) называется произвольная конъюнкция дизъюнктивных одночленов.
Дизъюнктивной нормальной формой (ДНФ) называется произвольная дизъюнкция конъюнктивных одночленов.

Всякую формулу равносильными преобразованиями можно привести к ДНФ и КНФ.
Алгоритм:
Избавиться от операций импликации, эквивалентности, штрих Шеффера, стрелка Пирса, сложение по модулю два;
Довести знаки отрицания до независимых переменных, используя законы де Моргана;
Применяя закон дистрибутивности, преобразовать формулу к дизъюнкции конъюнктивных одночленов (конъюнкции дизъюнктивных одночленов);
Постоянно избавляться от двойных отрицаний.

Замечание: Для того чтобы проверить правильно ли привели формулу к КНФ и ДНФ, можно построить таблицы истинности первоначальной и получившихся формул. Последние столбцы таблиц этих формул должны принимать одинаковые значения истинности.

Одночлен от некоторых переменных называется совершенным, если каждая из этих переменных входит в него ровно один раз, со знаком отрицания или без него.
Нормальная форма от некоторых переменных называется совершенной, если каждый входящий в нее одночлен является совершенным одночленом от тех же самых переменных. (СДНФ и СКНФ)

Теорема 1: Если формула не тождественно истинная, то для нее существует и при том единственная СКНФ.
Теорема 2: Если формула не тождественно ложная, то для нее существует и при том единственная СДНФ.

Алгоритм нахождения СДНФ:
Строим таблицу истинности;
Выбираем те строки таблицы, на которых формула принимает значение истина;
Для каждой выбранной строки строим конъюнктивный одночлен из переменных, от которых зависит формула следующим образом: если переменная в строке принимает значение истина, то она непосредственно входит в элементарную конъюнкцию, если ложь, то она входит с отрицанием;
Из конъюнктивных одночленов составляем СДНФ.