Русская Википедия:Комбинационная логика
Шаблон:Не путать Комбинационная логика (комбинационная схема) в теории цифровых устройств — двоичная логика функционирования устройств комбинационного типа. У комбинационных устройств состояние выхода однозначно определяется набором входных сигналов, что отличает комбинационную логику от секвенциальной логики, в рамках которой выходное значение зависит не только от текущего входного воздействия, но и от предыстории функционирования цифрового устройства. Другими словами, секвенциальная логика предполагает наличие памяти, которая в комбинационной логике не предусмотрена.
Характеристика
Комбинационная логика используется в вычислительных цепях для формирования входных сигналов и для подготовки данных, которые подлежат сохранению. На практике вычислительные устройства обычно сочетают комбинационную и секвенциальную логику. Например, арифметическое логическое устройство (АЛУ) содержит комбинационные узлы.
Математику комбинационной логики обеспечивает булева алгебра. Базовыми операциями являются:
- конъюнкция <math>x \land y</math>;
- дизъюнкция <math>x \lor y</math>;
- отрицание (инверсия) <math>\lnot x</math> или <math>\bar{x}</math>.
В комбинационных схемах используются логические элементы:
- конъюнктор (И);
- дизъюнктор (ИЛИ);
- инвертор (НЕ),
а также производные элементы:
- И-НЕ;
- ИЛИ-НЕ;
- Исключающее ИЛИ
- Эквивалентность (исключающее ИЛИ-НЕ).
Наиболее известными комбинационными устройствами являются сумматор, полусумматор, шифратор, дешифратор, мультиплексор и демультиплексор.
Формы представления
Формы представления логических выражений основаны на понятиях «истина» (T — true) и «ложь» (F — false). В двоичном счислении — это соответствует значениям 1 и 0, которыми кодируются пропозициональные переменные. Выражения комбинационной логики могут быть представлены в форме таблицы истинности, либо в виде формулы булевой алгебры. Ниже показан пример таблицы истинности для трёх переменных.
| <math>x </math> | <math>y </math> | <math>z </math> | Логическая формула | Результат |
|---|---|---|---|---|
| F | F | F | <math>\bar {x} \land \bar {y} \land \bar {z}</math> | T |
| F | F | T | <math>\bar {x} \land \bar {y} \land z</math> | T |
| F | T | F | <math>\bar {x} \land y \land \bar {z}</math> | F |
| F | T | T | <math>\bar {x} \land y \land z</math> | F |
| T | F | F | <math>x \land \bar {y} \land \bar {z}</math> | T |
| T | F | T | <math>x \land \bar {y} \land z</math> | F |
| T | T | F | <math>x \land y \land \bar {z}</math> | F |
| T | T | T | <math>x \land y \land z</math> | T |
Таблица истинности служит основой для представления логического выражения в виде алгебраической формулы:
- <math>x \land \bar {y} \land \bar {z} \lor x \land y \land z.</math>
В отличие от таблицы логическая формула способна преобразовываться по правилам булевой алгебры. Таким образом находится сокращённое выражение:
- <math>x \land (\bar {y} \land \bar {z} \lor y \land z).</math>
С точки зрения комбинационной логики представленные формулы определяют одну и ту же функцию. Разница в том, что сокращённая формула позволяет реализовать соответствующую комбинационную схему в более компактном виде.
Минимизация логических формул
Минимизация (упрощение) формул комбинационной логики осуществляется по следующим правилам:
- <math> (x \lor y) \land (x \lor z) = x \lor (y \land z),</math>
- <math> (x \land y) \lor (x \land z) = x \land (y \lor z);</math>
- <math> x \lor (x \land y) = x, </math>
- <math> x \land (x \lor y) = x; </math>
- <math> x \lor(\bar {x} \land y) = x \lor y,</math>
- <math> x \land(\bar {x} \lor y) = x \land y; </math>
- <math> (x \lor y)\land(\bar {x} \lor y)=y, </math>
- <math> (x \land y) \lor (\bar {x} \land y)=y. </math>
Процедура минимизации (упрощения) позволяет упростить логическую функцию и, тем самым, добиться более компактной реализации комбинационных схем.
См. также
Литература
- Поспелов Д. А. Логические методы анализа и синтеза схем./ Изд. 3-е, перераб. и доп. — М.: Энергия, 1974. — 368с.
