Лабораторная работа №9 Минимизация логических функций с помощью карт Карно

 

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

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

Правила минимизации следующие:

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

2. Четыре вершины могут объединяться, образуя 2-куб, содержащий две независимые координаты.

3. Восемь вершин могут объединяться, образуя один 3-куб.

4. Шестнадцать вершин, объединяясь, образуют один 4-куб и т.д.

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

 

Рисунок 1 – Минимизация функции пяти переменных с помощью карты Карно

 

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

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

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

 

 

Рисунок 2 – Построение карты Карно с помощью шестнадцатиклеточных карт

 

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

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

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

 

Рисунок 3 – Пример минимизации не полностью определенной функции

Оборудование

ПЭВМ IBMPC, операционная система Windows, OooWriter, MSWord.

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

Доопределить оптимальным образом и минимизировать с помощью карты Карно частичные логические функции

 

Вариант	f (a, b, c, d, e)	Запрещенные наборы (карты Карно)
1		10, 21, 24, 29
2		11, 20, 25, 27
3		0, 1, 10, 14, 15
4		0, 1, 3
5		15, 16, 25, 27, 28
6		0, 4, 17, 31

 

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

1. Какая логическая функция называется частичной?

2. Сколько ячеек содержит карта Карно для функции семи переменных?

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

4. Какое количество клеток карты Карно допустимо объединять? Существуют ли какие-нибудь ограничения?

5. Какие клетки в карте Карно считаются соседними?

6. В чем состоит главный недостаток применения карт Карно для
минимизации функций?

 

 

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

 

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

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

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

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

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

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

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

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

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

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

 

Таблица 1

Первичные импликанты

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

 

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

Таблица 2

Первичные импликанты С₁

Кубический комплекс	Число единиц	Кубы	Метки
С 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-кубов (таблица 3).

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

 

Таблица 3

Первичные импликанты С₂

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

 

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

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

 

Таблица 4

Таблица покрытий

	0000	0001	0010	0011	0100	1001	1010	1011	1100	1101	1111
	(0)	(1)	(2)	(3)	(4)	(9)	(10)	(11)	(12)	(13)	(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

 

Ответ: .

 

Оборудование

ПЭВМ IBMPC, операционная система Windows, OooWriter, MSWord.

 

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

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

Вариант	f (a, b, c, d, e)
1
2
3
4
5
6

 

 

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

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

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

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

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

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

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