Глава 4 Алгебра логики (стр. 5 )

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

Если в столбце имеется только одна пометка, то импликанта, соответствующая этой строке, называется существенной, и она обязательно должна присутствовать в минимальной ДНФ Þ она включается в ответ. Если не включить ее в ответ, в нем будет потеряна единица, соответствующая рассматриваемому столбцу. Включив эту импликанту в минимальную ДНФ, можно устранить из дальнейшего рассмотрения строку и все столбцы с пометками для этой импликанты Þ вычеркиваем столбец с одной пометкой и все остальные столбцы, имеющие пометки в этой строке, а также саму строку.

5) Вычеркивание доминируемых строк.

Если в j-ой строке имеются все пометки i-ой строки и может быть, еще некоторые, то j-я строка доминирует над i-ой, и i-ую строку можно исключить из дальнейшего рассмотрения. Из таблицы вычеркиваются все доминируемые строки (с меньшим числом пометок – в частности, строки без пометок).

6) Вычеркивание столбцов.

Если в m-ом столбце таблицы имеются все пометки k-го столбца и может быть, еще некоторые, то m-ый столбец доминирует над k-ым и m-ый столбец можно исключить из дальнейшего рассмотрения (т. е. вычеркивается столбец с большим числом пометок, в отличие от строки).

7) Этапы 4–6 повторяются до тех пор, пока это возможно. Полученная после таких преобразований таблица называется циклической.

8) Выбор минимального покрытия в циклической таблице.

Используется процедура ветвления:

а) выбирают столбец с минимальным количеством пометок (таких столбцов может быть несколько);

б) используя эти столбцы, выбирают из строк, содержащих пометки в выбранном столбце, ту, которая содержит максимальное количество пометок, и включают ее в минимальную ДНФ (в ответ). Если таких строк несколько, то берется любая.

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

В результате описанных преобразований таблицы будет получена минимальная ДНФ.

Пример 4.15  Найдем минимальную ДНФ для функции =.
1) Выпишем все наборы, на которых функция принимает значение 1 (т. е. 0-кубы функции): 0000, 0011, 0100, 0110, 0111, 1001, 1110, 1111. Разобьем наборы на группы по количеству единиц. Первая группа состоит из наборов, не содержащих единиц: {0000}; вторая – из наборов, содержащих одну единицу: {0100}, третья – две единицы: {0011, 0110, 1001}, четвертая – три {0111, 1110}, пятая – четыре {1111}. Выполним все возможные склеивания между наборами соседних групп, помечая участвующие в склеивании наборы: Результаты склеивания – 1-кубы 0x00, 01x0, 0x11, 011x, x110, x111, 111x. Импликанта 1001 – простая. Разобьем все полученные в результате склеивания импликанты по положению x на группы: 1-я группа: ; 2-я: ; 3-я: ; 4-я: .
Произведем все возможные склеивания внутри каждой группы, помечая наборы, участвующие в склеивании.
Результат склеивания – импликанта, соответствующая x11x, и набор простых импликант, соответствующих 0x00, 0x11, 01x0. Дальнейшее склеивание осуществить нельзя, поэтому x11x соответствует простой импликанте. Можно переходить к составлению импликантной таблицы.

	0000	0011	0100	0110	0111	1001	1110	1111
1001						v
0x00	v		v
01x0			v	v
0x11		v			v
x11x				v	v		v	v

Импликанты, соответствующие 0x00, 0x11, 1001, x11x – существенные, поэтому они обязательно входят в минимальную ДНФ. Удалим строки и столбцы для этих импликант из таблицы. Вычеркнутся все столбцы, следовательно, на этом процесс поиска минимальной ДНФ закончен.

Минимальная ДНФ имеет следующий вид:

Можно построить карту Карно и проверить полученный результат.

4.4.3  Минимизация частично определенных функций

Для минимизации неполностью определенных функций вводят в рассмотрение две дополнительных функции: j0(x1,x2,...,xn)=0 и j1(x1,x2,...,xn)=1 на всех наборах, на которых функция f не определена, и j0(x1,x2,...,xn)=j1(x1,x2,...,xn)=f там, где f определена. Для построения минимальной ДНФ нужно выбрать наименьшее покрытие 0-кубов функции j0 простыми импликантами функции j1.

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

  Пример 4.16  Рассмотрим функцию , заданную Т. И.

