Основы информатики_Савельев А.Я_Учебник_2001

10.3 Метод Квайна

импликантой является терм х^х-^. Столбцы, соответствующие существен­ ным импликантам, из таблицы вычеркиваются.

Т а б л и ц а 10.4

Этаг! 4. Вычеркивание лишних столбцов. После третьего этапа в ре­ зультате вычеркивания столбцов 2, 3, 7 и 8 получается таблица 10.5. Если в таблице есть два столбца, в которых имеются метки в одинаковых строках, то один из них вычеркивается. Покрытие оставшегося столбца будет осуществля1ь о1бротенный минтерм. В примере такого случая нет.

Э т а и 5. Вычеркивание лишних первичных импликант. Если после от­ брасывания некоторых столбцов на этапе 4 е таблице 10.5 появляются строки, в которых нет ни одной метки, то первичные импликанты, соответCTByioiune Т1ИМ ciрокам, исключаются из дальнейшего рассмотрения, так как они не покрывают оставшиеся в рассмотрении минтермы.

'^) I ан 6. Выбор минимального покрытия. Выбирается в таблице 10.5 такая coBoKymiocib первичных импликант, которая включает метки ао всех

1(1. Методы логического проектировании

столбцах по крайней мере по одной метке в каждом столбце. При несколь­ ких возможных вариантах такого выбора отдается предпочтение варианту покрытия с минимальным суммарнь|М числом букв в импликантах, обра­ зующих покрытие. Этому требованию удовлетворяют первичные импликанты X|,v,.Y4 и x^XfX^.

Таким образом, минимальная форма заданной функции складывается из суммы существенных импликант (этаг! 3) и первичных импликант, по­ крывающих оставшиеся минтермы (этаг! 6):

/ ( J C | , Xi,Xy, X,)=X^Xj \fX^X,X, -J X^XjXf .

10.4. Метод Квайна—Мак-Кляски

Недостаток метода Квайна — необходимость полного гюпарпо! о срав­ нения всех минтермов на этапе нахождения первичных импликант. С рос­ том числа минтермов увеличивается количество попарных сравнений. Чи­ словое представление функций алгебры логики позволяет упростить этап 1 (см. § 10.3). Все минтермы записываются в виде их двоичных номеров, а все номера разбиваются по числу единиц на непересекающиеся гругщы, так как ycjWBHe образования /"-куба — наличие расхождения в ( г - I ) - к у б а х только по одной координате в одном двоичном разряде и наличие об1цих независимых координат. Поэтому группы, которые различаются в двух раз­ рядах или более, просто не имеет смысла сравнивать. При этом в /-rpyiiny войдут все номера наборов, имеющие в своей двоичной записи / единиц. HoirapHoe сравнение можно проводить только между соседними по номеру группами.

Пример 10.3. Мупьзадаиафункция

/ ( ! , . Хг- ',- '4) = v(3, 4, 5, 7.9, 11,12.13). Р е QI е и и е . Сначала вы!сишем 0-кубы:

/r° = 0011, 0100, 0101. 0111,1001,1011,1100, 1101.

Разобьем 0-кубы на три группы !io количеству единиц в каждом двоичном наборе

Э т а н I, Нахождение первичных импликант: а) еравнение Л " и К^ :

0100 ООП

0101*

iOOi

1100*

Здесь и ниже символом «*>> отмечены наборы, которые склеиваюпхя.

На основании сравнения сгроим куб К\, в котором поглощенная координата заменяется

символом X,

'Моюххюо ;

б) сравнение К\ и К'^ :

ООП" 0111" 0101" 101Г 1001" 1101' 1100"

Строим куГ> А.']

0X11

X01I

01X1 к[ = 10X1

1X01

110Х

Х101

Первичной им||лика1гты ранга 4 нет; в) разобьем все 1-кубы на четыре группы в зависимости от положения независимой ко-

сравнение К^ и К]. Л"* и Л",^ внутри каждой группы:

