Комбінаційна логіка

В теорії цифрових пристроїв комбінаційною логікою (комбінаційною схемою) називають логіку функціонування пристроїв комбінаційного типу. У комбінаційних пристроїв стан виходу однозначно визначається набором вхідних сигналів. Це відрізняє комбінаційну логіку від секвенційної логіки, в рамках якої вихідне значення залежить не тільки від поточного вхідного впливу, але й від передісторії функціонування цифрового пристрою. Іншими словами, секвенційна логіка припускає наявність пам'яті, яку комбінаційна логіка не передбачає.

Класи автоматів (Клацання на кожному шарі скеровує до статті на відповідну тему)

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

Комбінаційна логіка використовується в обчислювальних схемах для формування вхідних сигналів і для підготовки даних, які підлягають збереженню. На практиці обчислювальні пристрої зазвичай поєднують комбінаційну та секвенційну логіку. Наприклад, Арифметико-логічний пристрій (АЛП) для математичних обчислень містить комбінаційні вузли. Математику комбінаційної логіки забезпечує булева алгебра. Базовими операціями є: кон'юнкція ${\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	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),\quad (x\land y)\lor (x\land z)=x\land (y\lor z);}$

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

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

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

Процедура мінімізації дозволяє спростити логічну функцію і, тим самим, домогтися більш компактною реалізації комбінаційних схем.

Див. також

• FPGA
• Асинхронна логіка
• Секвенційна логіка

Джерела

Література

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