Взаємні властивості множин, множин та їх елементів . . 3

2.3 Різновиди невпорядкованих множин............... 3

2.4 Впорядковані множини....................... 4

2.5 Операції над множинами...................... 5

2.5.1 Об’єднання множин...................... 5

2.5.2 Перетин множин......................... 5

2.5.3 Теорема про п’ять можливостей................ 6

2.5.4 Різниця множин......................... 6

2.5.5 Симетрична різниця....................... 6

2.5.6 Прямий добуток множин.................... 6

2.5.7 Універсальна множина та доповнення множини....... 7

2.5.8 Проекція множини........................ 8

2.5.9 Розбиття множини........................ 8

2.6 Властивості операцій над множинами............... 8

2.7 Відповідності на множинах..................... 10

2.7.1 Визначення та задання відповідності.............. 10

2.7.2 Обернена відповідність..................... 10

2.7.3 Композиція відповідностей................... 10

2.7.4 Різновиди відповідностей.................... 11

2.7.5 Деякі терміни та символіка при відображеннях........ 11

2.8 Відношення на множинах...................... 12

2.8.1 Визначення........................... 12

2.8.2 Властивості бінарних відношень................ 13

2.8.3 Матриця бінарного відношення................ 13

Операції над відношеннями.................. 15

2.8.4.1 Композиція відношень................... 15

2.8.4.2 Теоретико-множинні операції над відношеннями.... 15

2.8.4.3 Обернене відношення................... 15

2.8.4.4 Доповнення відношення.................. 15

2.8.5 Відношення еквівалентності.................. 15

2.8.6 Відношення порядку...................... 16

2.8.7 Відношення домінування................... 16

3 Схема зв’язків моделей та розділів дискретної математики..... 16

4 Елементи математичної логіки.................... 20

4.1 Предикати.............................. 20

4.2 Квантори.............................. 21

4.2.1 Умовні позначки та квантифікація.............. 21

4.2.2 Ситуації щодо істинності формул логіки предикатів.... 21

4.2.3 Деякі властивості кванторів................. 22

4.2.4 Зв’язок кванторів з функціями алгебри логіки....... 22

4.2.5 Про формалізацію доведень та неповноту аксіоматичних

систем.............................. 23

4.2.6 Про теорії алгоритмів та цифрових автоматів....... 23

5 Комбінаторна математика........................ 24

5.1 Правило суми............................ 25

5.2 Узагальнене правило суми..................... 25

5.3 Правило добутку...........................25

5.4 Узагальнене правило добутку................... 25

5.5 Розміщення с повтореннями або вибірки............ 25

5.5 Розміщення (без повторень).................... 26

5.6 Переставлення (без повторень)................... 27

5.7 Комбінації або сполучення.................... 28

5.8 Властивості формули для обчислення кількості комбінацій.. 29

5.9 Комбінації з повтореннями..................... 30

5.10 Переставлення з повтореннями та поліноміальні коефіцієнти. 31

5.11 Як розпізнати конфігурацію................... 32

6 Групи. Застосування у кодах...................... 33

6.1 Визначення............................. 33

6.2 Приклади груп............................ 34

6.2.1 Група переставлень або симетрична група порядку n!. 34

6.2.2 Zn– група залишків за модулем n............... 36

6.2.3 Коди у залишкових класах................... 36

6.2.4 Група коренів рівняння xn=1.................. 37

6.2.5 Група n-розрядних двійкових чисел з операцією

підсумовування розрялами (XOR).............. 38

6.2.6 Група многочленів над GF(2)................. 38

6.3 Підгрупи............................... 39

6.4 Циклічна підгрупа.......................... 39

6.5 Теорема Лагранжа.......................... 40

6.6 Розбиття групи на суміжні класи................. 40

7 Подібність алгебраїчних систем.................... 41

Ступіні та умови подібності систем................ 41

Приклади............................... 42

Кільця.................................. 44

Елементи теорії похибкостійкого кодування............. 45

9.1 Проблема достовірності передачи даних та деякі розв’язки... 45

9.2 Алгебра кодування лінійним кодом................ 46

9.3 Виявлення помилок.......................... 47

9.4 Виправлення помилок........................ 49

9.5 Алгебра кодування та декодування циклічним кодом..... 50

9.6 Виявляюча здатність циклічного коду............... 51

10 Основи теорії графів.......................... 53

10.1 Визначення............................ 60

10.2 Способи задання графів....................... 57

10.3 Відношення і графи......................... 60

10.4 Характеристики графів....................... 60

10.5 Деякі теореми про графи...................... 61

