Анализ и разработка логических схем. Синтез логических схем

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

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

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

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

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

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

эта форма не является КНФ, так как в ней первый член не связан с остальными операцией конъюнкции).

В СКНФ в каждом члене КНФ должны быть представлены все аргументы. Для перехода от КНФ к СКНФ необходимо добавить к каждому члену, не содержащему всех аргументов, члены вида хi*хi где аргумент, не представленный в члене. Так как хi *х =0, то такая операция не может повлиять на значение функции. Добавление хi *х, к некоторому члену Y образует выражение вида Yvхi *х, которое можно привести к виду

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

рассмотрим переход от КНФ

Подставив сюда значения z1 и z2, получим соответствующие члены приведенного выше выражения

при переходе от КНФ к СКНФ.

Совершенная КНФ функции легко строится по таблице истинности.

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

(2.3)

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

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

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

Рис. 2.1

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

Читайте также

Оптоэлектронные технологии
Оптоэлектроника - бурно развивающаяся область науки и техники. Многие ее достижения вошли в быт: индикаторы, дисплеи, лазерные видеопроигрыватели. Разрабатывается твердоте ...

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

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