# 2. Методичні вказівки

Цей розділ **самодостатній**: він містить усю теорію теми роботи — від логічних
елементів до алгебри Жегалкіна — та опис середовища [logic.ly](https://logic.ly/demo/),
у якому виконують завдання [4task.md](4task.md). Наприкінці наведено **наскрізний
демонстраційний приклад**, що проходить увесь шлях *умова → таблиця → форма →
мінімізація → схема* на даних, які **не збігаються** з жодним варіантом. Зовнішні
джерела не потрібні; ширше поняття подано в
[Лекції 3](../../Lectures/ODM-L03.md) та [Лекції 4](../../Lectures/ODM-L04.md).

## 2.1 Логічні змінні, функції та таблиця істинності

**Логічна (булева) змінна** набуває одного з двох значень: **1** (істина, `True`, `T`,
або **І**) чи **0** (хиба, `False`, `F`, або **Х**). У цій роботі кожен перемикач —
це логічна змінна: увімкнено $=1$, вимкнено $=0$.

> **Означення (булева функція).** **Булева функція** від $n$ змінних — це відображення
> $F\colon \{0,1\}^{n} \to \{0,1\}$, яке кожному наборові значень входів зіставляє один
> вихід $0$ або $1$.

Оскільки кожна з $n$ змінних незалежно набуває $2$ значень, різних вхідних наборів
рівно $2^{n}$. Функцію повністю задає **таблиця істинності** — перелік усіх $2^{n}$
наборів разом зі значенням $F$ на кожному. Для чотирьох перемикачів $A, B, C, D$ таких
рядків $2^{4} = 16$.

> **Зауваження (порядок рядків).** Рядки прийнято впорядковувати за зростанням
> двійкового числа $\overline{ABCD}$: від $0000$ до $1111$. Сталий порядок робить
> побудову форм і карт Карно механічною й убезпечує від пропусків.

Комбінаційна схема, яку ви будуватимете, — це апаратне втілення такої функції: стан
входів однозначно визначає вихід, без пам'яті про попередні стани.

## 2.2 Логічні елементи (вентилі) та їх позначення

**Логічний елемент** (**вентиль**, англ. *gate*) — це пристрій, що обчислює одну
булеву операцію над своїми входами. Нижче — операції, потрібні в роботі, їхні
позначення й таблиці істинності (за [Лекцією 3](../../Lectures/ODM-L03.md)).

| Елемент | UA / англ. | Позначення | Значення |
|---|---|:--:|---|
| Заперечення | НІ (NOT) | $\overline{A}$, $\neg A$ | $\overline{0}=1,\ \overline{1}=0$ |
| Кон'юнкція | ТА (AND) | $A \wedge B$, $AB$ | $1$ лише коли $A=B=1$ |
| Диз'юнкція | АБО (OR) | $A \vee B$, $A+B$ | $0$ лише коли $A=B=0$ |
| Виключне «або» | Викл. АБО (XOR) | $A \oplus B$ | $1$ коли входи **різні** |
| Штрих Шефера | ТА-НІ (NAND) | $A \mid B$ | $\overline{A \wedge B}$ |
| Стрілка Пірса | АБО-НІ (NOR) | $A \downarrow B$ | $\overline{A \vee B}$ |
| Рівнозначність | Викл. АБО-НІ (NXOR) | $A \equiv B$ | $1$ коли входи **однакові** |
| Повторювач | Буфер (Buffer) | $A$ | передає сигнал без змін |

Зведена таблиця істинності двомісних операцій:

| $A$ | $B$ | $A\wedge B$ | $A\vee B$ | $A\oplus B$ | $A\mid B$ | $A\downarrow B$ | $A\equiv B$ |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |

Умовні графічні позначення цих елементів (стандарт ANSI/IEEE, які використовує й
logic.ly) наведено на рисунку. Маленьке **кружальце** на виході означає інверсію: воно
перетворює ТА на ТА-НІ, АБО на АБО-НІ, а буфер на елемент НІ.

![Умовні графічні позначення логічних елементів: буфер, НІ, ТА, АБО, XOR, ТА-НІ, АБО-НІ, NXOR](img/lb1_gates.png)

> **Зауваження (число входів).** Кон'юнкцію та диз'юнкцію означують і для трьох, і для
> більшого числа входів: $A\wedge B\wedge C$ дорівнює $1$ лише коли всі входи $1$, а
> $A\vee B\vee C$ дорівнює $0$ лише коли всі входи $0$. У logic.ly кількість входів
> вентиля задають у його параметрах.

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

З таблиці істинності функцію завжди можна виписати формулою **двома** стандартними
способами. Обидва спираються на елементарні «цеглинки».

> **Означення (мінтерм, макстерм).** **Мінтерм** (конституента одиниці) — це
> кон'юнкція **всіх** змінних, у якій кожна змінна входить один раз: пряма, якщо в
> даному рядку вона дорівнює $1$, та інвертована, якщо $0$. **Макстерм** (конституента
> нуля) — це диз'юнкція всіх змінних: пряма, якщо змінна в рядку дорівнює $0$, та
> інвертована, якщо $1$.

Наприклад, для рядка $A{=}1, B{=}0, C{=}1, D{=}0$ мінтерм — це
$A\overline{B}C\overline{D}$, а макстерм — $\overline{A}\vee B\vee \overline{C}\vee D$.
Мінтерм дорівнює $1$ **рівно** у своєму рядку; макстерм дорівнює $0$ **рівно** у
своєму рядку.

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

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

Ці дві форми **канонічні**: для заданої функції кожна визначена однозначно. Правило
вибору: якщо одиниць у таблиці менше — коротшою буде ДДНФ; якщо менше нулів — ДКНФ.
Обидві, як правило, ще піддаються **мінімізації** (§2.4).

> **Типова помилка (переплутати правила знаків).** У **ДДНФ** (по одиницях) змінну
> беруть **прямою при $1$**; у **ДКНФ** (по нулях) — навпаки, **прямою при $0$**.
> Проговорюйте подумки: «мінтерм має дорівнювати $1$ у своєму рядку, тож при $0$
> змінну треба інвертувати».

## 2.4 Мінімізація картами Карно

Досконалі форми зазвичай надлишкові. **Карта Карно** — це таблиця істинності,
перекладена у прямокутну сітку так, щоб **сусідні клітинки відрізнялися рівно однією
змінною**. Це дає змогу «згорнути» сусідні мінтерми: якщо $F$ однакова у двох сусідів,
змінна, що між ними змінюється, зайва.

**Код Грея.** Рядки й стовпці нумерують не звичайним двійковим кодом, а **кодом Грея**
$00, 01, 11, 10$, у якому кожен наступний код відрізняється від попереднього одним
бітом. Для чотирьох змінних карта має розмір $4\times4$: рядки позначають парою $AB$,
стовпці — парою $CD$.

**Сусідність із «обгортанням».** Ліве й праве ребра карти вважають сусідніми, так само
верхнє й нижнє: карта замкнена в тор. Тому чотири кутові клітинки — теж сусіди.

> **Правила групування.**
> 1. Об'єднують клітинки з однаковим значенням у **прямокутники**, кількість клітинок
>    у яких є степенем двійки: $1, 2, 4, 8, 16$.
> 2. Групи роблять **якомога більшими** (більша група — коротший терм) і **якомога
>    меншим числом**; групи можуть **перекриватися** та **обгортати** краї.
> 3. Кожна одиниця (для МДНФ) або кожен нуль (для МКНФ) має потрапити хоча б в одну
>    групу.

**Від груп — до форми.**

- **МДНФ** (мінімальна диз'юнктивна) — групують **одиниці**. Кожна група дає один
  **кон'юнктивний терм**: до нього входять лише ті змінні, що **сталі** в межах групи
  (пряма при $1$, інвертована при $0$); змінні, що в групі змінюються, відкидають. МДНФ
  — диз'юнкція цих термів.
- **МКНФ** (мінімальна кон'юнктивна) — групують **нулі**. Кожна група дає один
  **диз'юнктивний терм** за дзеркальним правилом (пряма при $0$, інвертована при $1$).
  МКНФ — кон'юнкція цих термів.

> **Зауваження (невизначені набори).** Якщо для деяких наборів значення функції
> байдуже (позначають «$-$» або $d$), їх дозволено долучати до груп так, як вигідно для
> збільшення групи. У задачах цієї роботи функція визначена на всіх $16$ наборах, тож
> невизначених клітинок не буде.

Наскрізний приклад мінімізації показано в §2.8 (рисунок карти з двома групами).

## 2.5 Базиси ТА-НІ та АБО-НІ

Набір операцій називають **функціонально повним**, якщо через нього можна виразити
будь-яку булеву функцію. Класичний повний набір — $\{\neg, \wedge, \vee\}$. Виявляється,
достатньо **однієї** операції: штриха Шефера **або** стрілки Пірса. Саме тому мікросхеми
часто будують суцільно з елементів ТА-НІ чи АБО-НІ.

**Базис ТА-НІ (штрих Шефера, $\mid$).** Формули заміни (за
[Лекцією 3](../../Lectures/ODM-L03.md)):

$$
\overline{A} = A \mid A, \qquad
A \wedge B = (A \mid B) \mid (A \mid B), \qquad
A \vee B = (A \mid A) \mid (B \mid B).
$$

**Базис АБО-НІ (стрілка Пірса, $\downarrow$).**

$$
\overline{A} = A \downarrow A, \qquad
A \wedge B = (A \downarrow A) \downarrow (B \downarrow B), \qquad
A \vee B = (A \downarrow B) \downarrow (A \downarrow B).
$$

На практиці зручні два дзеркальні факти:

- **ДНФ (сума добутків) природно лягає у ТА-НІ.** Двоярусна схема ТА→АБО
  перетворюється на двоярусну ТА-НІ→ТА-НІ: досить замінити всі елементи на ТА-НІ.
- **КНФ (добуток сум) природно лягає в АБО-НІ.** Двоярусна схема АБО→ТА
  перетворюється на АБО-НІ→АБО-НІ.

Тому для базису ТА-НІ зручно виходити з **МДНФ**, а для АБО-НІ — з **МКНФ**. Конкретні
викладки — у §2.8.

## 2.6 Алгебра Жегалкіна

**Алгебра Жегалкіна** будується на двох операціях — **додавання за модулем 2**
$\oplus$ (те саме, що XOR) і **множення** $\wedge$ (кон'юнкція) — та константі $1$.
Ключові тотожності (за [Лекцією 3](../../Lectures/ODM-L03.md)):

$$
A \oplus A = 0, \qquad A \oplus 0 = A, \qquad A \oplus 1 = \overline{A},
$$
$$
A \wedge (B \oplus C) = (A\wedge B) \oplus (A \wedge C) \quad (\text{дистрибутивність}).
$$

Заперечення й диз'юнкцію виражають через $\oplus$ і $\wedge$ так:

$$
\overline{A} = A \oplus 1, \qquad A \vee B = A \oplus B \oplus A\wedge B.
$$

> **Означення (поліном Жегалкіна).** **Поліномом Жегалкіна** функції називають її
> запис у вигляді суми за модулем 2 різних кон'юнкцій змінних (і, можливо, вільного
> члена $1$), наприклад $F = 1 \oplus C \oplus AB \oplus ABCD$. Для кожної булевої
> функції такий запис **єдиний**.

Щоб отримати поліном, зазвичай беруть будь-яку формулу функції (найзручніше — ДДНФ або
вже знайдену МДНФ), замінюють $\overline{X}$ на $X\oplus 1$ та $X\vee Y$ на
$X\oplus Y\oplus XY$, розкривають дужки за дистрибутивністю й **скорочують однакові
доданки парами** (бо $t \oplus t = 0$). Приклад — у §2.8.

## 2.7 Середовище logic.ly

Роботу виконують в онлайн-редакторі логічних схем **logic.ly** (демо-версія:
<https://logic.ly/demo/>); реєстрація не потрібна, усе працює у браузері. **Ліва
панель** містить елементи, які перетягують на центральне поле. Потрібні в роботі:

**Вхідні керуючі елементи (Input Controls).**

- **Перемикач (Toggle Switch)** — залежно від положення подає логічну $1$ або $0$;
  саме ним задають входи $A, B, C, D$.
- **Генератор тактів (Clock)** — по черзі подає $1$ і $0$ із заданою частотою.
- **Логічна 1 (High Constant)** — постійно подає $1$; **Логічний 0 (Low Constant)** —
  постійно подає $0$.

**Вихідні елементи (Output Controls).**

- **Лампочка (Light Bulb)** — світиться, коли на вхід подано $1$; це вихід $F$.
- **Числова панель (4-Bit Digit)** — показує шістнадцяткову цифру за поданими бітами.

**Логічні елементи (Logic Gates).** Буфер (Buffer), ТА (AND), АБО (OR), Викл. АБО
(XOR), НІ (NOT), ТА-НІ (NAND), АБО-НІ (NOR), Викл. АБО-НІ (NXOR).

**Інші (Other).** Підпис (Label) — для позначення елементів.

**Як будувати схему.** Елементи перетягують на поле й **з'єднують**, ведучи лінію від
**виходу** одного елемента до **входу** іншого. Виділивши елемент, у правому нижньому
куті відкривають **панель параметрів**: для вхідних/вихідних елементів там задають
**змінну**, за яку відповідає елемент (наприклад, підписати перемикачі $A, B, C, D$), а
для вентилів — **кількість вхідних конекторів**. Зібравши схему, перемикають входи й
перевіряють, що лампочка світиться саме на тих наборах, де $F=1$ у вашій таблиці.

> **Порада.** Будуйте схему точно за формулою: спершу розставте перемикачі та
> потрібні елементи НІ (інвертори), потім елементи одного ярусу (усі ТА для ДДНФ або
> всі АБО для ДКНФ), нарешті — вихідний елемент, і лише тоді проводьте з'єднання.
> Кожну готову схему **знімайте** для звіту.

## 2.8 Наскрізний демонстраційний приклад

Пройдемо весь шлях на прикладі, **умова якого не збігається з жодним варіантом**
[4task.md](4task.md), тож він показує **техніку**, а не розв'язок завдання.

> **Умова (демонстраційна).** Лампа світиться тоді й лише тоді, коли одночасно
> ввімкнено перемикачі $A$ і $B$, **або** коли обидва перемикачі $C$ і $D$ вимкнено.

**Крок 1. Формалізація.** Словам відповідає функція

$$
F(A,B,C,D) = (A \wedge B) \vee (\overline{C} \wedge \overline{D}).
$$

**Крок 2. Таблиця істинності.** Обчислюємо $F$ на всіх $16$ наборах (пряма перевірка
за означеннями $\wedge, \vee, \neg$):

![Таблиця істинності демонстраційної функції F = (A∧B) ∨ (не C · не D) на всіх 16 наборах](img/lb1_truth.png)

Одиниці стоять у рядках $0000, 0100, 1000, 1100, 1101, 1110, 1111$ (сім рядків), нулі —
у решті дев'яти.

**Крок 3. ДДНФ (по семи одиницях).** Для кожного одиничного рядка беремо мінтерм:

$$
\begin{aligned}
\text{ДДНФ:}\quad F =\ & \overline{A}\,\overline{B}\,\overline{C}\,\overline{D}
\ \vee\ \overline{A}\,B\,\overline{C}\,\overline{D}
\ \vee\ A\,\overline{B}\,\overline{C}\,\overline{D}
\ \vee\ A\,B\,\overline{C}\,\overline{D} \\
&\vee\ A\,B\,\overline{C}\,D
\ \vee\ A\,B\,C\,\overline{D}
\ \vee\ A\,B\,C\,D.
\end{aligned}
$$

**Крок 4. ДКНФ (по дев'яти нулях).** Для кожного нульового рядка беремо макстерм
(пряма змінна при $0$):

$$
\begin{aligned}
\text{ДКНФ:}\quad F =\ 
& (A\vee B\vee C\vee \overline{D})\,
  (A\vee B\vee \overline{C}\vee D)\,
  (A\vee B\vee \overline{C}\vee \overline{D}) \\
&\cdot(A\vee \overline{B}\vee C\vee \overline{D})\,
  (A\vee \overline{B}\vee \overline{C}\vee D)\,
  (A\vee \overline{B}\vee \overline{C}\vee \overline{D}) \\
&\cdot(\overline{A}\vee B\vee C\vee \overline{D})\,
  (\overline{A}\vee B\vee \overline{C}\vee D)\,
  (\overline{A}\vee B\vee \overline{C}\vee \overline{D}).
\end{aligned}
$$

**Крок 5. Мінімізація картою Карно.** Переносимо одиниці на карту $4\times4$ (рядки
$AB$, стовпці $CD$ у коді Грея) і групуємо:

![Карта Карно демонстраційної функції з двома групами: рядок AB=11 та стовпець CD=00](img/lb1_karnaugh.png)

Дві максимальні групи по чотири клітинки:

- увесь **рядок $AB=11$** — стала лише пара $A=1, B=1$, тож терм $A\wedge B$;
- увесь **стовпець $CD=00$** — сталі $C=0, D=0$, тож терм $\overline{C}\,\overline{D}$.

Групи покривають усі сім одиниць (вони перетинаються в клітинці $AB{=}11, CD{=}00$).
Звідси

$$
\boxed{\ \text{МДНФ:}\quad F = A B \vee \overline{C}\,\overline{D}.\ }
$$

Для **МКНФ** групуємо нулі. Мінімальне покриття дають чотири групи по дві клітинки, що
відповідають чотирьом простим імплікантам; кожна дає диз'юнктивний терм:

$$
\boxed{\ \text{МКНФ:}\quad
F = (A\vee \overline{C})\,(A\vee \overline{D})\,(B\vee \overline{C})\,(B\vee \overline{D}).\ }
$$

Перевірка розкриттям підтверджує рівність:
$(A\vee \overline{C})(A\vee \overline{D}) = A \vee \overline{C}\,\overline{D}$,
$(B\vee \overline{C})(B\vee \overline{D}) = B \vee \overline{C}\,\overline{D}$, а їхній
добуток дорівнює $AB \vee \overline{C}\,\overline{D}$ — тій самій функції.

**Крок 6. Схема МДНФ.** Формулу $F = AB \vee \overline{C}\,\overline{D}$ збираємо з двох
елементів ТА, двох інверторів (НІ) та одного АБО; входи — перемикачі, вихід — лампочка:

![Логічна схема МДНФ F = AB ∨ (не C · не D) на елементах НІ, ТА, АБО](img/lb1_circuit.png)

**Крок 7. Базиси ТА-НІ та АБО-НІ (для рівня понад 75).** Двоярусну суму добутків
$F = AB \vee \overline{C}\,\overline{D}$ переписуємо в **ТА-НІ**, замінивши обидва яруси
на елементи ТА-НІ (а інвертори $\overline{C}=C\mid C$, $\overline{D}=D\mid D$):

$$
F = (A \mid B) \mid \big((C \mid C) \mid (D \mid D)\big).
$$

![Схема демонстраційної функції у базисі ТА-НІ з п'яти елементів NAND](img/lb1_nand.png)

Симетрично, виходячи з добутку сум (МКНФ), отримуємо реалізацію в **АБО-НІ** (тут
$\overline{C}=C\downarrow C$, $\overline{D}=D\downarrow D$):

$$
F = \big(A \downarrow (C\downarrow C)\big) \downarrow
    \big(A \downarrow (D\downarrow D)\big) \downarrow
    \big(B \downarrow (C\downarrow C)\big) \downarrow
    \big(B \downarrow (D\downarrow D)\big).
$$

**Крок 8. Поліном Жегалкіна (для рівня понад 90).** Замінюємо
$\overline{C}=C\oplus 1$, $\overline{D}=D\oplus 1$ і $X\vee Y = X\oplus Y\oplus XY$:

$$
\overline{C}\,\overline{D} = (C\oplus 1)(D\oplus 1) = CD \oplus C \oplus D \oplus 1,
$$

$$
F = AB \vee \overline{C}\,\overline{D}
  = AB \oplus (\overline{C}\,\overline{D}) \oplus AB\cdot(\overline{C}\,\overline{D}).
$$

Розкривши дужки й скоротивши пару $AB \oplus AB = 0$, дістаємо єдиний поліном:

$$
\boxed{\ F = 1 \oplus C \oplus D \oplus CD \oplus ABC \oplus ABD \oplus ABCD.\ }
$$

Його легко перевірити на кількох рядках таблиці: наприклад, на наборі $0000$ усі
кон'юнкції нульові, лишається вільний член $1$ — і справді $F(0000)=1$.

> **Підсумок прикладу.** Одну функцію ми подали **шістьма** способами — ДДНФ, ДКНФ,
> МДНФ, МКНФ, у базисах ТА-НІ/АБО-НІ та поліномом Жегалкіна — і кожен спосіб дає свою
> схему. У [4task.md](4task.md) той самий шлях ви пройдете для власного варіанта.