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

Огляд #

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

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

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

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

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$ = «Погода гарна».

Тоді:

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

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 = 6$ маємо $2^{64} \approx 1{,}8 \times 10^{19}$ функцій. Саме цей вибух пояснює, чому потрібні систематичні методи спрощення (Лекція 4): перебрати всі функції вручну неможливо.

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

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

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

• $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'$.

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

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

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

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

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

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

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

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

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

Еквівалентність (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 \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$, а тоді їхню диз’юнкцію:

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

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

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

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

• Поглинання. $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 Закони (тотожності) булевої алгебри #

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

У законі «дії з $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).

Приклад 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. Причина в тому, що обидві структури — окремі випадки однієї абстрактної структури, булевої алгебри, і їх можна вишикувати операція проти операції.

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

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

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

Наочно: на діаграмі Венна кожній точці універсуму відповідає рядок таблиці істинності (за тим, у яких колах вона лежить), а заштрихована область — це саме ті рядки, де складений вираз дорівнює $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$-бітове слово, а операції над множинами виконують побітовими командами процесора.

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

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. Уже зараз важливий висновок: кожну з $16$ функцій двох змінних можна записати через ТА-АБО-НІ, і ось цей повний перелік (зі слайдів лекції):

Зверніть увагу, як звичні операції лягли в перелік: $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$

Базис 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 (або NOR) сам по собі повний, має практичне значення: цілу цифрову схему можна побудувати з елементів одного типу. Це спрощує виробництво й уніфікує технологію; історично цілі сімейства мікросхем виготовляли на самих лише вентилях NAND. До фізичних логічних елементів і схем повернемося в Лекції 4.

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$

Маючи $\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 чи запису — одиничний збій змінює парність і одразу помітний.