книги из ГПНТБ / Архаров В.И. Арифметические и логические основы цифровых вычислительных машин учеб. пособие

Из таблицы 6-2 строим СДНФ функции

Процедура минимизации показана в таблице 6-3.

В первой вертикальной графе выписаны все конституенты «1» заданной функции. Идя сверху вниз по этой графе, выясняем воз­ можность склеивания каждой конституенты со стоящими ниже. Элементарные конъюнкции третьего ранга, полученные в итоге склеивания конституент «1», выписаны в графе 3, в правой части

Идя сверху вниз по графе 3, выясняем возможность склеиваний каждой элементарной конъюнкции третьего ранга с расположенным ниже. Итог склеиваний этих конъюнкций показан в графе 5.

В графе 4 против элементарной конъюнкции х 2х 1х 0 сделана от­ метка ПИ1, означающая, что эта конъюнкция не склеивается ни с одной из конъюнкций третьего ранга и поэтому является простой импликантой (ПИ) данной функции.

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

х \ / x \J х . . . = х,

х- . . . -х = х.

В итоге всех возможных склеиваний элементарных конъюнкций второго ранга получим три одинаковых элементарных конъюнкции

первого ранга (графа 7). Конъюнкции х 2х х и х2х0 не склеиваются ни с одной из конъюнкций второго ранга, поэтому они являются простыми импликантами (ПИ2, ПИЗ). В графе 6 это обозначено ПИ2, ПИЗ.

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

и является сокращенной нормальной формой булевой функции, за­ данной табл. 4-1.

Теперь выясним возможность - перехода от полученной сокра­ щенной нормальной формы к тупиковым нормальным формам, для чего надо выявить в выражении (6.6) лишние простые импликанты. Это можно сделать с помощью импликантной матрицы (см. таблицу

6-4).

141

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

Из таблицы 6-4 видно, что k0 накрывается только простой им­ пликантой х 3, k 10 только х 2х гх 0, k 12 только Х2Х1; k 15 только Х2Х0. Таким образом, ни одна из простых импликант сокращенной нор­ мальной формы не является лишней. Следовательно, полученная сокращенная нормальная форма (6.6) является одновременно и тупиковой и минимальной формой.

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

Метод Мак-Класки

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

142

дексом 2 сравнивается со всеми наборами, имеющими индексы 3, и т. д. На местах склеивания ставятся прочерки.

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

Исходные члены n-го ранга, подвергшиеся склеиванию, обра­ зуют группы с индексом 0— 1, 1—2, 2—3 и т. д., объединяющие члены п—1-го ранга. В соседних группах, т. е. с индексами, отли­ чающимися на единицу (например, 0—1 и 1—2, 1—2 и 2—3 и т. д.), снова производятся все возможные склеивания и так далее, до тех пор, пока дальнейшие склеивания и поглощения становятся невоз­ можными. Члены, полученные в итоге всех возможных склеиваний и поглощений, как и оставшиеся несклеенными, являются про­ стыми импликантами, дизъюнкция которых образует сокращен­ ную дизъюнктивную нормальную форму функции.

Нахождение лишних импликант, как и при минимизации по Куайну, производится с помощью импликантной матрицы. Проце­ дура минимизации по методу Мак-Класки СДНФ отображена в таб­ лице 6-5. Полученные в виде последовательности единиц, нулей и прочерков простые импликанты записываются с помощью букв и их отрицаний: на местах единиц ставится соответствующая буква, на местах нулей — соответствующая буква со знаком отрицания, а прочерки указывают исключенные в процессе склеиваний пере­

незначительно упрощает, в сравнении с алгоритмом Куайна, про­ цедуру минимизации СДНФ. Основным недостатком данного алго­ ритма является громоздкость и возможность допущения ошибок при склеивании.

Усовершенствованный алгоритм Куайна

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

144

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

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

Метод Карно—Вейча

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

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

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

145

указано на рис. 36. В каждом горизонтальном ряду первому слева квадрату геометрически соседними являются второй и четвертый квадраты. Карту Карно следует рассматривать как плоскость, по­ лученную из поверхности тора.

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

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

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

Каждый правильный прямоугольник объединяет конституенты единицы, к которым можно применить операцию неполного склеи­

146

вания и закон поглощения. В результате их выполнения получаем из каждого правильного прямоугольника один член ДНФ тем мень­ шей длины, чем больше 2 .

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

Рис. 37

