# Лекція 3. Основи булевої алгебри. Алгебра Жегалкіна

## Огляд

Ця лекція будує алгебраїчний фундамент для всієї «логічної» частини курсу. Ми
починаємо з побутового поняття **висловлення**, яке буває істинним або хибним,
кодуємо ці два значення символами $1$ та $0$ — і вивчаємо, як висловлення
поєднуються невеликим набором **булевих операцій**. Центральний об'єкт —
**булева алгебра**: двоелементна множина $\{0,1\}$ з операціями заперечення
($\neg$), кон'юнкції ($\wedge$) та диз'юнкції ($\vee$), а також похідними
операціями — виключним «або» ($\oplus$), стрілкою Пірса ($\downarrow$), штрихом
Шефера ($\mid$) та еквівалентністю ($\leftrightarrow$).

Три ідеї пронизують увесь розділ. **Перша:** кожна операція повністю задається
**таблицею істинності**, а булева функція $n$ змінних — це не що інше, як таблиця
істинності; звідси ми точно **порахуємо**, скільки таких функцій існує. **Друга:**
операції підпорядковані компактному списку **аксіом і законів** (комутативність,
асоціативність, дистрибутивність, поглинання, доповнення, де Моргана, …), і кожен
закон ми **доводимо** таблицею істинності, а не просто проголошуємо. **Третя:**
цей самий список законів — той самий, що керує **алгеброю множин** із
[Лекції 1](ODM-L01.md); булева алгебра, алгебра множин та алгебра бітів — це три
обличчя однієї структури, і саме тому діаграми Венна, які ви малювали для множин,
не суперечать таблицям істинності, які ми будуватимемо тут.

Насамкінець ми розглянемо два питання, суттєві для інженерної практики. **Функціональна
повнота** — які набори операцій достатні, щоб виразити будь-яку булеву функцію
(базис ТА-АБО-НІ, а також те, що однієї операції NOR або однієї NAND уже вистачає).
І **алгебра Жегалкіна** — погляд на булеві функції як на **многочлени** над полем із
двох елементів, де замість диз'юнкції працює додавання за модулем $2$ (виключне
«або» $\oplus$). Ця точка зору дає єдиний канонічний **многочлен Жегалкіна** для
кожної функції і лежить в основі контрольних сум, кодів парності та алгоритмів
виявлення помилок.

> **Про строгість.** Кілька результатів нижче оформлені як **теореми** та
> **твердження** з доведеннями, обмеженими позначками *Доведення.* … $\blacksquare$.
> Головний метод доведення тут — **таблицею істинності**: щоб довести рівність двох
> булевих виразів, будують обидві таблиці й порівнюють останні стовпці рядок за
> рядком. Читайте доведення активно; ці самі прийоми знадобляться в
> [Лекції 4](ODM-L04.md), де ми мінімізуємо функції та переходимо до логічних схем.

---

## 3.1 Висловлення та алфавіт булевої алгебри

### Висловлення й істиннісні значення

**Висловлення** (або **твердження**) — це розповідне речення, яке є або **істинним**,
або **хибним**, але не тим і тим водночас. Бути висловленням не залежить від того, чи
*знаємо* ми, котре з двох значень воно має; важливо лише, що речення однозначно є
одним із двох.

**Приклади і не-приклади.**

- «Сьогодні неділя.» — висловлення (істинне або хибне залежно від дня).
- «$2 + 2 = 4$.» — висловлення (істинне).
- «Існує нескінченно багато простих чисел-близнюків.» — висловлення: воно
  безумовно або істинне, або хибне, хоча (станом на сьогодні) ніхто не знає, котре
  саме. *Мати* істиннісне значення не означає *знати* його.
- «$x < 0$.» — це **предикат** (відкрите речення): воно стає висловленням лише
  після того, як $x$ зафіксовано. Предикати з квантифікаторами — предмет наступних
  лекцій, а не цієї.
- «Як справи?» — **не** висловлення; питання не має істиннісного значення.
- «Зачини двері.» — **не** висловлення; наказ не має істиннісного значення.
- «Це речення хибне.» — **не** висловлення: якщо припустити його істинним, воно
  стає хибним, і навпаки (**парадокс брехуна**).

Кожному висловленню зіставляємо символьне **істиннісне значення**. **Алфавіт**
булевої алгебри складається рівно з двох символів:

$$
\text{істина} = 1 = T = \text{І}, \qquad \text{хиба} = 0 = F = \text{Х}.
$$

Робота з цифрами $0$ та $1$ (а не зі словами) — це саме те, що перетворює логіку на
**алгебру**: істиннісні значення стають величинами, з якими можна обчислювати, а
логічні сполучники — операціями, схожими на $+$ та $\times$.

> **Зауваження (позначення).** Одні автори пишуть $T/F$, інші $\top/\bot$, ще інші
> $1/0$ або українські $\text{І}/\text{Х}$. Цей курс майже скрізь використовує $1$ і
> $0$, бо це робить наочним місток до арифметики та апаратури: кон'юнкція
> поводитиметься точно як множення бітів, а диз'юнкція — майже як додавання.

### Складені висловлення

Прості висловлення зазвичай позначають літерами $p, q, r, \dots$ (або $A, B, C$) і
поєднують у **складені висловлення** за допомогою **сполучників**. Нехай

- $p$ = «Сьогодні п'ятниця»,
- $q$ = «Погода гарна».

Тоді:

| Складене висловлення | Читається як |
|---|---|
| $p \wedge q$ | «Сьогодні п'ятниця **і** погода гарна» |
| $p \vee q$ | «Сьогодні п'ятниця **або** погода гарна» |
| $\neg p$ | «Сьогодні **не** п'ятниця» |
| $\neg p \wedge q$ | «Сьогодні не п'ятниця **і** погода гарна» |

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

---

## 3.2 Булеві змінні та булеві функції

**Булева змінна** — це змінна, що набуває значень із $\{0, 1\}$. **Булева функція
$n$ змінних** — це будь-яке правило

$$
f : \{0,1\}^n \longrightarrow \{0,1\},
$$

що кожному з $2^n$ можливих наборів входів зіставляє значення $0$ або $1$. Тут
$\{0,1\}^n$ — множина всіх $n$-ок (вхідних векторів) $(x_1, \dots, x_n)$ з бітів.

**Таблиця істинності *є* функцією.** Оскільки область визначення $\{0,1\}^n$
скінченна, булева функція повністю задається переліком її значення на кожному
вхідному рядку. Два булеві вирази задають ту саму функцію саме тоді, коли їхні
таблиці істинності збігаються в кожному рядку. Це — найважливіший інструмент розділу:

