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

Цей розділ самодостатній: він містить усю теорію теми роботи — від логічних елементів до алгебри Жегалкіна — та опис середовища logic.ly, у якому виконують завдання 4task.md. Наприкінці наведено наскрізний демонстраційний приклад, що проходить увесь шлях умова → таблиця → форма → мінімізація → схема на даних, які не збігаються з жодним варіантом. Зовнішні джерела не потрібні; ширше поняття подано в Лекції 3 та Лекції 4.

2.1 Логічні змінні, функції та таблиця істинності #

Логічна (булева) змінна набуває одного з двох значень: 1 (істина, True, T, або І) чи 0 (хиба, False, F, або Х). У цій роботі кожен перемикач — це логічна змінна: увімкнено $=1$, вимкнено $=0$.

Означення (булева функція). Булева функція від $n$ змінних — це відображення $F\colon \{0,1\}^{n} \to \{0,1\}$, яке кожному наборові значень входів зіставляє один вихід $0$ або $1$.

Оскільки кожна з $n$ змінних незалежно набуває $2$ значень, різних вхідних наборів рівно $2^{n}$. Функцію повністю задає таблиця істинності — перелік усіх $2^{n}$ наборів разом зі значенням $F$ на кожному. Для чотирьох перемикачів $A, B, C, D$ таких рядків $2^{4} = 16$.

Зауваження (порядок рядків). Рядки прийнято впорядковувати за зростанням двійкового числа $\overline{ABCD}$: від $0000$ до $1111$. Сталий порядок робить побудову форм і карт Карно механічною й убезпечує від пропусків.

Комбінаційна схема, яку ви будуватимете, — це апаратне втілення такої функції: стан входів однозначно визначає вихід, без пам’яті про попередні стани.

2.2 Логічні елементи (вентилі) та їх позначення #

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

Зведена таблиця істинності двомісних операцій:

Умовні графічні позначення цих елементів (стандарт ANSI/IEEE, які використовує й logic.ly) наведено на рисунку. Маленьке кружальце на виході означає інверсію: воно перетворює ТА на ТА-НІ, АБО на АБО-НІ, а буфер на елемент НІ.

Зауваження (число входів). Кон’юнкцію та диз’юнкцію означують і для трьох, і для більшого числа входів: $A\wedge B\wedge C$ дорівнює $1$ лише коли всі входи $1$, а $A\vee B\vee C$ дорівнює $0$ лише коли всі входи $0$. У logic.ly кількість входів вентиля задають у його параметрах.

2.3 Канонічні форми: ДДНФ і ДКНФ #

З таблиці істинності функцію завжди можна виписати формулою двома стандартними способами. Обидва спираються на елементарні «цеглинки».

Означення (мінтерм, макстерм). Мінтерм (конституента одиниці) — це кон’юнкція всіх змінних, у якій кожна змінна входить один раз: пряма, якщо в даному рядку вона дорівнює $1$, та інвертована, якщо $0$. Макстерм (конституента нуля) — це диз’юнкція всіх змінних: пряма, якщо змінна в рядку дорівнює $0$, та інвертована, якщо $1$.

Наприклад, для рядка $A{=}1, B{=}0, C{=}1, D{=}0$ мінтерм — це $A\overline{B}C\overline{D}$, а макстерм — $\overline{A}\vee B\vee \overline{C}\vee D$. Мінтерм дорівнює $1$ рівно у своєму рядку; макстерм дорівнює $0$ рівно у своєму рядку.

Означення (ДДНФ). Досконала диз’юнктивна нормальна форма — це диз’юнкція мінтермів, узятих по всіх рядках, де $F=1$. Вона істинна саме тоді, коли істинний хоча б один із цих мінтермів, тобто саме на одиничних наборах.

Означення (ДКНФ). Досконала кон’юнктивна нормальна форма — це кон’юнкція макстермів, узятих по всіх рядках, де $F=0$. Вона хибна саме тоді, коли хибний хоча б один із цих макстермів, тобто саме на нульових наборах.

Ці дві форми канонічні: для заданої функції кожна визначена однозначно. Правило вибору: якщо одиниць у таблиці менше — коротшою буде ДДНФ; якщо менше нулів — ДКНФ. Обидві, як правило, ще піддаються мінімізації (§2.4).

