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

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

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

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

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

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

СДНФ: Дезъюнкция элементарных конъюкций.
ДНФ - Дезъюнктивная нормальной формой называется такая форма представления функции, когда она выражается в виде дизъюнкции ряда членов, каждый из которых является простой конъюнкцией аргументов или их инверсий.
   Простые конъюнкции называются импликантами.
Простые конъюнкции называются импликантами.
Пример: ДНФ f(x1x2x3)=x1Vx2Vx1x2Vx2x3
НЕ ДНФ            f(x1x2x3)=x1Vx2Vx1x2V
               f(x1x2x3)=x1(x2 Vx1x2)Vx2x3
СДНФ – такая форма представления функции, где в каждом члене ДНФ представлены все аргументы .
   Для перехода от ДНФ к СДНФ необходимо в каждую из импликант, в которой представлены не все аргументы, ввести выражение вида( хiV), где хi – отсутсвующий аргумент в импликанте.
Пример: f(x1x2x3)=x1Vx2
f(x1x2x3)=x1(х2VVx1x2)(х3V)V(x1V)х2= x1x2x3V x1x2V x1х3V x1х3V x1x2x3V
После приведения подобных членов:
f(x1x2x3)= x1x2x3V x1x2V x1х3V x1V
Пример: Если исходная функция задана в виде таблицы истинности, необходимо записать столько импликант в виде конъюнкций, сколько единиц содержит функция в таблице . Любая функция имеет единственную СДНФ

СДНФ f=VV x1х3V x1x2x3

СКНФ:
КНФ – называется форма представления функции в виде конъюнкции ряда членов, каждый из которых является простой дизъюнкцией аргументов или их инверсий.
Пример: f== x1(x2V)(х1Vx2V)(x2Vx3)- КНФ
Не КНФ f= x1(x2V)(x2V)
   f= x1(x2V )(x1х2х3)(x2)
В СКНФ в каждой импликанте должно быть представлены все аргументы.
Для КНФ>СКНФ прибавить  хi=0
Пример:
f(x1x2x3)=x1(x2Vx3)
f=()()=(x1Vx2Vx3)( x1Vx2V)(x1VV x3) (x1VV x3) (x1Vx2V)(Vx2V)=(x1Vx2Vx3)( x1Vx2V)( x1VV x3)( x1VV)(Vx2V)
Пример: Функция, приведенная в таблице выше имеет вид СКНФ:
f=(x1Vx2Vx3)( x1Vx2V)(Vx2Vx3)( VVх3)
СКНФ содержит столько импликант, сколько нулей есть среди значений функции  в таблице истинности. Следует записать столько конъюнктивных импликант, при скольких наборах значений аргументов функция равна 0.Если в наборе значения аргумента =1, в импликанту входит инверсия данного аргумента.

Вернутся к содержанию...