- •Учебно-методический комплекс дисциплины сд.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. Учебные занятия по дисциплине ведут:
§ 9. Отображения и их свойства
Отображением множества X во множество Y называется правило, по которому каждому элементу множества X ставится в соответствие один или несколько элементов множества Y.
Пример. Пусть X - это множество современных отечественных актёров кино, а Y - это множество современных отечественных кинофильмов. Актёру x ставится в соответствие фильм y, если актёр x снимался в фильме y. Один актёр мог сниматься в нескольких фильмах, и, наоборот, в одном фильме может быть занято несколько актёров.
Однозначным отображением множества X во множество Y называется правило, по которому каждому элементу множества X ставится в соответствие единственный элемент из множества Y.
Пример. Пусть X - это множество студентов очного обучения г.Мурманска, а Y - это множество вузов г. Мурманска. Студенту x ставится в соответствие ВУЗ y, если студент x учится в вузе y. Очевидно, один студент учится только в одном вузе, тогда как в каждом вузе может учиться несколько студентов.
В дальнейшем речь пойдёт только об однозначных отображениях, поэтому слово “однозначное” применительно к отображению будем опускать. При отображении соответствие между элементами xX и yY записывается равенством y= (x), а самому отображению соответствует запись : XY. Множество X есть область определения отображения, а Y - область его значений.
Если X={x1,x2,...,xn}, то отображение : XY может быть представлено в виде двустрочной записи:
=,
где (xi)Y, i=1,2,...,n.
Пример 1.4. Отображение : XY, где X={1,2,3,4,5}, Y={a,b,c}, может быть задано так:
=.
Два отображения 1: X1Y1 и 2: X2Y2 равны, если они имеют одинаковые области определения: X1=X2, одинаковые области значений: Y1=Y2 и 1(x)= 2(x) для любого xX.
Множество -1(y)={x/ y=(x), xX}называется полным прообразом элемента y при отображении .
Пример. Выпишем полные прообразы для каждого элемента из области значений в примере 1.4: -1(a)={1,2,5}, -1(b)={3}, -1(c)={4}.
Отображение : XX множества X в себя называется преобразованием множества X.
Пример. Пусть X={0,1,2,3,4}, (x)=(x+1) mod 3. Тогда двустрочная запись такого преобразования имеет вид:
= .
Свойства отображений
1. Отображение : XY называется сюръективным, если каждый элемент yY имеет хотя бы один прообраз при этом отображении. Иными словами, для любого yY найдётся такой элемент xX, что y=(x). Значит, для любого yY -1(y) и мощность полного прообраза обязательно больше нуля: | -1(y) | 1.
Для конечных множеств X и Y сюръективность отображения означает, что мощность множества X не меньше мощности множества Y, т.е. |X| |Y|.
Примеры.
а) В примере 1.4 - сюръективное отображение.
б) Пусть множество Y - это множество благополучных (посещающих лекции и пишущих конспекты) студентов в группе, а множество X - это множество конспектов, написанных этими студентами за семестр. Отображение : XY является сюръективным, так как каждый конспект имеет только одного “хозяина”, а каждый студент написал не менее одного конспекта.
2. Отображение : XY называется инъективным, если для любого yY его полный прообраз содержит не более одного элемента, т.е. для любых xx1, x,x1X, (x)(x1). В этом случае для любого yY мощность его полного прообраза не больше единицы: | -1(y) | 1.
Для конечных множеств X и Y инъективность отображения означает, что мощность множества X не больше мощности множества Y, т.е. |X| |Y|.
Примеры.
а) В примере 1.4 - не инъективно ( |-1(a)| = 3 > 1).
б) Отображение 1: {1, 2, 3}{m, n, p, q} вида 1 =инъективно.
в) Пусть множество Y - это множество совершеннолетних законопослушных жителей г.Мурманска на 1 января 2001 года, а множество X - это множество выданных им водительских прав. Отображение : XY является инъективным, так как у каждых водительских прав только один владелец, но не каждый гражданин имеет водительские права, а если имеет, то только одни права (в силу своей законопослушности).
3. Отображение : XY называется биективным, если оно одновременно сюръективно и инъективно.
Из сюръективности следует, что | -1(y) | 1 для любого yY; из инъективности вытекает условие | -1(y) | 1 для каждого yY. Следовательно, биективность отображения означает, что | -1(y) | = 1 для любого yY, т.е. условие y=(x) для каждого yY однозначно определяет единственное значение xX.
Примеры.
а) В примере 2.4 не является биективным отображением, т.к. оно не инъективно.
б) Отображение : {1, 2, 3, 4}{m, n, p, q} вида 1 = биективно.
в) Пусть множество Y - это множество студентов в МГТУ на 1 января 2001 года, а множество X - это множество зачётных книжек, выданных этим студентам. Отображение : XY является биективным, так как у каждого студента имеется своя “зачётка”, причём только одна.
Биективное отображение устанавливает взаимно однозначное соответствие между множествами X и Y. Когда X и Y конечны, это означает равенство их мощностей: |X| = |Y|. Этот факт, во-первых, позволяет установить равенство мощностей двух множеств, не вычисляя этих мощностей, а во-вторых, часто даёт возможность вычислить мощность множества, установив его взаимно однозначное соответствие с множеством, мощность которого известна или легко вычисляется.