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

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

Введем относительно булевой функции две доопределенные функции:

- на всех неопределенных наборах начальной булевой функции доопределяется единицами;

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

Тогда теорема Квайна в этом случае утверждает следующее:

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

В качестве иллюстрации применения теоремы Квайна рассмотрим пример.

Пример 1.6. Булева функция задана таблицей истинности

Таблица 1.11.

Таблица истинности булевой функцию

		*		*				*

Найти минимальную ДНФ.

Если доопределить булеву функцию нулями получаем СДНФ функции (см. табл. 1.11). Она записывается так:

Затем доопределяя функцию единицами, получаем СДНФ в виде:

.

Используя метод минимизации Квайна, получаем окончательную сокращенную ДНФ .

Строим импликантную таблицу, столбцами которой будут макстермы функции , а строками простые импликанты (табл. 1.12).

Таблица 1.12

Импликантная таблица булевой функции

импликанты	макстермы
		*	*
	*
			*

Минимальную ДНФ запишем так:

Пример 1.7. Булева функция задана картой Карно (рис. 1.3.). Найти минимальное доопределение этой функции.

Прочерк в карте Карно означает, что таким образом обозначенные значения БФ не определенны. Из карты, приведенной на рис. 1.3, видно, какие наборы целесообразно доопределять единицами, а какие ну лями. Доопределяем функцию и записываем соответствующую карту Карно так (рис.1.4):

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

Заметим, что рассмотренный метод минимизации БФ будет использован ниже при синтезе полного одноразрядного двоичного сумматора.

Дата добавления: 2015-07-08