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

Цей розділ самодостатній: він збирає всю теорію теми — досконалі форми, алгебраїчну мінімізацію та карти Карно — разом із прийомами, потрібними для виконання завдань із 3task.md. Наприкінці наведено один повний демонстраційний приклад на власних даних (відмінних від будь-якого варіанта), щоб показати техніку, не розв’язуючи чужого варіанта.

2.1 Булеві функції та таблиці істинності #

Булева функція $n$ змінних кожній з $2^n$ комбінацій входів (наборів, інтерпретацій) ставить у відповідність значення з $\{0,1\}$; її таблиця істинності перелічує всі ці набори. Функцію будують зі змінних, констант $0,1$ та зв’язок $\neg$ (заперечення, пишемо $\overline{x}$), $\wedge$ (кон’юнкція, пишемо підряд $xy$) і $\vee$ (диз’юнкція). Літерал — це змінна або її заперечення ($x$ чи $\overline{x}$). Пріоритет: $\neg \succ \wedge \succ \vee$.

Дві похідні зв’язки, які трапляються в умовах, зводяться до базових так:

$$x \to y \;=\; \overline{x} \vee y, \qquad x \leftrightarrow y \;=\; xy \vee \overline{x}\,\overline{y}, \qquad x \oplus y \;=\; x\overline{y} \vee \overline{x}y .$$

2.2 Досконалі форми: ДДНФ і ДКНФ #

Дві особливі форми читаються прямо з таблиці істинності. (У літературі їх звуть також досконалими або повними; російсько-українські скорочення СДНФ/СКНФ позначають ті самі дві форми. Загальніше, ДНФ — це диз’юнкція елементарних кон’юнкцій, а КНФ — кон’юнкція елементарних диз’юнкцій.)

• Конституента одиниці (мінтерм) рядка — це кон’юнкція всіх $n$ змінних, де кожну взято без заперечення, якщо її значення $1$, і з запереченням, якщо $0$; вона дорівнює $1$ рівно на цьому рядку. ДДНФ (досконала ДНФ) — це диз’юнкція мінтермів усіх рядків зі значенням $1$.
• Конституента нуля (макстерм) рядка — це диз’юнкція всіх $n$ змінних, де кожну взято без заперечення, якщо її значення $0$, і з запереченням, якщо $1$; вона дорівнює $0$ рівно на цьому рядку. ДКНФ (досконала КНФ) — це кон’юнкція макстермів усіх рядків зі значенням $0$.

Правило полярності. У мінтермі змінну заперечують там, де її значення $0$; у макстермі — навпаки, там, де її значення $1$. Це «дзеркальне» правило далі діє й для груп на карті Карно.

Наприклад, якщо $f(x,y,z)$ дорівнює $1$ лише на рядках $(1,1,1)$ і $(0,0,0)$, то

$$\text{ДДНФ:}\quad f = xyz \vee \overline{x}\,\overline{y}\,\overline{z}.$$

Досконалі форми єдині, але зазвичай не мінімальні: кожен рядок додає повний терм, і мінімізація прибирає надлишок.

2.3 Закони булевої алгебри #

Мінімізація переписує формулу за цими тотожностями (закони йдуть двоїстими парами — заміна $\wedge \leftrightarrow \vee$ і $0 \leftrightarrow 1$).

Корисний наслідок (варіант поглинання): $\;x \vee \overline{x}y = x \vee y\;$ і двоїсто $\;x(\overline{x} \vee y) = xy$.

2.4 Мінімізація законами (алгебраїчно) #

Щоб мінімізувати рівносильними перетвореннями:

1. Усуньте імплікацію та еквіваленцію за тотожностями з §2.1 ($x \to y = \overline{x} \vee y$ тощо).
2. Внесіть заперечення всередину за де Морганом і подвійним запереченням, поки кожне $\neg$ не стоятиме над окремою змінною.
3. Спрощуйте дистрибутивністю, склеюванням ($xy \vee x\overline{y}=x$), поглинанням ($x \vee xy = x$) та законами доповнення, аж поки жодне правило не застосовне. Результат — МДНФ (двоїсто — МКНФ).

Демонстрація методу. Спростимо $\;g = \overline{\overline{x} \vee y} \vee xy \vee \overline{x}z\;$ (дані навмисно інші, ніж у варіантах):

$$\begin{aligned} g &= x\overline{y} \vee xy \vee \overline{x}z && \text{(де Морган: } \overline{\overline{x} \vee y}=x\overline{y}\text{)}\\ &= x(\overline{y} \vee y) \vee \overline{x}z && \text{(дистрибутивність)}\\ &= x \vee \overline{x}z && \text{(} \overline{y}\vee y=1;\ x\cdot 1=x\text{)}\\ &= x \vee z. && \text{(варіант поглинання)} \end{aligned}$$

Слабке місце алгебраїчного методу — легко не помітити можливе спрощення. Карта Карно робить усі допустимі групування видимими.

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

