Элементарной конъюнкцией называется конъюнкция переменных высказываний и (или) их отрицаний.
Например:
Элементарной дизъюнкциейназывается дизъюнкция переменных высказываний и (или) их отрицаний.
Например:
Введём обозначение .
тогда и только тогда, если .
Это позволяет записать элементарные конъюнкции в виде (точнее , но знак конъюнкции обычно опускают), где в качестве значений берётся 0 если входит в конъюнкцию с отрицанием, и 1 если без отрицания. Так же, элементарные дизъюнкции могут быть записаны в виде .
1) тогда и только тогда, если
Элементарная конъюнкция даёт 1 только на наборе переменных, в котором переменные, входящие в неё с отрицанием имеют значение 0, а переменные без отрицания 1.
2) тогда и только тогда, если
Элементарная дизъюнкция даёт 0 только на наборе переменных, в котором переменные, входящие в неё с отрицанием имеют значение 1, а переменные без отрицания 0)
Дизъюнктивной нормальной формой (ДНФ) данной формулы называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций.
Например, выражение является ДНФ.
Конъюнктивной нормальной формой (КНФ) данной формулы называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.
Например, выражение – КНФ.
Для того, чтобы построить по данной формуле алгебры логики равносильную ей ДНФ или КНФ необходимо:
1. Перейти в сигнатуру алгебры логики (выразить все операции через дизъюнкцию, конъюнкцию и отрицание),
2. Воспользоваться законом де Моргана для того, чтобы отрицания стояли лишь над элементарными переменными высказываниями,
3. Раскрыть скобки (для построения ДНФ) или воспользоваться дистрибутивным законом (для построения КНФ).