Алгоритм минимизации ФАЛ методом Мак - Класки (1 этап)

Вопросы и упражнения

1. Сформулируйте алгоритм минимизации ФАЛ методом Квайна.

2. Минимизировать ФАЛ f(x1, x2, x3, x4), принимающую значение 1 на наборах:

1) 1,2,6,7,9,12,13.

2) 2,3,5,6,10,11,14.

3) 0,8,10,11,13,15.

4) 6,8,9,12,13,14.

5) 6,7,8,10,11,13.

6) 1,2,3,12,13,14,15.

7) 0,4,5,6,7,14,15.

8) 2,4,7,9,10,14,15.

9) 0,2,4,8,12,14,15.

10) 0,2,3,5,11,12,15.

11) 5,7,8,9,10,11,15.

12) 5,6,7,8,9,13,14.

Сделать проверку с помощью таблиц истинности.

Тема 7. Минимизация булевых функций в классе ДНФ. Метод Квайна – Мак - Класки

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

В 1956 г. Мак – Класки модернизировал первый этап метода Квайна, что дало снижение числа сравнений минтермов.

а) Для записи минтермов в виде двоичных номеров, все номера разбивают по числу единиц на непересекающиеся множества. При этом в I – ю группу войдут все номера, имеющие в своей двоичной записи ровно I единиц.

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

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

Пример 7.1. Найти МДНФ функции, принимающей значение 1 на наборах: 0,1,2,3,4,6,7,8,9,11,15.

Решение.

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

Составим таблицу истинности:

Запишем минитермы по группам в двоичном коде.

- нулевая 0000;

- первая 0001, 0010, 1000, 0100;

- вторая 0011, 0110,1001;

- третья 0111, 1011;

- четвёртая 1111.

Сравниваем соседние группы, в результате чего получим минтермы третьего ранга.

а) и б) и в) и г) и

0000 0001 000- 0001 0011 00-1 0011 0111 0-11 0111 1111 -111

0010 00-0 0010 0110 -001 0110 1011 -011 1011 1-11.

1000 -000 1000 1001 001- 1001 10-1

0100 0-00 0100 01-0 011-

100-

0-10

Находим минитермы второго ранга:

а) и б) и в) и

000- 00-1 0 0 - - 00-1 0-11 -0-1 0-11 -111 --11

00-0 -001 - 0 0 - -001 -011 -0-1 -011 1-11 --11

-000 001- 0 0 - - 001- 10-1 0-1- 10-1

0-00 01-0 0 - - 0 01-0 011- 0-1- 011-

100- 0 - - 0 100-

0-10 - 0 0 - 0-10

00-- -0-1 --11

-00- 0-1-

0--0

Этап 2. Расстановка меток.

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

Существенной импликантой является терм и х3х4, т.к. в 5,8,10,11 столбцах имеется по одной метке. Вычёркиваем столбцы 1,2,3,4,5,6,7,8,9,10,11 т.к. в них есть существенная импликанта и строки 2,3,6.

Этап 6. Выбор минимального покрытия.

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

.

Составив таблицу истинности, убеждаемся в том, что ФАЛ минимизирована верно.