Аналитический метод минимизации ФАЛ

(Квайна-Мак-Класски)

 

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

 

Пример 3.1. Найти сокращенную ДНФ следующего логического выражения заданного в СДНФ

 

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

Алгоритм получения сокращенной ДНФ следующий:

1. Каждая конституэнта единицы, заданного логического выражения представляется двоичным числом.

2. Полученные двоичные числа разбиваются на группы по числу единиц и записываются в первый столбец в порядке возрастания числа единиц в группе.

3. Производится склеивание двоичных чисел первой группы с двоичными числами второй группы, двоичные числа второй группы с двоичными числами третей группы и т.д. Склеиваться будут только соседние двоичные числа. Два двоичных числа называются соседними, если они отличаются между собой только в одном разряде, например 110 и 100.

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

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

Для склеивания двоичных чисел второго и последующих столбцов необходимо выполнение двух условий:

1. Чтобы склеиваемые числа были соседними.

2. Черточки в склеиваемых числах должны стоять в одинаковых разрядах.

Склеивание импликант (сокращенных двоичных чисел) продолжается до тех пор, пока выполняются эти два условия.

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

Примечание. В процессе склеивания рекомендуется каждое двоичное число первого столбца обозначить его десятичным эквивалентом. Это необходимо для удобства при получении тупиковых ДНФ.

 

Решение примера 3.1. Выполняя вышеизложенный алгоритм получим:

Первый столбец	Второй столбец	Третий столбец
0.	0 0 0 0	Ú	0, 1	0 0 0 -	Ú	0, 1, 2, 3	0 0 - -	A
1.	0 0 0 1	Ú	0, 2	0 0 - 0	Ú	0, 1, 8, 9	- 0 0 -	B
2.	0 0 1 0	Ú	0, 4	0 - 0 0	Ú	0, 2, 4, 6	0 - - 0	C
4.	0 1 0 0	Ú	0, 8	- 0 0 0	Ú	0, 4, 2, 6	0 - - 0
8.	1 0 0 0	Ú	1, 3	0 0 - 1	Ú	0, 8, 1, 9	- 0 0 -
3.	0 0 1 1	Ú	1, 9	- 0 0 1	Ú	1, 3, 9, 11	- 0 - 1	D
6.	0 1 1 0	Ú	2, 3	0 0 1 -	Ú	1, 9, 3, 11	- 0 - 1
9.	1 0 0 1	Ú	2, 6	0 - 1 0	Ú	2, 3, 6, 7	0 - 1 -	E
7.	0 1 1 1	Ú	4, 6	0 1 - 0	Ú	2, 6, 3, 7	0 - 1 -
11.	1 0 1 1	Ú	8, 9	1 0 0 -	Ú	3, 7, 11, 15	- - 1 1	F
15.	1 1 1 1	Ú	3, 7	0 - 1 1	Ú	3, 11, 7, 15	- - 1 1
			3, 11	- 0 1 1	Ú
			6, 7	0 1 1 -	Ú
			9, 11	1 0 - 1	Ú
			7, 15	- 1 1 1	Ú
			11, 15	1 - 1 1	Ú

Из результатов склеивания видно, что все числа первого и второго столбцов склеились. Не склеились только числа третьего столбца, из которых выбираем импликанты A, B, C, D, E, F, повторяющиеся отбрасываем. Таким образом, сокращенная ДНФ будет иметь вид

A Ú B Ú C Ú D Ú E Ú F = .

 

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

Для получения тупиковых ДНФ необходимо построить импликантную таблицу, которая состоит из вертикальных и горизонтальных линий. Число вертикальных линий равно числу конституэнт единицы, которые содержаться в СДНФ заданного логического выражения. Число горизонтальных линий равно числу простых импликант сокращенной ДНФ. В рассмотренном примере 3.1. число конституэнт единицы равно 11 (0, 1, 2, 4, 8, 3, 6, 9, 7, 11, 15), а число простых импликант сокращенной ДНФ равно 6 (A, B, C, D, E, F). Импликантная таблица будет следующая

Таблица 3.1.

