Нормальные формы логических функций

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

 представлена в виде ДНФ с тремя дизъюнктами.

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

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

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

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

       Если составлена таблица истинности, тогда для логической функции СКНФ составляется следующим образом: выбирается строки со значением  и записываются отрицания их дизъюнкции, при этом получим конъюнкцию отрицаний и для записи каждой строки со знаком и связанной переменной со значением 0 или отрицание переменной со значением 1.