Тихомирова Л.С. Методы минимизации булевых функций - файл n1.doc

приобрести
Тихомирова Л.С. Методы минимизации булевых функций
скачать (205.9 kb.)
Доступные файлы (1):
n1.doc1820kb.23.12.2002 07:54скачать
Победи орков

Доступно в Google Play

n1.doc

1   2   3   4   5

4 метод. Метод Квайна
Этот метод применим к функции, записанной в СДНФ. Метод минимизации функции проводится поэтапно.

1 этап. Нахождение первичных импликант.

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

Члены

Результаты 1-го склеивания

Результаты 2-го склеивания

………….

1.

1.

1.




2.

2.

2.




3.

3.

3.
































Сравнить последовательно 1-й член со всеми остальными. Результаты склеивания записать во 2-й столбец, указывая в скобках номера склеенных членов, а склеенные члены 1-го столбца отметить звездочкой (*).Ранг полученных конъюнкций на единицу ниже, т.е. они содержат на один знак меньше. Эти конъюнкции нумеруются, затем операцию повторяют, записывая результат в 3-й столбец и т.д. Заканчивают эту процедуру когда вновь полученные конъюнкции уже не склеиваются между собой. Все неотмеченные знаком * конъюнкции называются первичными (простыми импликантами). Все члены, отмеченные знаком *, будут поглощены простыми импликантами на основании операции поглощения . Для удобства простые импликанты в таблице обводятся рамочкой.

Дизъюнкция всех простых импликант дает сокращенную ДНФ данной функции. Далее необходимо перейти к тупиковой ДНФ. Это 2-й этап.

Прежде рассмотрим 1-й этап на примере.
Пример 5. Минимизировать функцию (см. пример 1)

Поместим члены в 1-й столбец таблицы, занумеруем их. Применим закон склеивания, результат запишем во 2-й столбец таблицы, снова занумеруем их, склеенные члены 1-го столбца отметим звездочками, и т.д.





Члены

Результаты 1-го

склеивания

Результаты 2-го

склеивания

1.

*

(1, 2)

(2, 5)

2.

*

* (2, 3)

(3, 4)

3.

*

* (2, 4)




4.

*

* (3, 5)




5.

*

* (4, 5)





Несклеившиеся простые импликанты обводим рамочкой. Дизъюнкция их дает сокращенную ДНФ. В данном примере 1-й этап приводит к цели. есть минимальная форма функции. В общем случае надо перейти от сокращенной формы к тупиковой, а затем к минимальной.
Пример 6. Минимизировать функцию. (1 этап)


Запишем члены функции в 1-й столбец таблицы, применим к ним закон склеивания, рассматривая последовательно 1-й член со всеми остальными, затем 2-й со всеми остальными и т.д. Результаты запишем во 2-й столбец таблицы, занумеруем их и укажем в скобках номера склеенных членов, а в 1-ом столбце склеившиеся члены пометим звездочками. Повторим эту процедуру с членами 2-го столбца и т.д. Те импликанты, которые не склеиваются, обведем рамочками, они и являются простыми импликантами.

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




Члены

Результаты 1-го

склеивания

Результаты 2-го

склеивания

1.

*

(1, 4)

(3, 9)

2.

*

(1, 6)

(4, 6)

3.

*

* (2, 3)




4.

*

* (2, 7)




5.

*

(3, 4)




6.

*

* (3, 8)




7.

*

(5, 6)




8.

*

(5, 8)




9.




* (7, 8)





Если в результате склеивания получаются одинаковые импликанты, то оставляют только одну из них.

Итак, 1-й этап (“Нахождение первичных импликант”) закончен. Ими являются все импликанты, обведенные рамочками.
2 Этап. Расстановка меток.
Составляется таблица, число строк которой равно числу найденных простых импликант, а число столбцов – числу членов СДНФ данной функции. В 1-й столбец записываются первичные импликанты, в 1-ю строку члены функции. Если в член функции входит первичная импликанта, то на пересечении их ставится метка .

У первичных импликант 3-го порядка метки удобно проставить по номерам склеенных членов 1-го столбца, приписанным у импликант рядом (в скобках), а у первичных импликант 2-го порядка по номерам членов 1-го столбца. Число меток в строке зависит от числа исключенных букв в импликанте. Для исключенных букв число меток будет .

Рассмотрим 2-й этап на примере 6. Составим таблицу.






























(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)



V







V















V













V















V

V



























V

V





















V







V






V

V










V

V


Заметьте, член получился при склеивании членов 3 и 9, 2-го столбца, а те в свою очередь из членов 2, 3 и 7, 8 1-го столбца. Так, первичная импликанта соответствует членам 2, 3, 7, 8 данной функции. Итак, таблица меток построена.

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

