Тема 1. Множества, функции, отношения

Множества – основные понятия. Диаграммы Венна. Операции над множествами: объединение, пересечение, дополнение. Кортежи и прямое (декартово) произведение множеств. Соответствия и их свойства. Взаимно однозначные соответствия. Мощности бесконечных множеств. Принципы включений – выключений. Понятие функции. Обратные функции. Суперпозиции и формулы. Способы задания функций. Общее понятие отношения. Бинарные отношения и их свойства (рефлексивность, симметричность, транзитивность). Отношение эквивалентности и классы эквивалентности. Отношение порядка. Линейный порядок и частичный порядок. ([1, часть 2, кроме § 5, 6]; [2, разд. 1.1‒1.3]; [3, § 5.1, 13.1 – 13.3]).

Понятие множества относится к числу первичных, под которым понимается некоторая совокупность элементов, объединенных по каким-либо признакам. С множествами, их графическим изображением на диаграммах Венна студенты встречались ранее в курсах математического анализа и теории вероятностей. Там же рассматривались понятия подмножества В (части данного множества А: Тема 1. Множества, функции, отношения - student2.ru ), пустого множества Тема 1. Множества, функции, отношения - student2.ru (не содержащего ни одного элемента), дополнения Тема 1. Множества, функции, отношения - student2.ru множества А (состоящего из всех элементов некоторого универсального множества[2] U, не входящих в множество А). Определялись основные операции над множествами А и В: объединение Тема 1. Множества, функции, отношения - student2.ru (множество, состоящее из всех элементов множества А и В), пересечение Тема 1. Множества, функции, отношения - student2.ru (множество, состоящее из всех общих элементов А и В), разность Тема 1. Множества, функции, отношения - student2.ru (множество, состоящее из всех элементов множества А, не входящих в множество В).

В данном курсе вводится понятие прямого, или декартова, произведения множеств А и В, т.е. множество Тема 1. Множества, функции, отношения - student2.ru , элементы которого представляют всевозможные упорядоченные пары элементов множеств А и В (например, декартово произведение координатных осей Ох и Оу есть плоскость Оху).

Множество называется конечным, если содержит конечное число элементов и – бесконечным в противном случае.

Если между множествами А и В имеет место взаимно однозначное соответствие (т.е. каждому элементу Тема 1. Множества, функции, отношения - student2.ru соответствует определенный элемент Тема 1. Множества, функции, отношения - student2.ru ( Тема 1. Множества, функции, отношения - student2.ru ) и наоборот ( Тема 1. Множества, функции, отношения - student2.ru )), то говорят что множества А и В имеют одинаковую мощность или эквивалентны: Тема 1. Множества, функции, отношения - student2.ru ~ Тема 1. Множества, функции, отношения - student2.ru . Для конечных множеств это означает, что в них одинаковое число элементов. В случае бесконечного множества мощность является обобщением понятия «число элементов». В этом смысле счетные[3] множества являются «самыми маленькими» из бесконечных множеств.

Пример 1. Даны множества чисел Тема 1. Множества, функции, отношения - student2.ru , Тема 1. Множества, функции, отношения - student2.ru , Тема 1. Множества, функции, отношения - student2.ru и универсальное множество Тема 1. Множества, функции, отношения - student2.ru . Найти множества чисел: Тема 1. Множества, функции, отношения - student2.ru ; Тема 1. Множества, функции, отношения - student2.ru . Являются ли множества Е и D равными? эквивалентными? включающими одно в другое ( Тема 1. Множества, функции, отношения - student2.ru или Тема 1. Множества, функции, отношения - student2.ru )? пересекающимися, но не включающими одно в другое? непересекающимися ( Тема 1. Множества, функции, отношения - student2.ru Тема 1. Множества, функции, отношения - student2.ru )?

