Минимизация логических функций методом Квайна

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

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

Таблица 1. Таблица истинности к примеру

Номер набора	x1	x2	x3	x4	f
0	0	0	0	0	1
1	0	0	0	1	1
2	0	0	1	0	1
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	1
6	0	1	1	0	1
7	0	1	1	1	1
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	0
12	1	1	0	0	0
13	1	1	0	1	0
14	1	1	1	0	1
15	1	1	1	1	0

Нахождение простых импликант

Перебирают все пары минтермов исходной совершенной дизъюнктивной нормальной формы, склеивая те из них, для которых эта операция возможна. При составлении пар любой из минтермов может быть испоользован многократно. Процедура повторяется и над полученными импликантами - опять проводятся операции склеивания. Процесс повторяется до тех пор, пока не останется ни одной импликанты, допускающей склеивания с другими. Такие импликанты называются простыми. Участовавшие в склеивании элементарные конъюнкции помечаются каким-либо символом, например, "*".

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

Таблица 2. Склеивание минтермов совершенной ДНФ

Номер набора	Минтермы
0	*
1	*
2	*
5	*
6	*
7	*
8	*
9	*
10	*
14	*

Склеиваемые наборы	Минтермы
0, 1
0, 2
0, 8
1, 5
1, 9
2, 6
2, 10
5, 7
6, 7
6, 14
8, 9
8, 10
10, 14

В левой части таблицы показаны минтермы исходной совершенной ДНФ. Анализируюются все возможные пары минтермов, и, если это возможно, производится их склеивание. Минтермы, участовавшие в операции склеивания, помечаются символом "*". Результаты склеивания с указанием номеров "склеенных" минтермов показаны в правой части таблицы 2.

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

Таблица 3. Склеивание импликант ранга 3

Склеиваемые наборы	Минтермы
0, 1	*
0, 2	*
0, 8	*
1, 5
1, 9	*
2, 6	*
2, 10	*
5, 7
6, 7
6, 14	*
8, 9	*
8, 10	*
10, 14	*

Склеиваемые наборы	Импликанты
0, 1, 8, 9
0, 2, 8, 10
0, 8, 1, 9
0, 8, 2, 10
2, 6, 10, 14
2, 10, 6, 14

Из таблицы видно, что импликанты, обозначенные как 1,5; 5,7 и 6,7 остались непомеченными. Это означает, что они не были склеены ни с одной другой импликантой, поэтому являются простыми и должны учитываться на последующих этапах минимизации. В ходе склеивания образовались три пары импликант ранга 2. В соответсвии с теоремой идемпотентности из нескольких одинаковых импликант можно составить только одну. Нетрудно заметить, что дальнейшее склеивание трёх оставшихся импликант ранга 2 невозможно, то есть эти импликанты простые. Таким образом, в дополнение к трём простым импликантам ранга 3: , и получены ещё три простые импликанты ранга 2: , и . Логическая сумма перечисленных простых импликант представляет собой сокращённую ДНФ:

Составление импликантной матрицы и расстановка меток избыточности

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

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

Таблица 4. Импликантная матрица Квайна


0, 1, 8, 9
0, 2, 8, 10
2, 6, 10, 14
1, 5
5, 7
6, 7

0	1	2	5	6	7	8	9	10	14
√	√					√	√
√		√				√		√
		√		√				√	√
	√		√
			√		√
				√	√

Импликантная матрица для рассматриваемого примера (таблица 4) содержит 6 строк (по числу простых импликант) и 10 столбцов (по числу минтермов исходной СДНФ). В матрице минтермы обозначены своими номерами, а слева от простых импликант перечислены номера минтермов, из которых эти импликанты были получены. Расставим в ней метки в тех позициях, где простая импликанта, указанная в левом столбце, покрывает минтерм, записанный в верхней строке.

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

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

Таблица 5. Удаление из импликантной матрицы существенных импликант и покрываемых ими минтермов.


0, 1, 8, 9
0, 2, 8, 10
2, 6, 10, 14
1, 5
5, 7
6, 7

0	1	2	5	6	7	8	9	10	14
√	√					√	√
√		√				√		√
		√		√				√	√
	√		√
			√		√
				√	√

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

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

Таблица 6. Сокращённая импликантная матрица

	5	7
0, 2, 8, 10
1, 5	√
5, 7	√	√
6, 7		√

Первая строка не содержит меток избыточности, поэтому её можно удалить. (таблица 7)

Таблица 7. Сокращённая импликантная матрица после исключения пустых строк.

	5	7
1, 5	√
5, 7	√	√
6, 7		√

Выбор минимального элемента

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

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

;

Определение и запись минимальной нормальной формы

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

Коэффициент сложности первой из двух получившихся тупиковых форм равен 10, а второй - 14. По этой причине минимальной ДНФ следует признать первое выражение:

Нет времени вникать в решение? Можно заказать работу!

Пройти тест по теме Математическая логика

К началу страницы