Комбинационная логика

Не следует путать с Комбинаторная логика.

В теории цифровых устройств комбинационной логикой (комбинационной схемой) называют двоичную логику функционирования устройств комбинационного типа. У комбинационных устройств состояние выхода однозначно определяется набором входных сигналов. Это отличает комбинационную логику от секвенциальной логики, в рамках которой выходное значение зависит не только от текущего входного воздействия, но и от предыстории функционирования цифрового устройства. Другими словами, секвенциальная логика предполагает наличие памяти, которая в комбинационной логике не предусмотрена.

Характеристика

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

Математику комбинационной логики обеспечивает булева алгебра. Базовыми операциями являются:

• конъюнкция $x\land y$;
• дизъюнкция $x\lor y$;
• отрицание (инверсия) $\lnot x$ или ${\bar {x}}$.

В комбинационных схемах используются логические элементы:

• конъюнктор (И);
• дизъюнктор (ИЛИ);
• инвертор (НЕ),

а также производные элементы:

• И-НЕ;
• ИЛИ-НЕ;
• «Равнозначность» (исключающее ИЛИ-НЕ).

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

Формы представления

Формы представления логических выражений основаны на понятиях «истина» (T — true) и «ложь» (F — false). В двоичном счислении — это соответствует значениям 1 и 0, которыми кодируются пропозициональные переменные. Выражения комбинационной логики могут быть представлены в форме таблицы истинности, либо в виде формулы булевой алгебры. Ниже показан пример таблицы истинности для трёх переменных.

$x$	$y$	$z$	Логическая формула	Результат
F	F	F	${\bar {x}}\land {\bar {y}}\land {\bar {z}}$	T
F	F	T	${\bar {x}}\land {\bar {y}}\land z$	T
F	T	F	${\bar {x}}\land y\land {\bar {z}}$	F
F	T	T	${\bar {x}}\land y\land z$	F
T	F	F	$x\land {\bar {y}}\land {\bar {z}}$	T
T	F	T	$x\land {\bar {y}}\land z$	F
T	T	F	$x\land y\land {\bar {z}}$	F
T	T	T	$x\land y\land z$	T

Таблица истинности служит основой для представления логического выражения в виде алгебраической формулы:

$x\land {\bar {y}}\land {\bar {z}}\lor x\land y\land z.$

В отличие от таблицы логическая формула способна преобразовываться по правилам булевой алгебры. Таким образом находится сокращённое выражение:

$x\land ({\bar {y}}\land {\bar {z}}\lor y\land z).$

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

Минимизация логических формул

Минимизация (упрощение) формул комбинационной логики осуществляется по следующим правилам:

$(x\lor y)\land (x\lor z)=x\lor (y\land z),$

$(x\land y)\lor (x\land z)=x\land (y\lor z);$

$x\lor (x\land y)=x,$

$x\land (x\lor y)=x;$

$x\lor ({\bar {x}}\land y)=x\lor y,$

$x\land ({\bar {x}}\lor y)=x\land y;$

$(x\lor y)\land ({\bar {x}}\lor y)=y,$

$(x\land y)\lor ({\bar {x}}\land y)=y.$

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

См. также

• Асинхронная логика

Литература

• Поспелов Д. А. Логические методы анализа и синтеза схем./ Изд. 3-е, перераб. и доп. — М.: Энергия, 1974. — 368с.