Произвольные функции и логические схемы

 

Поскольку значениями логических функций могут быть только 0 или 1, то любые логические функции можно использовать как аргументы других логических функций, т.е. строить из простых функций более сложные. Пусть в таблице 1.2. задана произвольная функция Y трех аргументов, и ее нужно выразить с помощью простых функций НЕ, И, ИЛИ.

Очевидно, что Y = 1, когда или a c = 1 (строка 1), или (строка 3), или (строка 6), или (строка 7).

Таблица 1.2.

№	Аргументы	Функция	№	Аргументы	Функция
	a	b	c	Y		a	b	c	Y

 

Все это можно записать в виде одного общего аналитического выражения: (1.1)

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

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

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

НЕ, И; НЕ, ИЛИ; И-НЕ и ИЛИ-НЕ.

Для построения логической схемы, реализующей функцию, заданную таблицей истинности, обычно удобнее аналитическая форма представления функции. В данном случае - это выражение (1.1). Схема, реализующая (1.1), показана на рис. 1.6. Она состоит из трех ярусов. В первом ярусе расположены инверторы. Очевидно, что максимальное число инверторов не превышает числа аргументов. Во втором ярусе расположены элементы И, реализующие входящие в формулу элементарные конъюнкции. Число входов каждого элемента равно числу аргументов реализуемой функции, а число элементов- числу элементарных конъюнкций в формуле. В третьем ярусе схемы стоит элемент ИЛИ, число входов которого равно числу дизъюнкций в формуле.

Рис.1.6. Логическая схема, реализующая (1.1).

 

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

 

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

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

abc abc= (abc a c) (abc bc) (abc ab ) =

= ac(b ) bc(a ) ab(c ) = ac bc ab (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)

 

 

	б)

 

 

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

Пример.

Построить схему, реализующую функцию, заданную таблицей:

 

a	b	c	Y		a	b	c	y

 

СДНФ требуемой функции:

Для СДНФ будет значительно проще: .

Последнее выражение более обозримо и легко минимизируется:

= ac, откуда .

Для реализации необходим один двухвходовой элемент 2И–НЕ.

Рассмотрим особенности минимизации недоопределенных функций.

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

В таблице истинности не определенные значения функции отмечают прочерками.

Пример.

Построить схему, реализующую функцию Y, не определенную на наборах 000 и 111 и заданную таблицей.

	Y	bc
		a
	–
			–

 

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

В этом случае схема строится на двух ЛЭ: 2И и 2ИЛИ. (рис. 1.9.б)

 

Рис. 1.9.Реализация недоопределенной функции.