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

Синтез комбинационных устройств

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

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

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

Рис. 1

Если любая из конъюнкций равна логической 1, то функция принимает единичное значение.

Каждый аргумент либо его инверсия может входить в конъюнкцию только один раз. Пример ДНФ:

В ДНФ не каждый аргумент должен присутствовать в каждой конъюнкции. Число используемых в конъюнкции аргументов называется рангом конъюнкции n. Максимальный ранг конъюнкции определяется общим аргументов в функции N. В состав ДНФ могут входить конъюнкции с рангом меньше N.

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

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

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

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