- •Міністерство освіти і науки,
- •Упорядники: в.І. Хаханов,
- •Рецензент: є.І. Литвинова, д-р техн. Наук, проф. Каф. Апот хнуре
- •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.3 Алгебра множин Кантора
Визначення 1.4. Алгебра А є сукупністю носія N і сигнатури S:. Сигнатура задає набір операцій над елементами з носія, які діють за певними правилами.
Множини у сукупності з операціями об'єднання , перетинанняй доповнення – абоутворюютьалгебру множин Кантора. Порядок операцій: 1) –; 2); 3). Дані операції утворюють базис в алгебрі множин Кантора. Інші операції (різниця \ і симетрична різниця) можуть бути виражені через базисні.
Операції над множинами вводяться за такими правилами:
1. Перетинання складається із всіх елементів , які належать одночасно двом множинамі(рис. 1.4, а):
. (1.2)
2. Об'єднання складається із всіх елементів , які належать множиніабо множині(рис. 1.4, б):
. (1.3)
3. Доповнення визначається через теоретико-множинну різницю (рис. 1.4, в):
. (1.4)
4. Вирахування (теоретико-множинна різниця, рис. 1.4, г) складається із всіх елементів, які належать зменшуваній множині, але не належать віднімаючій множині
. (1.5)
Зв’язок з базисними операціями перетинання й різниці встановлюється за формулою:
. (1.6)
5. Симетрична різниця (рис. 1.4, д):
. (1.7)
Для симетричної різниці мають місце формули, що встановлюють зв’язок з базисними операціями:
. (1.8)
Діаграма Ейлера для симетричної різниці зображено на рис. 1.4, д.
Рисунок 1.4 – Ілюстрація результатів теоретико-множинних
операцій на діаграмах Ейлера
1.4 Закони й тотожності алгебри множин
1. Комутативність:
,. (1.9)
2. Асоціативність:
,. (1.10)
3. Дистрибутивність (розподільний закон):
,. (1.11)
4. Ідемпотентність (повторення, тавтологія):
. (1.12)
5. Операції з константами (як константи виступають порожня й універсальнамножини):
,,,. (1.13)
6. Закон виключеного третього:
. (1.14)
7. Закон протиріччя:
. (1.15)
8. Інволюція:
. (1.16)
9. Закон Де Моргана:
,. (1.17)
10. Елімінація (поглинання):
,. (1.18)
11. Склеювання:
,. (1.19)
12. Закони Порецького:
,. (1.20)
Для об'єднання й перетинання множин справедливі такі формули обчислення потужності:
, . (1.21)
Порожня й універсальна множини вводяться для замкнутості теоретико-множинних операцій. Це означає, що результат застосування цих операцій є елемент тієї ж природи, що й об'єкти з носія. Таким чином, алгебра множин Кантора замкнута щодо введених операцій.
1.5 Контрольні запитання
1. Як визначається множина?
2. Чи можуть повторюватися елементи множини?
3. Які існують способи задання множин?
4. Чому дорівнює потужність множини?
5. Чим характеризується невласна підмножина?
6. Яка множина є власною?
7. Чи є множина невласною підмножиною самого себе?
8. Коли дві множини є рівними?
9. Які теоретико-множинні операції є базисними?
10. Як визначається пріоритет операцій алгебри Кантора?
11. Чи є поняття потужності множини і його кардинального числа ідентичними?
12. Як формулюються закони й тотожності алгебри множин?
13. Як ілюструються теоретико-множинні операції за допомогою діаграм Ейлера?
14. Яка множина називається булеаном?
15. Яка формула використовується для обчислення потужності булеана?