x1	x2	x3	x4	f	j0	j1
0	0	0	0	1	1	1
0	0	0	1	*	0	1
0	0	1	0	*	0	1
0	0	1	1	0	0	0
0	1	0	0	*	0	1
0	1	0	1	0	0	0
0	1	1	0	1	1	1
0	1	1	1	*	0	1
1	0	0	0	*	0	1
1	0	0	1	1	1	1
1	0	1	0	0	0	0
1	0	1	1	*	0	1
1	1	0	0	0	0	0
1	1	0	1	*	0	1
1	1	1	0	1	1	1
1	1	1	1	*	0	1

Дополним ее функциями j0 и j1. Нужно найти сокращенную ДНФ для j1, а затем все покрытия 0-кубов j0.
Выпишем наборы, на которых функция j1 принимает значение 1: 0000, 0001, 0010, 0100, 0110, 0111, 1000, 1001, 1011, 1101, 1110, 1111. Разобьем наборы на группы по количеству единиц. K00={0000}; K01={0001,0010,0100,1000}; K02={0110,1001}; K03={0111,1011,1101,1110}, K04={1111}. Выполним все возможные склеивания между наборами соседних групп, помечая участвующие в склеивании наборы: Результаты склеивания – 1-кубы 000x, 00x0, 0x00, x000, x001, 01x0, 100x, 011x, x110, 10x1, 1x01, x111, 1x11, 11x1, 111x. Разобьем все полученные в результате склеивания импликанты по положению x на группы:
K11=; K12=; K13=; K14=.
Произведем все возможные склеивания внутри каждой группы, помечая наборы, участвующие в склеивании. Получим: x00x, x11x, 1xx1, 0xx0, 1xx1, x00x, x11x. После устранения дубликатов получим: x00x, x11x, 1xx1, 0xx0.
Результат склеивания – простая импликанта – 1-куб, соответствующая 0x00, и набор 2-кубов импликант, соответствующих x00x, x11x, 1xx1, 0xx0. Дальнейшее склеивание осуществить нельзя Þ это простые импликанты. Можно переходить к составлению импликантной таблицы, столбцы которой – 0-кубы функции j0.

	0000	0110	1001	1110
0x00	v
x00x	v		v
x11x		v		v
1xx1			v
0xx0	v	v

Импликанта x11x – существенная для 1110, вычеркиваем столбец 1110 и строку x11x, а также столбец 0110, который она покрывает, при этом импликанту x11x включаем в ответ. Больше существенных импликант нет, а строка x00x доминирует над всеми остальными Þ доминируемые строки вычеркиваем, а импликанту x00x выписываем в ответ. В итоге в ответ вошли импликанты x11x и x00x, т. е. функция имеет вид f = x2×x3 Ú `x2×`x3. Проверка: Построенная карта Карно подтверждает полученный результат. Для включения в покрытия всех единиц, используя при необходимости символы d и выбирая покрытия наибольшей размерности, достаточно покрытий x11x и x00x. Остальные символы d, не вошедшие в эти покрытия, заменяются нулями.

Итак, рассмотрены основные методы получения минимальной ДНФ для полностью определенных и частичных функций.

4.4.4  Контрольные вопросы

1.  Что является импликантой функции? В чем отличие простой импликанты?

2.  Что соответствует импликанте (простой импликанте) на карте Карно?

3.  Что такое сокращенная ДНФ?

4.  Каков алгоритм нахождения сокращенной ДНФ?

5.  Как можно получить минимальную ДНФ с помощью карт Карно?

6.  Что позволяет найти метод Квайна-Мак-Класки? Каковы основные этапы этого метода? Что является результатом каждого из этапов?

7.  Что такое 0-кубы? 1-кубы?

8.  Что представляет операция склеивания? Какие наборы возможно склеить?

9.  Как строится импликантная таблица? Что является ее строками, а что – столбцами? Какие строки и какие столбцы удаляются при упрощении импликантной таблицы?

10.  В чем состоит процедура ветвления?

11.  Единственна ли минимальная ДНФ?

12.  Что такое частично определенная функция?

13.  Чем отличается минимизация частично определенной функции?