Пример 3

Рассмотрим минимизацию ПФ, заданной с помощью числового представления f₃=V(1, 2, 4, 8, 9, 10, 11, 12, 14, 17, 19, 20, 24, 25, 26, 27, 28, 30).

Поскольку номер набора определяет 0-куб и, следовательно, набор переменных, на котором функция равна единице, СДНФ ПФ f₃ представляется в виде:

Карта Карно для ПФ f₃ построена на рис. 6, а. Минимальное покрытие единиц карты определено прямоугольниками с размерами , , , объединяющими по 4 и 8 соседних клеток и образующих 2- и 3-кубы.

x₂

x₂

x₂

x₂

x₂

x₁

x₁

x₃

x₃

x₃

x₄

x₄

x₄

x₅

x₅

x₂

x₂

x₁

x₄

x₅

a)

б)

Рис. 4. Определение минимальных ДНФ (а) и КНФ (б) ПФ f₃ пяти переменных.

Кубы с наибольшей размерностью, покрывающие ПФ (минимизация f₃ по «нулям»), приведены на рис.4, б. Минимальные ДНФ и КНФ представляются выражениями

Пример 4

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

x₁

x₂

x₃

x₄

x₂

x₁

x₃

x₄

x₁

x₂

x₃

x₄

a)

в)

б)

Рис. 5. Минимизация не полностью определенной ПФ

При минимизации не полностью определенных ПФ в клетки карты Карно, заполненные прочерками, записываются нули или единицы таким образом, чтобы получить покрытие «основных» единиц («основных» нулей) наименьшим числом кубов с наибольшей размерностью. Так, для ПФ (рис. 5, а) минимизация по «единицам» (рис.5, б) и по «нулям» (рис. 5, в) дает следующие результаты:

Практическое занятие 2 МИНИМИЗАЦИЯ ПЕРЕКЛЮЧАТЕЛЬНЫХ ФУНКЦИЙ МЕТОДОМ КВАЙНА – МАК-КЛАСКИ

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

Порядок выполнения задания и содержание отчета

1. Построить дизъюнктивную нормальную форму (ДНФ) заданной переключательной функции и представить ПФ комплексом 0-кубов.

2. Минимизировать ПФ методом Квайна – Мак-Класки. Определить минимальное покрытие.

3. Построить минимальную дизъюнктивную (ДНФ) нормальную форму.

Минимизация переключательной функции методом Квайна – Мак-Класки основывается на использовании правила поглощения, позволяющего вычислить все множество 1-, 2-, … n- кубов, образующих комплекс K(f). Из этого комплекса выделяются кубы наибольшей размерности, покрывающие все множество вершин функции, определяя покрытие Z(f) функции. Покрытие Z(f) упрощается с целью получения минимального.

Как уже отмечалось, 0-куб есть вершина, т.е. булев вектор, или набор аргументов типа «0100», «0000». 1-куб можно рассматривать как вектор, одна координата которого безразлична. Очевидно, что 1-куб может быть образован 0-кубами, различающимися только на одну единицу. Например, «0100» и «0000» образуют

1-куб «0x00». Аналогично 2-кубы образуются из 1-кубов, отличающихся только на 1 единицу (и имеющих «x» в одинаковых позициях), например «0x01» и «0x11» дадут 2-куб «0xx1» и т.д.

В задачах минимизации булевых функций используется понятие простой импликанты. Некоторый куб zK называется простой импликантой, если он не содержится ни в каком другом кубе комплекса К, т.е. не является гранью никакого другого куба из этого комплекса. Совокупность всех таких кубов образует множество Z={z} простых импликант данного комплекса. Любой куб минимального покрытия С_min является простой импликантой; следовательно, С_minZ. Минимизация функции состоит из последовательных этапов.

1. Нахождение простых импликант. Все 0-кубы сравниваются попарно между собой на предмет образования 1-кубов. Если 0-кубы образуют 1-куб, они помечаются. Для упрощения данной операции удобно множество 0-кубов разбить на группы, содержащие равное число единиц, 1-кубы могут быть образованы объединением 0-кубов только из смежных групп. Аналогично производится попытка построить множество 2-кубов на базе множества 1-кубов. Этап заканчивается, когда ни один куб более высокого порядка не может быть построен. Все неотмеченные кубы комплекса K(f) являются простыми импликантами и образуют покрытие Z(f) функции f, которое в общем случае не является минимальным.

2. Составление таблицы покрытий. Задача данного этапа – удалить все лишние простые импликанты. Составляется так называемая таблица покрытий. Строки данной таблицы помечаются простыми импликантами, полученными на шаге 1, столбцы - 0-кубы (термы) минимизированной функции. На пересечении

i-й строки и j-го столбца ставится метка 1, если i-я импликанта покрывает j-й 0-куб, т.е. соответствующие символы совпадают или покрываются символом «x» со стороны импликанты.

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

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

5. Вычеркивание лишних простых импликант. Если в остаточной таблице имеются строки, не имеющие ни одной метки, импликанты, соответствующие данным строкам, вычеркиваются.

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

Записывается минимальная ДНФ как дизъюнкция элементов минимального покрытия.

Рассмотрим порядок выполнения задания на примерах минимизации ПФ четырех переменных, минимизация функций с другим числом переменных производится аналогично.

Пример 5

Минимизировать методом Квайна – Мак-Класки ПФ четырех переменных, заданную в виде комплекса 0-кубов:

х₁ х₂ х₃ х₄

1 0 0 0 1 При записи минимизируемой функции

2 0 0 1 0 в виде комплекса К⁰, удобно наборы

3 1 0 0 0 разбить на группы (группа отделена чер-

4 0 0 1 1 той), содержащие одинаковое число