Р е ш е н и е. Для нахождения множества D вначале найдем: пересечения множеств Тема 1. Множества, функции, отношения - student2.ru , Тема 1. Множества, функции, отношения - student2.ru , дополнение множества С (до множества U) Тема 1. Множества, функции, отношения - student2.ru , разность множеств Тема 1. Множества, функции, отношения - student2.ru . Теперь Тема 1. Множества, функции, отношения - student2.ru .

Для нахождения множества Е вначале найдем: Тема 1. Множества, функции, отношения - student2.ru , Тема 1. Множества, функции, отношения - student2.ru , Тема 1. Множества, функции, отношения - student2.ru , Тема 1. Множества, функции, отношения - student2.ru . Теперь Тема 1. Множества, функции, отношения - student2.ru . Множества D и Е – не равные (так как не состоят из одинаковых элементов), не эквивалентные (так как имеют разные мощности (число элементов)), причем множество Е включается в множество D ( Тема 1. Множества, функции, отношения - student2.ru ). ►

Бинарным (двухместным) отношением множеств А и В называется любое подмножество R декартова множества Тема 1. Множества, функции, отношения - student2.ru , т.е. Тема 1. Множества, функции, отношения - student2.ru . Это означает, что если элементы х и у связаны бинарным отношением R (записываемым в виде xRy), то пара (х, у) является элементом R, т.е. Тема 1. Множества, функции, отношения - student2.ru . Среди свойств бинарных отношений выделяют рефлексивность, симметричность, транзитивность ([1, часть 2, § 10]; [3, §13.3]). Бинарное отношение, для которого выполнены указанные три свойства, называется отношением эквивалентности, являющееся обобщением понятия равенства. Подмножества элементов, эквивалентные данному, называется его классом эквивалентности. Если бинарное отношение R на множестве Х рефлексивно, транзитивно и антисимметрично, то оно называется отношением порядка (отношением частичного порядка). Отношение частичного порядка называется линейным порядком, если для любых значений х и у имеет место либо xRy, либо уRх.

Соответствие Тема 1. Множества, функции, отношения - student2.ru , сопоставляющее каждому элементу х множества Х один и только один элемент у множества Y, называется отображением множества Х на множество Y.

Функцией называется бинарное отношение Тема 1. Множества, функции, отношения - student2.ru , если из Тема 1. Множества, функции, отношения - student2.ru и Тема 1. Множества, функции, отношения - student2.ru , следует, что Тема 1. Множества, функции, отношения - student2.ru . Если область определения и область значений функции соответственно Х и Y, то говорят, что функция Тема 1. Множества, функции, отношения - student2.ru отображает множество Х на множество Y, т.е. Тема 1. Множества, функции, отношения - student2.ru . Это означает, что для любого элемента Тема 1. Множества, функции, отношения - student2.ru существует единственный элемент Тема 1. Множества, функции, отношения - student2.ru такой, что Тема 1. Множества, функции, отношения - student2.ru .

Подробнее о функциях говорилось в курсе «Математического анализа».

Важное значение в теории множеств имеет формула включений-выключений (принцип включений-выключений), позволяющая определить мощность объединения конечного числа конечных множеств. В простейших случаях (для двух или трех множеств) эта формула имеет вид:

Тема 1. Множества, функции, отношения - student2.ru , (1)

Тема 1. Множества, функции, отношения - student2.ru . (2)

Пример 2. Из 250 абитуриентов экономического вуза, сдававших вступительные экзамены, отметку «3» получили: по математике 86 чел, по русскому языку – 71, обществознанию – 50, по математике или русскому языку – 130, по математике или обществознанию – 112, по русскому языку или обществознанию– 94, по всем трем предметам – 18 чел. Сколько абитуриентов сдали вступительные экзамены: а) без троек; б) с одной тройкой по математике; в) с одной тройкой.

