# 6. Контрольні запитання

## Логічні елементи та функції

1. Що таке **булева функція** від $n$ змінних? Скільки рядків має її таблиця
   істинності й чому саме $2^{n}$?
2. Намалюйте умовні позначення елементів **ТА, АБО, НІ, ТА-НІ, АБО-НІ, XOR**. Що
   означає **кружальце** на виході елемента?
3. Чим відрізняються **штрих Шефера** (ТА-НІ) і **стрілка Пірса** (АБО-НІ)? Наведіть
   їхні таблиці істинності. Як пов'язані $A\mid B$ з $\overline{A\wedge B}$ і
   $A\downarrow B$ з $\overline{A\vee B}$?

## Канонічні форми

4. Що таке **мінтерм** і **макстерм**? За яким правилом змінна входить у мінтерм
   прямою чи інвертованою? А в макстерм?
5. Як побудувати **ДДНФ** і **ДКНФ** за таблицею істинності? По яких рядках
   (одиничних чи нульових) береться кожна з них?
6. Чому ДДНФ і ДКНФ називають **досконалими** (канонічними) формами? У якому випадку
   коротшою вийде ДДНФ, а в якому — ДКНФ?

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

7. Що таке **код Грея** і навіщо ним нумерують рядки та стовпці карти Карно? Чому
   сусідні клітинки повинні відрізнятися рівно одним бітом?
8. Сформулюйте **правила групування** клітинок. Чому розмір групи має бути степенем
   двійки? Що дає «обгортання» країв карти?
9. Як за групою **одиниць** скласти терм **МДНФ**? Як за групою **нулів** — терм
   **МКНФ**? Чому змінні, що змінюються в межах групи, відкидають?

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

10. Що таке **функціональна повнота** набору операцій? Чому одного елемента ТА-НІ (або
    АБО-НІ) достатньо, щоб реалізувати будь-яку булеву функцію?
11. Запишіть вирази для $\overline{A}$, $A\wedge B$ та $A\vee B$ через **штрих Шефера**
    і через **стрілку Пірса**. Чому суму добутків (ДНФ) зручно реалізувати в базисі
    ТА-НІ, а добуток сум (КНФ) — у базисі АБО-НІ?

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

12. На яких операціях будується **алгебра Жегалкіна**? Виразіть $\overline{A}$ і
    $A\vee B$ через $\oplus$ і $\wedge$.
13. Що таке **поліном Жегалкіна** і чому він для кожної функції єдиний? Чому під час
    зведення подібних доданки скорочуються **парами** (тобто чому $t\oplus t = 0$)?

## Середовище та самоперевірка

14. Які елементи **logic.ly** задають входи та вихід схеми? Як призначити елементу
    змінну й задати кількість входів вентиля? Як **перевірити** правильність зібраної
    схеми?

## Завдання для самоперевірки (виконати вручну)

15. Для функції $F(A,B,C)$, що дорівнює $1$, коли **ввімкнено принаймні два** з трьох
    входів (мажоритарна функція), побудуйте таблицю істинності, ДДНФ, ДКНФ, мінімізуйте
    її картою Карно $2\times4$ і накресліть схему. Ця функція **не** є жодним із
    варіантів [4task.md](4task.md) — це вправа на техніку.