Например, если правильный прямоугольник состоит из квадра­ тов К 0 и /<4 (рис. 36, в), то искомой элементарной конъюнкцией яв­

ляется х3ХхХ0, а переменная х 2 исключается, так как внутри этого прямоугольника они имеются как в прямых, так и в инверсных обозначениях. Этот прием позволяет сразу же определить резуль­ тат неполного склеивания с последующим поглощением, которые^ выполняются в отношении конституент единицы каждого из най­ денных правильных прямоугольников данной карты. Результат приведенных выше примеров соответствует следующим выкладкам;

ХзХ^Хо \J х3х2ххх0= ХзХгХо (х2 V *2) V х3х2ххх0\/ х3х.,ххх0= *3*1 *0'.

Х3 Х2 ХхХ0 V * 3 * 2 * 1 * 0 V * 3 * 2 * 1 * 0 V * 3 * 2 * 1 * 0 = * 3 * 2 * 0 (* 1 V * l ) V

V * 3 * 1 * 0 (* 2 V * 2) V * 3 * 1 * 0 (* 2 V * 2) V * 3 * 2 * 0 (* 1 V * 1) V * 3 * 2 * 1 * 0 V

V * 3* 2 * 1 * 0 V * 3 * 2 * 1 * 0 V * 3 * 2 * 1 * 0 = * 3 * 2 * 0 V * 3 * 1 * 0 V * 3 * 1 * 0 V * 3 * 2 * 0 =

= Х3 Х0 (ХоV * 2) V * 3 * 0 (* 1 V * l ) V * 3 * 2 * 0 V * 3 * 1 * 0 V * 3 * 1 * 0 V * 3 * 2 * 0 = * 3 * 0 -

147

При построении карт Карно для функций от 5 и более перемен­ ных теряется их основное достоинство — простота отыскания квад­ ратов с соседними конституентами единицы.

Пример 5. Рассмотрим минимизацию СДНФ функции с помощью карт Карно.

Требуется минимизировать СДНФ функции, заданной таблицей (рис. 37). Из карты Карно видно, что вся совокупность квадратов покрывается четырьмя правильными прямоугольниками:

Рис. 38

Прямоугольнику с г — 8 соответствует член х3 минимальной дизъюнктивной нормальной формы, прямоугольникам с z - -- 4 —

соответственно х 2хх и х 2х 0 и прямоугольнику с г = 2 — х2х1х0.

Рис. 39

Таким образом, приходим к минимальной дизъюнктивной нормаль­ ной форме

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

148

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

А{\J лулул'оV X^XiXq.

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

Пример 7. Доопределить функцию на карте Карно и произвести минимизацию (рис. 39).

В данном случае целесообразно приписать обоим условным со­ стояниям синтезируемой схемы значения выхода, равные 1. Мини­

мальная форма будет А = х г V *<>•

Метод Нельсона

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

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

внуль.

2.С помощью правила де Моргана переходим от полученного выражения к СКНФ функции.

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

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

где п — ранг членов совершенной нормальной формы; а, Ь, с, . . . , v — номера наборов значений аргументов, на которых функция обращается в 1, удобно пользоваться следующими формулами:

‘ # = ^ 2_,)_£,

d" =~k(2n- l )-«>

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

F ^ y k l t = 0, 1, 2, 4, 5, 8, 9, 10, 12, 13, 14, 16—31.

149

Эта функция обращается в нуль на наборах значений аргумен­

Склеивая I h IV, II и III, III и V члены СКНФ, получим конъюнк­ тивную нормальную форму

К = ( х 4 V * 2 V * 1 V Хо ) А (* 4 У Х 3 V * 2 V * l ) Л (* 4 У * 2 V Х 1 V * о ) •

Склеив I и III члены этой формулы, получим

Л = (хл УххV *о) Л (*4 V - ^ s V ^ V хд ■

Раскрыв скобки согласно распределительному закону, получим

F4 = x4 у х4х3 У х4х2 у х4хх у х4х4 У х4х3 У х 4х2 у

У х4 У х0х4 у х0х3 У XqX2 у XqX4.

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

^ l = *4V*lV*0*sV*0*2-

Нахождение минимальных конъюнктивных нормальных форм

Минимальные КНФ находятся с помощью правила де Моргана и методов минимизации СДНФ. Этот прием характеризуется тремя

любого из методов минимизации СДНФ, в результате чего прихо­

150