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

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

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

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

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

Джерела

• Матвієнко М. П. Комп'ютерна логіка. Навчальний посібник. — K.: Видавництво Jlipa-K, 2012. — 288 с. — ISBN 966-2609-09-7
• Поспелов Д. А. Логические методы анализа и синтеза схем./ Изд. 3-е, перераб. и доп. — М.: Энергия, 1974. — 368 с.
• Жабін В. І., Жуков I. A., Клименко I. A., Ткаченко В. В. Прикладна теорія цифрових автоматів. — К.: Видавництво НАУ, 2007. — 364 с.

Портал «Програмування»   Портал «Математика»