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

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

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

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

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

• конъюнкция $x\wedge y$;
• дизъюнкция $x\vee y$;
• отрицание (инверсия) $\mathrm{\neg }x$ или $\overline{x}$.

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

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

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

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

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

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

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

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

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

$x\wedge \overline{y}\wedge \overline{z}\vee x\wedge y\wedge z.$

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

$x\wedge (\overline{y}\wedge \overline{z}\vee y\wedge z).$

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

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

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

$(x\vee y)\wedge (x\vee z)=x\vee (y\wedge z),$

$(x\wedge y)\vee (x\wedge z)=x\wedge (y\vee z);$

$x\vee (x\wedge y)=x,$

$x\wedge (x\vee y)=x;$

$x\vee (\overline{x}\wedge y)=x\vee y,$

$x\wedge (\overline{x}\vee y)=x\wedge y;$

$(x\vee y)\wedge (\overline{x}\vee y)=y,$

$(x\wedge y)\vee (\overline{x}\wedge y)=y.$

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

См. также

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

Литература

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