> **Щоб довести рівність двох булевих виразів, будують обидві таблиці істинності й
> перевіряють, що останні стовпці збігаються рядок за рядком.** Щоб *спростувати*
> рівність, достатньо вказати **один** рядок, у якому вони різняться (контрприклад).

Рядки входів прийнято перелічувати в порядку зростання двійкового числа
($00, 01, 10, 11, \dots$), щоб нічого не пропустити. (На слайдах лекції окремі
таблиці подано у спадному порядку — це та сама функція, лише інша послідовність
рядків.)

### Скільки є булевих функцій?

Скільки різних булевих функцій $n$ змінних існує? Відповідь напрочуд велика й
зростає двічі експоненційно.

> **Теорема 3.1 (кількість булевих функцій).** Кількість булевих функцій $n$
> змінних дорівнює
> $$ N(n) = 2^{\,2^{\,n}}. $$
>
> *Доведення.* Лічимо у два кроки.
>
> *Крок 1 — кількість вхідних рядків.* Вхід — це $n$-ка $(x_1, \dots, x_n)$, де
> кожен $x_i \in \{0,1\}$. За правилом добутку маємо $2$ незалежні варіанти для
> кожної з $n$ координат, тому
> $$ |\{0,1\}^n| = \underbrace{2 \cdot 2 \cdots 2}_{n} = 2^{\,n} $$
> різних вхідних рядків. Позначимо це число $m = 2^n$.
>
> *Крок 2 — кількість способів заповнити стовпець виходів.* Функція $f$ однозначно
> визначається значеннями, які вона надає кожному з $m$ рядків, і ці значення
> обираються **незалежно**: будь-який зі стовпців довжини $m$ (кожен запис — $0$ або
> $1$) задає справжню функцію, а різні стовпці задають різні функції. Знову за
> правилом добутку таких стовпців
> $$ \underbrace{2 \cdot 2 \cdots 2}_{m} = 2^{\,m}. $$
> Підставляючи $m = 2^n$, дістаємо $N(n) = 2^{\,2^{\,n}}$. $\blacksquare$

Двокроковість — спершу порахувати рядки ($2^n$), потім заповнення ($2^{(\text{рядків})}$) —
і є причиною того, що показник сам є експонентою.

| $n$ | рядків $2^n$ | функцій $2^{2^n}$ |
|:-:|:-:|:-:|
| $0$ | $1$ | $2$ |
| $1$ | $2$ | $4$ |
| $2$ | $4$ | $16$ |
| $3$ | $8$ | $256$ |
| $4$ | $16$ | $65\,536$ |
| $5$ | $32$ | $4\,294\,967\,296$ |

Зростання нестримне: уже при $n = 6$ маємо $2^{64} \approx 1{,}8 \times 10^{19}$
функцій. Саме цей вибух пояснює, чому потрібні **систематичні** методи спрощення
([Лекція 4](ODM-L04.md)): перебрати всі функції вручну неможливо.

### Усі шістнадцять функцій двох змінних

При $n = 2$ маємо рівно $2^{4} = 16$ функцій $F_0, \dots, F_{15}$. Читаючи кожен
стовпець згори вниз над вхідними рядками $(x,y) = 00, 01, 10, 11$, дістаємо таблицю
істинності цієї функції; а нижній індекс $k$ — це двійкове число, «прочитане» тим
стовпцем (старший біт угорі):

| $x$ | $y$ | $F_0$ | $F_1$ | $F_2$ | $F_3$ | $F_4$ | $F_5$ | $F_6$ | $F_7$ | $F_8$ | $F_9$ | $F_{10}$ | $F_{11}$ | $F_{12}$ | $F_{13}$ | $F_{14}$ | $F_{15}$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $0$ | $0$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| $0$ | $1$ | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| $1$ | $0$ | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| $1$ | $1$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |

![Усі 16 булевих функцій двох змінних: чотири вхідні рядки (x,y) та стовпці F0…F15, кожен зі своєю таблицею істинності](img/l03_16functions.png)

Кілька з цих стовпців — операції, які ми невдовзі назвемо:

- $F_0 = 0$ (тотожний нуль, суперечність), $F_{15} = 1$ (тотожна одиниця, тавтологія);
- $F_1 = x \wedge y$ (AND), $F_7 = x \vee y$ (OR);
- $F_3 = x$, $F_5 = y$, $F_{12} = \neg x$, $F_{10} = \neg y$ (проєкції та їхні заперечення);
- $F_6 = x \oplus y$ (XOR), $F_9 = x \leftrightarrow y$ (еквівалентність, XNOR);
- $F_{13} = x \to y$, $F_{11} = y \to x$ (імплікації);
- $F_8 = x \downarrow y$ (NOR, стрілка Пірса), $F_{14} = x \mid y$ (NAND, штрих Шефера).

Найважливіше тут — не окремі назви, а **кількість**: кожна можлива таблиця
істинності двох змінних трапляється рівно один раз, і їх рівно $16$ — не більше й не
менше.

---

## 3.3 Елементарні булеві операції

Розглянемо операції по черзі. Кожну задаємо **таблицею істинності**. Заперечення —
**унарна** операція (один вхід); решта — **бінарні** (два входи).

### Заперечення (NOT, $\neg$)

**Заперечення** перемикає істиннісне значення на протилежне: $\neg A$ істинне саме
тоді, коли $A$ хибне. Уживані позначення: $\neg A$, $\sim A$, $!A$, $\overline{A}$,
$A'$.

| $A$ | $\neg A$ |
|:-:|:-:|
| 0 | 1 |
| 1 | 0 |

### Кон'юнкція (AND, $\wedge$)

**Кон'юнкція** $A \wedge B$ істинна саме тоді, коли істинні **обидва** операнди.
Позначення: $A \wedge B$, $A \cdot B$, $AB$. Порівняння таблиці нижче з таблицею
множення для $0/1$ показує їхню тотожність: $A \wedge B = A \cdot B$. Тому кон'юнкцію
часто пишуть як добуток.

| $A$ | $B$ | $A \wedge B$ |
|:-:|:-:|:-:|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

### Диз'юнкція (OR, $\vee$)

**Диз'юнкція** $A \vee B$ істинна, коли істинний **принаймні один** операнд (це
*включне* «або»). Позначення: $A \vee B$, $A + B$. Вона поводиться як додавання
бітів, *окрім* того, що $1 \vee 1 = 1$ (а не $2$): диз'юнкція — це «насичене»
додавання з верхньою межею $1$.

| $A$ | $B$ | $A \vee B$ |
|:-:|:-:|:-:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |

> **Типова помилка (включне проти виключного «або»).** Побутове «або» часто
> *виключне* («суп або салат» означає одне, не обидва), але логічне $\vee$ —
> **включне**: $1 \vee 1 = 1$. Виключне прочитання — це інша операція, XOR, яку
> означуємо далі.

