Навчальний посібник. – К.: Видавничо-поліграфічний центр "Київський університет", 2006. – 113 с.
Навчальний посібник створено для студентів, які вивчають базовий
нормативний курс Дискретна математика. У посібнику викладаються основи
теорії графів. Він містить усі необхідні означення, формулювання та доведення
теорем, а також багато задач. Його призначено для самостійної роботи; ним можна
користуватися як при вивченні теоретичного курсу, так і під час практичних занять
з дискретної математики.
Посібник складається з семи глав, у яких наводиться відповідний теоретичний
матеріал і задачі. До кожної задачі наприкінці глави є відповідь, вказівка або
розв’язання.
Зміст:
Передмова.
Вступ. Початкові відомості.
Інтуїтивне поняття твердження. Логічні зв'язки. Запис логічних зв′язок. Таблиці істинності. Еквівалентність виразів з логічними зв'язками. Квантори ∀ та ∃. Твердження з кванторами. Деякі властивості кванторів. Елементи теорії доведень. Логічні висновки. Теореми. Доведення теорем. Проста індукція. Відповідь на питання ″Чи істинно, що …?″.
Задачі.
Алгебра множин.
Поняття множини. Операції над множинами. Основні теоретико-множинні тотожності. Булеан множини. Сім′ї множин та їх властивості.
Задачі.
Відповідності.
Декартів добуток множин. Поняття декартового добутку. Властивості операції декартового добутку множин. Відповідності. Основні означення. Обернена відповідність та її властивості. Властивості проекцій відповідностей. Властивості образу та прообразу. Композиція відповідностей та її властивості.
Задачі.
Спеціальні типи відповідностей.
Основні типи відповідностей. Усюди визначені та сюр′єктивні відповідності. Функціональні та ін′єктивні відповідності. Приклади функцій. Властивості відповідностей спеціальних типів. Критерії типізацій відповідностей. Інваріантність типів відповідностей відносно теоретико-множинних операцій. Інваріантність типів відповідностей відносно операції композиції. Додаткові властивості функцій. Властивості бієкцій, їх побудова. Означення бієкції. Побудова бієкцій.
Задачі.
Відношення.
Відношення. Властивості відношень. Базові властивості відношень. Інваріантність типів відношень відносно теоретико-множинних операцій. Замикання відношень. Відношення еквівалентності. Означення та приклади. Фактор-множина.
Задачі.
Відношення порядку.
Відношення порядку. Лінійний порядок. Екстремальні елементи частково впорядкованих множин. Індуктивні множини та принцип трансфінітної індукції. Повний порядок частково впорядкованих множин. Решітки. Верхні та нижні грані. Решітки та їх найпростіші властивості. Поняття повноти решіток. Прямі добутки решіток. Монотонне відображення. Нерухома точка відображення.
Задачі.
Відповіді, вказівки, розв′язання.
