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

Различают две основные формы представления логических функций в базисе И, ИЛИ, НЕ - дизъюнктивную и конъюнктивную. Форма определяется той операцией, которая выполняется последней. При этом очередность выполнения операций следующая: сначала выполняют те операции, которые заключены в скобки, затем отрицание, конъюнкцию, дизъюнкцию. Например, F1=X1X2(X3+X4), F2=X1X2X3+X4. F1 - конъюнктивная, F2 - дизъюнктивная форма.

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

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

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

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

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

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

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

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

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

X1X2X3+X4=(X1+X4)(X2X3+X4)=(X1+X4)(X2+X4)(X3+X4).

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

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

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

X1X2+ X2X3= X1X2( Дизъюнктивные и конъюнктивные нормальные формы булевых функций - student2.ru )+X2X3( Дизъюнктивные и конъюнктивные нормальные формы булевых функций - student2.ru )= Дизъюнктивные и конъюнктивные нормальные формы булевых функций - student2.ru .

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

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

Наши рекомендации