Минимизация функций

Дата добавления: 2013-12-23; просмотров: 820; Нарушение авторских прав

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

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

abcabc= (abc ac)(abc bc)(abcab) =

= ac(b)bc(a)ac(c) = acbcac (1.2)

Рис. 1.7. Схема, реализующая (1.2).

a) в булевском базисе; б) в базисе И-НЕ.

В инженерной практике для минимизации наиболее часто применяют карты Карнау (Карно).

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

Таблица истинности (а) и структура карты Карно (б) для функции двух переменных.

x1	x2	f(x1,x2)
		f(0,0)
		f(0,1)
		f(1,0)
		f(1,1)

	x2
x1
	f(0,0)	f(0,1)
	f(1,0)	f(1,1)

б)

а)

Таблица истинности (а) и cтруктура карты Карно (б) для функции трех переменных.

x1	x2	x3	f(x1,x2,x3)
			f(0,0,0)
			f(0,0,1)
			f(0,1,0)
			f(0,1,1)
			f(1,0,0)
			f(1,0,1)
			f(1,1,0)
			f(1,1,1)

а)

	x2,x3
x1
	f(0,0,0)	f(0,0,1)	f(0,1,1)	f(0,1,0)
	f(1,0,0)	f(1,0,1)	f(1,1,1)	f(1,1,0)

б)

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

<== предыдущая лекция	\|	следующая лекция ==>
Произвольные функции и логические схемы	\|	Интегральные логические элементы.