В таблице меток (см. пример 6) столбцами с единственной меткой являются столбцы (2), (7). Соответствующая импликанта является существенной. Метку обводят кружочком, существенные импликанты – рамочкой, а столбцы с единственной меткой вычеркивают из таблицы. По закону поглощения меньшее количество меток в столбце может исключить большее. Так (2) и (7) столбцы входят соответственно в (3) и в (8), поэтому исключаем (3) и (8) столбцы из таблицы меток. 3-й этап закончен.
4 этап. Вычеркивание лишних столбцов.
Если в таблице после 3-го этапа два одинаковых столбца (в которых метки стоят в одинаковых строках), то один из них вычеркивается, т.к. покрытие оставшегося столбца будет осуществлять покрытие выброшенной исходной импликанты. В рассматриваемом примере таких столбцов нет.
5 этап. Вычеркивание лишних строк.
Если в таблице после 4-го этапа появились строки в которых нет ни одной метки, то их вычеркивают, т.е. первичные импликанты, соответствующие им, исключаются из минимальной формы функции, т.к. они не покрываются оставшихся исходных импликант. В рассмотренном примере таких строк нет.
6 этап. Выбор минимального покрытия.


















(1)

(4)

(5)

(6)



V

V









V







V






V















V

V









V





Исследуем таблицу, полученную после всех предыдущих этапов (см. 3-й этап). Выбирается такая совокупность первичных импликант, которая бы имела метки во всех столбцах. Предпочтение отдается варианту покрытия с минимальным числом букв в первичных импликантах, образующих покрытие. В данном примере все оставшиеся первичные импликанты содержат одинаковое число букв. Выберем покрытие из импликант и , т.к. они покрывают все 4 оставшиеся исходные импликанты. Они и будут существенными импликантами.

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

Она должна быть неизбыточной. В данном примере – это и есть минимальная форма функции.

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

Замечание 2. По методу Квайна получаются тупиковые формы. Их может быть несколько. Среди них и надо искать минимальные формы. Все возможные тупиковые формы можно найти по методу Патрика.


Метод Патрика

нахождение всех возможных тупиковых форм.
Не находя существенных импликант, обозначим все простые импликанты латинскими буквами. Исходная функция может быть записана в виде дизъюнкции простых импликант, что соответствует сокращенной форме (которая является единственной). Эта форма является также тупиковой. Для отыскания всего множества тупиковых форм запишем тождественную логическую формулу:


где - простые импликанты, соответствующие меткам -го столбца, - количество меток в -м столбце, - количество столбцов в таблице меток. Формула дает полную совершенную нормальную дизъюнктивную форму функции, т.е. .

Если в формуле встретятся члены и , то член можно не писать, ибо (вот почему на 3 этапе метода Квайна выброшены большие столбцы).

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


№№

Тупиковые формы

Общее число букв в тупиковой форме

Число членов в тупиковой форме

1.










2.










3.










.










.











Тупиковые формы с наименьшим числом букв и есть минимальные формы, тупиковые формы с наименьшим числом членов есть кратчайшие формы. Чаще всего минимальная форма не совпадает с кратчайшей.

Рассмотрим на примере 5 этот метод (см. таблицу этапа 2 в методе Квайна). Начертим ее здесь. Обозначив первичные импликанты латинскими буквами a, b, c, d, e, f, а столбцы цифрами (1), (2), … , (8).




























(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)



a

V







V















b

V













V









c







V

V















d













V

V









e













V







V



f




V

V










V

V


Составим функцию .

Дизъюнкция включается для реализации меток 1-го столбца и т.д. По закону поглощения , поэтому члены 3 и 8 можно не записывать. Упростим .









Раскроем скобки


Каждый из членов дает тупиковую форму данной функции. Составим таблицу.


№№

Тупиковые формы

Общее число букв в тупиковой форме

Число членов в тупиковой форме

1.



3+3+2=8

3

2.



3+3+3+2=11

4

3.



3+3+3+2=11

4

4.



3+3+3+2=11

4


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

Итак, есть минимальная форма данной функции.

Замечание 3. Таблица покрытий может не содержать существенных импликаций. Поясним, как в этом случае поступить. Пусть таблица меток имеет вид: (см. ниже).

Исключим 2 и 7 столбцы, т.к. 3 и 5 являются их частями, а из оставшихся столбцов выбираем столбец с наименьшим числом меток. Здесь во всех столбцах их по 2, поэтому возьмем 1-й столбец. Примем за псевдосущественную импликанту , а затем .





1

2

3

4

5

6

7

a

v

v

v










v

b




v

v

v




v




c




v




v

v




v

d

v










v

v

v




Рассмотрим 2 частных случая:







1

3

4

5

6

1)




1

3

4

5

6

2)




1

3

4

5

6

a

v

v













a

v

v













a

v

v










b




v

v




v




b




v

v




v




b




v

v




v

c







v

v







c







v

v







c







v

v




d

v







v

v




d

v







v

v




d

v







v

v


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

1):



(1)

2):



(4)






(2)






(5)






(3)











Рассмотрим совместно множества решений. Решение (2) входит в (5), (3) совпадает с (4), а (1) нет соответствующего во 2-й таблице, наиболее простая тупиковая форма (5). Таким образом, разбиение на подтаблицы упрощает отыскание тупиковых форм.
1   2   3   4   5


4 метод. Метод Квайна
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации