# Лекція 4. Мінімізація виразів. Логічні схеми

## Огляд

У [Лекції 3](ODM-L03.md) ми ввели булеву область $\{0,1\}$, операції
$\wedge$ (кон'юнкція, І), $\vee$ (диз'юнкція, АБО), $\overline{\ \cdot\ }$
(заперечення, НЕ), їхні таблиці істинності та основні тотожності — комутативність,
асоціативність, дистрибутивність, закони де Моргана, поглинання й доповнення. Усе це
ми вважаємо відомим і вільно використовуємо. Заперечення позначаємо рискою зверху:
$\overline{x}$ (те саме, що $\neg x$).

Там ця алгебра була набором *правил*. Ця лекція змушує правила працювати. За всіма
питаннями нижче стоїть **вартість**: одну й ту саму булеву функцію можна записати
незліченною кількістю рівносильних формул, а в апаратурі кожна виписана нами операція
стає фізичним **вентилем**, який займає площу кристала, споживає енергію й вносить
затримку. Процесор містить мільярди вентилів; зекономити один вентиль у схемі, яку
повторено мільйон разів, — це вже відчутно. Тому центральна інженерна задача така:
*за заданою поведінкою (таблицею істинності) знайти найдешевшу формулу, що її
реалізує.* Ця лекція будує теорію й методи, які цю задачу розв'язують.

Ми пройдемо шість тем:

- **Логічні елементи (вентилі)** — фізичні пристрої, що обчислюють одну булеву
  операцію: їхні умовні позначення, таблиці істинності, реальні мікросхеми та
  оглядово транзисторна реалізація.
- **Мінімізація законами алгебри** — покрокове спрощення формули тотожностями
  Лекції 3.
- **Канонічні форми** — досконала диз'юнктивна (ДДНФ) і досконала кон'юнктивна (ДКНФ)
  нормальні форми, які однозначно читаються з таблиці істинності.
- **Мінімальні форми** — МДНФ і МКНФ, найдешевші дворівневі записи.
- **Карти Карно** — код Грея, склеювання сусідніх клітин, зчитування МДНФ по одиницях
  і МКНФ по нулях.
- **Логічні схеми** — побудова схеми за МДНФ/МКНФ та переписування її у базиси ТА-НІ
  (NAND) та АБО-НІ (NOR).

Усе тут — **комбінаційна** логіка: вихід залежить лише від поточних входів, без
пам'яті. Оскільки істиннісних значень лише два, кожна функція $n$ змінних повністю
описана скінченною таблицею істинності з $2^n$ рядків — цим фактом ми користуємося
постійно. Побудовані нижче схеми ви складатимете власноруч в онлайн-симуляторі під час
[лабораторної роботи 1](../Laboratory/Laboratory1/main.md); ця лекція — її теоретична
основа. Далі, у [Лекції 5](ODM-L05.md), ми переходимо від булевих схем до мови
математичної логіки — висловлень та їхніх логічних зв'язок.