10.6 Гамільтонів цикл на багатовимірному одиничному кубі

та рефлексні коди......................... 62

10.7 Графи як моделі програм, даних та процесів........... 63

10.8 Зважені орграфи. Марківська та напівмарківська модель

системи або програми....................... 63

10.9 Приклад використання зважених графів для визначення

характеристик системи передавання даних з вирішальним

зворотним зв’язком......................... 64

10.10 Ордерево як форма організації динамічних словників..... 65

10.11 Перелік задач системного програмування та відповідних

задач на графах.......................... 66

10.12 Задачі на зважених графах.................... 67

10.12.1 Аналіз електричних кіл................... 67

10.12.2 Задача про найкоротший щлях............... 67

10.12.3 Задача побудови графа найменшої довжини........ 67

10.12.4 Транспортні мережі та задача про найбільший потік... 67

10.12.5 Задача комівояжера..................... 68

10.12.6 Сіткове планування..................... 69

10.12.7 Мережі Петрі......................... 69

ЛІТЕРАТУРА............................... 70

Додаток 1................................74

 

Додаток 1

В віразі (5) використана позначка логічної операції “ Ù”. Це - кон’юнкція

або логічне множення, або операція “і”, або англійською “AND”. Це елемент алгебри логіки. Для виконання вправ з задання множин не буде зайвим поверхневе знайомство з алгеброю логіки. В алгебрі логіки є константа “true”, що означає “істинний”, та константа “false”, що означає “хибний” (ложный). Змінні можуть набувати таких значень. Наприклад, a=true, b=false. Над константами та змінними можна виконувати операції алгебри логіки. В операції с=аÙb з двома операндами, є чотири варіанти значень операндів, як те подано у таблиці Д1-1, і є чотири результати операції

 

Таблиця Д1-1 істинності для кон’юнкції с=аÙb

Операнди	Результат
a	b	c
false	false	false
false	true	false
true	false	false
true	true	true

 

Для зручності, умовно значення false записують як цифру “0”, а значення true записують як цифру “1”; цифри тут не мають арифметичного значення, хоча результати кон’юнкції можна визначати

звичайним множенням. Наступна таблиця показує результати логічної

операції – диз’юнкції (логічного складання, операції “або”, OR).

 

Таблиця Д1-2 істинності для диз’юнкції c=aÚb

Операнди	Результат
а	b	c

 

Взагалі в графі результату можна розташувати 16 різних послідовностей нулів та одиниць – тобто існує 16 двомісних (з двома операндами) операцій алгебри логіки, Серед них можна відщукати такі,

комбінуючи які у виразах, можна виконувати будь-які інші операції. Такі

набори або окремі функції звуть повними. Якщо ввести одномісну опера-цію інверсії “ні” (позначена рискою зверху) true = false, false=true,

то інверсія разом з кон’юнкцією або разом з диз’юнкцією є повні набори

операцій. Виробники мікросхем обчислювальної техніки завжди виробляли мікросхеми, де реалізовані повні набори операцій, так, як

“або-ні”, “і-ні” з двома або більшою кількістю операндів. Вирази алгебри

логіки для таких операцій відповідно такі:

c=aÚb та с=aÙb

Операції у виразах можна замінювати, використовуючи формули Де Моргана

aÙb=aÚb або aÚb= aÙb

Звичайними для алгебри логіки є задачи синтезу виразу операції

або функції за заданою таблицею істиності, та мінімізація виразу

(перетворення з метою зменшення кількості елементів виразу), що

зменшує апаратурні витрати у побудованих за цими виразами пристроях.

Окрім згаданих вище часто використовується операція ”або з винятком” (вона має значення ”істинний”, якщо операнди мають неоднакові значення; інші назви: “двійковий суматор без перенесення”, “XOR”, “нерівнозначність”).

Операція з назвою “імплікація від першого операнда до другого”

c=aÉb може бути виконана через диз’юнкцію та інверсію як c=aÚb.

У таблиці Д1 стовпчик результата має чотири значення, тобто, є чотири двійкових розряди. Різних варіантів таких чотирирозрядних

чисел набереться шістнадцять. З цього випливає, що існують 16

різних функцій двох змінних. Вище бало розглятуто лише декілька,

які використовуються в межах цього посібника або в задачах на практичних заняттях. Таблиця властивостей операцій алгебри логіки

має вигляд, схожий на таблицю властивостей операцій над множинами.

Це тому, що операції алгебри логіки відрізняються від операцій над

множинами (стор. 9) лише тим, що то є операції над двійковими множинами, які складаються лише з двох елементів - true та false.