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

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