Список вопросов для подготовки к экзамену по дисциплине
“Дискретная математика” для группы 247. Весна 2010-2011


1. Простые и сложные высказывания. Основные логические связки и их таблицы истинности.
2. Основные логические тождества и их доказательство.
3. Множества и связанные с ними обозначения. Примеры. Понятия принадлежности, элемента, подмножества.
4. Операции пересечения, объединения, дополнения множеств и их свойства. Алгебра подмножеств данного множества.
5. Функция, область определения, область значений и множество значений функции. Образы и прообразы множеств и их свойства.
6. Сюръекция, инъекция и биекция (взаимно-однозначная функция). Понятие обратной функции.
7. Сложная функция (композиция функций) . Свойства композиции. Группа преобразований множества.
8. Декартовы произведения и многоместные отношения. Примеры.
9. Бинарные отношения на множестве, их свойства. Примеры.
10. Отношение эквивалентности. Классы эквивалентности. Примеры.
11. Отношение порядка. Частично упорядоченные, вполне упорядоченные и линейно упорядоченные множества. Примеры.
12. Функции алгебры логики. Таблицы истинности основных двуместных функций.
13. Дизъюнктивная нормальная форма(ДНФ). Совершенная ДНФ функции.
14. Замыкание системы функций, полная система. Примеры.
15. Существенные и фиктивные переменные функции алгебры логики.
16. Полиномы Жегалкина.
17. Сокращенная ДНФ. Метод Блейка.
18. Смешанный граф. Подграф. Изоморфизм графов. Ориентированные и неориентированные графы.
19. Таблица инцидентности и матрица инцидентности смешанного графа.
20. Матрицы смежности ориентированного и неориентированного графа.
21. Укладка или реализация графа в пространстве и на плоскости. Примеры.
22. Маршруты, цепи, циклы. Связность и компоненты связности. Цикломатическое число графа.
23. Эйлеровы и гамильтоновы графы. Примеры.
24. Задача о женихах и невестах. Двудольный граф. Теорема Холла.
25. Полный граф и полный двудольный граф. Их свойства. Клика.
26. Теорема Эйлера для плоских графов.
27. Теорема Понтрягина-Куратовского. Гомеоморфизм графов.
28. Дерево и лес. Их свойства.
29. Взвешенный граф. Алгоритм Дейкстры поиска кратчайшего пути.