Карта Карно — це таблиця істинності, викладена на ґратці так, щоб фізично сусідні клітини різнилися рівно в одній змінній (упорядкування за кодом Грея). Для чотирьох змінних $x,y,z,t$ карта — ґратка $4 \times 4$: рядки позначено парою $xy$, стовпці — парою $zt$, обидві в коді Грея $00,\,01,\,11,\,10$. У кожну клітину ставлять значення функції на відповідному наборі.

Ключова властивість — циклічне (тороїдальне) сусідство: сусідять не лише внутрішні клітини, а й перший та останній стовпці ($zt=00$ і $zt=10$) і так само перший та останній рядки ($xy=00$ і $xy=10$). Тому групою може бути й «чотири кути» карти, і пара клітин на протилежних краях.

Зчитування МДНФ (по одиницях).

• Групуйте одиниці у прямокутні блоки розміром $1,2,4,8,16$ (степінь двійки), кожен — якомога більший;
• сусідство замикається по колу: крайні стовпці сусідні, крайні рядки сусідні;
• група з $2^k$ клітин вилучає $k$ змінних; її терм (елементарна кон’юнкція) — це кон’юнкція літералів, що лишаються сталими в межах групи, за правилом: стала $1 \Rightarrow$ змінна без заперечення, стала $0 \Rightarrow$ з запереченням;
• оберіть найменше число найбільших груп, які разом покривають усі одиниці (перекриття дозволені); МДНФ — диз’юнкція термів усіх груп.

Зчитування МКНФ (по нулях). Ту саму процедуру застосовують до нулів. Групування нулів дає МДНФ функції $\overline{f}$; заперечивши її за де Морганом, кожну кон’юнкцію обертають на диз’юнкцію — це й є МКНФ функції $f$. На практиці кожну групу нулів одразу читають як одну елементарну диз’юнкцію за дзеркальним правилом полярності: стала $0 \Rightarrow$ змінна без заперечення, стала $1 \Rightarrow$ з запереченням.

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

2.6 Демонстраційний приклад (карта Карно) #

Розгляньмо функцію $f(x,y,z,t)$, задану картою (це інші дані, ніж у будь-якому варіанті завдання 2):

Крок 1. МДНФ — групуємо одиниці. Дві групи покривають усі вісім одиниць:

• блок з $8$ клітин — обидва стовпці $zt=00,01$ (де $z=0$), усі чотири рядки; сталою лишається тільки $z=0$, тож терм — $\overline{z}$;
• блок з $4$ клітин — рядки $xy=11,10$ (де $x=1$) і стовпці $zt=01,11$ (де $t=1$); сталі $x=1$ та $t=1$, тож терм — $xt$.

$$\boxed{\ \text{МДНФ:}\quad f = \overline{z} \vee xt\ }$$

Крок 2. МКНФ — групуємо нулі. Нулі стоять у стовпці $zt=10$ та у верхній частині стовпця $zt=11$. Дві групи нулів:

• блок з $4$ клітин — стовпець $zt=10$ (де $z=1,\ t=0$), усі рядки; сталі $z=1$ і $t=0$; за дзеркальним правилом полярності це диз’юнкція $(\overline{z} \vee t)$;
• блок з $4$ клітин — рядки $xy=00,01$ (де $x=0$) і стовпці $zt=11,10$ (де $z=1$); сталі $x=0$ і $z=1$, звідки диз’юнкція $(x \vee \overline{z})$.

$$\boxed{\ \text{МКНФ:}\quad f = (x \vee \overline{z})(\overline{z} \vee t)\ }$$

Перевірка узгодженості. Розкривши дужки МКНФ, $(x \vee \overline{z})(\overline{z} \vee t) = \overline{z} \vee xt$ — той самий вираз, що й МДНФ. Обидві форми задають одну функцію; зауважте, що вона не залежить від $y$ (змінна $y$ не входить до жодного терму), і карта унаочнює це, бо верхня й нижня половини по $y$ однакові.

2.7 Робочий чеклист #

• Щоб дістати ДДНФ/ДКНФ: складіть таблицю істинності; візьміть диз’юнкцію мінтермів рядків-одиниць (ДДНФ) або кон’юнкцію макстермів рядків-нулів (ДКНФ); стежте за правилом полярності (мінтерм: заперечення там, де $0$; макстерм: там, де $1$).
• Алгебраїчно: усуньте $\to,\ \leftrightarrow,\ \oplus$; внесіть заперечення за де Морганом; спрощуйте склеюванням і поглинанням, поки можливо.
• На карті Карно: групуйте у степені двійки, якомога більшими блоками, з урахуванням циклічного сусідства, і покрийте всі одиниці найменшим числом груп; терм групи читайте зі сталих літералів.
• Для МКНФ: групуйте нулі (або переведіть МДНФ функції $\overline{f}$ за де Морганом), застосовуючи дзеркальне правило полярності.

Practical/Practical3/2method.md · 14.7 KB · updated 2026-08-04 14:37