Совершенная дизъюнктивная нормальная форма (СДНФ).

СИНТЕЗ КОМБИНАЦИОННЫХ УСТРОЙСТВ

Канонические формы представления логических функций.

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

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

Совершенная дизъюнктивная нормальная форма (СДНФ).

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

Примером ДНФ может служить выражение

(3.9)

Приведем форму представления функций, не являющейся ДНФ. Например, функция

представлена не в ДНФ, так как последний член не является простой конъюнкцией аргументов.

Также не является ДНФ следующая форма представления функции:

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

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

Добавление в члены выражений вида приведет функцию к виду

На основании (3.1)

Отсюда после приведения подобных членов:

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

Пусть дана функция в форме табл. 3.4. Для этой функции СДНФ имеет вид

(3.10)

Как видно из выражения (3.10), в нем каждый член соответствует определенному набору значений аргументов, при котором функция

равна 1. Каждый из наборов аргументов, при которых равна 1 (3, 4, 6, 8-й столбцы наборов), обращает в единицу соответствующий член выражения (3.10), вследствие чего и вся функция оказывается раиной единице.

Можно сформулировать следующее правило записи СДНФ функции, заданной таблицей истинности.

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

Следует отметить, что любая функция имеет единственную СДНФ.