Теоретические основы минимизации булевых функций методом Квайна

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

СЕВАСТОПОЛЬСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ ЯДЕРНОЙ ЭНЕРГИИ И ПРОМЫШЛЕННОСТИ

Лабораторное занятие №

по дисциплине "ПТЦА"

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

Задание выполнил:

Студент 62? класса

____________

Поверил:

____________

Севастополь – 20 г.

Теоретические основы минимизации булевых функций методом Квайна

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

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

Определение. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций.

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

Определение. Булева функция называется импликантой булевой функции , если для любого набора переменных, на котором g = 1, справедливо f =1.

Пример. Булева функция f задана табл. 1. Там же приведены все ее импликанты. При записи функции f и ее импликант в СДНФ имеем:

Таблица 1
x1	x2	x3	f	g1	g2	g3	g4	g5	g6	g7

Определение. Импликанта g булевой функции f, являющаяся элементарной конъюнкцией, называется простой, если никакая часть импликанты g не является импликантой функции f.

Из примера видно, что импликанты и , являются простыми импликантами функции f. Импликанты g₁, g₂, g₄, g₆ не являются простыми, так как их части являются импликантами функции f, например g₅ является частью g₁. Приведем без доказательства два утверждения, полезные при получении минимальной ДНФ.

1. Дизъюнкция любого числа импликант булевой функции f также является импликантой этой функции.

2. Любая булева функция f эквивалентна дизъюнкции всех своих простых импликант. Такая форма представления булевой функции называется сокращенной ДНФ.

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

.

Как видно из табл. 1, импликанты g₃,, g₅ в совокупности покрывают своими единицами все единицы функции f. Получение сокращенных ДНФ является первым этапом отыскания минимальных форм булевых функций. Как уже отмечалось, в сокращенную ДНФ входят все простые импликанты булевой функции. Иногда из сокращенной ДНФ можно убрать одну или несколько простых импликант, не нарушая эквивалентности исходной функции. Такие простые импликанты назовем лишними. Исключение лишних простых импликант из сокращенных ДНФ — второй этап минимизации.

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

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

Утверждение. Тупиковые ДНФ булевой функции f, содержащие минимальное число букв, являются минимальными. Минимальных ДНФ тоже может быть несколько.

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

Метод Квайна

Метод Квайна основывается на применении двух основных соотношений.

1. Соотношение склеивания

,

где А — любое элементарное произведение.

2. Соотношение поглощения

.

Таблица 2
x1	x2	x3	x4	f

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

Для доказательства достаточно показать, что произвольная простая импликанта может быть получена. В самом деле, применяя к р операцию развертывания (обратную операции склеивания):

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

Пример. Пусть имеется булева функция, заданная таблицей истинности (табл. 9.12). Ее СДНФ имеет вид:

Для удобства изложения пометим каждую конституенту единицы из СДНФ функции f каким-либо десятичным номером (произвольно). Выполняем склеивания. Конституента 1 склеивается только с конституентой 2 (по переменной ) и с конституентой 3 (по переменной ), конституента 2 с конституентой 4 и т. д.

В результате получаем

1—2:

1—3:

2—4:

3—4:

4—6:

5—6:

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

Далее производим склеивания получаемых элементарных произведений. Склеиваются только те произведения, которые содержат одинаковые переменные. Имеет место два случая склеивания:

;

,

с появлением одного и того же элементарного произведения Дальнейшие склеи­вания невозможны. Произведя поглощения (из полученной ДНФ вычеркиваем все поглощаемые элементарные произведения), получим сокращенную ДНФ:

.

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

Пример (продолжение). Импликантная матрица имеет вид (табл. 3).

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

1) ищутся столбцы импликантной матрицы, имеющие только один крестик. Соответствующие этим крестикам простые импликанты называются базисными и составляют так называемое ядро булевой функции. Ядро обязательно входит в минимальную ДНФ.

2) рассматриваются различные варианты выбора совокупности простых импликант, которые накроют крестиками остальные столб­цы импликантной матрицы, и выбираются варианты с

минимальным суммарным числом букв в такой совокупности импликант.

Таблица 3
Простые Импликанты	Конституенты единицы
	x	x	x	x
				x		x
					x	x

Пример (продолжение). Ядром нашей функции являются импликанты ; .Импликанта — лишняя, так как ядро накрывает все столбцы импликант­ной матрицы. Поэтому функция имеет единственную тупиковую и минимальную ДНФ:

f = .

Следует отметить, что число N крестиков в одной строке всегда является степенью 2. Более того, читатель может легко убедиться в том, что

,где k — число букв, содержащихся в простой импликанте.

Заметим также, что используя различные соотношения, можно расширить"область применения метода Квайна за пределы совершенной ДНФ.

Пример. Минимизировать булеву функцию f методом Квайна:

.

1. Избавляемся от отрицаний и скобок, используя приведенные соотношения

2. Восстанавливаем СДНФ функции f, применяя операцию развертывания

.

3. Найдем сокращенную ДНФ функции f, производя в СДНФ все возможные склеивания

.

4. Ищем минимальную ДНФ функции f по импликантной матрице (табл. 4). Ядро булевой функции: , .Минимальные ДНФ:

;

.

Таблица 4
Простые импликанты системы функций	Конституенты единицы функции
	x1x2x3
	x	x
	x				x
		x	x
			x	x