Дискретная математика. Учебное пособие

СОДЕРЖАНИЕ: ПРЕДИСЛОВИЕ (3). 1. ТЕОРЕТИКО-МНОЖЕСТВЕННЫЕ ОСНОВАНИЯ ДИСЦИПЛИНЫ (5). 1.1. Понятия и аксиомы теории множеств (5). 1.2. Декартовы произведения, отношения и отношение эквивалентности (16). 1.3. Понятия образа, прообраза, функции и отображения на конечном множестве. Аксиома выделения (23). 1.4. Аксиомы степени и бесконечности. Мощности и кардинальные числа множеств (27). 1.5. Счетные и континуальные множества (30). 1.6. Ординалы и трансфиниты. Аксиома выбора и континуум-гипотеза (35). Задачи (41). 2. ОСНОВЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ (45). 2.1. Высказывания и функции на высказываниях (45). 2.2. Операции математической логики (48). 2.3. Понятие формулы и свойства операций (50). 2.4. Полнота и замкнутость систем булевых функций (51). 2.5. Исчисление предикатов (53). 2.6. Введение в методы теории доказательств (55). Задачи (57). 3. КОМБИНАТОРИКА (61). 3.1. Размещения (61). 3.2. Размещения без повторений (67). 3.3. Перестановки и подстановки (69). 3.4. Сочетания, структура соединений (73). 3.5. Свойства биномиальных коэффициентов (75). 3.6. Понятие производящей функции (77). 3.7. Соединения с повторениями (79). 3.8. Разбиения множеств (82). 3.9. Разбиения чисел (86). 3.10. Композиции чисел (89). Задачи (90). 4. ОСНОВЫ ТЕОРИИ ГРАФОВ (93). 4.1. Основные понятия и определения (93). 4.2. Графы и бинарные отношения (95). 4.3. Понятие изоморфизма и изоморфизм плоских графов (98). 4.4. Степени вершин графа (100). 4.5. Представление графов матрицами (101). 4.6. Представление графов списками инцидентности. Оценка пространственной сложности алгоритмов (103). 4.7. Маршруты, цепи, циклы и связность (106). 4.7. Эйлеровы циклы и цепи (108). 4.9. Гамильтоновы циклы. Оценка временной сложности алгоритмов (110). 4.10. Деревья (114). 4.11. Раскраска вершин и теорема Шеннона об информационной емкости графа (117). 4.12. Раскраска ребер графа и теоремы о хроматическом классе (120). Задачи (121). ОТВЕТЫ И РЕШЕНИЯ (124). ЛИТЕРАТУРА (138). АЛФАВИТНЫЙ УКАЗАТЕЛЬ (140). Аннотация издательства: В данном пособии значительное внимание уделено алгоритмическим методам при доказательствах теорем и решениях дискретных задач, методам математической логики, комбинаторному анализу и теории графов. Теоретический материал рассматривается на конкретных практических задачах и упражнениях. Материал пособия соответствует типовым программам высших учебных заведений стран СНГ, изучающих дискретную математику как фундаментальную основу многих естественных наук. Рассчитано на учащихся выпускных математических классов, студентов технических вузов и математических факультетов.