> **Про строгість.** Кілька результатів нижче оформлені як **теореми** й
> **твердження** та супроводжуються доведенням, обмеженим позначками *Доведення.* …
> $\blacksquare$. Читайте доведення активно, запитуючи на кожному кроці «чому цей крок
> дозволений?». Прийоми (аналіз за випадками, доведення через індикаторну властивість,
> подвійне включення множин розв'язків) — ті самі, що й у попередніх лекціях.

---

## 4.1 Логічні елементи (вентилі)

### Що таке вентиль

> **Означення (логічний елемент).** **Логічний елемент** (**вентиль**, англ. *gate*) —
> це фізичний пристрій, сьогодні транзисторна схема всередині інтегральної мікросхеми,
> що обчислює одну булеву операцію над своїми вхідними напругами, тлумачачи «високий»
> рівень як $1$, а «низький» — як $0$.

Вентилі — це атоми цифрової апаратури, а абстрактна алгебра [Лекції 3](ODM-L03.md) є
рівно математикою того, що ці пристрої обчислюють. Кожному вентилю відповідає стандартне
**умовне графічне позначення** (УГП) та таблиця істинності.

![Умовні позначення основних вентилів: НЕ, І, АБО, ТА-НІ, АБО-НІ, XOR](img/l04_gates.png)

Форма позначення кодує операцію: пряма спинка й округлений «ніс» — це **І** (AND);
опукла спинка й гострий ніс — **АБО** (OR); трикутник — повторювач/**НЕ** (NOT).
**Кружечок** (bubble) на виході завжди означає заперечення — саме тому ТА-НІ (NAND)
малюють як І з кружечком, а АБО-НІ (NOR) — як АБО з кружечком. XOR — це АБО з
додатковою дугою на спинці.

![Таблиці істинності основних вентилів](img/l04_truth_gates.png)

Зведемо всі шість елементів у таблицю. Тут $A,B$ — входи; наведено булеву функцію,
характерну форму позначення та приклад однокорпусної мікросхеми (за слайдами курсу).

| Вентиль | UA | Функція | Форма УГП | Приклад мікросхеми |
|---|---|---|---|---|
| **AND** | І | $A\wedge B$ | пряма спинка, округлий ніс | SN74LVC1G08 |
| **OR** | АБО | $A\vee B$ | опукла спинка, гострий ніс | SN74LVC1G32 |
| **NOT** | НЕ | $\overline{A}$ | трикутник + кружечок | 7404 (шість інверторів) |
| **NAND** | ТА-НІ | $\overline{A\wedge B}$ | І + кружечок | SN74AHC1G00 |
| **NOR** | АБО-НІ | $\overline{A\vee B}$ | АБО + кружечок | SN74AHC1G02 |
| **XOR** | «виключне АБО» | $A\oplus B$ | АБО + дуга на спинці | SN74LVC1G86 |

Таблиці істинності двовходових елементів (і одновходового НЕ):

| $A$ | $B$ | $A\wedge B$ | $A\vee B$ | $\overline{A\wedge B}$ | $\overline{A\vee B}$ | $A\oplus B$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |

**Виключне «або»** $A\oplus B$ дорівнює $1$ саме тоді, коли входи *різні*; звідси його
роль у контролі парності. Наприклад, мікросхема **CY54FCT480T** — це подвійний
8-бітовий генератор/контролер парності: усередині вона є деревом елементів XOR, бо
парність вектора бітів дорівнює XOR усіх його бітів (XOR асоціативний, тож дерево
визначене коректно).

### Складні схеми та багатовходові елементи

Вентилі І, АБО, ТА-НІ, АБО-НІ бувають і на **більше ніж два входи**: тривходовий
елемент І обчислює $A\wedge B\wedge C$, $n$-входовий АБО — диз'юнкцію $n$ входів тощо.
Ціла булева функція реалізується мережею таких вентилів, з'єднаних провідниками; вихід
однієї мережі стає входом іншої. Так з кількох простих елементів складають суматори,
дешифратори, мультиплексори та згадані контролери парності.

Читають мережу зсередини назовні. Наприклад, у ланцюжку «елемент І над $A,C$, потім
елемент АБО над його виходом і сигналом $\overline{B}$» проміжний вузол несе $AC$, а
вихід — $\overline{B}\vee AC$; сáме таку мережу ми будуємо в §4.6. Кожен фізичний вузол
відповідає одному підвиразу формули — тому *коротша формула — менша схема*.

### Штрих Шефера та стрілка Пірса

Два з наведених елементів мають власні імена й особливий статус (див. нижче).

> **Означення (штрих Шефера).** **Штрих Шефера** (операція ТА-НІ, NAND) позначають
> $A\mid B$ або $A\uparrow B$ і означують як
> $$ A\uparrow B \;=\; \overline{A\wedge B}. $$

> **Означення (стрілка Пірса).** **Стрілку Пірса** (операцію АБО-НІ, NOR) позначають
> $A\downarrow B$ і означують як
> $$ A\downarrow B \;=\; \overline{A\vee B}. $$

Кожна з цих операцій сама по собі дає змогу виразити всі інші. Це — теоретичне
обґрунтування того, що цілі мікросхеми будують з одного типу вентиля.

> **Твердження 4.1 (штрих Шефера є функціонально повним).** Операція $\uparrow$ сама
> по собі виражає заперечення, кон'юнкцію та диз'юнкцію:
> $$ \overline{A}=A\uparrow A,\qquad A\wedge B=(A\uparrow B)\uparrow(A\uparrow B),
> \qquad A\vee B=(A\uparrow A)\uparrow(B\uparrow B). $$
>
> *Доведення.* Перевіримо кожну тотожність, спираючись на означення $\uparrow$ і
> тотожності [Лекції 3](ODM-L03.md).
> — $A\uparrow A=\overline{A\wedge A}=\overline{A}$ (ідемпотентність $A\wedge A=A$).
> — $(A\uparrow B)\uparrow(A\uparrow B)=\overline{(A\uparrow B)\wedge(A\uparrow B)}
>   =\overline{A\uparrow B}=\overline{\overline{A\wedge B}}=A\wedge B$ (подвійне
>   заперечення).
> — $(A\uparrow A)\uparrow(B\uparrow B)=\overline{A}\uparrow\overline{B}
>   =\overline{\overline{A}\wedge\overline{B}}=A\vee B$ (закон де Моргана).
> Оскільки набір $\{\wedge,\vee,\overline{\ \cdot\ }\}$ функціонально повний (кожну
> булеву функцію можна ним записати — див. Лекцію 3), а тепер кожну з цих трьох
> операцій виражено через $\uparrow$, то й один $\uparrow$ функціонально повний.
> $\blacksquare$

> **Наслідок 4.2 (стрілка Пірса є функціонально повною).** Двоїсто до Твердження 4.1:
> $$ \overline{A}=A\downarrow A,\qquad A\vee B=(A\downarrow B)\downarrow(A\downarrow B),
> \qquad A\wedge B=(A\downarrow A)\downarrow(B\downarrow B). $$
> Доведення дослівно повторює попереднє із заміною $\wedge\leftrightarrow\vee$ і
> застосуванням другого закону де Моргана. $\blacksquare$

> **Типова помилка (неасоціативність).** Ані $\uparrow$, ані $\downarrow$ не
> асоціативні. Наприклад, $(1\uparrow 0)\uparrow 0=1\uparrow 0=1$, тоді як
> $1\uparrow(0\uparrow 0)=1\uparrow 1=0$. Тому запис $A\uparrow B\uparrow C$
> **неоднозначний**; завжди ставте дужки й не плутайте $A\uparrow B\uparrow C$ із
> $\overline{ABC}$ (тривходовий елемент ТА-НІ — це інший вентиль).

### Транзисторна реалізація (оглядово)

Сучасні вентилі будують за технологією **КМОН** (комплементарний метал-оксид-
напівпровідник, англ. CMOS) із двох типів польових транзисторів. **n-канальний**
транзистор провідний, коли на його затворі $1$ (працює як замкнений ключ), і
розімкнений при $0$; **p-канальний** — навпаки (провідний при $0$; на позначенні його
затвор має кружечок). Транзистори з'єднують так, щоб вихід підтягувався до живлення
$+U$ (лог. $1$) або до землі (лог. $0$), але ніколи водночас.

Найпростіший елемент — **інвертор** (НЕ): один p-канальний транзистор між $+U$ і
виходом та один n-канальний між виходом і землею; входом керуються обидва затвори.

![КМОН-реалізація елемента НЕ (інвертор): p-канальний та n-канальний транзистори](img/l04_cmos.png)

Коли $A=0$, верхній (p) транзистор відкритий, нижній (n) закритий — вихід приєднано до
$+U$, тобто $F=1$. Коли $A=1$ — навпаки, $F=0$. Отже, $F=\overline{A}$. Складніші
вентилі будують за тим самим принципом: у **ТА-НІ** два n-транзистори з'єднують
*послідовно* (обидва входи мають бути $1$, щоб «просадити» вихід до нуля), а два
p-транзистори — *паралельно*. Саме тому в КМОН елементи ТА-НІ та АБО-НІ **дешевші** за
І та АБО (останні є ТА-НІ/АБО-НІ з додатковим інвертором): це практична причина, чому
$\uparrow$ і $\downarrow$ вважають «природними» вентилями (§4.6).

---

## 4.2 Мінімізація булевих виразів законами алгебри

**Алгебрична мінімізація** застосовує тотожності [Лекції 3](ODM-L03.md), щоб зменшити
формулу, зберігши її таблицю істинності. Робочі закони:

| Закон | Формулювання |
|---|---|
| Ідемпотентність | $A\vee A=A,\qquad A\wedge A=A$ |
| Доповнення | $A\vee\overline{A}=1,\qquad A\wedge\overline{A}=0$ |
| Поглинання | $A\vee AB=A,\qquad A(A\vee B)=A$ |
| Поглинання (2-га форма) | $\overline{A}\vee AB=\overline{A}\vee B$ |
| Склеювання | $AB\vee A\overline{B}=A$; і «розщеплення» $P=P\wedge(A\vee\overline{A})$ |
| Закони де Моргана | $\overline{A\vee B}=\overline{A}\,\overline{B},\qquad \overline{A\wedge B}=\overline{A}\vee\overline{B}$ |

**Закон склеювання** $AB\vee A\overline{B}=A$ — алгебричне серце всіх методів цієї
лекції: два добутки, що збігаються всюди, крім однієї змінної, у якій різняться,
зливаються в один коротший. Карти Карно (§4.5) — це лише впорядкований, вичерпний спосіб
знайти всі законні застосування цього одного закону.

### Швидкий приклад (склеювання й поглинання)

$$
XY\vee X\overline{Y}\vee \overline{X}Y \;=\; X(Y\vee\overline{Y})\vee\overline{X}Y \;=\;
X\vee\overline{X}Y \;=\; X\vee Y.
$$

Спершу склеїли $XY$ з $X\overline{Y}$ у $X$, потім застосували другу форму поглинання
$X\vee\overline{X}Y=X\vee Y$. Три добутки згорнулися в одну диз'юнкцію.

**Приклад із «зайвим» доданком (консенсус).** У виразі
$XY\vee\overline{X}Z\vee YZ$ третій доданок $YZ$ — *консенсус* перших двох (утворений
викреслюванням протилежної змінної $X$) — надлишковий:
$$
YZ=YZ(X\vee\overline{X})=XYZ\vee\overline{X}YZ,\qquad XYZ\le XY,\ \ \overline{X}YZ\le\overline{X}Z,
$$
тож $YZ\le XY\vee\overline{X}Z$ і $XY\vee\overline{X}Z\vee YZ=XY\vee\overline{X}Z$.
Уміння впізнавати надлишковий консенсус — це рівно те, що на карті Карно означає «не
додавай групу, без якої можна обійтися».

### Розгорнутий приклад

Спростимо вираз зі слайда лекції:

$$
F=\overline{(x\vee\overline{y})}\ \vee\ \bigl((\overline{y}\vee\overline{z})\vee \overline{x}\,z\bigr).
$$

Тут $\overline{x}\,z$ означає $\overline{x}\wedge z$. Ведемо перетворення покроково, на
кожному кроці посилаючись на закон.

| Крок | Вираз | Обґрунтування |
|:-:|---|---|
| 1 | $\overline{(x\vee\overline{y})}\vee\bigl((\overline{y}\vee\overline{z})\vee\overline{x}z\bigr)$ | вихідний вираз |
| 2 | $(\overline{x}\wedge\overline{\overline{y}})\vee(\overline{y}\vee\overline{z}\vee\overline{x}z)$ | закон де Моргана до першого доданка; знято внутрішні дужки |
| 3 | $\overline{x}y\vee\overline{y}\vee\overline{z}\vee\overline{x}z$ | подвійне заперечення $\overline{\overline{y}}=y$ |
| 4 | $\overline{x}y\vee\overline{x}z\vee\overline{y}(x\vee\overline{x})\vee\overline{z}(x\vee\overline{x})$ | переставлено доданки; помножено $\overline{y},\overline{z}$ на $(x\vee\overline{x})=1$ |
| 5 | $\overline{x}y\vee\overline{x}z\vee x\overline{y}\vee\overline{x}\,\overline{y}\vee x\overline{z}\vee\overline{x}\,\overline{z}$ | розкрито дужки (дистрибутивність) |
| 6 | $\overline{x}(y\vee\overline{y})\vee\overline{x}(z\vee\overline{z})\vee x\overline{y}\vee x\overline{z}$ | згруповано $\overline{x}y$ з $\overline{x}\,\overline{y}$ і $\overline{x}z$ з $\overline{x}\,\overline{z}$ |
| 7 | $\overline{x}\vee\overline{x}\vee x\overline{y}\vee x\overline{z}$ | закон доповнення $y\vee\overline{y}=1$, $z\vee\overline{z}=1$ |
| 8 | $\overline{x}\vee x(\overline{y}\vee\overline{z})$ | ідемпотентність $\overline{x}\vee\overline{x}=\overline{x}$; винесено $x$ за дужки |
| 9 | $\overline{x}\vee(\overline{y}\vee\overline{z})$ | поглинання (2-га форма) $\overline{x}\vee xW=\overline{x}\vee W$, де $W=\overline{y}\vee\overline{z}$ |
| 10 | $\overline{x}\vee\overline{y}\vee\overline{z}$ | знято дужки |

Отже,
$$
F=\overline{x}\vee\overline{y}\vee\overline{z}=\overline{xyz}.
$$

> **Зауваження (довший шлях зі слайда).** Оригінальний слайд доходить до тієї самої
> відповіді з кроку 8 ланцюжком перетворень де Моргана, без явного поглинання:
> $$
> \overline{x}\vee x(\overline{y}\vee\overline{z})
> =\overline{\,x\wedge\overline{x(\overline{y}\vee\overline{z})}\,}
> =\overline{\,x\wedge(\overline{x}\vee\overline{\overline{y}\vee\overline{z}})\,}
> =\overline{\,x\wedge(\overline{x}\vee yz)\,}
> =\overline{\,x\overline{x}\vee xyz\,}
> =\overline{xyz}
> =\overline{x}\vee\overline{y}\vee\overline{z}.
> $$
> Він правильний, але довший; упізнавання закону поглинання (крок 9 вище) згортає шість
> рядків в один. Саме тому нам потрібні *систематичні* методи: алгебрична вправність у
> різних людей різна, і немає гарантії, що ви побачили найкоротший шлях.

**Перевірка таблицею істинності.** Побудова обох частин по стовпцях підтверджує
рівність (вони відрізняються від $1$ лише там, де всі змінні дорівнюють $1$):

| $x$ | $y$ | $z$ | $\overline{(x\vee\overline{y})}$ | $\overline{y}\vee\overline{z}$ | $\overline{x}z$ | $F$ (вихідний) | $\overline{xyz}$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |

Алгебрична мінімізація діє завжди, проте не дає ані гарантії досягнення найменшої
форми, ані правила зупинки — ніколи не певен, що вже завершив. Це мотивує систематичні
методи, які *справді* знаходять найменшу дворівневу форму.

---

## 4.3 Канонічні форми: ДДНФ і ДКНФ

Мінімізації потрібна чітко визначена відправна точка. Її дають **канонічні нормальні
форми** — стандартні вирази, побудовані прямо з таблиці істинності, по одному для кожної
функції, *єдині*. Спершу — словник.

> **Означення (літерал).** **Літерал** — це змінна або її заперечення ($x$ або
> $\overline{x}$).

> **Означення (мінтерм, макстерм).** Для набору значень $a=(a_1,\dots,a_n)\in\{0,1\}^n$:
> **мінтерм** (**конституента одиниці**) — це кон'юнкція $n$ літералів, по одному на
> кожну змінну,
> $$ m_a=\bigwedge_{i=1}^{n} x_i^{a_i},\qquad x_i^{1}=x_i,\ \ x_i^{0}=\overline{x_i}; $$
> **макстерм** (**конституента нуля**) — це диз'юнкція $n$ літералів,
> $$ M_a=\bigvee_{i=1}^{n} x_i^{\,1-a_i} $$
> (змінна входить *із запереченням* там, де $a_i=1$, і *без* — де $a_i=0$: дзеркально
> до правила для мінтерма).

Уся теорія спирається на одну лему: кожен мінтерм «вмикається» рівно на одному рядку, а
кожен макстерм «вимикається» рівно на одному рядку.

> **Твердження 4.3 (індикаторна властивість).** Для всіх $a,b\in\{0,1\}^n$:
> $$ m_a(b)=1\iff b=a,\qquad M_a(b)=0\iff b=a. $$
>
> *Доведення.* Обчислимо літерал $x_i^{a_i}$ на наборі $b$: якщо $a_i=1$, він дорівнює
> $b_i$; якщо $a_i=0$, він дорівнює $\overline{b_i}$. В обох випадках літерал дорівнює
> $1$ **тоді й лише тоді**, коли $b_i=a_i$. Мінтерм $m_a(b)$ — це кон'юнкція всіх $n$
> літералів, тож він дорівнює $1$ саме тоді, коли *кожен* літерал дорівнює $1$, тобто
> коли $b_i=a_i$ для всіх $i$, тобто $b=a$.
> Двоїсто, у $M_a$ літерал $x_i^{\,1-a_i}$ на наборі $b$ дорівнює $0$ саме тоді, коли
> $b_i=a_i$; макстерм — це диз'юнкція цих літералів, отже $M_a(b)=0$ саме тоді, коли
> *усі* літерали дорівнюють $0$, тобто знову $b=a$. $\blacksquare$

### Досконала диз'юнктивна нормальна форма (ДДНФ)

> **Означення (ДДНФ).** **Досконала диз'юнктивна нормальна форма** функції $F$ — це
> диз'юнкція мінтермів усіх тих рядків, де $F=1$.

> **Теорема 4.4 (існування та єдиність ДДНФ).** Кожна булева функція $f\not\equiv 0$
> дорівнює диз'юнкції мінтермів своїх одиничних рядків,
> $$ f=\bigvee_{a:\,f(a)=1} m_a, $$
> і це — єдиний спосіб записати $f$ як диз'юнкцію різних мінтермів.
>
> *Доведення.* **Існування.** Нехай $g=\bigvee_{a:\,f(a)=1} m_a$ (непорожня диз'юнкція,
> бо $f\not\equiv 0$). Для довільного набору $b$ за Твердженням 4.3 доданок $m_b$
> дорівнює $1$ саме тоді, коли $f(b)=1$, а всі інші мінтерми дорівнюють $0$ на $b$.
> Отже, $g(b)=1\iff f(b)=1$, тобто $g=f$.
> **Єдиність.** Нехай $f=\bigvee_{a\in S}m_a$ для якоїсь множини наборів $S$. Обчислимо
> на довільному $b$: за Твердженням 4.3 єдиний доданок, що може бути ненульовим на $b$,
> — це $m_b$, і він присутній саме тоді, коли $b\in S$. Тому $f(b)=1\iff b\in S$, звідки
> $S=\{b:f(b)=1\}$ визначено однозначно. $\blacksquare$

### Досконала кон'юнктивна нормальна форма (ДКНФ)

> **Означення (ДКНФ).** **Досконала кон'юнктивна нормальна форма** функції $F$ — це
> кон'юнкція макстермів усіх тих рядків, де $F=0$.

> **Теорема 4.5 (існування та єдиність ДКНФ).** Кожна булева функція $f\not\equiv 1$
> дорівнює
> $$ f=\bigwedge_{a:\,f(a)=0} M_a, $$
> і це — єдиний її запис як кон'юнкції різних макстермів.
>
> *Доведення.* За Твердженням 4.3 $M_a(b)=0$ саме тоді, коли $b=a$. Отже, добуток
> $h=\bigwedge_{a:\,f(a)=0}M_a$ дорівнює $0$ на $b$ саме тоді, коли серед множників є
> $M_b$ із $f(b)=0$, тобто коли $f(b)=0$; значить $h=f$. Єдиність доводять як у Теоремі
> 4.4: обчислення на $b$ показує, що множник $M_b$ присутній тоді й лише тоді, коли
> $f(b)=0$, тож множина макстермів визначена однозначно. $\blacksquare$

### Приклад: $F(A,B,C)$ зі слайда

Розгляньмо функцію трьох змінних, задану таблицею істинності:

| $A$ | $B$ | $C$ | $F$ | № рядка |
|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 2 |
| 0 | 1 | 1 | 0 | 3 |
| 1 | 0 | 0 | 1 | 4 |
| 1 | 0 | 1 | 1 | 5 |
| 1 | 1 | 0 | 0 | 6 |
| 1 | 1 | 1 | 1 | 7 |

**Будуємо ДДНФ.** Одиничні рядки — це $0,1,4,5,7$. Для кожного випишемо мінтерм
(змінна без риски, якщо в рядку вона $1$, і з рискою, якщо $0$):

![Таблиця істинності F(A,B,C): виділено рядки, де F=1 (мінтерми для ДДНФ)](img/l04_ddnf.png)

$$
F=\overline{A}\,\overline{B}\,\overline{C}\ \vee\ \overline{A}\,\overline{B}C\ \vee\
A\overline{B}\,\overline{C}\ \vee\ A\overline{B}C\ \vee\ ABC.
$$

Позначаючи мінтерм десятковим номером його рядка, коротко пишуть
$F=\textstyle\bigvee m(0,1,4,5,7)$.

**Будуємо ДКНФ.** Нульові рядки — це $2,3,6$. Для кожного випишемо макстерм (змінна з
рискою, якщо в рядку вона $1$, і без — якщо $0$):

![Таблиця істинності F(A,B,C): виділено рядки, де F=0 (макстерми для ДКНФ)](img/l04_dknf.png)

$$
F=(A\vee\overline{B}\vee C)\,(A\vee\overline{B}\vee\overline{C})\,(\overline{A}\vee\overline{B}\vee C)
=\textstyle\bigwedge M(2,3,6).
$$

> **Зауваження (яка форма коротша).** Рядки поділяються начисто: ДДНФ використовує
> одиничні рядки, ДКНФ — нульові, а разом їх $2^n$. Тому
> $\#(\text{мінтермів})+\#(\text{макстермів})=2^{n}$. Функція, що переважно дорівнює
> $1$, має довгу ДДНФ і коротку ДКНФ, і навпаки — розкладайте навколо того значення, яке
> трапляється рідше. Для нашого $F$: $5$ мінтермів проти $3$ макстермів, тож ДКНФ
> компактніша.

> **Типова помилка (полярність літералів протилежна).** У мінтермі (одиничний рядок)
> змінна, що дорівнює $1$, входить **без** риски; у макстермі (нульовий рядок) змінна,
> що дорівнює $1$, входить **із** рискою. Переплутати ці полярності — найпоширеніша
> похибка; за сумніву перевиведіть правило з Твердження 4.3, а не завчайте.

> **Зауваження (поліном Жегалкіна).** Існує й третя канонічна форма — **алгебрична
> нормальна форма** (поліном Жегалкіна), що використовує XOR замість диз'юнкції. Кожна
> функція єдиним чином подається як
> $$ f=c_0\oplus c_1x_1\oplus\cdots\oplus c_nx_n\oplus c_{12}x_1x_2\oplus\cdots\oplus c_{1\ldots n}x_1\cdots x_n,\qquad c_i\in\{0,1\}. $$
> До неї переходять заміною $\overline{a}=a\oplus 1$ та $a\vee b=a\oplus b\oplus ab$ з
> подальшим спрощенням ($a\oplus a=0$, $aa=a$). Ця форма природна для задач парності та
> контрольних сум (згадана мікросхема CY54FCT480T).

---

## 4.4 Мінімальні форми (МДНФ, МКНФ)

Канонічні форми єдині, але зазвичай далекі від найкоротших. Тому вводять мінімальні
форми та відповідний словник.

> **Означення (ДНФ, КНФ).** **Диз'юнктивна нормальна форма** (ДНФ) — це диз'юнкція
> елементарних кон'юнкцій (добутків літералів), як-от $\overline{B}\vee AC$.
> **Кон'юнктивна нормальна форма** (КНФ) — кон'юнкція елементарних диз'юнкцій (сум
> літералів). ДДНФ і ДКНФ — це часткові випадки, у яких кожен доданок містить *усі*
> змінні.

> **Означення (імпліканта, проста імпліканта).** Добуток літералів $p$ називають
> **імплікантою** функції $f$, якщо $p\le f$ (тобто з $p=1$ випливає $f=1$). Імпліканту
> називають **простою**, якщо з неї не можна викреслити жодного літерала, зберігши
> властивість імпліканти. **Суттєвою** називають просту імпліканту, що покриває хоча б
> один одиничний набір, не покритий жодною іншою простою імплікантою.

> **Означення (МДНФ, МКНФ).** **Мінімальна диз'юнктивна нормальна форма** (МДНФ) — це
> ДНФ функції з найменшою можливою сумарною «вартістю» (найменше число доданків, а за
> рівності — літералів). Аналогічно **мінімальна кон'юнктивна нормальна форма** (МКНФ) —
> найдешевша КНФ.

Мінімальна ДНФ — це найменший набір простих імплікант, що покриває всі одиниці; він
обов'язково містить кожну суттєву просту імпліканту, а решту одиниць покриває
найдешевше. Систематичний спосіб усе це знайти для функцій до $4$–$5$ змінних — **карти
Карно**.

---

## 4.5 Карти Карно

> **Означення (карта Карно).** **Карта Карно** — це таблиця істинності, перемальована у
> вигляді ґратки, рядки й стовпці якої підписані в порядку **коду Грея**
> $00,01,11,10$: сусідні підписи (зокрема й «замикання» останнього з першим) різняться
> рівно в одному біті.

![Код Грея (2 біти) і порожній шаблон карти на 4 змінні](img/l04_gray.png)

Саме таке підписування — весь сенс карти.

> **Твердження 4.6 (сусідство $=$ зміна однієї змінної).** За підписів кодом Грея дві
> клітини, що мають спільну сторону — або лежать на протилежних кінцях одного рядка чи
> стовпця («замикання»), — відповідають наборам, що різняться рівно в одній змінній.
>
> *Доведення.* Горизонтальний перехід змінює лише підпис стовпця на один крок коду
> Грея, а це перемикає рівно одну зі «стовпцевих» змінних і лишає незмінними змінні
> рядка (та решту стовпцевих). Вертикальний перехід робить те саме для змінних рядка.
> Код Грея *циклічний* — для двох бітів $10\to 00$ теж різняться в одному біті, — тому
> перший і останній рядки (стовпці) також сусідні, що обґрунтовує «замикання».
> $\blacksquare$

За законом склеювання дві сусідні одиничні клітини, що різняться змінною $v$,
зливаються: $(\text{решта})\,v\ \vee\ (\text{решта})\,\overline{v}=(\text{решта})$.
Повторюючи, блок із $2^k$ клітин, що утворює **підкуб** (де $k$ вибраних змінних
пробігають усі комбінації, а решта $n-k$ лишаються сталими), згортається в один добуток
з $n-k$ сталих літералів.

> **Теорема 4.7 (склеювання на карті).** Блок із $2^k$ клітин, що утворює підкуб,
> відповідає добутку $p$ своїх $n-k$ сталих літералів (стала $1$ — змінна без риски,
> стала $0$ — з рискою). Цей $p$ є імплікантою функції $f$ **тоді й лише тоді**, коли всі
> $2^k$ клітин містять $1$.
>
> *Доведення.* За побудовою $p=1$ саме на $2^k$ клітинах підкуба: вільні змінні
> необмежені, а сталі літерали фіксують решту. Тоді $p\le f$ означає, що $f=1$ у кожній
> точці, де $p=1$, тобто що всі ці клітини містять $1$. Розмір блоку — степінь двійки,
> бо $k$ бінарних змінних дають $2^k$ комбінацій. $\blacksquare$

Отже, *групування одиниць у найбільші законні підкуби* прямо дає короткі добутки. Форми
шаблонів (порожні клітини):

Дві змінні — рядки $x$, стовпці $y$:

| $x\backslash y$ | 0 | 1 |
|:-:|:-:|:-:|
| **0** |  |  |
| **1** |  |  |

Три змінні — рядки $x$, стовпці $yz$ у коді Грея:

| $x\backslash yz$ | 00 | 01 | 11 | 10 |
|:-:|:-:|:-:|:-:|:-:|
| **0** |  |  |  |  |
| **1** |  |  |  |  |

Чотири змінні — рядки $xy$, стовпці $zt$, обидві осі в коді Грея:

| $xy\backslash zt$ | 00 | 01 | 11 | 10 |
|:-:|:-:|:-:|:-:|:-:|
| **00** |  |  |  |  |
| **01** |  |  |  |  |
| **11** |  |  |  |  |
| **10** |  |  |  |  |

> **Типова помилка.** Не підписуйте осі $00,01,10,11$ (звичайний двійковий порядок). Між
> $01$ і $10$ змінюються *два* біти, тож такі «сусіди» не є логічно сусідніми і закон
> склеювання не діє. Порядок Грея $00,01,11,10$ обов'язковий. Так само групи мають бути
> прямокутниками розміру степеня двійки ($1,2,4,8,\dots$); «кутик» чи група з трьох
> клітин недопустимі.

### Приклад 1 — МДНФ трьох змінних

Візьмемо $F(A,B,C)=\bigvee m(0,1,4,5,7)$ із §4.3. Рядки — $A$, стовпці — $BC$:

![Карта Карно 3 змінних для F(A,B,C): групи ¬B та AC дають МДНФ ¬B∨AC](img/l04_kmap3.png)

- Ліва половина (стовпці $BC=00,01$, обидва рядки) — чотири сусідні одиниці, у яких
  сталою є лише $B=0$, тобто $\overline{B}$. Ця проста імпліканта **суттєва** (тільки
  вона покриває клітини при $BC=00$).
- Дві одиниці при $(A{=}1,\ BC{=}01)$ і $(A{=}1,\ BC{=}11)$ мають спільні $A=1,\ C=1$,
  тобто $AC$. Суттєва, бо клітину при $BC=11$ (мінтерм $7$) не покриває жодна інша група.

Разом вони покривають усі одиниці (клітину при $A{=}1, BC{=}01$ поділено, що дозволено),
даючи **МДНФ**
$$
F=\overline{B}\vee AC.
$$
Це різко коротше за п'ятимінтермну ДДНФ (яку ми виписали в §4.3).

### Приклад 2 — замикання країв

Нехай $G(A,B,C)=\bigvee m(0,2,4,6)$ (усі парні рядки). Рядки — $A$, стовпці — $BC$:

| $A\backslash BC$ | 00 | 01 | 11 | 10 |
|:-:|:-:|:-:|:-:|:-:|
| **0** | 1 | 0 | 0 | 1 |
| **1** | 1 | 0 | 0 | 1 |

Чотири одиниці стоять у стовпцях $BC=00$ і $BC=10$ — **першому й останньому**, які
сусідні через замикання. Усі вони мають спільне $C=0$, тож утворюють одну законну групу
розміру $4$:
$$
G=\overline{C}.
$$
Без замикання довелося б хибно розбити її на дві групи розміру $2$
($\overline{A}\,\overline{C}$ і $A\overline{C}$), а потім склеювати їх алгебрично.
Замикання дає змогу карті одразу знайти найбільшу групу.

### Приклад 3 — МДНФ і МКНФ чотирьох змінних (зі слайда)

Розгляньмо функцію $F(x,y,z,t)$, задану вісьмома мінтермами (запис зі слайда):

$$
xyz\overline{t}\vee x\overline{y}zt\vee\overline{x}yzt\vee\overline{x}\,\overline{y}zt\vee
x\overline{y}\,\overline{z}t\vee\overline{x}\,\overline{y}\,\overline{z}t\vee
x\overline{y}\,\overline{z}\,\overline{t}\vee\overline{x}\,\overline{y}\,\overline{z}\,\overline{t}.
$$

Нанесемо кожен мінтерм на карту (рядки $xy$, стовпці $zt$):

| $xy\backslash zt$ | 00 | 01 | 11 | 10 |
|:-:|:-:|:-:|:-:|:-:|
| **00** | 1 | 1 | 1 | 0 |
| **01** | 0 | 0 | 1 | 0 |
| **11** | 0 | 0 | 0 | 1 |
| **10** | 1 | 1 | 1 | 0 |

**МДНФ (групуємо одиниці).**

![Карта Карно 4 змінних: покриття одиниць чотирма групами дає МДНФ](img/l04_kmap4_mdnf.png)

- Рядки $xy=00$ і $xy=10$ (сусідні через замикання, обидва мають $y=0$) $\times$ стовпці
  $zt=00,01$ ($z=0$): блок $2\times2$ $\Rightarrow \overline{y}\,\overline{z}$.
- Ті самі два рядки ($y=0$) $\times$ стовпці $zt=01,11$ ($t=1$): блок $2\times2$
  $\Rightarrow \overline{y}t$.
- Стовпець $zt=11$, рядки $xy=00,01$ ($x=0$): вертикальна пара
  $\Rightarrow \overline{x}zt$ (суттєва — лише вона покриває клітину $(01,11)$).
- Ізольована клітина $xy=11,\ zt=10$ не розширюється (усі сусіди — нулі), тож лишається
  повним мінтермом $\Rightarrow xyz\overline{t}$ (суттєва).

$$
F_{\text{МДНФ}}=\overline{y}\,\overline{z}\ \vee\ \overline{y}t\ \vee\ \overline{x}zt\ \vee\ xyz\overline{t}.
$$

**МКНФ (групуємо нулі).** Щоб отримати мінімальну КНФ, групуємо **нулі** й читаємо
кожен блок як макстерм: змінні, сталі на блоці, беремо з рискою там, де змінна $=1$, і
без — де $=0$ (Теорема 4.7 із протилежною полярністю, бо група нулів — це проста
імпліканта функції $\overline{F}$).

![Карта Карно 4 змінних: покриття нулів чотирма групами дає МКНФ](img/l04_kmap4_mknf.png)

- Рядки $xy=01,11$ ($y=1$) $\times$ стовпці $zt=00,01$ ($z=0$): блок $2\times2$
  $\Rightarrow (\overline{y}\vee z)$.
- Рядок $xy=11$ ($x=1,y=1$) $\times$ стовпці $zt=01,11$ ($t=1$): пара
  $\Rightarrow (\overline{x}\vee\overline{y}\vee\overline{t})$.
- Стовпець $zt=10$ ($z=1,t=0$), рядки $xy=00,01$ ($x=0$): пара
  $\Rightarrow (x\vee\overline{z}\vee t)$.
- Стовпець $zt=10$ ($z=1,t=0$), рядки $xy=00,10$ ($y=0$, через замикання): пара
  $\Rightarrow (y\vee\overline{z}\vee t)$.

$$
F_{\text{МКНФ}}=(\overline{y}\vee z)\,(\overline{x}\vee\overline{y}\vee\overline{t})\,(x\vee\overline{z}\vee t)\,(y\vee\overline{z}\vee t).
$$

Обидва записи описують ту саму функцію; форма ДНФ дешевша, коли одиниці збиваються в
купки, а КНФ — коли купкуються нулі.

### Невизначені стани (don't-care)

Часто деякі комбінації входів *не можуть трапитися* або їхній вихід байдужий. Такі рядки
називають **невизначеними** (don't-care) і позначають $\times$. Невизначену клітину можна
трактувати як $1$ **або** як $0$ — незалежно для кожної групи, як вигідніше, щоб групи
були більшими. Покрити треба всі *справжні* одиниці, але жодну $\times$ покривати не
зобов'язані.

**Приклад 4 — двійково-десятковий код.** Входи $A,B,C,D$ кодують десяткову цифру
$8A+4B+2C+D$; комбінації $10$–$15$ у такому коді неможливі, тож вони невизначені.
Нехай $F=1$ саме тоді, коли цифра $\ge 5$, тобто на мінтермах $\{5,6,7,8,9\}$ з
$\times$ на $\{10,\dots,15\}$. Рядки — $AB$, стовпці — $CD$:

| $AB\backslash CD$ | 00 | 01 | 11 | 10 |
|:-:|:-:|:-:|:-:|:-:|
| **00** | 0 | 0 | 0 | 0 |
| **01** | 0 | 1 | 1 | 1 |
| **11** | $\times$ | $\times$ | $\times$ | $\times$ |
| **10** | 1 | 1 | $\times$ | $\times$ |

Використовуючи $\times$ як $1$ там, де це допомагає:

- уся нижня половина $A=1$ (рядки $11,10$) може бути одиничною (справжні $1$ на $8,9$,
  решта — $\times$): група з $8$ клітин $\Rightarrow A$;
- рядки $01,11$ ($B=1$) $\times$ стовпці $01,11$ ($D=1$): $2\times2 \Rightarrow BD$;
- рядки $01,11$ ($B=1$) $\times$ стовпці $11,10$ ($C=1$): $2\times2 \Rightarrow BC$.

$$
F_{\text{МДНФ}}=A\vee BC\vee BD\qquad(3\text{ доданки},\ 5\text{ літералів}).
$$

Якби ми змусили кожну невизначеність дорівнювати $0$, та сама функція звелася б до
$\overline{A}BC\vee\overline{A}BD\vee A\overline{B}\,\overline{C}$ (3 доданки, аж
9 літералів) — помітно дорожче. Використання невизначеностей — один із найбільших
практичних виграшів у синтезі логіки.

> **Історична довідка.** Алгебру логіки створив **Джордж Буль** («Математичний аналіз
> логіки», 1847). Її застосування до схем належить **Клоду Шеннону**, чия магістерська
> праця 1937 р. показала, що булева алгебра точно описує — і спрощує — мережі реле та
> перемикачів; це заснувало цифрову техніку. Що одного зв'язкового досить, зауважив
> близько 1880 р. **Чарлз Пірс** (стрілка $\downarrow$), а **Генрі Шеффер** довів це
> друком 1913 р. для штриха $\uparrow$. Карту, якою ми користуємося, запропонував
> **Едвард Вейч** (1952) і вдосконалив **Моріс Карно** (1953, Bell Labs).

> **Практичні правила карт Карно.**
> - Групи — прямокутники розміру степеня двійки; дозволене замикання через усі чотири
>   краї (і чотири кути).
> - Беріть *найбільші* законні групи (більша група $\Rightarrow$ менше літералів) і
>   *найменше* число груп, що покривають усі цільові клітини.
> - Спершу виявляйте **суттєві** прості імпліканти (одиниця, яку може покрити лише одна
>   група, змушує взяти цю групу), потім найдешевше покривайте решту.
> - Групи можуть перекриватися; кожна одиниця (для ДНФ) чи кожен нуль (для КНФ) має
>   потрапити принаймні в одну групу.
> - Карти читні до $4$–$5$ змінних; далі застосовують табличний метод Квайна—Мак-Класкі.

---

## 4.6 Побудова логічних схем

Формула перекладається у мережу вентилів механічно: кожна операція стає вентилем,
кожна змінна — вхідним провідником, а з'єднання йдуть за вкладеністю виразу.
Заперечені входи створюють інвертори.

### Схема за МДНФ

**Диз'юнктивна** форма (сума добутків) читається зліва направо як **дворівнева** схема:
шар елементів І, чиї виходи подано на один елемент АБО, а інвертори постачають
заперечені літерали. Візьмемо $F=\overline{B}\vee AC$ (МДНФ із §4.5):

- інвертор дає $\overline{B}$ з $B$;
- двовходовий елемент І дає $AC$ з $A,C$;
- двовходовий елемент АБО об'єднує $\overline{B}$ та $AC$ у $F$.

![Логічна схема МДНФ F = ¬B ∨ AC на елементах НЕ, І, АБО](img/l04_circuit_mdnf.png)

Кількість вентилів: $1$ НЕ $+\ 1$ І $+\ 1$ АБО $=\ 3$. Порівняймо з прямою реалізацією
п'ятимінтермної ДДНФ:

| Показник | ДДНФ $\bigvee m(0,1,4,5,7)$ | МДНФ $\overline{B}\vee AC$ |
|---|:-:|:-:|
| Добутків (елементів І) | 5 (тривходові) | 1 (двовходовий) |
| Літералів | 15 | 3 |
| Інверторів (НЕ) | 3 | 1 |
| Елементів АБО | 1 (п'ятивходовий) | 1 (двовходовий) |
| Усього вентилів | 9 | 3 |

Мінімізація скоротила число вентилів утричі без втрати швидкодії (обидві схеми
дворівневі). Помножте таку економію на мільйони примірників стандартної комірки в
сучасному кристалі — і мотивація §§4.2–4.5 стає очевидною: **алгебра і є проєкт**, а
менша алгебра — менший, швидший і холодніший кристал.

### Схема за МКНФ

**Кон'юнктивна** форма (добуток сум) двоїсто читається як шар елементів АБО, що подають
на один елемент І. Для $F$ з §4.5 МКНФ
$(\overline{y}\vee z)(\overline{x}\vee\overline{y}\vee\overline{t})(x\vee\overline{z}\vee t)(y\vee\overline{z}\vee t)$
дає чотири елементи АБО (на $2$–$3$ входи) та один чотиривходовий елемент І, плюс
інвертори для заперечених літералів.

### Переписування у базис ТА-НІ (NAND)

Оскільки $\uparrow$ функціонально повний (Твердження 4.1), будь-яку дворівневу схему
І–АБО можна перемалювати як мережу з самих лише ТА-НІ **тієї самої форми**. Прийом:
на кожен провідник між шаром І та шаром АБО додають два кружечки (подвійне заперечення,
що не змінює значення). Елементи І дістають кружечок на виході й стають ТА-НІ; елемент
АБО дістає кружечки на входах і за законом де Моргана *також* стає ТА-НІ. Коротко:
**І-потім-АБО перетворюється на ТА-НІ-потім-ТА-НІ**.

Для $F=\overline{B}\vee AC$ це дає надзвичайно компактний запис. За законом де Моргана
$$
F=\overline{B}\vee AC=\overline{\,B\wedge\overline{AC}\,}=B\uparrow\overline{AC}=B\uparrow(A\uparrow C),
$$
бо $A\uparrow C=\overline{AC}$. Отже, вистачає **двох** двовходових елементів ТА-НІ (а
$\overline{B}$ окремо породжувати не треба — його «постачає» другий вентиль):

![Та сама функція у базисі ТА-НІ: F = B ↑ (A ↑ C) на двох елементах NAND](img/l04_circuit_nand.png)

### Переписування у базис АБО-НІ (NOR)

Двоїсто, будь-яку схему АБО–І (за МКНФ) переписують у самі лише елементи АБО-НІ:
**АБО-потім-І перетворюється на АБО-НІ-потім-АБО-НІ**. Знайдімо спершу МКНФ нашого
$F=\overline{B}\vee AC$, згрупувавши нулі на його карті (§4.5, приклад 1):
$F=(A\vee\overline{B})(\overline{B}\vee C)$. Тоді за Наслідком 4.2
$$
F=(A\vee\overline{B})\wedge(\overline{B}\vee C)
=\overline{\ \overline{A\vee\overline{B}}\ \vee\ \overline{\overline{B}\vee C}\ }
=(A\downarrow\overline{B})\ \downarrow\ (\overline{B}\downarrow C),
$$
де заперечення $\overline{B}$ у базисі АБО-НІ дає сам вентиль $\overline{B}=B\downarrow B$.
Так функцію реалізовано лише елементами АБО-НІ.

> **Зауваження (чому це зручно).** На платі вже може бути встановлений корпус із
> вентилями ТА-НІ або АБО-НІ, і немає потреби додавати інші типи. До того ж у КМОН
> (§4.1) елементи $\uparrow$ і $\downarrow$ дешевші за І та АБО. Головний висновок:
> *спершу мінімізуйте алгебру*, бо кожен усунутий літерал і кожен усунутий доданок — це
> вентилі, транзистори, площа, затримка й енергія, яких ви ніколи не збудуєте.

---

## Застосування у видавництві та поліграфії

Логічні схеми та їх мінімізація прямо обслуговують завдання фаху:

- **Керування друкарським обладнанням.** Логіка блокувань і послідовностей у
  друкарській машині (папір на місці **І** фарба готова **І** захист знято) — це булеві
  вирази; їх реалізують у програмованих логічних контролерах саме як мінімізовані форми
  сум добутків.
- **Контроль парності при передачі.** Під час передавання растрових даних до
  друкувального пристрою біти захищають контролем парності — деревом елементів XOR
  (згадана мікросхема CY54FCT480T). Це виявляє поодинокі помилки в потоці.
- **Растровий процесор (RIP).** Порогові та логічні операції над бітовими площинами
  кольороподілу (CMYK) — кон'юнкції та диз'юнкції масок; мінімізація зменшує обсяг
  обчислень на піксель.
- **Вбудовані контролери.** У ризографах, принтерах і фальцювальних автоматах менша
  логічна схема означає менше енергоспоживання й нижчу ціну керуючого мікроконтролера.
- **Умовне складання документів.** Правила «показати блок, якщо (є знижка **АБО** статус
  VIP) **І НЕ** чернетка» у системах верстки — булеві функції, які варто спрощувати
  задля читності та швидкості.

---

## Підсумок

- **Логічний елемент (вентиль)** — фізичний пристрій, що обчислює одну булеву операцію;
  основні: І, АБО, НЕ, ТА-НІ, АБО-НІ, XOR. Кружечок на позначенні означає заперечення.
  У КМОН елементи будують з комплементарних n- і p-транзисторів.
- **Штрих Шефера** $A\uparrow B=\overline{A\wedge B}$ та **стрілка Пірса**
  $A\downarrow B=\overline{A\vee B}$ кожен **функціонально повні** (Твердження 4.1,
  Наслідок 4.2): $\overline{A}=A\uparrow A=A\downarrow A$ тощо.
- **Алгебрична мінімізація** застосовує тотожності (склеювання, поглинання, де Морган) —
  потужна, але без правила зупинки.
- **Канонічні форми** читаються з таблиці: **ДДНФ** $=$ сума мінтермів по одиничних
  рядках, **ДКНФ** $=$ добуток макстермів по нульових; обидві **існують і єдині**
  (Теореми 4.4–4.5). Полярності мінтерма й макстерма протилежні.
- **Мінімальні форми** (МДНФ, МКНФ) — найдешевші дворівневі записи; будуються з простих
  імплікант, серед яких обов'язкові — суттєві.
- **Карта Карно** використовує код Грея, щоб сусідство означало зміну однієї змінної
  (Твердження 4.6); групування одиниць у підкуби степеня двійки (Теорема 4.7) дає МДНФ,
  групування нулів — МКНФ. Дозволене замикання країв.
- **Схему** будують за МДНФ (І–АБО) чи МКНФ (АБО–І) і переписують у базис ТА-НІ
  (І–АБО $\to$ ТА-НІ–ТА-НІ) або АБО-НІ (АБО–І $\to$ АБО-НІ–АБО-НІ). Мінімізація економить
  вентилі, транзистори, площу, енергію та затримку.

---

## Вправи

### Для розігріву

1. Побудуйте таблиці істинності елементів ТА-НІ та АБО-НІ й переконайтеся, що
   $A\uparrow B=\overline{A\wedge B}$ і $A\downarrow B=\overline{A\vee B}$.
2. Скориставшись лише елементами ТА-НІ, зберіть: (а) інвертор; (б) двовходовий І.
   Скільки вентилів у кожному випадку?
3. Для набору $(A,B,C)=(1,0,1)$ випишіть: (а) його мінтерм; (б) його макстерм. Зверніть
   увагу на протилежну полярність.
4. Чому стовпці карти Карно підписують $00,01,11,10$, а не $00,01,10,11$? Наведіть пару
   двобітових підписів, які за неправильного порядку стали б «сусідніми» помилково.
5. Спростіть одним законом кожен вираз: (а) $A\vee AB$; (б) $A(A\vee B)$;
   (в) $\overline{A}\vee AB$.

### Стандартні

6. Для $F(A,B,C)=\bigvee m(0,2,5,7)$ запишіть ДДНФ як вираз і ДКНФ як список
   $\bigwedge M(\dots)$.
7. Доведіть, що $A\wedge B=\overline{\overline{A}\vee\overline{B}}$, і поясніть, чому
   звідси випливає функціональна повнота набору $\{\vee,\overline{\ \cdot\ }\}$.
8. Мінімізуйте $F(A,B,C)=\bigvee m(0,1,2,3,4,5)$ картою Карно; подайте результат через
   іменовану операцію двох змінних.
9. Мінімізуйте $F(A,B,C,D)=\bigvee m(1,3,5,7,9,11,13,15)$. (Спершу подивіться на
   таблицю, а тоді рахуйте.)
10. Для МДНФ $F=\overline{B}\vee AC$: намалюйте схему на елементах НЕ, І, АБО, полічіть
    вентилі; тоді перепишіть її у базис ТА-НІ й порівняйте кількість вентилів.
11. Побудуйте ДДНФ і ДКНФ функції $F(A,B,C)=\bigvee m(0,1,4,5,7)$ (наш приклад із §4.3) і
    перевірте, що множини $\{0,1,4,5,7\}$ та $\{2,3,6\}$ разом дають усі рядки
    $\{0,\dots,7\}$.

### Підвищеної складності

12. Доведіть двоїсту до Твердження 4.1 частину — що стрілка Пірса функціонально повна, —
    перевіривши всі три тотожності Наслідку 4.2.
13. Виразіть $A\oplus B$ (виключне «або») лише через елементи АБО-НІ й полічіть вентилі.
    (Підказка: $A\oplus B=A\overline{B}\vee\overline{A}B$; або спершу дістаньте
    $\overline{\ \cdot\ },\wedge,\vee$ зі стрілки Пірса.)
14. Функція чотирьох змінних дорівнює $1$ на наборах $\{2,3,7,9,11,13\}$ і має
    невизначені значення (можна брати як завгодно) на $\{1,10,15\}$, а на решті $0$.
    Мінімізуйте її як ДНФ картою Карно, скориставшись невизначеностями, щоб збільшити
    групи.
15. Доведіть, що $2^n$ мінтермів $n$ змінних утворюють розбиття множини $\{0,1\}^n$
    (кожен набір задовольняє рівно один мінтерм), і виведіть звідси
    $\bigvee_{a} m_a\equiv 1$.
16. Розгляньте функцію, задану на карті чотирьох змінних, у якій одиниці розташовані «в
    шаховому порядку» (немає двох сусідніх одиниць). Скільки груп матиме її МДНФ і чому
    карти Карно тут не дають виграшу? Зв'яжіть відповідь із поняттям простої імпліканти.