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

Карта карно – таблица истинности для определения булевой функции. Эта карта имеет 2^n клеток, где n – число переменных.

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

С геометрической точки зрения карта карно есть способ представления гиперкуба размерностью от 3 до 6.

В карте карно любые 2 соседние клетки, а также 2 любые клетки на границе карты закодированы соседними кодами.

ТЕОРЕМА: правильными конфигурациями ранга i для карты карно 3 переменных является все прямоугольники, вертикали, горизонтали и квадраты, имеющие площадь , i=1,2,3 и только такие прямоугольники

ТЕОРЕМА: правильными конфигурациями ранга i для карты карно 4 переменных является все прямоугольники, вертикали, горизонтали и квадраты, имеющие площадь , i=1,2,3,4 и только такие прямоугольники

 

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

 

Простую импликанту называют избыточной относительно дизъюнктивно-нормальной формы, если ее можно удалить из этой дизъюнктивно нормальной формы без потерь эквивалентности исходной записи.

Любую ДНФ из эквивадентной исходной СДНФ формы, содержащую все ядровые импликанты и не содержащую ни одной избыточной импликанты называют тупиковой ДНФ.

 

 

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

Исходная функция представляется в СДНФ

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

Все элементарные конъюнкции сравниваются попарно

Если встречаются 2 конъюнкции ранга i вида , то они образуют элементарную импликанту ранга i-1

Импликанта i ранга, принимающая участие в организации простой импликанты i-1 ранга помечается, а все неотмеченные импликанты называются простыми или первичными.

В результате получим 9 импликант ранга 3 а импликант ранга 4 не осталось.

В результате попарного сравнения импликант ранга 3 мы выделили 1 импликанту ранга 2 и осталось 5 простых импликант ранга 3.

2 Шаг. Расстановка меток.

Для построения таблицы покрытия нужно выбрать минимальное число первичных импликант.

Составляется таблица, число строк равно чису простых импликант ранга 3.

В столбцах присутствуют все импликанты ранга 4, не покрываемые импликантами ранга 2. В таблице покрытий ставятся метки на пересечение столбца конъюнкции i-го ранда и входящей в нее простой импликанты меньшего ранга.

3 Шаг. Нахождение существенных импликант

Если в каком-то из столбцов составленной таблицы имеется только 1 метка, то первичный импликант, стоящий в соответствующей строке, называют существенным импликантой и она не может быть исключена из первой части ДНФ.

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