Р е ш е н и е. а) Пусть Тема 1. Множества, функции, отношения - student2.ru , Тема 1. Множества, функции, отношения - student2.ru , Тема 1. Множества, функции, отношения - student2.ru – число абитуриентов, получивших отметку «3» соответственно по математике, русскому языку и обществознанию. По условию Тема 1. Множества, функции, отношения - student2.ru , Тема 1. Множества, функции, отношения - student2.ru , Тема 1. Множества, функции, отношения - student2.ru , Тема 1. Множества, функции, отношения - student2.ru , Тема 1. Множества, функции, отношения - student2.ru , Тема 1. Множества, функции, отношения - student2.ru , Тема 1. Множества, функции, отношения - student2.ru . Вначале найдем число абитуриентов, получивших оценку «3» по математике и русскому языку, т.е. Тема 1. Множества, функции, отношения - student2.ru . Из формулы (1) Тема 1. Множества, функции, отношения - student2.ru . Аналогично Тема 1. Множества, функции, отношения - student2.ru , Тема 1. Множества, функции, отношения - student2.ru .

Теперь найдем число, абитуриентов, получивших оценку «3» хотя бы по одному из трех предметов, т.е. Тема 1. Множества, функции, отношения - student2.ru . По формуле (2) Тема 1. Множества, функции, отношения - student2.ru . Следовательно, число абитуриентов, сдавших вступительные экзамены без троек, равно 250–147=103 (чел).

Тема 1. Множества, функции, отношения - student2.ru б) Вначале найдем число абитуриентов, имеющих только две тройки – по математике и русскому языку: Тема 1. Множества, функции, отношения - student2.ru , по математике

и обществознанию: Тема 1. Множества, функции, отношения - student2.ru Следовательно, только одну тройку по математике имеют 86– –9–6–18=53 (чел).

в) Аналогично п. б) найдем число абитуриентов, имеющих только одну тройку по русскому языку: 71– (27–18) –(27–18) –18=35 (чел) и по обществознанию:50–(24– –18) – (27–18) –18=17 (чел). Всего абитуриентов, имеющих только одну тройку, равно 53+35+17=105

(чел). Решение задачи легко иллю-

Рис. 1 стрируется на диаграмме Венна. (рис.1)►

Тема 2. Комбинаторика

Предмет комбинаторики. Правило суммы и правило произведения. Размещения, перестановки, сочетания без повторений и с повторениями. Биномиальные коэффициенты и соотношения для них. Задачи перечисления. Подсчет числа функций с конечными областями определения. ([1, часть 3]; [2, разд. 3.1]); [3, § 1.5]).

Комбинаторика – раздел математики, изучающий методы решения задач, связанных с выбором и расположением частей конечного множества, в частности, комбинаторных задач на подсчет числа различных комбинаций.

Студенты должны четко знать правила комбинаторики:

- правило суммы: если объект Тема 1. Множества, функции, отношения - student2.ru может быть выбран Тема 1. Множества, функции, отношения - student2.ru способами, Тема 1. Множества, функции, отношения - student2.ru – другими Тема 1. Множества, функции, отношения - student2.ru способами, то выбор одного из объектов Тема 1. Множества, функции, отношения - student2.ru или Тема 1. Множества, функции, отношения - student2.ru может быть осуществлен Тема 1. Множества, функции, отношения - student2.ru + Тема 1. Множества, функции, отношения - student2.ru способами;

- правило произведения: если объект Тема 1. Множества, функции, отношения - student2.ru может быть выбран Тема 1. Множества, функции, отношения - student2.ru способами, после каждого такого выбора объект Тема 1. Множества, функции, отношения - student2.ru может быть выбран Тема 1. Множества, функции, отношения - student2.ru способами, то выбор всех объектов Тема 1. Множества, функции, отношения - student2.ru , Тема 1. Множества, функции, отношения - student2.ru в указанном порядке может быть осуществлен Тема 1. Множества, функции, отношения - student2.ru Тема 1. Множества, функции, отношения - student2.ru способами.

