- •Учебно-методический комплекс дисциплины сд.12 дискретная математика
- •061800 «Математические методы в экономике»
- •Раздел 1. Программа учебной дисциплины. Структура программы учебной дисциплины
- •1.3 Пояснительная записка:
- •1.5. Объем дисциплины и виды учебной работы.
- •1.6 Содержание дисциплины.
- •1.7 Методические рекомендации по организации изучения дисциплины.
- •1.8 Учебно-методическое обеспечение дисциплины.
- •1.9 Материально-техническое обеспечение дисциплины.
- •1.10 Примерные зачетные тестовые задания.
- •1.11 Примерный перечень вопросов к зачету (экзамену).
- •1.12 Комплект экзаменационных билетов
- •1.13 Примерная тематика рефератов.
- •1.14 Примерная тематика курсовых работ.
- •Элементы теории множеств
- •§ 2. Бинарные операции и их свойства
- •§ 3. Операции над множествами. Законы де Моргана
- •§ 4. Вектор. Прямое произведение
- •§ 5. Мощность конечного множества
- •§ 6. Отношения и их свойства
- •§ 7. Отношение эквивалентности
- •§ 8. Отношение порядка
- •§ 9. Отображения и их свойства
- •Глава II. Элементы теории графов
- •§ 1. Графы, их вершины, рёбра и дуги
- •§ 2. Операции над графами
- •§ 3. Способы задания псевдографов. Степени вершин
- •§ 4. Отношение связности для вершин неориентированного графа
- •§ 5. Отношение достижимости для вершин орграфа
- •§ 6. Эйлеров граф и условия его существования
- •§ 7. Гамильтонов граф и условия его существования
- •§ 8. Деревья и их свойства. Цикломатическое число
- •§ 9. Формула Кэли
- •§ 10. Двудольный граф
- •§ 11. Планарность
- •§ 12. Раскраска графов
- •Глава III. Булевы функции
- •§ 1. Основные определения
- •§ 2. Свойства булевых функций
- •§ 3. Переключательные функции
- •§ 4. Совершенные нормальные формы
- •§ 5. Полнота. Примеры полных систем
- •§ 6. Замыкание и его свойства
- •§ 7. Важнейшие замкнутые классы
- •§ 8. Теорема о функциональной полноте
- •Раздел 4. Словарь терминов (глоссарий) Элементы теории множеств
- •Конечные графы
- •Функциональные системы с операциями: алгебра логики
- •Раздел 5. Практикум по решению задач (практических ситуаций) по темам лекций (одна из составляющих частей итоговой государственной аттестации) Элементы теории множеств
- •Задачи для самостоятельного решения
- •Конечные графы
- •Задачи для самостоятельного решения
- •Функциональные системы с операциями: алгебра логики
- •Задачи для самостоятельного решения
- •Раздел 6. Изменения в рабочей программе, которые произошли после утверждения программы.
- •Раздел 7. Учебные занятия по дисциплине ведут:
Раздел 4. Словарь терминов (глоссарий) Элементы теории множеств
Вектор
Декартово произведение
Множество
Операции над множествами
дополнения
объединения
пересечения
разности
Отношение
бинарное
порядка
эквивалентности
Элемент множества
Конечные графы
Вершина графа
Граф
базисный
гамильтонов
двудольный
изоморфный
неориентированный
нулевой
однородный (регулярный)
ориентированный
планарный
плоский
полный
связный
эйлеров
Дерево
Дуга графа
Компонента связности
Лес
Маршрут
Матрица
инцидентности
смежности
Мост
Мультиграф
Отношение
достижимости
связности
Подграф
собственный
Полустепень
исхода
захода
Псевдограф
эйлеров
Путь
Ребро графа
Список
рёбер
смежности
Степень вершины
Точка сочленения
Хроматическое число
Цепь
эйлерова
гамильтонова
Цикл
эйлеров
гамильтонов
Часть графа
Функциональные системы с операциями: алгебра логики
Дизъюнкция
Замыкание
Импликация
Конъюнкция
Класс функций
линейных
монотонных
самодвойственных функций
сохраняющих константу 0
сохраняющих константу 1
Метод минимизирующих карт
Нормальная форма
совершенная конъюнктивная
совершенная дизъюнктивная
Отрицание
Полином Жегалкина
Полная система
Сложение по модулю 2
Стрелка Пирса
Таблица значений
Функция
булева
Штрих Шеффера
Эквивалентность
Раздел 5. Практикум по решению задач (практических ситуаций) по темам лекций (одна из составляющих частей итоговой государственной аттестации) Элементы теории множеств
Задание 1.1. Составить все подмножества для A = {3, 6, 9}.
Решение. Их восемь: , {3}, {6}, {9}, {3, 6}, {3, 9}, {6, 9}, {3, 6, 9}.
Задание 1.2. Найти объединение, пересечение и обе разности множеств A = {12, 15, 18} и B = {12, 14, 16, 18}.
Решение. AB = {12, 14, 15, 16, 18}, AB = {12, 18}, A \ B ={15}, В \ А ={14, 16}.
Задание 1.3. Равны ли множества А и В, если А = {}, В = ?
Решение. Множество А содержит один элемент (этот элемент − пустое множество), а в множестве В элементы отсутствуют; поэтому А В.
Задание 1.4. Существуют ли множества А, В, С такие, что для них выполняется набор условий (если “да”, то привести пример таких множеств): АВ = В, АС = , С В ?
Решение. Существуют. Например, А = {1, 5} В = {1, 2, 4, 5, 9} С = {4, 9}.
Задание 1.5. Проверить справедливость равенства для множеств А = {1, 2}, B = {2, 3}, C = {1, 3}: B (A C) = (B A) \ (B (A \ C)) .
Решение.
A C = {1};
поэтому слева: B (A C) = {(2, 1), (3,1)};
B A = {(2, 1), (2, 2), (3, 1), (3, 2)}; A \ C = {2}; B (A \ C) = {(2, 2), (3, 2)};
поэтому справа: (B A) \ (B (A \ C)) = {(2, 1), (3, 1)}.
Задание 1.6. Пусть M − множество точек действительной плоскости. Какими свойствами обладают следующие бинарные отношения, заданные на множестве M:
а) Отношение “находиться на одинаковом расстоянии от начала координат”.
б). Отношение “расстояние между точками равно 5”.
Решение.
а) Отношение
-
рефлексивное, т.к. для любой точки плоскости выполняется: aRa,
-
симметричное, т.к. для любых двух точек плоскости из аRb следует bRa,
-
транзитивное, т.к. из для любых трёх точек плоскости из аRb и bRc следует аRc.
б). Отношение симметричное. Рефлексивным оно не является, т.к., расстояние от точки до неё самой равно 0, а не 5. Транзитивным оно тоже не является: например, точка (4,2) находится на расстоянии 5 от точки (−1, 2), точка (−1, 2) находится на расстоянии 5 от точки (−6, 2), тогда как расстояние между точками (4,2) и (−6, 2) не равно 5.