Схемы из функциональных элементов

Различают схемы без памяти (комбинационные схемы) и схемы с памятью (последовательные схемы). Одной из математических моделей комбинационных схем являются схемы из функциональных элементов (СФЭ). Другими моделями являются контактные схемы (C. Shannon, 1937) и двоичные решающие диаграммы (C. Lee, 1959). По сути, указанные формализмы являются разными способами представления функций алгебры логики (ФАЛ). Напомним определение СФЭ.

Определение. Базисом называется непустое множество функций алгебры логики.

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

1) вершины, являющиеся истоками, помечены символами переменных и называются входами (разным вершинам соответствуют разные переменные);

2) каждая вершина, в которую входит k ³ 1 дуг, помечена функцией из базиса B, зависящей от k переменных (такие вершины называются функциональными элементами или вентилями);

3) некоторые вершины выделены как выходы (входные вершины могут быть и выходными).

Определение. Сложностью СФЭ называется число входящих в нее ФЭ.

Часто в качестве базиса используют {Ù, Ú, Ø}. Соответствующие ФЭ называются дизъюнктором (вентиль ИЛИ), конъюнктором (вентиль И) и инвертором (вентиль НЕ). Графически вентили изображаются следующим образом (стандарт ANSI).

	OR	Дизъюнкция (ИЛИ)
	AND	Конъюнкция (И)
	NOT	Отрицание (НЕ)
	XOR	Сумма по модулю 2 (исключающее ИЛИ)
	NOR	Стрелка Пирса (НЕ-ИЛИ)
	NAND	Штрих Шеффера (НЕ-И)
	XNOR	Эквиваленция (исключающее ИЛИ-НЕ)

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

Задание. Изобразить графически схемы, реализующие следующие функции:

1) мультиплексор 2-в-1 (if sel then out=in₀ else out=in₁);

2) мультиплексор 4-в-1.

Домашнее задание. Изобразить графически схемы, реализующие следующие функции:

1) демультиплексор 1-в-2 (if sel then out₀=in else out₁=in);

2) демультиплексор 1-в-4.