Типова помилка (переплутати правила знаків). У ДДНФ (по одиницях) змінну беруть прямою при $1$; у ДКНФ (по нулях) — навпаки, прямою при $0$. Проговорюйте подумки: «мінтерм має дорівнювати $1$ у своєму рядку, тож при $0$ змінну треба інвертувати».

2.4 Мінімізація картами Карно #

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

Код Грея. Рядки й стовпці нумерують не звичайним двійковим кодом, а кодом Грея $00, 01, 11, 10$, у якому кожен наступний код відрізняється від попереднього одним бітом. Для чотирьох змінних карта має розмір $4\times4$: рядки позначають парою $AB$, стовпці — парою $CD$.

Сусідність із «обгортанням». Ліве й праве ребра карти вважають сусідніми, так само верхнє й нижнє: карта замкнена в тор. Тому чотири кутові клітинки — теж сусіди.

Правила групування.

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

Від груп — до форми.

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

Зауваження (невизначені набори). Якщо для деяких наборів значення функції байдуже (позначають «$-$» або $d$), їх дозволено долучати до груп так, як вигідно для збільшення групи. У задачах цієї роботи функція визначена на всіх $16$ наборах, тож невизначених клітинок не буде.

Наскрізний приклад мінімізації показано в §2.8 (рисунок карти з двома групами).

2.5 Базиси ТА-НІ та АБО-НІ #

Набір операцій називають функціонально повним, якщо через нього можна виразити будь-яку булеву функцію. Класичний повний набір — $\{\neg, \wedge, \vee\}$. Виявляється, достатньо однієї операції: штриха Шефера або стрілки Пірса. Саме тому мікросхеми часто будують суцільно з елементів ТА-НІ чи АБО-НІ.

Базис ТА-НІ (штрих Шефера, $\mid$). Формули заміни (за Лекцією 3):

$$\overline{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).$$

Базис АБО-НІ (стрілка Пірса, $\downarrow$).

$$\overline{A} = A \downarrow A, \qquad A \wedge B = (A \downarrow A) \downarrow (B \downarrow B), \qquad A \vee B = (A \downarrow B) \downarrow (A \downarrow B).$$

На практиці зручні два дзеркальні факти:

• ДНФ (сума добутків) природно лягає у ТА-НІ. Двоярусна схема ТА→АБО перетворюється на двоярусну ТА-НІ→ТА-НІ: досить замінити всі елементи на ТА-НІ.
• КНФ (добуток сум) природно лягає в АБО-НІ. Двоярусна схема АБО→ТА перетворюється на АБО-НІ→АБО-НІ.

Тому для базису ТА-НІ зручно виходити з МДНФ, а для АБО-НІ — з МКНФ. Конкретні викладки — у §2.8.

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

Алгебра Жегалкіна будується на двох операціях — додавання за модулем 2 $\oplus$ (те саме, що XOR) і множення $\wedge$ (кон’юнкція) — та константі $1$. Ключові тотожності (за Лекцією 3):

$$A \oplus A = 0, \qquad A \oplus 0 = A, \qquad A \oplus 1 = \overline{A},$$

$$A \wedge (B \oplus C) = (A\wedge B) \oplus (A \wedge C) \quad (\text{дистрибутивність}).$$

Заперечення й диз’юнкцію виражають через $\oplus$ і $\wedge$ так:

$$\overline{A} = A \oplus 1, \qquad A \vee B = A \oplus B \oplus A\wedge B.$$

Означення (поліном Жегалкіна). Поліномом Жегалкіна функції називають її запис у вигляді суми за модулем 2 різних кон’юнкцій змінних (і, можливо, вільного члена $1$), наприклад $F = 1 \oplus C \oplus AB \oplus ABCD$. Для кожної булевої функції такий запис єдиний.

Щоб отримати поліном, зазвичай беруть будь-яку формулу функції (найзручніше — ДДНФ або вже знайдену МДНФ), замінюють $\overline{X}$ на $X\oplus 1$ та $X\vee Y$ на $X\oplus Y\oplus XY$, розкривають дужки за дистрибутивністю й скорочують однакові доданки парами (бо $t \oplus t = 0$). Приклад — у §2.8.

2.7 Середовище logic.ly #

