Двоїсті функції
Двоїста булева функція – це булева функція, яка отримується з початкової функції, якщо над кожним її аргументом поставити заперечення, а також поставити заперечення над всією функцією
Для того щоб отримати двоїсту формулу булевої алгебри необхідно замінити в ній всі кон'юнкції на диз'юнкції, диз'юнкції на кон'юнкції, 0 на 1, 1 на 0, і використовувати дужки, де необхідно, щоб зберегти порядок виконання операцій.
Самодвоїста булева функція – це функція, що дорівнює своїй двоїстій
Нормальні форми
Елементарна кон'юнкція – це кон'юнкція булевих змінних, взятих з запереченням або без нього, в якій кожна змінна зустрічається не більше одного разу.
ДНФ – формула, подана у вигляді диз’юнкції елементарних кон’юнкцій
КНФ – формула, подана у вигляді кон’юнкції елементарних диз’юнкцій
Мінтерм (конституента одиниці) – це функція, представлена у вигляді елементарної кон’юнкції, що набуває значення одиниці тільки на одній інтерпретації.
Макстерм (конституента нуля) – це функція, представлена у вигляді елементарної диз’юнкції, що набуває значення нуля тільки на одній інтерпретації.
ДДНФ - формула, подана у вигляді диз'юнкції конституент одиниці даної функції.
ДКНФ - формула, подана у вигляді кон'юнкції конституент нуля даної функції.
Карти Карно
Завдання мінімізації полягає в знаходженні найпростішої, відповідно до обраного критерію мінімізації, формули серед безлічі формул, відповідних заданій булевій функції.
Критерії мінімізації:
Кількість змінних у формулі;
Кількість операцій;
Комбінування.
Імплікантою деякої функції f називається функція g, така, що на всіх інтерпретаціях, на яких g дорівнює одиниці, f теж дорівнює одиниці (мінтерми ф-ції, елементарні кон. ДНФ).
Власна частина кон’юнкції – це будь-яка елементарна кон'юнкція, що входить до складу цієї елементарної кон’юнкції і містить менше змінних.
Проста імпліканта – це така імпліканта, що ніяка її власна частина не є імплікантою даної функції.
Покриття функції – це безліч всіх простих імплікант даної функції
Скорочена ДНФ – диз'юнкція всіх простих імплікант функції.
Тупикова ДНФ – це ДНФ функції, що складається тільки з простих імплікант.
Мінімальна ДНФ функції (МДНФ) – це одна з її тупикових ДНФ, якій відповідає найменше значення обраного критерія мінімізації ДНФ.
Карти Карно – це таблиці спеціального виду, що використовуються для визначення булевих функцій і дозволяють спростити процес пошуку мінімальних форм. Сусідні рядки і стовпці відрізняються значеннями тільки однієї змінної.
Максимальна група - це група, яка не входить цілком ні в жодну іншу групу і відповідає простій імпліканті функції.
Карта Карно для функції п'яти змінних представляє в просторі двошаровий паралелепіпед, де кожен шар відповідає карті Карно від перших чотирьох змінних функції.
Карта Карно для функції шести змінних представляє в просторі чотирьохшаровий паралелепіпед, де кожен шар відповідає карті Карно від перших чотирьох змінних функції.