Импликантная таблица для примера 3.2

 

Простые импликанты получились в результате склеивания конституэнт единицы столбца 1. Например простая импликанта А получилась в результате склеивания четырех конституэнт единицы 0, 1, 2, 3 (см. столбец 3). В таблице 3.1. на пересечении горизонтальной линии импликанты А с вертикальными линиями конституэнт единицы 0, 1, 2, 3 стоят крестики, свидетельствующие о том, что импликанта А поглощает конституенты единицы 0, 1, 2, 3. Все остальные крестики в таблице 3.1. на пересечениях вертикальных и горизонтальных линий говорят о поглощении простыми импликантами соответствующих конституэнт единицы.

Для получения тупиковых ДНФ из таблицы 3.1. запишем следующее выражение

y = (A Ú B Ú C)(A Ú B Ú D)(A Ú C Ú E)C×B×(A Ú D Ú E Ú F)(C Ú E)(B Ú D)(E Ú

Ú F) × (D Ú F)F (3.1)

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

Раскрытие скобок выражения (3.1) представляет собой достаточно сложную процедуру, поэтому получить тупиковые ДНФ можно простым анализом импликантной таблицы и выражения (3.1). В выражении (3.1) в качестве отдельных сомножителей присутствуют импликанты B, C, F, которые обязательно должны войти в тупиковую ДНФ, т.к. конституэнта 4 (см. табл. 3.1.) поглощается только импликантой С, конституэнта 8 только импликантой В, а конституэнта 15 только импликантой F. Во все суммы простых импликант выражения (3.1) в качестве слагаемого входит хотя бы одна из импликант B, C, F. Следовательно, все конституэнты единицы будут поглощаться импликантами B, C, F. Отсюда следует, что тупиковая ДНФ для заданной ФАЛ в примере 3.2. будет только одна

B Ú C Ú F= .

Эта тупиковая ДНФ одновременно будет и минимальной ДНФ.

 

Пример 3.2. Найти минимальную ДНФ следующего логического выражения

.

Решение

Первый столбец	Второй столбец
0.	0 0 0 0	Ú	0, 2	0 0 - 0	A
2.	0 0 1 0	Ú	0, 8	- 0 0 0	B
8.	1 0 0 0	Ú	2, 6	0 - 1 0	C
6.	0 1 1 0	Ú	8, 9	1 0 0 -	D
9.	1 0 0 1	Ú	6, 7	0 1 1 -	E
7.	0 1 1 1	Ú	9, 13	1 - 0 1	F
13.	1 1 0 1	Ú	7, 15	- 1 1 1	G
15.	1 1 1 1	Ú	13, 15	1 1 - 1	H

 

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

A Ú B Ú C Ú D Ú E Ú F Ú G Ú H =00-0 Ú -000 Ú 0-10 Ú 100- Ú

Ú 011- Ú 1-01 Ú -111 Ú 11-1 =

.

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

Таблица 3.2.

 

На основе импликантной таблицы 3.2., по аналогии с примером 3.1, запишем выражение

y = (A Ú B)(A Ú С)(В Ú D)(С Ú E)(D Ú F)(E Ú G)(F Ú H)(G Ú H).

Раскрыв скобки данного выражения получим

y = ABDEH Ú ABEFG Ú ABEFH Ú ACDEH Ú ACDFG Ú ADEH Ú ADGH Ú

Ú ADEFG Ú ADEFH Ú BCDEH Ú BCDGH Ú BCFG Ú BCEFH.

Все полученные произведения по составу импликант являются тупиковыми ДНФ. Из полученных тупиковых ДНФ необходимо выбрать минимальную ДНФ. Так как все импликанты A B C D E F G H по длине одинаковые, то минимальной ДНФ будет та тупиковая ДНФ, которая содержит наименьшее число импликант. Таких тупиковых ДНФ три ADEH, ADGH и BCFH, которые состоят из четырех импликант. Любая из этих трех тупиковых будет минимальной.

Например B Ú C Ú F Ú H = -000 Ú 0-10 Ú 1-01 Ú 11-1 =

= .