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

Огляд #

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

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

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

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

Усе тут — комбінаційна логіка: вихід залежить лише від поточних входів, без пам’яті. Оскільки істиннісних значень лише два, кожна функція $n$ змінних повністю описана скінченною таблицею істинності з $2^n$ рядків — цим фактом ми користуємося постійно. Побудовані нижче схеми ви складатимете власноруч в онлайн-симуляторі під час лабораторної роботи 1; ця лекція — її теоретична основа. Далі, у Лекції 5, ми переходимо від булевих схем до мови математичної логіки — висловлень та їхніх логічних зв’язок.

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

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

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

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

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

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

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

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

Виключне «або» $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. — $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-канальний між виходом і землею; входом керуються обидва затвори.

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

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

Алгебрична мінімізація застосовує тотожності Лекції 3, щоб зменшити формулу, зберігши її таблицю істинності. Робочі закони:

Закон склеювання $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$. Ведемо перетворення покроково, на кожному кроці посилаючись на закон.

Отже,

$$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$):

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

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)$ зі слайда #

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

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

$$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\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$: сусідні підписи (зокрема й «замикання» останнього з першим) різняться рівно в одному біті.

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

Твердження 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$, стовпці $yz$ у коді Грея:

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

Типова помилка. Не підписуйте осі $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$:

• Ліва половина (стовпці $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$:

Чотири одиниці стоять у стовпцях $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=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}$).

• Рядки $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$:

Використовуючи $\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$.

Кількість вентилів: $1$ НЕ $+\ 1$ І $+\ 1$ АБО $=\ 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}$ окремо породжувати не треба — його «постачає» другий вентиль):

Переписування у базис АБО-НІ (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. Розгляньте функцію, задану на карті чотирьох змінних, у якій одиниці розташовані «в шаховому порядку» (немає двох сусідніх одиниць). Скільки груп матиме її МДНФ і чому карти Карно тут не дають виграшу? Зв’яжіть відповідь із поняттям простої імпліканти.

Lectures/ODM-L04.md · 63.4 KB · updated 2026-08-04 15:45