Файл: Сарингулян, Э. В. Арифметические и логические основы цифровых машин учеб. пособие.pdf

Т а б л и ц а 3.3

Представление логических функций двух аргументов в СДНФ и СКНФ

В действительности функция f5(x, у) повторяет на наборах

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

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

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

Рассмотрим минимизацию логической функции, заданной или приведенной к совершенной дизъюнктивной нормальной форме методом Квайна. Алгоритм минимизации СДНФ вклю­ чает два этапа:

1) нахождение сокращенной дизъюнктивной нормальной формы аналитическим способом;

2) построение минимальной дизъюнктивной нормальной формы аналитическим или табличным способом.

Получение сокращенной дизъюнктивной нормальной фор­ мы методом Квайна основано на использовании операций склеивания и поглощения.

При выполнении операции склеивания все члены необходи­ мо оставлять в выражении, чтобы можно было использовать

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

Процесс понижения рангов конъюнкций продолжается до об­ разования всех изолированных конъюнкций.

Вид функции, полученный после всех этапов склеивания и поглощения, является сокращенной дизъюнктивной нормаль­ ной формой. Любая переключательная функция имеет единст­ венную сокращенную дизъюнктивную нормальную форму [2].

Пример. Найти сокращенную дизъюнктивную нормальную форму логической функции / (a, b, с, d) — abc у cibd V abcd\/ V ab c d.

Прежде всего необходимо представить исходную функцию в совершенной дизъюнктивной нормальной форме. Для этого умножим первый член на d\/d~ 1, а второй член на с\/с—1.

f(a , b, с, d) — abc (d V d) V abd (с у с) \/ abed \/ abed =

—abed V abed V abed- \J abed \J abed. V abed

=- abed V abc d \/ abed, У abed \/ a b c d.

Проведем операции склеивания (3.29): _ первого члена со вторым по переменной d(abc), второго члена с третьим по переменной c(abd), второго члена с пятым по переменной b(acd).

68

Результат запишем в такой форме:

fin, b, с, d)=--abcd\fabcd\/abcdyabcd\'abcci\/abc\ abd\/acd.

Произведение abc поглощает первый и второй члены, про­

паведение abd— второй и третий члены и произведение acd— второй и пятый члены:

/ (а, b, с, d) = abc V abd \/ ас d \/ abed,

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

Пример. Найти сокращенную дизъюнктивную нормальную

форму переключательной функции f(a., b, с) = abc \J bc\/abc. Необходимо заданную лопическую функцию привести к со­

вершенной дизъюнктивной нормальной форме:

1) abc \/ be V abc = {a v b) c \J (b \J с) (a \/ b V c) ~

= ас V be v ab \/ ас V be V be = ас V be V ab \J ax \/ bc\

2)ac(b\/b) Vbc(a\/a) V <^b(c\/c)\/ac(byb)V bc(aVa)==

~a b c\ ja b c y abc\/a b c\Jabc\,'ab c\/abc\fab c\/ abc \/ ub7=

—abc V a be V abc \J ab с V abc V abc.

Полученное выражение есть совершенная дизъюнктивная нормальная форма.

3) Проведем операции склеивания:

первого члена со вторым по переменной Ь(ас), первого члена с шестым по переменной c(ab), второго члена с третьим по переменной а(Ьс), третьего члена с четвертым по переменной c(ab), четвертого члена с пятым по переменной Ь(ас), пятого члена с шестым по переменной а(Ьс).

_ 4)_ Проведем операции поглощения произведениями ас, ab, be, ab, ас, Ьс всех конституант единицы СДНФ:

/ (а, Ь, с) = ас V ab V Ьс \/ ab V ас \/ Ьс.

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

6 9

Пример. Найти сокращенную дизъюнктивную нормальную фо.рму логической функции

/ ( « , й, с, cl) : abc d V abc d У a b с d V a b с d.

Выполним операции склеивания:

первого члена со вторым по переменной a(bcd)_, первого члена с четвертым по переменной b(acd), второго члена с третьим по переменной b (acd), третьего члена с четвертым по переменной a{bcd). Затем проведем операции поглощения

f(a, b, с, d) — b c d y a c d y a c d y bed .

Полученное выражение позволяет провести еще раз опера­ ции склеивания:

первого члена с четвертым по переменной b(cd), второго члена с третьим по переменной a (erf). В результате имеем:

f(a, b, с, d) = be d\/а с d У ас d \ / b с d\/с d \ / cd-

Произведение cd поглощает первый, второй, третий и чет­ вертый члены, после чего сокращенная дизъюнктивная нор­ мальная форма имеет вид:

f(a, b, с, d) — cd.

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

Проведем удаление лишних произведений из сокращенной дизъюнктивной нормальной формы табличным способом, вклю­ чающим построение таблицы минимизации. Число столбцов таблицы равно числу членов СДНФ, а количество строк опре­ деляется произведениями сокращенной формы. После построе­ ния таблицы необходимо сопоставить каждый член сокращен­ ной дизъюнктивной нормальной формы с конституентами еди­ ницы СДНФ. В случае вхождения некоторой изолированной конъюнкции в состав члена СДНФ на пересечении соответст­ вующих строки и столбца делается отметка. После всех сопо­ ставлений для нахождения минимальной дизъюнктивной нор­ мальной формы достаточно определить минимальное количе­ ство членов сокращенной дизъюнктивной нормальной формы, которые совместно накрывают отметками ©се столбцы таблицы минимизации. Переключательная функция может иметь несколько минимальных ДНФ, а в ряде случаев мини­ мальная ДНФ совпадает с сокращенной.

70