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

Синтез логического устройства распадается на несколько этапов.

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

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

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

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

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

Таблица 1

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

(1)

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

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

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

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

Рассмотрим в качестве примера функцию, приведенную в табл. 1.

(2)

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

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

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