Ознайомлення з історією виникнення теорії множин. Способи опису характеристичних властивостей множин. Декартовий добуток та бінарні відношення. Ін’єктивні, сюр’єктивні та бієктивні відображення. Поняття та властивості бінарної алгебраїчної операції.
Краткое сожержание материала:

Размещено на

Зміст

• 1. Основи теорії множин
• 1.1 Коротка історична довідка
• 1.2 Поняття множини
• 1.3 Способи опису множин
• 1.4 Операції над множинами
• 1.4.1 Діаграми Ейлера-Венна
• 1.4.2 Деякі операції над множинами
• 1.5 Властивості операцій над множинами
• 1.6 Доведення тотожностей
• 1.7 Парадокси теорії множин
• 2. Основи теорії відношень
• 2.1 Декартовий добуток
• 2.2 Поняття відношень. Завдання відношення
• 2.3 Властивості бінарних відношень
• 2.4 Відношення еквівалентності
• 2.4.1 Фактор-множина
• 2.4.2 Рівнопотужні множини
• 2.4.3 Зчисленні множини
• 2.4.4 Потужність континууму
• 2.5 Операції над бінарними відношеннями
• 2.5.1 Правила побудови матриць відношень
• 2.6 Відображення
• 2.6.1 Визначення і приклади
• 2.6.2 Деякі часткові випадки
• 2.6.3 Ін'єктивні, сюр'єктивні та бієктивні відображення
• 2.6.4 Композиція відображень
• 2.7 Функції
• 3. Алгебраїчні системи
• 3.1 Поняття бінарної алгебраїчної операції
• 3.2 Властивості бінарних алгебраїчних операцій
• 3.3 Обернені бінарні операції
• 3.4 Елементи, виділені відносно бінарної операції
• 3.5 Поняття алгебраїчної структури
• 3.6 Основні типи алгебраїчних структур
• 3.7 Ізоморфізми та гомоморфізми алгебраїчних структур
• 3.8 Булеві алгебри
• 4. Комбінаторний аналіз
• 4.1 Правило добутку
• 4.2 Правило суми
• 4.3 Розміщення
• 4.3.1 Розміщення з повтореннями
• 4.3.2 Розміщення без повторень
• 4.4 Перестановки
• 4.5 Сполучення (комбінації)
• 4.6 Формула включень і вилучень
• 5. Основи теорії графів
• 5.1 Основні визначення
• 5.2 Способи завдання графів
• 5.3 Зв'язність графа. Маршрути, шляхи, ланцюги, цикли
• 5.3.1 G _ неорієнтований граф
• 5.3.2 G _ орієнтований граф
• 5.4 Метрика на графах
• 5.5 Ейлерів цикл. Ейлерів граф
• 5.6 Шляхи і цикли Гамільтона
• 5.7 Планарні графи
• 5.8 Розфарбування графів
• 5.9 Дерева і ліс
• 5.10 Алгоритми пошуку найкоротших шляхів
• 5.10.1 Алгоритм пошуку у глибину
• 5.10.2 Алгоритм пошуку завширшки
• 5.10.3 Алгоритм Дейкстри
• 5.10.4 Алгоритм Флойда
• Література
• множина декартовий бінарний алгебраїчний
• 1. Основи теорії множин

Дискретна математика є розділом математики, що зародилася в давні часи. Її головною відмінністю є дискретність, тобто антипод неперервності. Дискретна математика включає традиційні розділи математики, які вже сформувалися (математичну логіку, алгебру, теорію чисел), і нові, що інтенсивно розвиваються.

У більш як двотисячорічній історії дискретної математики сучасний період є одним із найінтенсивніших періодів її розвитку: дуже швидко розширюється сфера застосування, інтенсивно зростають обсяги нової інформації та кількість нових результатів. Якщо ще порівняно недавно ця наука була сферою інтересів лише вузького кола фахівців, то тепер вона перетворюється на наукову дисципліну, дуже важливу й потрібну для багатьох, а у сфері сучасної освіти - для всіх.

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

Базовим розділом як дискретної математики, так і взагалі всієї математики, є теорія множин.

1.1 Коротка історична довідка

Основи теорії множин були закладені відомим німецьким математиком Георгом Кантором у другій половині минулого століття. Поява теорії множин була зустрінута з ентузіазмом багатьма авторитетними математиками. Вони побачили в ній можливість створення метамови математики, тобто формальної одностайної системи понять і принципів, за допомогою якої можна було б викласти з єдиних позицій зміст різноманітних традиційно далеких один від одного розділів математики. Перші такі досить успішні спроби були виконані вже незабаром після виникнення канторівської теорії множин.

Однак пізніші дослідники виявили в теорії Кантора чимало суперечностей: так званих парадоксів або антиномій теорії множин. Виникла кризова ситуація. Одна частина математиків, посилаючись на штучність сформульованих антиномій, вважала за краще не помічати ці суперечності або не надавати їм великого значення. У той час як інша (скажімо, відповідальніша) група математиків зосередила свої зусилля на пошуках більш обгрунтованих та точних принципів і концепцій, на яких могла б бути побудована несуперечлива теорія множин.

У результаті було запропоновано кілька формальних (або аксіоматичних) систем, які служать фундаментом сучасної теорії множин, а значить, фундаментом всієї класичної математики. Важливість цих досліджень серед іншого підкреслює той факт, що значний внесок у становлення аксіоматичної теорії множин зробили такі видатні математики і мислителі XX століття, як Б. Рассел, Д. Гільберт, К. Гедель та ін.

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

1.2 Поняття множини

Для наших цілей достатньо буде викладення основ так званої інтуїтивної або наївної теорії множин, яка в головних своїх положеннях зберігає ідеї та результати засновника теорії Г. Кантора.

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

Канторівський вираз: "Множина - це зібрання в єдине ціле визначених об'єктів, які чітко розрізняються нашою інтуіцією або нашою думкою" - безумовно не може вважатися строгим математичним означенням, а є скоріше поясненням поняття множини, яке заміняє термін "множина" на термін "зібрання". Іншими синонімами основного слова "множина" є "сукупність", "набір", "колекція", "об'єднання" тощо.

Прикладами множин можуть служити: множина десяткових цифр, множина літер українського алфавіту, множина мешканців Одеси, множина парних чисел, множина розв'язків деякого рівняння та ін.

Визначення. Множиною називається сукупність визначених об'єктів, різних між собою, об'єднаних за певною ознакою чи властивістю.

На письмі множини позначаються, як правило, великими літерами. Для деяких множин у математиці вживаються сталі позначення. Наприклад, N - множина натуральних чисел, Z - множина цілих чисел, Q - множина раціональних чисел, R - множина дійсних чисел, C - множина комплексних чисел тощо.

Визначення. Якщо один з об'єктів множини , то говорять, що _ елемент множини , або належить .

Елементи множин позначатимемо малими літерами латинського алфавіту. Той факт, що об'єкт a є елементом множини M записується так: aM (читається: "a належить M" або "a є елемент M"). Для того, щоб підкреслити, що деякий елемент a не належить множині M, вживають позначення aM.

Запис a, b, c,...M використовують для скорочення запису aM, bM, cM,....

1.3 Способи опису множин

Множини можуть задаватися наступними способами:

1) Перерахуванням, тобто списком всіх своїх елементів. Такий спосіб завдання прийнятний тільки при завданні кінцевих множин. Позначення списку - у фігурних дужках. Порядок запису елементів множини при цьому позначенні є неістотним.

Наприклад, множина, що складається з перших п'яти простих чисел . Множина спортсменів університетської хокейної команди:

.

Слід пікреслити, що однією з основних ідей канторівської теорії множин був розгляд множини як нового самостійного об'єкта математичного дослідження. Тому необхідно розрізняти такі два різні об'єкти, як елемент a і множина {a}, яка складається з єдиного елемента a. Зокрема, множини можуть виступати в ролі елементів якоїсь іншої множини. Наприклад, множина всіх можливих невпорядкованих пар з елементів a, b і c (елементи в парі не співпадають) D = {{a,b},{a,c},{b,c}} складається з трьох елементів і задана цілком коректно.

2) Процедурою, що породжує і описує спосіб одержання елементів множини із уже отриманих елементів або з інших об'єктів. Цей спосіб задання множин грунтується на зазначенні загальної властивості або породжувальної процедури для всіх об'єктів, що утворюють описувану множину.

У загальному випадку задання множини M має вигляд: M = {a | F(a)}.

Цей вираз читається так: "множина M - це множина всіх таких елементів a, для яких виконується властивість F", де через F(a) позначено властивість, яку мають елементи множини M і тільки вони.

Приклад.

S = { n | n - непарне число } або S = { n | n = 2k+1, kZ },

X = { x | x = k, kZ },

F = { fi | fi+2 = fi+1 + fi, iN, f1 = f2 = 1 }.

Другий спосіб є більш загальним способом задання множин. Наприклад...