- •Учебно-методический комплекс дисциплины сд.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. Учебные занятия по дисциплине ведут:
§ 7. Отношение эквивалентности
Отношение называется отношением эквивалентности (или просто эквивалентностью), если оно рефлексивно, симметрично и транзитивно. Если элементы a и b связаны отношением эквивалентности, то применяется запись: a~b.
Примеры.
1. Отношение равенства Е на любом множестве является отношением эквивалентности. Равенство - это минимальное отношение эквивалентности в том смысле, что при удалении любой пары из множества Е (т.е. любой единицы на диагонали матрицы Е) оно перестаёт быть рефлексивным и, следовательно, уже не является эквивалентностью.
2. Отношение “иметь один и тот же остаток от деления на 4” является эквивалентностью на N{0}. Это отношение выполняется, например, для пар (19,43), (12,20) и не выполняется для пар (18,43), (12,21).
3. Отношение “быть параллельными”, заданное на множестве всех прямых на плоскости, также представляет собой эквивалентность.
Пусть на множестве М задано отношение эквивалентности R. Выполним следующее построение. Выберем элемент a1М и образуем класс (подмножество М) C1, состоящий из a1 и всех элементов, эквивалентных a1; затем выберем из М элемент a2C1 и образуем класс C2, состоящий из a2 и всех элементов, эквивалентных a2, и т.д. Получится система (возможно, бесконечная) классов C1, C2,..., в которой каждый элемент из М входит хотя бы в один класс, т.е. =M.
Эта система классов имеет следующие свойства:
1) она образует разбиение (классы попарно не пересекаются);
2) любые два элемента из одного класса эквивалентны;
3) любые два элемента из разных классов не эквивалентны.
Свойства 2, 3 непосредственно следуют из способа построения классов эквивалентности, поэтому ограничимся доказательством свойства 1.
Предположим, что два класса, например C1 и C2, пересекаются. Это значит, что они имеют хотя бы один общий элемент b, причём, по построению, b~ a1 и b~ a2. Тогда, в силу транзитивности отношения эквивалентности, a1~a2. Полученный результат противоречит построению C2. Остаётся утверждать, что C1 и C2 не пересекаются.
Построенное разбиение называется системой классов эквивалентности по отношению к R. Мощность этой системы называется индексом разбиения.
Примеры.
1. Все классы эквивалентности для отношения равенства Е состоят из одного элемента (“а” равно только себе самому).
2. Разбиение на N{0} для отношения “иметь один и тот же остаток от деления на 4” имеет конечный индекс 4 и состоит из четырёх классов:
C1={0,4,8,12,...}={c / c=4k-4, kN}, C2={1,5,9,13,...}= {c / c=4k-3, kN},
C3={2,6,10,14,...}= {c / c=4k-2, kN}, C4={3,7,11,15, ...}= {c / c=4k-1, kN}.
§ 8. Отношение порядка
Отношение называется отношением нестрогого порядка, если оно рефлексивно, антисимметрично и транзитивно.
Отношение называется отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно.
Оба типа отношений называются отношениями порядка.
Элементы a и b сравнимы по отношению порядка R, если выполняется одно из условий aRb или b R-1а.
Множество М, на котором задано отношение порядка, называется полностью упорядоченным, если любые два элемента М сравнимы, и частично упорядоченным в противном случае.
Примеры.
1. Отношения ““ и ““ для чисел являются отношениями нестрогого порядка, а отношения ““ и ““ - отношениями строгого порядка. Оба отношения полностью упорядочивают множества N и R.
2. Определим отношения ““ и ““ для векторов на Rn следуюшим образом:
(a1,a2,...,an)(b1,b2,...,bn), если a1 b1, a2 b2, an bn;
(a1,a2,...,an)<(b1,b2,...,bn), если (a1,a2,...,an)(b1,b2,...,bn) и хотя бы в одной координате i выполнено условие ai<bi.
Эти отношения определяют частичный порядок на Rn.
Например, при n=3 (7,4,-3)<(7,6,-3), а (7,4,-3) и (7,0,0) не сравнимы.
3. На системе подмножеств множества М отношение включения ““ задаёт нестрогий частичный порядок, а отношение ““ задаёт строгий частичный порядок. Например, {1,2}{1,2,3}, а {1,2} и {1,3,4} не сравнимы.
4. Отношение подчинённости на предприятии задаёт строгий частичный порядок. Несравнимыми в нём являются сотрудники разных отделов.
5. Пусть в списке букв конечного алфавита А порядок букв зафиксирован, как, например, в русском или латинском алфавите. Тогда этот список определяет полное упорядочение букв, которое называют отношением предшествования и обозначают “” (aiaj, если ai предшествует aj в списке букв. На основе отношения предшествования букв строится отношение предшествования слов, определяемое следующим образом. Пусть даны слова
1=a11 a12 ... a1n и 2=a21 a22 ... a2m. Тогда 12, когда
- либо 1=ai, 2=aj и aiaj (, , - некоторые слова, возможно, пустые; ai и aj - буквы),
- либо 2=1, где - непустое слово.
Это отношение задаёт полное упорядочение множества всех конечных слов в алфавите А, которое называется лексико-графическим упорядочением слов.
а) Наиболее известным примером лексико-графического упорядочения является упорядочение слов в словарях. Например,
математика материал (здесь =мате, мр, =атика, =иал);
ком команда (здесь =анда).
б) Если рассматривать числа в позиционных системах счисления (например, в двоичной или десятичной) как слова в алфавите цифр, то их лексико-графическое упорядочение совпадает с обычным, если сравниваемые числа имеют одинаковое число разрядов.
В общем случае эти два вида упорядочения могут не совпадать: например, 70<705 и 80<705, но 70 705, а 80705. Чтобы они совпали, нужно выровнять число разрядов у сравниваемых чисел, приписывая слева нули, например 080705. Такое выравнивание автоматически происходит при записи целых чисел в ЭВМ.
в) Лексико-графическое упорядочение цифровых представлений дат вида 31.01.98 не совпадает с естественным упорядочением дат от ранних к поздним: например, 31.01.98 лексико-графически “старше” 27 числа любого года. Чтобы возрастание дат совпало с лексико-графическим упорядочением, на первое место в дате надо поставить год, затем месяц и, наконец, число: 98.01.31. Так обычно хранят даты в памяти ЭВМ.