237

10 5 Метод минимизирующих карт

В результате получим / = v(jc,, JCj,..-, Jc,,). Далее необходимо воспользо­ ваться соо1ношениями де Моргана, с тем чтобы привести функцию к СНДФ. Все дальнейшие действия аналогичны вышеизложенным.

10.5. Метод минимизирующих карт

Один из способов графического представления булевых функций от небольшог о числа переменных — карты Карно. Их разновидность — карты

клегки, лежащие на границах карты, также являются соседними по отноше­ нию друг к другу (пример образования 1-куба см. на рис. 10.5,0). Незави­ симая координата обозначена символом X.

239

10. Методы логического проектирования

Рис. 10.5. Минимизация логических функций с помощью кар\

2.Четыре вершины могут объединяться, образуя 2-ку6, содержащий две не­ зависимые ксюрдинаты (пример образования 2-куба изображен на рис. ! 0.5, в).

3.Восемь вершин могут объединяться, образуя один 3-куб.

4.Шестнадцать вершин, объединяясь, образуют один 4-куб и т. д.

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

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

/Об Минимизация логических функций в базисе ®, л . 1

10.6. Минимизация логических функций в базисе Ф, л , i

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

Рассмотрим применение метода неопределенных коэффициентов на примере базиса Ф, л, 1 . Функцию /(jc,, JC;, ^з) представим в виде, анало­ гичном нормальной дизъюнктивной форме, где вместо дизъюнкции стоит знак операции сложения Ф по модулю 2. Эта операция имеет особенности, отличающие ее от операций дизъюнкции:

где т ^ 2к •••••- четрюе количество единиц:

(3) операции сложения по модулю 2 усложняет минимизацию. Так как ос­ новными критериями минимизации по-прежнему являются минимальный ранг каждою терма и минимальное количество термов, при минимизации в базисе Ф, л, 1 uejiecoo6pa3HO приравнять к нулю все коэффициенты на на­ борах, гле / - О, так как тогда в единичных строках могут остаться термы высокою pania. Иоэшму особой разницы между выбором очередной стро­ ки нулевой или единичной нет. Количество коэффициентов, остающихся в нулевых строках, должно быть четным, а в единичных — нечетным. Лучше начать с единичных строк и оставлять те коэффициенты минимального ранг а, которые чаще гговгоряются в этих строках.

Пример Ш.5. За;|ама(|1ункция /(:Г|. д;^, д:,) - ® (О, I, 5,6).

Найти минимальное нредстанлсние в базисе ®, л, т,

Рс 111 е и ие . CociaRHM таблицу !0.8.

ИlaOiiHTic кспффиниенг А? повторяется три раза и его целесообразно оставить- В нуле­ вой cipoKe пало ociaiiHsb eute какой-нибудь коэффициент минимального paHia, который

гакжс иовгоряе^гся и i e \ елииичных строках, в которых еще не было оставлено ни одного ко )ф<|>ит1ис1иа Для т!0!1учения минимальной формы выполним следующие действия.

!. !1осчи1аем, сколько раз встречаются в единичных строках термы первого минимальиок) распа, и оставим ге из них, которые встречаются максимальное число раз.

241

10 7 Минимизация функций в базисах Шеффера и Пирса

Рис. Ш.7. Графические решения задачи минимизации для примера 10.6

10.7. Минимизация функций в базисах Шеффера и Пирса

Рассмотрим сначала функцию Шеффера;

Запись логической функции в базисе Шеффера осуществляется сле­ дующим образом:

1.Чтобы по таблице истинности записать терм в базисе Шеффера, пе­ ременные можно оставить без изменения.

2.Если задавать функцию на нулевых наборах, то в конце выражения

следует ставить знак общего отрицания: {/(х))/]; если задавать функцию

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

Х^ I- Х^ = Х^ + Х2 •

Запись логической функции в базисе Вебба происходит следующим образом:

245