Материал: Дискретная математика. учебное пособие. Горбунов В.В., Лапшина М.Л

Пример 1.8. Отображение : {1, 2, 3, 4} {у , у , y } с условиями , не является сюрьективным (не все y имеют прообразы).

Отображение : X Y называется инъективным, или инъекцией, если каждый элемент y Y имеет хотя бы один прообраз х Х либо вообще не имеет прообраза.

Пример 1.9. Пусть Х = {1, 2, 3}, Y = {у , у , y , }, Отображение : инъективно, если , , . Все значения x имеют образы.

Если отображение одновременно является сюръективным и инъективным, то оно называется биективным отображением или биекцией.

Пример 1.10. Пусть Х={1, 2,3}, Y={у , у , y }. Отображение биективно, если , , .

При биективном отображении каждому элементу одного множества соответствует ровно один элемент другого множества, при этом определено обратное отображение, которое обладает тем же свойством. Поэтому биективное отображение называют ещё взаимно-однозначным отображением (соответствием). Биективное отображение определяет взаимно однозначное соответствие между множествами Х и Y, которые считаются эквивалентными (равномощными).

Если для каждого х, такого что (х,у) f, имеется единственный образ, то соответствие называется функциональным и определяет функцию f на множестве Х со значениями в множестве Y.

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

Функция вида называется n-местной функцией. В этом случае принято считать , что функция имеет n аргументов: .

Функция называется инъективной, если для любых из и следует, что (все x имеют свои y).

Функция f называется сюръективной, если для любого элемента существует элемент такой, что у = f (х) (все y имеют свои x).

Функция f называется биективной, если f одновременно сюръективна и инъективна.

Если существует биективная функция f, то говорят, что f осуществляет взаимно - однозначное соответствие между множествами и .

Если функция f задает отображение , a функция g задает отображение , то функция F, соответствующая отображению и определенная для каждого формулой , называется композицией функций f и g или сложной функцией. Например, композицией отображения и отображения является отображение .

Если функция f задает отображение , совокупность всевозможных упорядоченных пар вида , образует функцию, которая называется обратной функцией для функции f и обозначается . Обратная функция ставит в соответствие каждому элементу у его прообраз (y). Заметим, что для того, чтобы являлась функцией, достаточно, чтобы функция f была инъективной.

Пример 1.11. Функция инъективна при отображении , но не сюрьективна (не все y имеют соответствующие значения аргументов);

Функция биективна.

К специальным отображениям относятся понятия оператора и функционала.

Вопросы для самопроверки

1. Что такое множество?

2. Как обозначаются множества и их элементы?

3. Какими способами задаются множества?

4. Указать варианты описания множества нечетных натуральных чисел.

5. Какое множество называется пустым?

6. Что такое подмножество?

7. Какие множества называются счетными?

8. Поясните термин «мощность множества» и укажите его обозначение.

9. Что такое «универсальное « множество?

10. Перечислите операции над множествами.

11. Дайте определение объединения множеств.

12. Проиллюстрируйте с помощью диаграммы Венна операцию пересечения множеств.

13. Какие множества называются непересекающимися?

14. Дайте определение разности множеств и опишите разность множеств как множество описательным способом.

15. Дайте определение дополнения множества.

16. Можно ли определить дополнение множества, если не описано универсальное множество?

17. Перечислите законы (тождества) для операций объединения и пересечения множеств и докажите их.

18. Перечислите законы (тождества) для операции разности множеств и докажите их.

19. Перечислите законы (тождества) для операции дополнения множеств и докажите их.

Задачи по теме «Операции над множествами»

Задача 1. Укажите все собственные подмножества множества .

Ответ: , , , Ø.

Задача 2. Для каких из следующих соотношений пар множеств имеет место для множеств и ?

Ответ: .

Задача 3. Найти .

Ответ: .

Задача 4. Даны множества , , , . Задайте списками множество , , .

Ответ: , ,

.

Задача 5. Изобразите с помощью диаграмм Венна множество .

Ответ:

Это множество является объединением двух разностей, называется симметрической разностью и обозначается , т. е. = .

Задача 6. Опрос 100 студентов дал следующие результаты о количестве студентов, изучающих различные иностранные языки: испанский — 28; немецкий — 30; французский — 42; испанский и немецкий — 8; испанский и французский — 10; немецкий и французский — 5; все три языка — 3.

а) Сколько студентов не изучает ни одного языка?

б) Сколько студентов изучает один французский язык?

в) Сколько студентов изучает немецкий язык в том и только в том случае, если они изучают французский язык?

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

Ответ: а) 20; б) 30; в) 38.

2. Элементы комбинаторики

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

Рассмотрим первое основное правило комбинаторики или правило произведения.

Пусть необходимо выполнить работу, совершая последовательно k действий. Определим количество способов N выполнения работы. Если первое действие можно выполнить способами, второе способами и так далее, причем последнее k-тое действие можно выполнить способами, то все k действий можно выполнить способами, т.е.

N= .

Другим часто применяемым в комбинаторике правилом является правило суммы. Это правило формулируется следующим образом: если элемент может быть выбран способами, а элемент — способами, и т.д., то количество N вариантов выбора «либо , либо , …,либо » равно