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

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

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

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

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

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

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

Говорят, что элементарная конъюнкция К покрывает элементарную конъюнкцию L (K>L), если любой литерал, входящий в К, входит и в L.

Литерал – элементарная переменная или ее отрицание

Вертикальный прямоугольник говорит, что

Функция получилась как дизъюнкция трех конъюнкций, каждая из которых предсавляет собой импликант

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

F1 и f2 – равнозначные записи. Первые три конъюнкции в f1 и f2 соответствуют ядру

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Полнота логических функций.

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

ТЕОРЕМА: для полноты любого набора булевых операций необходимо и достаточно чтобы с помощью операций этого набора можно было построить функцию и одну из функций xy или .

Существует 7 полных наборов булевых функций:

1) (&, ) «и не» конъюнктивный базис Буль;

2) () «или не» дизъюнктивный базис Буль;

3) { | } – Шеффер;

4) { } – базис Пирса;

5) { , 0} -

6) { , } – импликативные базисы (5, 6);

7) { , &} – базис Жигалкина;

При этом можно переходить из одного базиса в другой.