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

Лабораторная работа №8. Минимизация логических функций методом Квайна – Мак-Класки

1. Цель работы

Изучить метод Квайна – Мак-Класки минимизации логических функций.

2. Теоретические сведения

Метод Квайна – Мак-Класки является одним из формальных методов минимизации логических выражений, реализующий достаточно простой алгоритм решения поставленной задачи. Исходную логическую функцию необходимо представить в совершенной дизъюнктивной нормальной форме (СДНФ), которая при расчетах заменяется кубическим комплексом C₀.

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

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

Минимизация логического выражения осуществляется с использованием двух логических операций: склеивания и поглощения. Очевидно, что при группировании кубов в классы по количеству единиц в их наборах, склеивание возможно лишь между элементами соседних классов, поэтому такое упорядочение упрощает поиск соответствующих пар элементов.

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

На первом этапе первого цикла выполняются все возможные склеивания между 0-кубами. Результаты помещаются в продолжение таблицы. Затем производятся все поглощения 0-кубов 1-кубами. Если останутся 0-кубы, не поглощенные в результате второго этапа, им присваивается метка «первичная импликанта». На этом первый цикл склеивания и поглощения заканчивается.

Второй цикл выполняется аналогично, но уже над комплексом C₁, составленным из 1-кубов. Циклы продолжаются до тех пор, пока это возможно.

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

Пример. Найти минимальную форму для функции .

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

Таблица 7 - Первичные импликанты С0
Кубический комплекс	Число единиц	Кубы	Метки
С0	0	0000	*
	1	0001 0010 0100	* * *
	2	0011 1001 1010 1100	* * * *
	3	1011 1101	* *
	4	1111	*

Затем производится поглощение 0-кубов 1-кубами (таблица 8). Сам процесс аналогичен поглощению 0-кубов.

Таблица 8 - Первичные импликанты С1
Кубический комплекс	Число единиц	Кубы	Метки
С1	0	000х 00х0 0х00	* * ПИ
	1	00х1 х001 001х х010 х100	* * * * ПИ
	2	х011 10х1 1х01 101х 110х	* * * * ПИ
	3	1х11 11х1	* *

Аналогичная процедура повторяется для кубического комплекса С₁. в результате поглощений и склеиваний 1-кубов формируется таблица 2-кубов (таблица 9).

Следует обратить внимание на то, что при обработке комплекса С₁ и последующих сравнивать можно лишь те кубы, которые имеют метку х в одном и том же разряде.

Таблица 9 - Первичные импликанты С2
Кубический комплекс	Число единиц	Кубы	Метки
С2	0	00хх	ПИ
	1	х0х1 х01х	ПИ ПИ
	2	1хх1	ПИ

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

В данном случае импликанты из второй, четвертой, шестой и седьмой строк обеспечивают минимальное покрытие.

Таблица 10 - Таблица покрытий
	0000 (0)	0001 (1)	0010 (2)	0011 (3)	0100 (4)	1001 (9)	1010 (10)	1011 (11)	1100 (12)	1101 (13)	1111 (15)
0х00	v				v
х100					v				v
110х									v	v
00хх	v	v	v	v
х0х1		v		v		v		v
х01х			v	v			v	v
1хх1						v		v		v	v

Ответ: .

3. Порядок выполнения работы

·         Ознакомиться с теоретическими сведениями.

·         Получить вариант задания у преподавателя.

·         Выполнить задание.

·         Продемонстрировать выполнение работы преподавателю.

·         Оформить отчет.

·         Защитить лабораторную работу.

4. Требования к оформлению отчета

Отчет по лабораторной работе должен содержать следующие разделы:

·         титульный лист;

·         цель работы:

·         задание на лабораторную работу;

·         ход работы;

·         ответы на контрольные вопросы;

·         выводы по проделанной работе.

5. Задание на работу

Минимизировать методом Квайна–Мак-Класки логические функции (таблица 11).

Таблица 11 - Варианты заданий на работу
Вариант	f(a, b, c, d, e)
1
2
3
4
5
6

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

1.     В каком виде должна быть представлена функция для минимизации по методу Квайна–Мак-Класки?

2.     Как в методе Квайна–Мак-Класки называются непоглощенные n-кубы?

3.     Какова особенность минимизации n-кубов в методе Квайна – Мак-Класки?

4.     Для чего в методе Квайна–Мак-Класки строится таблица покрытий?

5.     По какому принципу производится выбор подмножества простых импликант?

6.     В какой форме представляется результат минимизации по методу Квайна–Мак-Класки?

7. Литература

1.     Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов / Под ред. B.C. Зарубина, А.П. Крищенко. – 3-е изд., стереотип. – М.: Издательство МГТУ им. Н.Э. Баумана, 2004. – 744 с.

2.     Савельев А.Я. Основы информатики. – М.: Издательство МГТУ имени Н.Э.Баумана, 2001. – 328 с.