### Виключне «або» (XOR, $\oplus$)

**Виключне «або»** $A \oplus B$ істинне, коли операнди **різні** — істинний рівно
один із них. Це «або, але не обидва», а також «операнди нерівні»: $A \oplus B = 1$
тоді й лише тоді, коли $A \ne B$. Воно поводиться як додавання **за модулем $2$**:
$A \oplus B = (A + B) \bmod 2$.

| $A$ | $B$ | $A \oplus B$ |
|:-:|:-:|:-:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

Саме тому, що $\oplus$ — це додавання за модулем $2$, воно має чисту **алгебру**
(§3.8), і на ній ґрунтується алгебра Жегалкіна.

### Стрілка Пірса (NOR, $\downarrow$)

**Стрілка Пірса** $A \downarrow B$ — це заперечення диз'юнкції: $A \downarrow B =
\neg(A \vee B)$. Вона істинна саме тоді, коли **обидва** операнди хибні («ні $A$, ні
$B$»).

| $A$ | $B$ | $A \downarrow B$ |
|:-:|:-:|:-:|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |

### Штрих Шефера (NAND, $\mid$)

**Штрих Шефера** $A \mid B$ (також $A \uparrow B$) — це заперечення кон'юнкції:
$A \mid B = \neg(A \wedge B)$. Він хибний лише тоді, коли **обидва** операнди
істинні, і істинний в усіх інших випадках.

| $A$ | $B$ | $A \mid B$ |
|:-:|:-:|:-:|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

### Еквівалентність (XNOR, $\leftrightarrow$)

**Еквівалентність** $A \leftrightarrow B$ (також $A \equiv B$, $A \sim B$) істинна,
коли операнди мають **однакове** значення. Це точно заперечення XOR:
$A \leftrightarrow B = \neg(A \oplus B)$, тобто $A \leftrightarrow B = 1$ тоді й лише
тоді, коли $A = B$.

| $A$ | $B$ | $A \leftrightarrow B$ |
|:-:|:-:|:-:|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

### Усі операції поряд

Поставивши операції двох змінних поруч, легко порівняти їхні візерунки:

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

![Таблиці істинності основних операцій поряд: заперечення, кон'юнкція, диз'юнкція, виключне «або», стрілка Пірса, штрих Шефера, еквівалентність](img/l03_gates.png)

Зверніть увагу на пари-заперечення: стовпець $A \downarrow B$ — це заперечення
$A \vee B$; стовпець $A \mid B$ — заперечення $A \wedge B$; стовпець
$A \leftrightarrow B$ — заперечення $A \oplus B$. Три «нижні» операції ($\downarrow,
\mid, \leftrightarrow$) — це просто заперечені три «верхні» ($\vee, \wedge, \oplus$).

### Пріоритет операцій

