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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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