Тема 3. Булеві функції

Question 1

Що таке булева функція?

Answer 1

Булева функція — функція, область значень
якої 0 та 1, і яка залежить від змінних, що
набувають лише цих значень.

Question 2

Який результат булевих функцій?

Answer 2

Булеві (або логічні) функції оперують з
булевими змінними, їх результат - 0 або 1.

Question 3

Що таке булеві змінні?

Answer 3

Булевими змінними називаються змінні,
що приймають значення 0 або 1.

Question 4

Три основні способи задання
булевих функцій:

Answer 4

1. Таблиця істинності
2. У вигляді формул
3. Логічна схема

Question 5

Номери наборів значень змінних n-місної булевої функції змінюються від…

Answer 5

0 до 2^n - 1.

Question 6

Область визначення булевої функції - це…

Answer 6

Це набір всіх можливих комбінацій значень змінних, для яких ця функція визначена. Простіше кажучи, це всі можливі способи, як можна підставити значення в змінні булевої функції.

Question 7

Нульярні булеві функції - це…

Answer 7

Це сталі 0 і 1

Question 8

Що таке суперпозиція?

Answer 8

Суперпозиція - це спосіб отримання нових функцій шляхом підстановки значень одних функцій замість значень аргументів інших функцій.

Question 9

Що таке формула?

Answer 9

Формула - це вираз, що задає деяку функцію у вигляді суперпозиції інших функцій.

Question 10

Еквівалентні формули - це…

Answer 10

Формули, що представляють одну і ту ж функцію – називаються еквівалентними або рівносильними

Question 11

Закон Блейка-Порецького

Answer 11

Див. зошит

Question 12

Закон склеювання

Answer 12

Див. зошит

Question 13

Закон контрапозиції

Answer 13

Див. зошит

Question 14

Закон комплементності

Answer 14

Див. зошит

Question 15

Вміти знайти порядковий номер функції 1101

Answer 15

Так

Question 16

Вміти побудувати таблицю істинності для функції f198

Answer 16

Так

Question 17

Поняття сусідні та протилежні набори

Answer 17

Сусідні набори різняться точно однією компонентою, а протилежні — усіма n компонентами. Наприклад, набори:
(0100) і (1100) — сусідні,
(0100) і (1011) — протилежні.

Question 18

В чому полягає особливість двоїстої функції?

Answer 18

Ми заперечуємо усе в цій функції

Question 19

Що таке самосуперечна функція?

Answer 19

Функція, що рівна своїй суперечній - називається самосуперечною.

Question 20

Правило отримання суперечних формул:

Answer 20

Для того, щоб отримати суперечну формулу булевої алгебри, необхідно замінити в ній всі кон’юнкції на диз’юнкції, диз’юнкції на кон’юнкції, 0 на 1, 1 на 0, і використовувати дужки, де необхідно, щоб порядок виконання операцій залишився колишнім

Question 21

Що таке ранг елементарної кон’юнкції?

Answer 21

Кількість змінних, що входять в елементарну кон’юнкцію,
називається рангом елементарної кон’юнкції.

Question 22

Диз’юнктивний одночлен:

Answer 22

Диз’юнктивний одночлен (макстерм, конституента 0) від змінних X1,X2,…,Xn {0,1} — диз’юнкція цих змінних або їх заперечень.
– Макстерм дорівнює 0 тільки при єдиному наборі аргументів.
– Якщо макстерм містить одночасно змінну і її заперечення, то він
завжди дорівнює 1.

Question 23

Кон’юнктивний одночлен:

Answer 23

Кон’юктивний одночлен (мінтерм, конституента 1) - від змінних X1,X2,…,Xn {0,1} — кон’юнкція цих змінних або їх заперечень.
– елементарна кон’юнкція, набуває значення одиниці лише на одному з кортежів своїх змінних
– Якщо мінтерм містить одночасно змінну і її заперечення, то він завжди дорівнює 0.

Question 24

Що таке ДДНФ?

Answer 24

Досконалою диз’юнктивною нормальною формою (ДДНФ)
булевої функції називається формула, подана у вигляді
диз’юнкції конституент одиниці даної функції

Question 25

Умови ДДНФ:

Answer 25

- в ній немає однакових доданків; * жоден із доданків не містить двох однакових співмножників; * жоден із доданків не містить змінну разом із її запереченням; * в кожному окремому доданку є як співмножник або змінна xi , або її заперечення для будь-якого i = 1, 2, …, n.

Question 26

Що таке ДКНФ?

Answer 26

Досконалою кон'юнктивною нормальною формою (ДКНФ) функції називається формула, подана у вигляді кон'юнкції конституент нуля (макстермів) даної функції.

Question 27

Умови ДКНФ:

Answer 27

в ній немає однакових співмножників; * жоден із співмножників не містить двох однакових доданків; * жоден із співмножників не містить якої-небудь змінної разом з її запереченням; * в кожному окремому співмножнику є як складова або змінна xi, або її заперечення для будь-якого i=1,2,…,n.

Question 28

Що таке поліном Жегалкіна?

Answer 28

Поліномом Жегалкіна називається скінчена сума по модулю 2 попарно різних елементарних кон’юнкцій над множиною змінних (x1, x2, …, xn).

Question 29

Розуміти метод невизначених коефіцієнтів

Answer 29

Так

Question 30

Що таке передповний клас функцій алгебри логіки?

Answer 30

Це клас булевих функцій, що наближається до функціонально повного, але не є таким через відсутність однієї або декількох важливих властивостей.

Question 31

Всього є 5 класів:

Answer 31

1. T0 - Клас функцій, що зберігають константу 0 2. T1 - Клас функцій, що зберігають константу 1 3. S - Клас самодвоїстих функцій 4. M - Клас монотонних функцій 5. L - Клас лінійних функцій

Question 32

В чому полягає теорема Поста?

Answer 32

За теоремою Поста , щоб система булевих функцій була повною, треба, щоб в ній існували: * Хоча б одна функція, що не зберігає 0; * Хоча б одна функція, що не зберігає 1; * Хоча б одна нелінійна функція; * Хоча б одна немонотонна функція; * Хоча б одна несамодвоїста функція.

Question 33

Що таке мінімізація булевих функцій?

Answer 33

Це спрощення булевих виразів.

Question 34

Які є методи мінімізації?

Answer 34

Розрізняють аналітичні і табличні методи мінімізації.

Question 35

Аналітичні методи мінімізації - це...

Answer 35

Це методи перетворень з використанням законів перетворень булевих виразів.

Question 36

Табличні методи мінімізації - це...

Answer 36

Алгоритм карти Карно мінімізації булевої функції