Щоб не громадити дужки, домовляються про **пріоритет** (силу зв'язування), від
найвищого до найнижчого:

$$ \neg \;\succ\; \wedge \;\succ\; \vee,\ \oplus \;\succ\; \to,\ \leftrightarrow. $$

Отже, $\neg A \wedge B$ означає $(\neg A) \wedge B$, а $A \wedge B \vee C$ означає
$(A \wedge B) \vee C$. Заперечення діє на найменший вираз праворуч від себе;
$\wedge$ зв'язує як множення, а $\vee$ — як додавання. Оскільки $\oplus$ і $\vee$
стоять на одному рівні, вирази з обома краще дужкувати. Коли є сумнів — ставте дужки:
ясність важливіша за стислість.

> **Типова помилка.** $\neg A \wedge B$ — це $(\neg A) \wedge B$, а **не**
> $\neg(A \wedge B)$: риска заперечення не «розтягується» на $\wedge$, доки ви не
> напишете її так явно. У записі $\overline{A}\,B$ проти $\overline{AB}$ різниця
> видима; у лінійному тексті це часте джерело помилок.

**Приклад 3.2 (обчислення таблиці складеного виразу).** Побудуймо таблицю
$(A \wedge B) \vee \neg C$. Три змінні дають $2^3 = 8$ рядків; уводимо допоміжні
стовпці $A \wedge B$ і $\neg C$, а тоді їхню диз'юнкцію:

| $A$ | $B$ | $C$ | $A \wedge B$ | $\neg C$ | $(A \wedge B) \vee \neg C$ |
|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 1 |

Останній стовпець — це функція, яку обчислює вираз; вона дорівнює $1$ у п'яти рядках
із восьми.

---

## 3.4 Аксіоми булевої алгебри

Булеву алгебру можна будувати аксіоматично: приймають кілька тотожностей за
**аксіоми**, а решту законів виводять із них. Наведемо систему аксіом зі слайдів
лекції; вона записана **дуальними парами** — форма з $\wedge$ та форма з $\vee$.

| Аксіома | Форма з $\wedge$ | Форма з $\vee$ |
|---|---|---|
| **Комутативність** | $A B = B A$ | $A \vee B = B \vee A$ |
| **Асоціативність** | $A(BC) = (AB)C$ | $A \vee (B \vee C) = (A \vee B) \vee C$ |
| **Дистрибутивність** | $A(B \vee C) = AB \vee AC$ | $A \vee BC = (A \vee B)(A \vee C)$ |
| **Поглинання** | $(A \vee B)\,B = B$ | $AB \vee B = B$ |
| **Доповнення** | $(A \wedge \neg A) \vee B = B$ | $(A \vee \neg A)\,B = B$ |

Пояснимо два останні рядки, бо їхня форма незвична.

- **Поглинання.** $AB \vee B = B$ каже, що доданок $AB$ «поглинається» доданком $B$:
  хоч би яким було $A$, результат дорівнює $B$. Дуально $(A \vee B)B = B$.
- **Доповнення.** Аксіома фіксує поведінку заперечення через сталі: оскільки
  $A \wedge \neg A = 0$ і $A \vee \neg A = 1$, маємо $(A \wedge \neg A) \vee B =
  0 \vee B = B$ і $(A \vee \neg A)B = 1 \cdot B = B$. Тобто $0$ — нейтральний
  елемент для $\vee$, а $1$ — нейтральний для $\wedge$, а заперечення дає «протилежний»
  елемент, який у парі з вихідним породжує сталі $0$ та $1$.

> **Зауваження (дуальність).** Помітьте: у таблиці аксіом ліва й права колонки —
> дзеркальні. Якщо у будь-якій істинній тотожності одночасно поміняти місцями
> $\wedge \leftrightarrow \vee$ та $0 \leftrightarrow 1$, знову дістанемо істинну
> тотожність. Це **принцип дуальності**; завдяки йому закони йдуть парами, і,
> довівши один, ми задарма маємо його двоїстий.

---

## 3.5 Закони (тотожності) булевої алгебри

Із аксіом випливають робочі закони, якими щодня користуються для спрощення виразів.
Наведемо їх (зі слайдів лекції), а найважливіші **доведемо** таблицею істинності.

| Закон | Форма з $\wedge$ | Форма з $\vee$ |
|---|---|---|
| **Ідемпотентність** | $A \wedge A = A$ | $A \vee A = A$ |
| **Дії з $0$ та $1$** | $A \wedge 0 = 0,\quad A \wedge 1 = A$ | $A \vee 0 = A,\quad A \vee 1 = 1$ |
| **Доповнення** | $A \wedge \neg A = 0$ | $A \vee \neg A = 1$ |
| **Закони де Моргана** | $\neg(A \wedge B) = \neg A \vee \neg B$ | $\neg(A \vee B) = \neg A \wedge \neg B$ |
| **Подвійне заперечення** | $\neg\neg A = A$ | (самодвоїстий) |

У законі «дії з $0$ та $1$» варто розрізняти дві ролі сталих: $1$ — нейтральний
елемент для $\wedge$ ($A \wedge 1 = A$), а $0$ — нейтральний для $\vee$
($A \vee 0 = A$); натомість $0$ **поглинає** під $\wedge$ ($A \wedge 0 = 0$, як
$a \cdot 0 = 0$), а $1$ поглинає під $\vee$ ($A \vee 1 = 1$).

### Ідемпотентність

> **Теорема 3.3 (ідемпотентність).** $A \wedge A = A$ і $A \vee A = A$.
>
> *Доведення.* Оскільки бере участь лише одна змінна, таблиця має два рядки:
>
> | $A$ | $A \wedge A$ | $A \vee A$ |
> |:-:|:-:|:-:|
> | 0 | 0 | 0 |
> | 1 | 1 | 1 |
>
> Обидва стовпці збігаються зі стовпцем $A$. $\blacksquare$

> **Зауваження.** Саме тут булева алгебра різко розходиться з арифметикою:
> $A + A = A$ та $A \cdot A = A$ для *всіх* булевих значень, тоді як $a + a = 2a$ і
> $a^2$ зазвичай відмінні від $a$. Через це повторювані доданки згортаються
> ($A \vee A \vee A = A$) — це перший інструмент спрощення. (Запам'ятайте цей
> контраст: в алгебрі Жегалкіна §3.8 для $\oplus$ буде натомість $x \oplus x = 0$.)

### Закони де Моргана

> **Теорема 3.4 (де Морган).** $\neg(A \wedge B) = \neg A \vee \neg B$ і
> $\neg(A \vee B) = \neg A \wedge \neg B$.
>
> *Доведення.* Перший закон:
>
> | $A$ | $B$ | $A \wedge B$ | $\neg(A \wedge B)$ | $\neg A$ | $\neg B$ | $\neg A \vee \neg B$ |
> |:-:|:-:|:-:|:-:|:-:|:-:|:-:|
> | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
> | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
> | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
> | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
>
> Стовпці $\neg(A \wedge B)$ та $\neg A \vee \neg B$ рівні в кожному рядку. Другий
> закон:
>
> | $A$ | $B$ | $A \vee B$ | $\neg(A \vee B)$ | $\neg A$ | $\neg B$ | $\neg A \wedge \neg B$ |
> |:-:|:-:|:-:|:-:|:-:|:-:|:-:|
> | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
> | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
> | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
> | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
>
> Стовпці $\neg(A \vee B)$ та $\neg A \wedge \neg B$ рівні в кожному рядку.
> $\blacksquare$

> **Типова помилка.** Закони де Моргана кажуть, що заперечення **змінює сполучник**:
> $\neg(A \wedge B)$ — це $\neg A \vee \neg B$, а **не** $\neg A \wedge \neg B$. «Не
> (багатий і відомий)» означає «бідний *або* невідомий», а не «бідний *і*
> невідомий». Перенесення заперечення через $\wedge/\vee$ без зміни сполучника —
> найпоширеніша помилка в цьому предметі.

Закони де Моргана показують ще й те, що набори $\{\wedge, \neg\}$ та $\{\vee, \neg\}$
кожен окремо достатні, щоб виразити відсутній сполучник:
$A \vee B = \neg(\neg A \wedge \neg B)$ і $A \wedge B = \neg(\neg A \vee \neg B)$.
Цю ідею **функціональної повноти** розвинемо в §3.7.

### Подвійне заперечення (інволюція)

> **Теорема 3.5 (подвійне заперечення).** $\neg\neg A = A$.
>
> *Доведення.*
>
> | $A$ | $\neg A$ | $\neg\neg A$ |
> |:-:|:-:|:-:|
> | 0 | 1 | 0 |
> | 1 | 0 | 1 |
>
> Стовпець $\neg\neg A$ збігається зі стовпцем $A$. $\blacksquare$

### Спрощення виразів

Щойно закони встановлено, нові тотожності можна доводити **алгебраїчно** — переписуючи
одну частину в іншу за законами як за правилами перетворення. Саме так спрощують
логічні схеми ([Лекція 4](ODM-L04.md)).

**Приклад 3.6 (спрощення).** Спростимо $\neg(\neg A \wedge B) \wedge (A \vee B)$:

$$
\begin{aligned}
\neg(\neg A \wedge B) \wedge (A \vee B)
&= (\neg\neg A \vee \neg B) \wedge (A \vee B) && \text{(де Морган)}\\
&= (A \vee \neg B) \wedge (A \vee B) && \text{(подвійне заперечення)}\\
&= A \vee (\neg B \wedge B) && \text{(дистрибутивність)}\\
&= A \vee 0 && \text{(доповнення)}\\
&= A. && \text{(дії з } 0)
\end{aligned}
$$

Вираз із чотирьох операцій згортається до однієї змінної $A$. Перевірка таблицею
зайняла б чотири рядки; алгебра ж пояснює, *чому* так.

---

## 3.6 Зв'язок булевої алгебри з алгеброю множин

Закони, які ми довели, не є чимось особливим саме для істиннісних значень. **Той
самий список законів** керує **алгеброю множин** із [Лекції 1](ODM-L01.md). Причина
в тому, що обидві структури — окремі випадки однієї абстрактної структури, *булевої
алгебри*, і їх можна вишикувати операція проти операції.

| Поняття | Логіка (біти) | Множини |
|---|---|---|
| «і» | $A \wedge B$ | $A \cap B$ |
| «або» | $A \vee B$ | $A \cup B$ |
| «не» | $\neg A$ | $\overline{A}$ |
| низ / порожнеча | $0$ (хиба) | $\varnothing$ |
| верх / універсум | $1$ (істина) | $U$ |
| «те саме» | $A \leftrightarrow B$ | $A = B$ |
| «не більше ніж» | $A \to B$ | $A \subseteq B$ |

Кожен закон читається однаково вниз по будь-якому стовпцю. Наприклад, де Морган:

$$
\neg(A \wedge B) = \neg A \vee \neg B, \qquad \overline{A \cap B} = \overline{A} \cup \overline{B};
$$

а дистрибутивність, поглинання, доповнення й решта збігаються рядок за рядком. Саме
тому інтуїція діаграм Венна з [Лекції 1](ODM-L01.md) ніколи не суперечить таблицям
істинності цієї лекції: **членська таблиця** для множин — це *те саме обчислення*,
що й таблиця істинності для логіки.

![Круги Ейлера/діаграми Венна: кон'юнкція відповідає перетину, диз'юнкція — об'єднанню, заперечення — доповненню](img/l03_venn_logic.png)

Наочно: на діаграмі Венна кожній точці універсуму відповідає рядок таблиці
істинності (за тим, у яких колах вона лежить), а заштрихована область — це саме ті
рядки, де складений вираз дорівнює $1$. Тому $A \wedge B$ «висвічує» перетин,
$A \vee B$ — об'єднання, а $\neg A$ — усе поза колом $A$.

**Приклад 3.7 (характеристичний вектор — точний місток).** Зафіксуймо універсум
$U = \{1,2,3\}$ і підмножини $A = \{1,2\}$, $B = \{2,3\}$. Кожній підмножині
зіставмо її **характеристичний вектор** із бітів (одиниця на позиції елемента, що
належить множині):

$$
\chi_A = (1,1,0), \qquad \chi_B = (0,1,1).
$$

Тоді покоординатно $\chi_A \wedge \chi_B = (0,1,0) = \chi_{A \cap B}$ (бо
$A \cap B = \{2\}$); $\chi_A \vee \chi_B = (1,1,1) = \chi_{A \cup B}$ (бо
$A \cup B = U$); $\neg\chi_A = (0,0,1) = \chi_{\overline{A}}$ (бо
$\overline{A} = \{3\}$). Відповідність $A \mapsto \chi_A$ — бієкція між
множиною-ступенем $\mathcal{P}(U)$ та множиною бітових векторів $\{0,1\}^{|U|}$, яка
*зберігає всі операції*. Ось чому підмножину $n$-елементного універсуму зберігають у
комп'ютері як одне $n$-бітове слово, а операції над множинами виконують побітовими
командами процесора.

Демонструє один із законів де Моргана вже суто «множинно» і наступний рисунок.

![Закон де Моргана на діаграмах Венна: доповнення об'єднання збігається з перетином доповнень](img/l03_demorgan.png)

---

## 3.7 Функціональна повнота та базиси

Ми бачили $16$ функцій двох змінних і навіть $2^{2^n}$ функцій узагалі. Виникає
природне питання: **чи достатньо кількох операцій, щоб виразити всі решту?**

> **Означення (функціональна повнота).** Набір булевих операцій називають
> **функціонально повним** (**базисом**), якщо будь-яку булеву функцію будь-якого
> числа змінних можна записати формулою, що використовує лише операції цього набору
> (та змінні й, за потреби, сталі).

### Базис ТА-АБО-НІ ($\{\neg, \wedge, \vee\}$)

> **Теорема 3.8 (повнота базису ТА-АБО-НІ).** Набір $\{\neg, \wedge, \vee\}$
> функціонально повний.
>
> *Доведення (через досконалу диз'юнктивну нормальну форму).* Нехай $f(x_1, \dots,
> x_n)$ — довільна булева функція. Якщо $f \equiv 0$, то $f = x_1 \wedge \neg x_1$
> (сталий нуль виражається). Інакше розгляньмо всі вхідні набори
> $\alpha = (a_1, \dots, a_n)$, на яких $f(\alpha) = 1$. Кожному такому набору
> зіставмо **конституенту одиниці** (мінтерм)
> $$ K_\alpha = \ell_1 \wedge \ell_2 \wedge \dots \wedge \ell_n, \qquad
> \ell_i = \begin{cases} x_i, & a_i = 1,\\ \neg x_i, & a_i = 0, \end{cases} $$
> яка дорівнює $1$ рівно на наборі $\alpha$ і $0$ на всіх інших. Тоді
> $$ f = \bigvee_{\alpha:\, f(\alpha)=1} K_\alpha $$
> — диз'юнкція всіх таких мінтермів приймає значення $1$ саме на тих наборах, де
> $f = 1$. Ця формула використовує лише $\neg, \wedge, \vee$, тож набір повний.
> $\blacksquare$

Побудований у доведенні вираз — це **досконала диз'юнктивна нормальна форма** (ДДНФ)
функції; докладно нормальні форми ДНФ/КНФ вивчатимемо в [Лекції 4](ODM-L04.md). Уже
зараз важливий висновок: **кожну** з $16$ функцій двох змінних можна записати через
ТА-АБО-НІ, і ось цей повний перелік (зі слайдів лекції):

![Усі 16 функцій двох змінних, виражені в базисі ТА-АБО-НІ: для кожної наведено її вихідний вектор і формулу через заперечення, кон'юнкцію та диз'юнкцію](img/l03_andornot_basis.png)

| $F_k$ | вихід $C$ на $(A,B){=}00,01,10,11$ | вираз у базисі $\{\neg,\wedge,\vee\}$ |
|:-:|:-:|:--|
| $F_0$ | $0000$ | $0$ |
| $F_1$ | $0001$ | $A \wedge B$ |
| $F_2$ | $0010$ | $A \wedge \neg B$ |
| $F_3$ | $0011$ | $A$ |
| $F_4$ | $0100$ | $\neg A \wedge B$ |
| $F_5$ | $0101$ | $B$ |
| $F_6$ | $0110$ | $A \wedge \neg B \ \vee\ \neg A \wedge B$ |
| $F_7$ | $0111$ | $A \vee B$ |
| $F_8$ | $1000$ | $\neg A \wedge \neg B$ |
| $F_9$ | $1001$ | $A \wedge B \ \vee\ \neg A \wedge \neg B$ |
| $F_{10}$ | $1010$ | $\neg B$ |
| $F_{11}$ | $1011$ | $A \vee \neg B$ |
| $F_{12}$ | $1100$ | $\neg A$ |
| $F_{13}$ | $1101$ | $\neg A \vee B$ |
| $F_{14}$ | $1110$ | $\neg A \vee \neg B$ |
| $F_{15}$ | $1111$ | $1$ |

Зверніть увагу, як звичні операції лягли в перелік: $F_6$ — це XOR, записаний через
базис; $F_9$ — еквівалентність; $F_8$ — NOR; $F_{14}$ — NAND; $F_{13}$ та $F_{11}$ —
дві імплікації. Це конкретне підтвердження теореми: усі $16$ функцій справді
виражаються через ТА-АБО-НІ.

Понад те, за законами де Моргана навіть $\{\wedge, \neg\}$ і $\{\vee, \neg\}$ —
повні базиси: одне з двох ($\wedge$ або $\vee$) зайве. А чи можна обійтися **однією**
операцією? Так — і аж двома способами.

### Базис NOR ($\{\downarrow\}$)

> **Твердження 3.9 (повнота стрілки Пірса).** Сама лише операція $\downarrow$
> функціонально повна. Зокрема:
> $$ \neg 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). $$
>
> *Доведення.* Достатньо виразити повний базис $\{\neg, \vee, \wedge\}$ через
> $\downarrow$; тоді за Теоремою 3.8 виражається все.
> - $A \downarrow A = \neg(A \vee A) = \neg A$ (ідемпотентність $\vee$).
> - $A \vee B = \neg\neg(A \vee B) = \neg(A \downarrow B) = (A \downarrow B)
>   \downarrow (A \downarrow B)$ (за попереднім рядком, застосованим до
>   $X = A \downarrow B$).
> - $A \wedge B = \neg(\neg A \vee \neg B) = \neg A \downarrow \neg B =
>   (A \downarrow A) \downarrow (B \downarrow B)$ (де Морган, тоді заперечення
>   аргументів через $\downarrow$). $\blacksquare$

![Перевірка базису NOR таблицею істинності: A↓A відтворює заперечення, а комбінації стрілки Пірса дають кон'юнкцію та диз'юнкцію](img/l03_nor_basis.png)

### Базис NAND ($\{\mid\}$)

> **Твердження 3.10 (повнота штриха Шефера).** Сама лише операція $\mid$
> функціонально повна. Зокрема:
> $$ \neg 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). $$
>
> *Доведення.* Двоїсто до NOR.
> - $A \mid A = \neg(A \wedge A) = \neg A$.
> - $A \wedge B = \neg\neg(A \wedge B) = \neg(A \mid B) = (A \mid B) \mid (A \mid B)$.
> - $A \vee B = \neg(\neg A \wedge \neg B) = \neg A \mid \neg B = (A \mid A) \mid
>   (B \mid B)$ (де Морган). $\blacksquare$

![Перевірка базису NAND таблицею істинності: A|A відтворює заперечення, а комбінації штриха Шефера дають кон'юнкцію та диз'юнкцію](img/l03_nand_basis.png)

> **Зауваження (чому це важливо для апаратури).** Те, що NAND (або NOR) сам по собі
> повний, має практичне значення: цілу цифрову схему можна побудувати з елементів
> **одного** типу. Це спрощує виробництво й уніфікує технологію; історично цілі
> сімейства мікросхем виготовляли на самих лише вентилях NAND. До фізичних логічних
> елементів і схем повернемося в [Лекції 4](ODM-L04.md).

---

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

Досі диз'юнкція $\vee$ була нашим «додаванням». Але вона незручна для алгебри: у неї
немає оберненого ($A \vee X = 0$ не завжди розв'язне). Ідея **алгебри Жегалкіна** —
узяти за додавання **виключне «або»** $\oplus$ (додавання за модулем $2$), лишивши
множенням кон'юнкцію $\wedge$. Тоді $\{0,1\}$ стає повноцінним **полем** із двох
елементів, а булеві функції — **многочленами** над ним.

Отже, дві операції алгебри Жегалкіна:

$$
\wedge \ (\text{множення, }xy) \qquad\text{та}\qquad \oplus \ (\text{додавання за модулем } 2).
$$

### Тотожності

Для кон'юнкції зберігаються звичні властивості (як у булевій алгебрі):

$$
x(yz) = (xy)z, \qquad xy = yx, \qquad x \wedge x = x, \qquad x \wedge 0 = 0, \qquad x \wedge 1 = x.
$$

Виключне «або» поводиться як додавання за модулем $2$:

$$
x \oplus (y \oplus z) = (x \oplus y) \oplus z, \qquad x \oplus y = y \oplus x,
$$
$$
x \oplus x = 0 \ \text{(зведення подібних доданків)}, \qquad x \oplus 0 = x,
$$

а кон'юнкція **дистрибутивна** відносно $\oplus$:

$$
x(y \oplus z) = xy \oplus xz.
$$

> **Зауваження (контраст із булевою алгеброю).** Порівняйте $x \wedge x = x$
> (ідемпотентність, лишається) з $x \oplus x = 0$ (замість «ідемпотентності»
> додавання маємо самознищення). Це і є ключова відмінність: $\oplus$ — не насичене
> «або», а справжнє додавання з оберненим, і оберненим до $x$ є сам $x$.

### Самооберненість XOR

Найкорисніша властивість $\oplus$ — те, що **кожен елемент є оберненим сам до себе**.

> **Твердження 3.11 (самооберненість XOR).** Для всіх булевих $a, b$:
> $$ a \oplus a = 0, \qquad a \oplus b \oplus a = b, \qquad b \oplus a \oplus b = a. $$
>
> *Доведення.* Рівність $a \oplus a = 0$ читається з таблиці XOR (рядки $00$ і $11$
> дають $0$) або з $a + a = 2a \equiv 0 \pmod 2$. Далі, користуючись комутативністю
> й асоціативністю:
> $$ a \oplus b \oplus a = (a \oplus a) \oplus b = 0 \oplus b = b. $$
> Симетрично $b \oplus a \oplus b = (b \oplus b) \oplus a = 0 \oplus a = a$.
> $\blacksquare$

> **Застосування (XOR-шифр і обмін значень).** Із $a \oplus b \oplus a = b$ негайно
> випливає, що застосувати XOR із ключем $a$ двічі — означає повернути початкове
> значення: $(b \oplus a) \oplus a = b$. На цьому стоять найпростіший потоковий
> шифр (гамування) та відомий трюк обміну двох змінних без третьої:
> $x \mathrel{\oplus}= y;\ y \mathrel{\oplus}= x;\ x \mathrel{\oplus}= y$.

### Зображення основних операцій через $\{\wedge, \oplus, 1\}$

Набір $\{\wedge, \oplus, 1\}$ (кон'юнкція, XOR та стала $1$) також є повним базисом.
Ось ключові переклади зі звичних операцій:

$$
\neg x = x \oplus 1, \qquad x \vee y = x \oplus y \oplus xy.
$$

> **Твердження 3.12.** $\neg x = x \oplus 1$ і $x \vee y = x \oplus y \oplus xy$.
>
> *Доведення (таблицею істинності).*
>
> | $x$ | $y$ | $x \oplus 1$ | $\neg x$ | $xy$ | $x \oplus y$ | $x \oplus y \oplus xy$ | $x \vee y$ |
> |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
> | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
> | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
> | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
> | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
>
> Стовпець $x \oplus 1$ збігається з $\neg x$, а стовпець $x \oplus y \oplus xy$ —
> з $x \vee y$. $\blacksquare$

![Перевірка зображень у базисі Жегалкіна: заперечення дорівнює x⊕1, а диз'юнкція — x⊕y⊕xy](img/l03_zhegalkin.png)

Маючи $\neg x = x \oplus 1$, легко перекласти й решту операцій:

$$
x \mid y = \neg(xy) = 1 \oplus xy, \qquad x \downarrow y = \neg(x \vee y) = 1 \oplus x \oplus y \oplus xy,
$$
$$
x \to y = \neg x \vee y = 1 \oplus x \oplus xy, \qquad x \leftrightarrow y = 1 \oplus x \oplus y.
$$

(Останню варто запам'ятати: **еквівалентність — це заперечення XOR**, а отже просто
$1 \oplus x \oplus y$.)

### Многочлен Жегалкіна

Розкриваючи всі дужки за наведеними тотожностями й зводячи подібні доданки
($x \oplus x = 0$, $x \wedge x = x$), будь-який булев вираз можна звести до
**канонічного вигляду** — суми (за модулем $2$) різних кон'юнкцій змінних без
заперечень.

> **Означення (многочлен Жегалкіна).** **Многочленом Жегалкіна** функції
> $f(x_1, \dots, x_n)$ називають її запис у вигляді
> $$ f = c_0 \ \oplus\ \bigoplus_{i} c_i\, x_i \ \oplus\ \bigoplus_{i<j} c_{ij}\, x_i x_j
> \ \oplus\ \dots\ \oplus\ c_{12\dots n}\, x_1 x_2 \cdots x_n, $$
> де кожен коефіцієнт $c \in \{0,1\}$, а всі кон'юнкції різні й без повторів змінних
> (многочлен **лінійний** за кожною змінною, бо $x_i \wedge x_i = x_i$).

> **Теорема 3.13 (існування та єдиність).** Кожна булева функція $n$ змінних має
> многочлен Жегалкіна, і притому **єдиний**.
>
> *Доведення (ескіз).* *Існування:* візьмемо ДДНФ функції (Теорема 3.8); мінтерми
> попарно не перетинаються (жоден набір не задовольняє двох одразу), тому диз'юнкцію
> мінтермів можна замінити на $\oplus$ без зміни значення; далі кожне $\neg x_i$
> замінюємо на $x_i \oplus 1$ і розкриваємо дужки за дистрибутивністю
> $x(y \oplus z) = xy \oplus xz$, зводячи подібні. Дістаємо многочлен потрібного
> вигляду. *Єдиність:* різних одночленів (кон'юнкцій підмножин змінних) рівно
> $2^n$, тож різних многочленів рівно $2^{2^n}$ — стільки ж, скільки булевих функцій
> (Теорема 3.1). Оскільки кожна функція має принаймні один многочлен, а кількості
> збігаються, відповідність «функція $\leftrightarrow$ многочлен» бієктивна, тобто
> многочлен єдиний. $\blacksquare$

**Приклад 3.14 (многочлен для диз'юнкції).** Виведемо $x \vee y$ алгебраїчно, без
таблиці. ДДНФ диз'юнкції — це мінтерми на трьох одиничних наборах:
$x \vee y = \neg x\, y \ \vee\ x\, \neg y \ \vee\ x y$. Мінтерми диз'юнктні, тому
замінюємо $\vee$ на $\oplus$, а $\neg$ — на $\ \cdot \oplus 1$:

$$
\begin{aligned}
x \vee y &= (x \oplus 1)y \ \oplus\ x(y \oplus 1) \ \oplus\ xy && \text{(ДДНФ; } \vee\to\oplus,\ \neg t = t\oplus 1)\\
&= (xy \oplus y) \ \oplus\ (xy \oplus x) \ \oplus\ xy && \text{(дистрибутивність)}\\
&= x \oplus y \oplus (xy \oplus xy \oplus xy) && \text{(комутативність, групування)}\\
&= x \oplus y \oplus xy. && (xy \oplus xy = 0)
\end{aligned}
$$

Це збігається з формулою Твердження 3.12.

**Приклад 3.15 (многочлен для імплікації).** Аналогічно
$x \to y = \neg x \vee y$. Скориставшись $a \vee b = a \oplus b \oplus ab$ з
$a = \neg x = x \oplus 1$, $b = y$:

$$
\begin{aligned}
x \to y &= (x \oplus 1) \oplus y \oplus (x \oplus 1)y\\
&= x \oplus 1 \oplus y \oplus (xy \oplus y)\\
&= 1 \oplus x \oplus xy. && (y \oplus y = 0)
\end{aligned}
$$

Отже, $x \to y = 1 \oplus x \oplus xy$ — вільний член дорівнює $1$, тому функція
приймає значення $1$ на «майже всіх» наборах, окрім тих, де $x \oplus xy = 1$, тобто
$x = 1, y = 0$ — саме той єдиний рядок, де імплікація хибна.

> **Зауваження (лінійні функції та застосування).** Функції, у многочлені яких
> **немає жодного добутку** змінних (лише $\oplus$ і, можливо, $1$), називають
> **лінійними**: це $0, 1, x_i, x_i \oplus x_j, \dots$ та функція парності
> $x_1 \oplus \dots \oplus x_n$. Парність — основа **контрольних сум** і **кодів
> виявлення помилок**: один додатковий біт парності виявляє будь-яку одиничну
> помилку в переданому чи записаному блоці даних.

---

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

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

- **Растрові маски й побітові операції.** Однобітове зображення (чорне/біле) — це
  бітова карта; накладання, вирізання та інверсія масок — це покоординатні
  $\wedge, \vee, \neg$ (той самий ізоморфізм множин і бітів із §3.6). Виключне «або»
  двох версій растру $\text{стара} \oplus \text{нова}$ висвічує **рівно ті пікселі,
  що змінилися**, — зручний спосіб порівняти дві коректури.
- **Умови в препресі та автоматизації.** Правила складання завдань на друк —
  булеві вирази: «друкувати, якщо (кольорове $\wedge\ \neg$чернетка) $\vee$ ручне
  перевизначення». Спрощення таких умов за законами §3.5 усуває зайві перевірки й
  «мертві» гілки.
- **Порогові рішення півтонування.** Перетворення напівтонового зображення на
  растрову (бінарну) точку — це булева функція «яскравість вища за поріг?»; матриці
  дизерингу задають цілі таблиці таких рішень.
- **Один тип вентиля в контролерах.** Схеми керування друкарським та
  фінішним обладнанням реалізують на стандартних логічних елементах; повнота NAND і
  NOR (§3.7) означає, що будь-яку логіку керування можна зібрати з елементів одного
  типу.
- **Контроль цілісності файлів.** Біти парності та контрольні суми на основі XOR
  (лінійні функції Жегалкіна, §3.8) виявляють спотворення файлів під час передавання
  на RIP чи запису — одиничний збій змінює парність і одразу помітний.

---

## Підсумок

- **Висловлення** — розповідне речення, яке однозначно істинне або хибне; значення
  кодуємо як $1$ (істина, $T$, І) та $0$ (хиба, $F$, Х). Складені висловлення
  **істиннісно-функціональні**: їхнє значення залежить лише від значень частин і
  сполучників.
- **Булева функція** $n$ змінних — це таблиця істинності з $2^n$ рядків; таких
  функцій рівно $2^{2^n}$ (**доведено** підрахунком рядків, а тоді заповнень). Для
  $n=2$ маємо $16$ функцій $F_0, \dots, F_{15}$.
- Основні операції та їхні таблиці: заперечення $\neg$, кон'юнкція $\wedge$ (AND),
  диз'юнкція $\vee$ (OR, включне), виключне «або» $\oplus$ (XOR), стрілка Пірса
  $\downarrow$ (NOR), штрих Шефера $\mid$ (NAND), еквівалентність $\leftrightarrow$
  (XNOR). Пріоритет: $\neg \succ \wedge \succ \vee, \oplus \succ \to, \leftrightarrow$.
- **Аксіоми** (комутативність, асоціативність, дистрибутивність, поглинання,
  доповнення) та **закони** (ідемпотентність, дії з $0$ та $1$, доповнення, де
  Моргана, подвійне заперечення) йдуть **дуальними парами**; ключові доведено
  таблицею істинності. Тотожності можна виводити й **алгебраїчно**.
- **Логіка, множини й біти — одна структура:** $\wedge\leftrightarrow\cap$,
  $\vee\leftrightarrow\cup$, $\neg\leftrightarrow$ доповнення, $0\leftrightarrow\varnothing$,
  $1\leftrightarrow U$; відповідність $A\mapsto\chi_A$ зберігає всі операції, тож
  кожен закон переноситься між трьома «обличчями».
- **Функціональна повнота:** базис $\{\neg,\wedge,\vee\}$ (ТА-АБО-НІ) виражає будь-яку
  функцію (через ДДНФ); понад те, повні навіть окремо взяті $\downarrow$ (NOR) та
  $\mid$ (NAND) — з формулами $\neg A = A\downarrow A = A\mid A$ і т. д.
- **Алгебра Жегалкіна:** операції $\wedge$ (множення) та $\oplus$ (додавання за
  модулем $2$); XOR самооборотне ($a\oplus a=0$, $a\oplus b\oplus a=b$); кожна
  функція має **єдиний многочлен Жегалкіна**; переклади $\neg x=x\oplus1$,
  $x\vee y=x\oplus y\oplus xy$, $x\leftrightarrow y=1\oplus x\oplus y$.
- **Далі:** у [Лекції 4](ODM-L04.md) — логічні елементи та схеми, нормальні форми
  ДНФ/КНФ (ДДНФ/ДКНФ) та систематична **мінімізація** булевих функцій (зокрема карти
  Карно).

## Вправи

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

1. Класифікуйте кожне речення як висловлення чи ні; для висловлення вкажіть значення,
   якщо його можна визначити: (а) «$17$ — просте число»; (б) «Прочитайте Лекцію 3»;
   (в) «$x^2 = 4$»; (г) «Кожне парне число, більше за $2$, є сумою двох простих»;
   (ґ) «Ой!».
2. З пам'яті випишіть таблиці істинності операцій $\neg A$, $A \wedge B$,
   $A \vee B$, $A \oplus B$, $A \downarrow B$, $A \mid B$, $A \leftrightarrow B$. Для
   кожної однією фразою скажіть, коли вона дорівнює $1$.
3. Обчисліть значення $(A \vee B) \wedge \neg C$ та $A \to (B \vee \neg C)$ при
   $A = 1$, $B = 0$, $C = 1$.
4. Розставте всі дужки згідно з пріоритетом: (а) $\neg A \wedge B \vee C$;
   (б) $A \vee B \to \neg C$; (в) $\neg\neg A \wedge B$.
5. Дайте для кожної з операцій $\wedge$, $\vee$, $\neg$, $0$, $1$ її відповідник в
   алгебрі множин.

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

6. Побудуйте повну таблицю істинності виразу $(A \vee \neg B) \wedge C$ і вкажіть, на
   скількох із $8$ рядків він дорівнює $1$.
7. Доведіть таблицею істинності другий закон де Моргана
   $\neg(A \vee B) = \neg A \wedge \neg B$ (порівняйте з доведенням у тексті).
8. Спростіть алгебраїчно, називаючи кожен закон: (а) $(A \wedge B) \vee (A \wedge
   \neg B)$; (б) $(A \vee B) \wedge (\neg A \vee B)$. Кожен вираз має звестися до
   однієї змінної.
9. Користуючись лише формулами базису NAND ($\neg A = A \mid A$, …), запишіть
   $A \vee B$ через штрих Шефера й перевірте результат таблицею істинності.
10. Доведіть тотожність $a \oplus b \oplus a = b$ спершу алгебраїчно (як у Твердженні
    3.11), а тоді таблицею істинності для всіх чотирьох наборів $(a,b)$.
11. Побудуйте многочлен Жегалкіна функції $A \leftrightarrow B$ (еквівалентність) і
    переконайтеся, що він дорівнює $1 \oplus A \oplus B$.

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

12. Скільки є булевих функцій $3$ змінних? $5$ змінних? Зі $16$ функцій двох змінних
    скільки **комутативних** (тобто $f(A,B) = f(B,A)$)? Обґрунтуйте останнє число.
13. Виразіть кон'юнкцію $A \wedge B$ **лише** через стрілку Пірса $\downarrow$,
    використавши якнайменше входжень операції, і доведіть коректність.
14. Побудуйте многочлен Жегалкіна для «мажоритарної» функції трьох змінних
    $\mathrm{maj}(x,y,z)$, що дорівнює $1$, коли принаймні дві змінні дорівнюють $1$.
    (Підказка: почніть з ДДНФ або скористайтеся тим, що
    $\mathrm{maj} = xy \vee yz \vee xz$, і перекладіть у $\oplus$.)
15. Функцію називають **лінійною**, якщо її многочлен Жегалкіна не містить добутків
    змінних. Скільки є лінійних функцій $n$ змінних? Скільки з них істотно залежать
    від усіх $n$ змінних?