Роботу виконують в онлайн-редакторі логічних схем logic.ly (демо-версія: https://logic.ly/demo/); реєстрація не потрібна, усе працює у браузері. Ліва панель містить елементи, які перетягують на центральне поле. Потрібні в роботі:

Вхідні керуючі елементи (Input Controls).

• Перемикач (Toggle Switch) — залежно від положення подає логічну $1$ або $0$; саме ним задають входи $A, B, C, D$.
• Генератор тактів (Clock) — по черзі подає $1$ і $0$ із заданою частотою.
• Логічна 1 (High Constant) — постійно подає $1$; Логічний 0 (Low Constant) — постійно подає $0$.

Вихідні елементи (Output Controls).

• Лампочка (Light Bulb) — світиться, коли на вхід подано $1$; це вихід $F$.
• Числова панель (4-Bit Digit) — показує шістнадцяткову цифру за поданими бітами.

Логічні елементи (Logic Gates). Буфер (Buffer), ТА (AND), АБО (OR), Викл. АБО (XOR), НІ (NOT), ТА-НІ (NAND), АБО-НІ (NOR), Викл. АБО-НІ (NXOR).

Інші (Other). Підпис (Label) — для позначення елементів.

Як будувати схему. Елементи перетягують на поле й з’єднують, ведучи лінію від виходу одного елемента до входу іншого. Виділивши елемент, у правому нижньому куті відкривають панель параметрів: для вхідних/вихідних елементів там задають змінну, за яку відповідає елемент (наприклад, підписати перемикачі $A, B, C, D$), а для вентилів — кількість вхідних конекторів. Зібравши схему, перемикають входи й перевіряють, що лампочка світиться саме на тих наборах, де $F=1$ у вашій таблиці.

Порада. Будуйте схему точно за формулою: спершу розставте перемикачі та потрібні елементи НІ (інвертори), потім елементи одного ярусу (усі ТА для ДДНФ або всі АБО для ДКНФ), нарешті — вихідний елемент, і лише тоді проводьте з’єднання. Кожну готову схему знімайте для звіту.

2.8 Наскрізний демонстраційний приклад #

Пройдемо весь шлях на прикладі, умова якого не збігається з жодним варіантом 4task.md, тож він показує техніку, а не розв’язок завдання.

Умова (демонстраційна). Лампа світиться тоді й лише тоді, коли одночасно ввімкнено перемикачі $A$ і $B$, або коли обидва перемикачі $C$ і $D$ вимкнено.

Крок 1. Формалізація. Словам відповідає функція

$$F(A,B,C,D) = (A \wedge B) \vee (\overline{C} \wedge \overline{D}).$$

Крок 2. Таблиця істинності. Обчислюємо $F$ на всіх $16$ наборах (пряма перевірка за означеннями $\wedge, \vee, \neg$):

Одиниці стоять у рядках $0000, 0100, 1000, 1100, 1101, 1110, 1111$ (сім рядків), нулі — у решті дев’яти.

Крок 3. ДДНФ (по семи одиницях). Для кожного одиничного рядка беремо мінтерм:

$$\begin{aligned} \text{ДДНФ:}\quad F =\ & \overline{A}\,\overline{B}\,\overline{C}\,\overline{D} \ \vee\ \overline{A}\,B\,\overline{C}\,\overline{D} \ \vee\ A\,\overline{B}\,\overline{C}\,\overline{D} \ \vee\ A\,B\,\overline{C}\,\overline{D} \\ &\vee\ A\,B\,\overline{C}\,D \ \vee\ A\,B\,C\,\overline{D} \ \vee\ A\,B\,C\,D. \end{aligned}$$

Крок 4. ДКНФ (по дев’яти нулях). Для кожного нульового рядка беремо макстерм (пряма змінна при $0$):

$$\begin{aligned} \text{ДКНФ:}\quad F =\ & (A\vee B\vee C\vee \overline{D})\, (A\vee B\vee \overline{C}\vee D)\, (A\vee B\vee \overline{C}\vee \overline{D}) \\ &\cdot(A\vee \overline{B}\vee C\vee \overline{D})\, (A\vee \overline{B}\vee \overline{C}\vee D)\, (A\vee \overline{B}\vee \overline{C}\vee \overline{D}) \\ &\cdot(\overline{A}\vee B\vee C\vee \overline{D})\, (\overline{A}\vee B\vee \overline{C}\vee D)\, (\overline{A}\vee B\vee \overline{C}\vee \overline{D}). \end{aligned}$$

Крок 5. Мінімізація картою Карно. Переносимо одиниці на карту $4\times4$ (рядки $AB$, стовпці $CD$ у коді Грея) і групуємо:

Дві максимальні групи по чотири клітинки:

• увесь рядок $AB=11$ — стала лише пара $A=1, B=1$, тож терм $A\wedge B$;
• увесь стовпець $CD=00$ — сталі $C=0, D=0$, тож терм $\overline{C}\,\overline{D}$.

Групи покривають усі сім одиниць (вони перетинаються в клітинці $AB{=}11, CD{=}00$). Звідси

$$\boxed{\ \text{МДНФ:}\quad F = A B \vee \overline{C}\,\overline{D}.\ }$$

Для МКНФ групуємо нулі. Мінімальне покриття дають чотири групи по дві клітинки, що відповідають чотирьом простим імплікантам; кожна дає диз’юнктивний терм:

$$\boxed{\ \text{МКНФ:}\quad F = (A\vee \overline{C})\,(A\vee \overline{D})\,(B\vee \overline{C})\,(B\vee \overline{D}).\ }$$

Перевірка розкриттям підтверджує рівність: $(A\vee \overline{C})(A\vee \overline{D}) = A \vee \overline{C}\,\overline{D}$, $(B\vee \overline{C})(B\vee \overline{D}) = B \vee \overline{C}\,\overline{D}$, а їхній добуток дорівнює $AB \vee \overline{C}\,\overline{D}$ — тій самій функції.

Крок 6. Схема МДНФ. Формулу $F = AB \vee \overline{C}\,\overline{D}$ збираємо з двох елементів ТА, двох інверторів (НІ) та одного АБО; входи — перемикачі, вихід — лампочка:

Крок 7. Базиси ТА-НІ та АБО-НІ (для рівня понад 75). Двоярусну суму добутків $F = AB \vee \overline{C}\,\overline{D}$ переписуємо в ТА-НІ, замінивши обидва яруси на елементи ТА-НІ (а інвертори $\overline{C}=C\mid C$, $\overline{D}=D\mid D$):

$$F = (A \mid B) \mid \big((C \mid C) \mid (D \mid D)\big).$$

Симетрично, виходячи з добутку сум (МКНФ), отримуємо реалізацію в АБО-НІ (тут $\overline{C}=C\downarrow C$, $\overline{D}=D\downarrow D$):

$$F = \big(A \downarrow (C\downarrow C)\big) \downarrow \big(A \downarrow (D\downarrow D)\big) \downarrow \big(B \downarrow (C\downarrow C)\big) \downarrow \big(B \downarrow (D\downarrow D)\big).$$

Крок 8. Поліном Жегалкіна (для рівня понад 90). Замінюємо $\overline{C}=C\oplus 1$, $\overline{D}=D\oplus 1$ і $X\vee Y = X\oplus Y\oplus XY$:

$$\overline{C}\,\overline{D} = (C\oplus 1)(D\oplus 1) = CD \oplus C \oplus D \oplus 1,$$

$$F = AB \vee \overline{C}\,\overline{D} = AB \oplus (\overline{C}\,\overline{D}) \oplus AB\cdot(\overline{C}\,\overline{D}).$$

Розкривши дужки й скоротивши пару $AB \oplus AB = 0$, дістаємо єдиний поліном:

$$\boxed{\ F = 1 \oplus C \oplus D \oplus CD \oplus ABC \oplus ABD \oplus ABCD.\ }$$

Його легко перевірити на кількох рядках таблиці: наприклад, на наборі $0000$ усі кон’юнкції нульові, лишається вільний член $1$ — і справді $F(0000)=1$.

Підсумок прикладу. Одну функцію ми подали шістьма способами — ДДНФ, ДКНФ, МДНФ, МКНФ, у базисах ТА-НІ/АБО-НІ та поліномом Жегалкіна — і кожен спосіб дає свою схему. У 4task.md той самий шлях ви пройдете для власного варіанта.

Laboratory/Laboratory1/2method.md · 24.9 KB · updated 2026-08-04 14:48