Из множества Тема 1. Множества, функции, отношения - student2.ru различных элементов могут быть образованы подмножества (комбинации) из Тема 1. Множества, функции, отношения - student2.ru элементов Тема 1. Множества, функции, отношения - student2.ru .

Если комбинации из Тема 1. Множества, функции, отношения - student2.ru элементов по Тема 1. Множества, функции, отношения - student2.ru отличаются, либо составом элементов, либо порядком их расположения (либо и тем и другим), то их называют размещениями. Число размещений из Тема 1. Множества, функции, отношения - student2.ru элементов по Тема 1. Множества, функции, отношения - student2.ru находятся по формуле:

Тема 1. Множества, функции, отношения - student2.ru или Тема 1. Множества, функции, отношения - student2.ru .

(где Тема 1. Множества, функции, отношения - student2.ru ).

Если комбинации из Тема 1. Множества, функции, отношения - student2.ru элементов по Тема 1. Множества, функции, отношения - student2.ru отличаются только составом элементов, то их называют сочетаниями. Число сочетаний из Тема 1. Множества, функции, отношения - student2.ru элементов по Тема 1. Множества, функции, отношения - student2.ru находятся по формуле:

Тема 1. Множества, функции, отношения - student2.ru или Тема 1. Множества, функции, отношения - student2.ru .

Свойства числа сочетаний:

Тема 1. Множества, функции, отношения - student2.ru (ибо Тема 1. Множества, функции, отношения - student2.ru ), Тема 1. Множества, функции, отношения - student2.ru .

Если комбинации из Тема 1. Множества, функции, отношения - student2.ru элементов отличаются только порядком элементов, то их называют перестановками. Число перестановок из Тема 1. Множества, функции, отношения - student2.ru элементов находится по формуле:

Тема 1. Множества, функции, отношения - student2.ru

Пример 3.В первом туре конкурса участвуют 16 человек. Сколько существует различных исходов этого тура, при которых совпадают участники, занявшие призовые 1-е, 2-е и 3-е места, а также два участника, занявшие 15-е и 16-е места и выбывающие из дальнейшего участия в конкурсе?

Р е ш е н и е. Способы распределения участников, занявших 1-е, 2-е и 3-е места (из 16), отличаются как составом участников, так и их порядком; их число – число размещений Тема 1. Множества, функции, отношения - student2.ru . Из оставшихся Тема 1. Множества, функции, отношения - student2.ru участников два выбывают из конкурса (порядок этих участников значения не имеет); их число – число сочетаний Тема 1. Множества, функции, отношения - student2.ru . По правилу произведения (см. с. 8) получаем, что число различных исходов первого тура конкурса, удовлетворяющих условию задачи, есть

Тема 1. Множества, функции, отношения - student2.ru

(или Тема 1. Множества, функции, отношения - student2.ru ).

Другой способ решения состоит в том, что общее число различных исходов первого тура с 16-ю участниками (без учета распределения тех или иных мест) равно числу перестановок Тема 1. Множества, функции, отношения - student2.ru . Перестановки участников, занявших места с 4-го по 14-е (т.е. 11 мест), а также 15-е и 16-е места (2 места) приводят к совпадающему в соответствии с условием исходу первого тура; их число (по правилу произведения) равно Тема 1. Множества, функции, отношения - student2.ru . Значит, число различных исходов первого тура конкурса, удовлетворяющих условию, есть

Тема 1. Множества, функции, отношения - student2.ru . ►

Если в комбинациях из Тема 1. Множества, функции, отношения - student2.ru элементов часть элементов (или все) являются одинаковыми, то их называют комбинациями (размещениями, сочетаниями, перестановками) с повторениями.

Соответствующие формулы таких комбинаций с повторениями, приведены в пособии ([1, часть 3]; [3, § 1.5]). Там же рассматриваются задачи на подсчет различных комбинаций [1, 1-ое практическое занятие]; [3, примеры 1.11 – 1.15].

Наши рекомендации