- •Міністерство освіти і науки,
- •Упорядники: в.І. Хаханов,
- •Рецензент: є.І. Литвинова, д-р техн. Наук, проф. Каф. Апот хнуре
- •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 Позначення до розділу «булева алгебра»
- •Перелік посилань
- •Упорядники хаханов Володимир Іванович
1 Основні поняття теорії множин
1.1 Відношення приналежності та включення
Множина – одне з первинних понять у математиці. Будь-яке визначення в дискретній математиці можна вивести за допомогою поняття множини. Під множиноюслід розуміти об'єднання в одне ціле об'єктів, що добре розрізнюються інтуїцією або думкою. Термін ”множина” має синоніми – ”сукупність”, “набір”. Об'єкти, які утворюють множину, називаються йогоелементами. Як правило, множину утворюють елементи однієї природи. Наприклад, числа (натуральні, цілі, дійсні), букви латинського алфавіту.
Відношення приналежності. Приналежність об'єкта множиніпозначається за допомогою символу:.
Відношення включення. Говорять, що множина є підмножиною множини, якщо кожний елементє елементом, тобто належить(виконується поелементна приналежність):
,
при цьому –підмножинамножини;–надмножинамножини(рис. 1.1, а).
Відношення строгого включення не припускає співпадіння множин й позначається символом :(див. рис. 1.1, а).
Множини рівні , якщо вони складаються з тих самих елементів. Якщой(), то(рис. 1.1, б).
а б
Рисунок 1.1 – Відношення включення
Таким чином, відношення приналежності встановлює зв'язок між множиною і його елементами, а відношення включення – між двома множинами. Нестроге включення допускає рівність двох множин.
Приклад 1.1. Дано множина(рис. 1.2). Які з наступних тверджень правильні?
Рисунок 1.2 – Структура множини А із прикладу 1.1
Розв’язок: – правильне, тому що в множині є елемент 2;
–правильне, тому що в множині є елементи 1, 2, тобто , ;
–правильне, тому що в множині є елемент 3, тобто ;
–правильне, тому що в множині є елемент {3};
–не правильне, оскільки в множині немає елемента 4;
–правильне, тому що в множині є елемент ;
–не правильне, оскільки в множині немає елемента 4, тобто .
1.2 Способи задання множин
Множину можна задати декількома способами, а саме:
1) перерахуванням елементів: ,;
2) використанням характеристичної властивості:
M={x | x, що мають властивість Q} або ;
;;
3) за допомогою процедури, що породжує (породжувальна процедура – операції над множинами) ;
4) графічно за допомогою діаграм Ейлера (рис. 1.3):
Рисунок 1.3 – Діаграма Ейлера для ілюстрації множини
Визначення 1.1.Булеанмножини– є множина всіх підмножин множини, при цьомуназиваєтьсяуніверсумом(універсальною множиноюабо простором) і часто позначається.
Визначення 1.2.Потужністьмножини (кардинальне число) – кількість елементів множини. Потужність множини позначаєтьсяабо.Потужність булеанавизначається формулою:
. (1.1)
Кінцева множина містить кінцеве число елементів.
Порожня множина не містить жодного елемента, його потужність дорівнює нулю:.
Приклад 1.2. Дано: множина. Знайти:.
Розв’язок.Потужність множинивизначається кількістю елементів:. Потужність булеана множини А обчислюється за формулою (1.1): . Булеан множини містить порожню множину – ;всі одноелементні підмножини множини–,,; всі двоелементні підмножини множини–,,; триелементну підмножину, що співпадає із самою множиною –:
.
Таким чином, булеан множини А складається з порожньої множини, трьох одноелементних підмножин множини А, трьох двоелементних підмножин множини А та самої множини А.
Визначення 1.3. Множина А називається власною підмножиною множини В, якщо А є підмножиною множини В, а В не є підмножиною множини A.
Порожня множина є підмножиною будь-якої множини. Універсум U або універсальну множину можна розглядати як надмножину всіх множин:.
Універсум – поняття відносне. Якщо мова йде про множину чисел в арифметиці, множина R дійсних чисел розглядається як універсум U. Якщо мова йде про вузівський захід, то U краще вибрати як множину студентів даного вузу, а не людей міста або країни.
У прикладі 1.2 універсумом є множина А як надмножина всіх множин булеана. Порожня множина і сама множина є невласними, інші множини – елементи булеана – власні.