Дизъюнктивные и конъюнктивные нормальные формы булевых функций

Различают две основные формы представления логических функций в базисе И, ИЛИ, НЕ - дизъюнктивную и конъюнктивную. Форма определяется той операцией, которая выполняется последней. При этом очередность выполнения операций следующая: сначала выполняют те операции, которые заключены в скобки, затем отрицание, конъюнкцию, дизъюнкцию. Например, F₁=X₁X₂(X₃+X₄), F₂=X₁X₂X₃+X₄. F₁ - конъюнктивная, F₂ - дизъюнктивная форма.

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

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

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

1. Пользуясь соответствующими тождествами алгебры логики перевести заданную функцию в базис И, ИЛИ, НЕ.

2. Используя законы де-Моргана и дистрибутивные законы преобразовать функцию в нужную форму.

При преобразованиях логических формул может возникнуть необходимость перейти от конъюнктивной формы к дизъюнктивной и наоборот. В первом случае задача сводится к раскрытию скобок, что аналогично соответствующей операции в алгебре чисел.

При переходе от дизъюнктивной формы к конъюнктивной нужно использовать второй дистрибутивный закон, не имеющий места в алгебре чисел:

AB+C=(A+C)(B+C).

Например, преобразуем функцию F₂ из предыдущего примера в КНФ:

X₁X₂X₃+X₄=(X₁+X₄)(X₂X₃+X₄)=(X₁+X₄)(X₂+X₄)(X₃+X₄).

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

Пусть булева функция задана в ДНФ. Для преобразования ее в СДНФ нужно каждую элементарную конъюнкцию, в которой не хватает каких-либо переменных данной функции (например, X _i, X_k, X_n) умножить на выражение, тождественно равное единице

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

X₁X₂+ X₂X₃= X₁X₂()+X₂X₃()= .

Пусть булева функция задана в КНФ. Для преобразования ее в СКНФ нужно к каждой элементарной дизъюнкции, в которой не хватает каких-либо переменных данной функции (например, X _i,X_k,X_n) прибавить выражение, тождественно равное нулю , а затем проделать последовательно преобразования по второму дистрибутивному закону. В результате получится конъюнкция элементарных дизъюнкций, каждая из которых будет содержать все переменные данной функции, т.е. конъюнкция конституент нуля - СКНФ. Пример: