Ознайомлення з історією виникнення теорії множин. Способи опису характеристичних властивостей множин. Декартовий добуток та бінарні відношення. Ін’єктивні, сюр’єктивні та бієктивні відображення. Поняття та властивості бінарної алгебраїчної операції.
Дискретна математика є розділом математики, що зародилася в давні часи. У більш як двотисячорічній історії дискретної математики сучасний період є одним із найінтенсивніших періодів її розвитку: дуже швидко розширюється сфера застосування, інтенсивно зростають обсяги нової інформації та кількість нових результатів.Основи теорії множин були закладені відомим німецьким математиком Георгом Кантором у другій половині минулого століття. Поява теорії множин була зустрінута з ентузіазмом багатьма авторитетними математиками. Вони побачили в ній можливість створення метамови математики, тобто формальної одностайної системи понять і принципів, за допомогою якої можна було б викласти з єдиних позицій зміст різноманітних традиційно далеких один від одного розділів математики. Перші такі досить успішні спроби були виконані вже незабаром після виникнення канторівської теорії множин.Для наших цілей достатньо буде викладення основ так званої інтуїтивної або наївної теорії множин, яка в головних своїх положеннях зберігає ідеї та результати засновника теорії Г. Кантора. В інтуїтивній теорії множин поняття "множина" належить до первинних невизначальних понять, тобто воно не може бути означено через інші більш прості терміни або обєкти, а пояснюється на прикладах, апелюючи до нашої уяви та інтуіції. Канторівський вираз: "Множина - це зібрання в єдине ціле визначених обєктів, які чітко розрізняються нашою інтуіцією або нашою думкою" - безумовно не може вважатися строгим математичним означенням, а є скоріше поясненням поняття множини, яке заміняє термін "множина" на термін "зібрання". Множиною називається сукупність визначених обєктів, різних між собою, обєднаних за певною ознакою чи властивістю. Для деяких множин у математиці вживаються сталі позначення.Множини можуть задаватися наступними способами: 1) Перерахуванням, тобто списком всіх своїх елементів. Зокрема, множини можуть виступати в ролі елементів якоїсь іншої множини. Наприклад, множина всіх можливих невпорядкованих пар з елементів a, b і c (елементи в парі не співпадають) D = {{a,b},{a,c},{b,c}} складається з трьох елементів і задана цілком коректно. Цей вираз читається так: "множина M - це множина всіх таких елементів a, для яких виконується властивість F", де через F(a) позначено властивість, яку мають елементи множини M і тільки вони. Далі будемо вважати, що кожна розумна властивість визначає деяку множину X елементів, що мають цю властивість, і, навпаки, будь-якій множині відповідає властивість її елементів бути елементами цієї множини.Якщо припустити, що існує кілька множин опису алгоритмів, а в дійсності ситуація виглядає саме так, то повинна бути множина модифікацій для цього способу задання множин.Для графічної ілюстрації відносин між множинами даної універсальної множини використовують діаграми Ейлера-Венна. Діаграма Венна - діаграма, що показує всі можливі логічні відношення для скінченного набору множин. Використовуються для вивчення елементарної теорії множин, та ілюстрування простих співвідношень в теорії ймовірностей, логіці, статистиці, мовознавстві та інформатиці.Розглянемо дві множини А і В та введемо операції над ними. Обєднанням множин і називається множина, що складається із всіх тих елементів, які належать хоча б однієї з множин або . Перетином множин і називається множина, що складається із всіх тих елементів, які належать і множині і множині . Доповненням (або абсолютним доповненням) множини називається множина, що складається із всіх елементів універсальної множини, які не належать . Симетричною різницею множин і називається множина, що складається з обєднання всіх елементів, що належать множині і не містяться в , і елементів, що належать множині і не містяться в .Операції над множинами, як і операції над числами, мають деякі властивості (табл.1). Останні виражаються сукупністю тотожностей незалежно від конкретних множин, що входять у ці тотожності та є підмножинами деякого універсуму U. Взагалі поняття "операція "дуже важливе і його широко застосовують у різних галузях математики для конструювання одних обєктів з інших, для визначення нових математичних обєктів тощо. A називається розбиттям П множини Тут множини підмножин П1, П2, П3 - розбиття, а множина підмножин П4 не є розбиттям, тому що не виконується умова 2).Основний метод доведення тотожностей в алгебрі множин ґрунтується на згаданому раніше факті: А = В тоді і тільки тоді, коли А I В і В I А. Доведемо, наприклад, тотожність 3а) А E (В C С) = (А E В) C (А E С). Це рівносильно x I (А E В) C (А E С), що й треба було довести. Це рівносильно x I А або (x I В і x I С), тобто x I А E (В C С), що й потрібно було довести. Із властивості асоціативності операції обєднання множин випливає, що обєднання кількох множин можна виконати, послідовно обєднуючи їх, причому порядок входження множин не впливає на результат: А E (В E С) = (А E В) E С = А E В E С.Вживання терміна "парадокс" стосовно до тих суперечностей, які були виявлені рі
План
Зміст
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 Ізоморфізми та гомоморфізми алгебраїчних структур
