- •Міністерство освіти і науки,
- •Упорядники: в.І. Хаханов,
- •Рецензент: є.І. Литвинова, д-р техн. Наук, проф. Каф. Апот хнуре
- •1 Основні поняття теорії множин
- •1.1 Відношення приналежності та включення
- •1.2 Способи задання множин
- •1.3 Алгебра множин Кантора
- •1.4 Закони й тотожності алгебри множин
- •1.5 Контрольні запитання
- •2 Відповідності. Функції. Відображення
- •2.1 Поняття впорядкованої пари й вектора
- •2.2 Декартів (прямий) добуток множин
- •2.4 Функції. Відображення
- •2.5 Контрольні запитання
- •3 Відношення. Алгебра відношень
- •3.1 Поняття відношення
- •3.2 Операції над відношеннями
- •3.3 Алгебра відношень
- •3.4 Контрольні запитання
- •4 Бінарні відношення
- •4.1 Способи завдання бінарних відношень
- •4.2 Властивості бінарних відношень
- •4.3 Бінарне відношення еквівалентності
- •4.4 Контрольні запитання
- •5 Бінарне відношення порядку
- •5.1 Упорядковані множини. Бінарне відношення порядку
- •5.2 Типи порядку (лінійний, частковий, передпорядок)
- •5.3 Контрольні запитання
- •6 Структури. Алгебраїчні системи. Ізоморфізм
- •6.1 Структура
- •6.2 Дедекиндові (модулярні) структури
- •6.3 Дистрибутивні структури
- •6.4 Ізоморфізм множин
- •6.5 Контрольні запитання
- •7 Висновки до розділу «Теорія множин»
- •8 Позначення до розділу «Теорія множин»
- •9 Основні поняття булевої алгебри
- •9.1 Логічні операції й логічні функції
- •9.2 Закони й тотожності булевої алгебри
- •9.3 Доведення законів булевої алгебри
- •9.4 Контрольні запитання
- •10 Диз’юнктивні та кон’юнктивні нормальні форми (днф і кнф). Досконалі днф і кнф (дднф і дкнф)
- •10.1 Днф і кнф
- •10.2 Дднф і дкнф
- •10.3 Складність зображення булевих функцій
- •10.4 Теорема Шенона про розкладання булевих функцій
- •10.5 Контрольні запитання
- •11 Елементи логічних схем. Булеві функції від двох змінних
- •11.1 Фізичний зміст логічних функцій і, або, ні та їх схемотехнічне зображення
- •11.2 Таблиця аналітичного й схемотехнічного зображення булевих функцій від двох змінних
- •11.3 Властивості й аналітичні подання елементарних булевих функцій від двох змінних
- •11.4 Приклади розв’язання практичних завдань
- •11.5 Контрольні запитання й завдання
- •12 Способи зображення булевих функцій
- •12.1 Табличний спосіб зображення булевих функцій
- •12.2 Числовий спосіб зображення булевих функцій
- •12.3 Аналітична форма запису булевих функцій
- •12.4 Геометрична інтерпретація булевих функцій
- •12.5 Кубічна форма зображення булевих функцій
- •12.6 Схемотехнічне зображення
- •12.7 Контрольні запитання й завдання
- •13 Системи функцій алгебри логіки. Функціональна повнота
- •13.1 Класи булевих функцій
- •13.2 Повнота функцій алгебри логіки
- •13.3 Контрольні запитання
- •14 Булеві похідні
- •14.1 Булеві похідні першого порядку
- •14.2 Фізичний зміст булевої похідної першого порядку
- •14.3 Змішана похідна -го порядку
- •14.4 Булеві похідні k-го порядку
- •14.5 Контрольні запитання
- •15 Мінімізація булевих функцій. Методи квайна і квайна-мак-класки
- •Булеві функції застосувуються при реалізації логічних схем. Різні вирази однієї й тієї ж функції представляють різні схеми.
- •15.1 Основні положення методу квайна
- •15.2 Мінімізація булевих функцій за методом Квайна-Мак-Класки
- •15.3 Контрольні запитання
- •16 Мінімізація булевих функцій: метод невизначених коефіцієнтів
- •16.1 Основні припущення
- •16.2 Алгоритм знаходження невизначених коефіцієнтів
- •16.3 Контрольні запитання
- •17 Мінімізація булевих функцій: метод карт карно
- •17.1 Основні положення
- •17.2 Спрощений стандарт карт Карно
- •17.3 Мінімізація за картами Карно
- •17.4 Контрольні запитання
- •18 Висновки до розділу «булева алгебра»
- •19 Позначення до розділу «булева алгебра»
- •Перелік посилань
- •Упорядники хаханов Володимир Іванович
17.4 Контрольні запитання
1. Як складаються карти Карно для функцій від двох, трьох і чотирьох змінних?
2. Чим відрізняються карти Карно від таблиць істинності?
3. Яке основне призначення карт Карно?
4. Як установлюється зв'язок між двійковими наборами й комірками карти Карно двох (трьох, чотирьох) змінних?
5. Які комірки карти є сусідніми?
6. Як подається функція на карті?
7. У чому полягає спрощений стандарт карт Карно?
8. Які властивості мають карти Карно?
9. Що таке р-клітинки?
10. Які основні правила склеювання за картами?
11. Як виконується мінімізація за картами Карно?
12. Що являють собою мінімізуючі контури?
18 Висновки до розділу «булева алгебра»
Булева алгебра може виступати як модель для схем з логічних елементів. Вона має зв’язок з такими розділами математики як теорія множин, теорія груп, логіка, теорія структур, теорія перемикаючихх схем. Теорію булевих алгебр покладено до основи побудови моделі, яка описує поведінку перемикаючих схем. Вона є ефективним математичним апаратом для їх дослідження.
19 Позначення до розділу «булева алгебра»
Символ |
Розшифровка |
Диз’юнкція (логічне додавання) | |
Кон’юнкція (логічне множення) | |
− |
Заперечення |
Імплікація | |
Сума за модулем два, XOR | |
Еквівалентність | |
Штрих Шефера | |
Стрілка Пірса (функція Веба) | |
1 |
Істина (істиннісне значення булевої змінної або булевої функції) |
0 |
Хибність (хибне значення булевої змінної або булевої функції) |
, |
Двійковий набір (вектор) |
Первинний терм | |
Елементарна кон’юнкція | |
Елементарна диз’юнкція | |
Диз’юнктивна нормальна форма (ДНФ) | |
Кон’юнктивна нормальна форма (КНФ) | |
Досконала ДНФ (ДДНФ) | |
Досконала КНФ | |
Складність форми булевої функції | |
Складність форми булевої функції за Квайном, число кон’юнктивних термів функції | |
Граничне диз’юнктивне розкладання функції за Шенноном (ДДНФ) | |
Граничне кон’юнктивне розкладання функції за Шенноном (ДКНФ) | |
AND |
AND-Оператор (І) |
OR |
OR-Оператор (АБО) |
NOT |
NOT-Оператор (НІ) |
Х |
Незалежна координата |
0-куб |
Точка (вершина одиничного куба) |
1-куб |
Відрізок (ребро одиничного куба) |
2-куб |
Площина (грань одиничного куба) |
Комплекс 0-кубів | |
Комплекс 1-кубів | |
Клас функцій, що зберігають константу нуль | |
Клас функцій, що зберігають константу одиниця | |
Клас самодвоїстих функцій | |
Клас монотонних функцій | |
Клас лінійних функцій | |
Поліном Жегалкіна, де та,є або 1, або змінна, або кон’юнкція різних змінних | |
Поліном першого ступеня, де | |
( ) |
Передування (порівнянність) двійковихнаборів |
Двоїста функція | |
Одинична залишкова функція | |
Нульова залишкова функція | |
Булева похідна першого порядку за змінною | |
Змішана похідна k-го порядку булевої функції | |
Похідна k-го порядку |