# Практична робота 3 — Булева алгебра: мінімізація та карти Карно

> Третя практична робота курсу **ОДМ**. Виконується **вручну, за варіантом**: ви
> мінімізуєте булеві вирази законами алгебри логіки, а потім мінімізуєте функції,
> задані таблицями істинності, за допомогою **карт Карно**, зчитуючи з них
> **МДНФ** (по одиницях) та **МКНФ** (по нулях).

## Коротко

| | |
|---|---|
| **Тема** | Булева алгебра: ДДНФ/ДКНФ, мінімізація законами, карти Карно, МДНФ/МКНФ |
| **Передумови** | [Лекція 3](../../Lectures/ODM-L03.md), [Лекція 4](../../Lectures/ODM-L04.md) |
| **Формат** | Домашнє завдання **за варіантом**; виконується вручну (без комп'ютерних мінімізаторів) |
| **Варіант** | $N \bmod 10 + 1$, де $N$ — номер за журналом |
| **Здати** | Оформлені розв'язання обох завдань свого варіанта з проміжними кроками |

## Передумови

Робота спирається на матеріал двох лекцій: [Лекція 3](../../Lectures/ODM-L03.md)
(булеві функції, таблиці істинності, нормальні форми ДНФ/КНФ та досконалі форми
ДДНФ/ДКНФ) і [Лекція 4](../../Lectures/ODM-L04.md) (закони булевої алгебри,
мінімізація рівносильними перетвореннями, карти Карно). Уся потрібна теорія стисло,
але самодостатньо відтворена в [2method.md](2method.md) — окремих джерел для
виконання не потрібно.

## Зміст

| # | Частина | Файл |
|:--:|---|---|
| 1 | Мета роботи | [1purpose.md](1purpose.md) |
| 2 | Методичні вказівки (самодостатня теорія + приклад) | [2method.md](2method.md) |
| 3 | Завдання за варіантами | [3task.md](3task.md) |
| 6 | Контрольні запитання | [6questions.md](6questions.md) |

## Домовленості

- **Мова.** Усе оформлюється українською.
- **Домашнє завдання за варіантом; розв'язків не наведено.** Файл
  [3task.md](3task.md) містить лише **умови** — самі вирази й таблиці для кожного
  варіанта. Готових відповідей у методичних матеріалах немає: техніку демонструє
  **окремий приклад на інших даних** у [2method.md](2method.md), а свій варіант ви
  розв'язуєте самостійно.
- **Вручну.** Мінімізуйте законами булевої алгебри та за картами Карно, а не
  програмою; на карті показуйте самі́ **групування** й виписуйте терм, який дає
  кожна група.
- **Позначення фіксовані й самодостатні.** Риска $\overline{x}$ означає заперечення
  $\neg x$; запис підряд $xy$ — кон'юнкцію $x \wedge y$; $\vee$ — диз'юнкцію.
  Пріоритет операцій: $\neg \;\succ\; \wedge \;\succ\; \vee$. Терміни *літерал,
  конституента одиниці (мінтерм), конституента нуля (макстерм), ДДНФ/ДКНФ,
  МДНФ/МКНФ* означені в [2method.md](2method.md).
- **Чотиризмінні карти.** У завданні 2 рядки карти позначено парою $xy$, стовпці —
  парою $zt$, **обидві в коді Грея** $00,\,01,\,11,\,10$; сусідство циклічне (крайні
  рядки та крайні стовпці — сусіди).

## Підсумок

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