5 1 0 0 1 единиц, и пронумеруем каждый 0-куб.

6 1 1 0 0 В процессе вычислений будем также

7 0 1 1 1 помечать кубы.

8 1 1 1 0

9 1 1 1 1

Построим комплекс K¹, помечая, посредством слияния каких 0-кубов или импликант создана текущая импликанта.

1 0 0 x 1 1 – 4

2 x 0 0 1 1 – 5

3 0 0 1 x 2 – 4

4 1 0 0 x 3 – 5

5 1 x 0 0 3 – 6

6 0 x 1 1 4 – 7

7 1 1 x 0 6 – 8

8 x 1 1 1 7 – 9

9 1 1 1 x 8 – 9

Построим комплекс : .

Пометим знаком « » все импликанты, покрываемые кубами более высокого порядка.

Таким образом, имеем набор простых импликант:

0 0 x 1

x 0 0 1

0 0 1 x

1 0 0 x

1 x 0 0

0 x 1 1

1 1 x 0

x 1 1 1

1 1 1 x

Составляем таблицу покрытий (табл. 1).

Таблица 1

Импли-\0-куб канта \	0001	0010	1000	0011	1001	1100	0111	1110	1111
0 0 х 1	1			1
 x 0 0 1	1				1
 0 0 1 x		1		1
1 0 0 x			1		1
 1 x 0 0			1			1
0 х 1 1				1			1
 1 1 х 0						1		1
 x 1 1 1							1		1
 1 1 1 x								1	1
									

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

Далее следует решить задачу о наименьшем покрытии в остаточной таблице, т.е. покрыть минимальным количеством импликант (соответствуют строкам) все истинные наборы (или 0-кубы, соответствуют столбцам). В нашем случае любая импликанты покрывает два набора, обычно при выборе импликант отдается предпочтение тем из них, которые покрывают наибольшее число наборов (их называют короткими импликантами).

Первый столбец (0001) покрывается первой и второй импликантой (00х1 и х001). Здесь, скорее всего, лучше выбрать импликанту х001, поскольку она дополнительно поглощает столбец 1001, тогда как импликанта 00х1 поглощает еще столбец 0011, поглощенный существенной импликантой х001, которая обязательно войдет в решение. Соответствующая единица помечена горизонтально расположенным овалом, строку и столбец, соответствующие выбранной импликанте (х001) и покрываемые ей столбцы пометим знаком «» и из рассмотрения исключаем. Действуя аналогично, рассмотрев столбец 1000 и импликанты 100х и 1х00, выберем импликанту 1х00; рассмотрев столбец 0111 и импликанты 0х11 и х111 выберем импликанту х111, после чего в таблице останется только один не выбранный столбец 1110. Для его поглощения можно выбрать любую из двух импликант: 11х0 или 111х, соответствующие столбцы и строки пометим знаком «».

Таким образом, в данном случае можно построить два минимальных покрытия:

х 0 0 1 х 0 0 1

0 0 1 х 0 0 1 х

1 х 0 0 1 х 0 0

х 1 1 1 х 1 1 1

1 1 х 0 1 1 1 х

Запишем результат в виде ДНФ: и .

Обе минимальные формы равноправны.

Существует формальный алгоритм, называемый алгоритмом Петрика [4, 5], позволяющий автоматизировать решение задачи о наименьшем покрытии остаточной таблицы.

Пример 6

Минимизировать методом Квайна – Мак-Класки ПФ из примера 2.

х₁ х₂ х₃ х₄

1 0 0 0 0 Запишем минимизируемую функцию

2 1 0 0 0 из примера 2, при этом, для

3 0 1 0 0 удобства наборы разобьем на группы,

4 0 0 1 0 содержащие одинаковое число единиц, и

5 0 0 0 1 пронумеруем каждый 0-куб. В процессе

6 0 1 1 0 вычислений будем также помечать

7 1 0 0 1 кубы.

8 0 0 1 1

Построим комплекс K¹, помечая, посредством слияния каких 0-кубов или импликант создана текущая импликанта.

1 x 0 0 0 1 – 2

2 0 x 0 0 1 – 3

3 0 0 x 0 1 – 4

4 0 0 0 x 1 – 5

5 1 0 0 x 2 – 7

6 0 1 x 0 3 – 6

7 0 x 1 0 4 – 6

8 0 0 1 x 4 – 8

9 x 0 0 1 5 – 7

10 0 0 x 1 5 – 8

П остроим комплекс :

x 0 0 х 1 – 9, 4-5

0 x x 0 2 – 7, 3-6

0 0 x х 3 – 10, 4-8

В данном случае импликанты покрывают все предыдущие, таким образом, имеем набор простых импликант:

х 0 0 х

0 х х 0

0 0 х х .

Составляем таблицу покрытий (табл. 2).

Таблица 2

Импли-\0-куб канта \	0000	1 000	0100	0010	0001	0110	1001	0011
х 0 0 х	1	1			1		1
0 х х 0	1		1	1		1
0 0 х х	1			1	1			1

В данной таблице покрытий все импликанты являются существенными (имеют единственную единицу в столбце, соответствующие единицы обведены) . Таким образом, в данном случае имеем минимальное покрытие:

х х 0 0

0 х х 0 .

0 0 х х

Запишем результат в виде ДНФ:

.

Как видим, результат, полученный методом Квайна – Мак-Класки совпадает с результатом, полученным методом карт Карно.

Практическое занятие 3 СИНТЕЗ КОМБИНАЦИОННЫХ СХЕМ В БАЗИСЕ «И, ИЛИ, НЕ»

Цель занятия: изучение метода синтеза комбинационных схем в логически полном базисе «И, ИЛИ, НЕ».