# 2. Методичні вказівки Цей розділ **самодостатній**: він збирає всю теорію теми — досконалі форми, алгебраїчну мінімізацію та карти Карно — разом із прийомами, потрібними для виконання завдань із [3task.md](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$). | Закон | Для $\wedge$ | Для $\vee$ | |---|---|---| | Комутативність | $xy = yx$ | $x \vee y = y \vee x$ | | Асоціативність | $x(yz) = (xy)z$ | $x \vee (y \vee z) = (x \vee y) \vee z$ | | Дистрибутивність | $x(y \vee z) = xy \vee xz$ | $x \vee yz = (x \vee y)(x \vee z)$ | | Ідемпотентність | $xx = x$ | $x \vee x = x$ | | Константи | $x \cdot 1 = x,\ \ x \cdot 0 = 0$ | $x \vee 0 = x,\ \ x \vee 1 = 1$ | | Доповнення | $x\,\overline{x} = 0$ | $x \vee \overline{x} = 1$ | | Подвійне заперечення | $\overline{\overline{x}} = x$ | | | Поглинання | $x(x \vee y) = x$ | $x \vee xy = x$ | | Склеювання | $(x \vee y)(x \vee \overline{y}) = x$ | $xy \vee x\overline{y} = x$ | | Де Морган | $\overline{xy} = \overline{x} \vee \overline{y}$ | $\overline{x \vee y} = \overline{x}\,\overline{y}$ | Корисний наслідок (варіант поглинання): $\;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$. У кожну клітину ставлять значення функції на відповідному наборі. ![Розмітка карти 4×4: у клітинах номери мінтермів; краї карти сусідні циклічно](img/p3_layout.png) Ключова властивість — **циклічне (тороїдальне) сусідство**: сусідять не лише внутрішні клітини, а й **перший та останній стовпці** ($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): | $xy \backslash zt$ | 00 | 01 | 11 | 10 | |:--:|:--:|:--:|:--:|:--:| | **00** | 1 | 1 | 0 | 0 | | **01** | 1 | 1 | 0 | 0 | | **11** | 1 | 1 | 1 | 0 | | **10** | 1 | 1 | 1 | 0 | **Крок 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\ }$$ ![Демонстраційна карта: група-8 $\overline{z}$ та група-4 $xt$ покривають усі одиниці](img/p3_kmap_mdnf.png) **Крок 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)\ }$$ ![Та сама карта: дві групи нулів дають дві елементарні диз'юнкції МКНФ](img/p3_kmap_mknf.png) **Перевірка узгодженості.** Розкривши дужки МКНФ, $(x \vee \overline{z})(\overline{z} \vee t) = \overline{z} \vee xt$ — той самий вираз, що й МДНФ. Обидві форми задають одну функцію; зауважте, що вона **не залежить** від $y$ (змінна $y$ не входить до жодного терму), і карта унаочнює це, бо верхня й нижня половини по $y$ однакові. ## 2.7 Робочий чеклист - Щоб дістати **ДДНФ/ДКНФ**: складіть таблицю істинності; візьміть **диз'юнкцію мінтермів рядків-одиниць** (ДДНФ) або **кон'юнкцію макстермів рядків-нулів** (ДКНФ); стежте за правилом полярності (мінтерм: заперечення там, де $0$; макстерм: там, де $1$). - **Алгебраїчно**: усуньте $\to,\ \leftrightarrow,\ \oplus$; внесіть заперечення за де Морганом; спрощуйте склеюванням і поглинанням, поки можливо. - На **карті Карно**: групуйте у **степені двійки**, **якомога більшими** блоками, з урахуванням **циклічного** сусідства, і покрийте всі одиниці найменшим числом груп; терм групи читайте зі сталих літералів. - Для **МКНФ**: групуйте **нулі** (або переведіть МДНФ функції $\overline{f}$ за де Морганом), застосовуючи дзеркальне правило полярності.