5. Минимизация логических функций методом Квайна – Мак-Класки Метод Карно позволяет минимизировать логические функции с относительно малым числом переменных. - презентация

1 5. Минимизация логических функций методом Квайна – Мак-Класки Метод Карно позволяет минимизировать логические функции с относительно малым числом переменных. Кроме того метод является визуальным и сложным для алгоритмизации. Метод минимизации Квайна – Мак-Класки (далее просто Мак-Класки) является систематичным и его легко алгоритмизировать. Кроме того в нем отсутствуют ограничения на число переменных логической функции.

2 Метод Мак-Класки состоит из двух основных этапов: 1.Нахождение всех простых импликант логической функции, используя правило склеивания 2. Минимизации полученного множества простых импликант (задача нахождения оптимального покрытия) 10. Законы склеивания: a)(A & B) (A & B) A b)(A B) & (A B) A

3 Метод Мак-Класки. 1-ый этап. Разделить двоичные векторы области единиц логической функции на секции в соответствии с их индексами. Индекс двоичного вектора = число единиц, входящих в состав этого вектора. Составить таблицу интервалов, используя правило склеивания. Склеивать между собой только те двоичные векторы, которые отличаются друг от друга только в одной координате (ближайшие векторы). Склеивание происходит по этой координате. Ближайшие векторы могут находится только в соседних секциях таблицы. В конце первого этапа получают все простые импликанты логической функции.

4 В ходе второго этапа полученное множество простых импликант минимизируют, т.е. выбирают минимальное количество простых импликант, которое позволяет покрыть всю область единиц логической функции (типичная задача нахождения оптимального покрытия). Метод Мак-Класки. 2-ой этап.

5 1-ый этап – нахождение всех простых импликант логической функции. Пример 5.1 пусть задана логическая функция f (X 1, X 2, X 3, Х 4 ) = (0,1,2,5,6,7,8,9,10,14) 1 Найти МДНФ методом Мак-Класки. Решение: Выпишем двоичные векторы области единиц логической функции и найдем их индексы V 1 (X 1, X 2, X 3,Х 4 ) ={(0000), (0001), (0010), (0101), (0110), (0111), (1000), (1001), (1010), (1110),} Разделим двоичные векторы на секции в соответствии с их индексами, получим таблицу:

6 индексинтервал Таблица интервалов: Склеиваем между собой ближайшие векторы соседних секций пока это возможно.

7 индексинтервалиндексинтер- вал индексинтервалобозн A A A Все оставшиеся не склеенными интервалы образуют множество всех простых импликант логической функции. А1 А2 А3

8 2-ой этап – минимизация полученного множества простых импликант логической функции. Импли- кант A1 0-01xx A2 01-1xx A3 011-xx A4 -00-xxxx A5 -0-0xxxx A6 --10xxxx Вся область единиц должна быть покрыта простыми импликантами (в каждом столбце хотя бы один «х»), и их должно быть минимальное количество.

9 Оптимальное покрытие: А2, А4, А6. МДНФ: А2 А4 А6 = X 1 &X 2 &X 4 X 2 & X 3 X 3 & X 4.

10 Сходство методов Мак-Класки и Карно: 1.Векторы соседних клеток карты Карно = векторы соседних секций таблицы склеивания метода Мак- Класки. 2.Объдинение в контуры на карте Карно = склеивание в методе Мак-Класки. 3.Нахождение МДНФ и МКНФ методом Мак-Класки отличаются между собой по таким же принципам как и в методе Карно.

11

12 = (X 1 X 2 X 4 ) & ( X 1 X 2 X 3 ) & ( X 3 X 4 )