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

Пример 2. Минимизировать булеву функцию f (хъ х 2, х 3), заданную следующей совершенной нормальной формой:

* 1 * 2 * 3 V * 1 * 2 * 3 V * 1 * 2 * 3 V * 1 * 2 * 3 -

Образуем три пары соседних конъюнкций

(* 1 * 2 * 3 > *1*2*з) >

(* 1 * 2 * 3 . * 1* 2* з ) ,

( X ^ X g , * х * 2* з ) .

Применяя к ним операции склеивания, получим конъюнкции

второго ранга: х хх 2, х хх 3, х 2х 3. Строим из них дизъюнктивную нор­ мальную форму

* 1 * 2 V * 1 * 3 V * 2 * 3 •

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

* 1 * 2 V * 1 * 3 -

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

Пример 3. Минимизировать функцию А, заданную в конъюнк­ тивной нормальной форме

А= ( * l V * 2 V * 3 ) A ( * l V * 2 V * 3 ) -

Раскроем скобки и получим дизъюнктивную нормальную форму

А = *]*2 V * 1 * 3 V * 2 * 3 V * 2 * 3 V * 1 * 2 V * 1 * 3 •

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

S ^ X ^ V * 2*3 V * 1* з -

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

Метод Куайна

При минимизации по методу Куайна исходной является СДНФ функции. Если функция задана одной из своих ДНФ, то с помощью развертывания (5.10) нетрудно перейти к СДНФ.

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

138

ная конъюнкция, могла бы быть склеена со всеми соседними, не­ обходимо воспользоваться операцией склеивания (12). При каж­ дом склеивании конституент единицы — элементарных конъюнк­ ций ранга п, в соответствии с операцией (12), получаем элементар­ ные конъюнкции ранга п—1 и подвергнутые склеиванию конституенты единицы. После выполнения всех возможных склеиваний используем закон поглощения (11).

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

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

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

Пример 4. Рассмотрим минимизацию по Куайну СДНФ. Пусть

139

\

Из таблицы 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