Дизъюнктивная нормальная форма (днф)[править | править исходный текст]

Основная статья: Дизъюнктивная нормальная форма

Простой конъюнкциейиликонъюнктомназывается конъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза.Дизъюнктивной нормальной формойилиДНФназывается дизъюнкция простых конъюнкций. Элементарная конъюнкция

• правильная, если каждая переменная входит в неё не более одного раза (включая отрицание);

• полная, если каждая переменная (или её отрицание) входит в неё ровно 1 раз;

• монотонная, если она не содержит отрицаний переменных.

Например — является ДНФ.

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

Легко убедиться, что каждой булевой функции соответствует некоторая ДНФ, а функции, отличной от тождественного нуля — даже СДНФ. Для этого достаточно в таблице истинности этой функции найти все булевы векторы, на которых её значение равно 1, и для каждого такого вектора построить конъюнкцию , где . Дизъюнкция этих конъюнкций является СДНФ исходной функции, поскольку на всех булевых векторах её значения совпадают со значениями исходной функции. Например, для импликации результатом является , что можно упростить до .