- Главная
- Математика
- Элементы Комбинаторики Множество и операции над ними
Содержание
- 2. Любую совокупность действительных чисел называют числовым множеством. Множества с элементами - это понятие не определяется, а
- 3. Два множества называют равными, если они состоят из одних и тех же элементов. Например, множество равносторонних
- 4. Бесконечное множество нельзя задать списком. Его задают обычно характеристическим свойством – свойством, которым обладают элементы множества
- 5. Если Y X, то разность X\Y называют дополнением множества Y в множестве X и обозначают Yx.
- 6. Алгебра множеств. Операции над множествами обладают свойствами, которые отчасти напоминают свойства действий над числами, а отчасти
- 7. IV. Выполняются равенства 5) ø’=U и 5’) U’=ø, V. Для любых двух множеств X и Y
- 8. Разбиение множества на подмножества. Определение: Пусть U – некоторое множество и Xα, αЄА – система подмножеств
- 9. Кортежи и декартово произведение множеств. Определение: Пусть даны множества X1, …, Xn. Кортежем длины n, составленным
- 10. Отличия понятия кортежа и множества: Кортежи отличающиеся порядком элементов, различны даже в случае, когда они имеют
- 11. Отображение множеств. Определение: Соответствие, сопоставляющее каждому элементу x множества X один и только один элемент множества
- 12. Определение: Если при отображении f различные элементы множества X переходят в различные элементы множества Y, то
- 14. Скачать презентацию
Любую совокупность действительных чисел называют числовым множеством.
Множества с элементами - это
Любую совокупность действительных чисел называют числовым множеством.
Множества с элементами - это
Пример 1: Если X – множество русских слов из словаря В.И. Даля, то «семья» Є X, а «sieben» Є X, 8 Є X.
Є X
Два множества называют равными, если они состоят из одних и тех
Два множества называют равными, если они состоят из одних и тех
Множество, не содержащее ни одного элемента (например, множество натуральных корней уравнения 4x2-1=0), называют пустым множеством. Его обозначают ø.
Множество яблок в мешке, рыб в океане, видов живых существ конечны – количество их элементов можно выразить натуральным числом. Множества натуральных чисел, ромбов на плоскости, шаров в пространстве бесконечны. Конечное множество можно задать списком его элементов (например, множество учеников в классе задается их списком в классном журнале). Два списка элементов одного и того же множества X могут отличатся друг от друга лишь порядком элементов. Например, {1, 2, 3} и {3, 1, 2} – списки одного и того же множества {1, 2, 3}={3, 1, 2}.
Бесконечное множество нельзя задать списком. Его задают обычно характеристическим свойством –
Бесконечное множество нельзя задать списком. Его задают обычно характеристическим свойством –
Если каждый элемент множества X является в то же время элементом множества Y, то говорят, что X – часть, или иначе, подмножество множества Y (X Y).
Определение: Пересечением множеств X и Y называется множество X∩Y, состоящее из элементов, которые принадлежат как X, так и Y.
X
Y
Y
X
X∩Y
Если Y X, то разность X\Y называют дополнением множества Y в
Если Y X, то разность X\Y называют дополнением множества Y в
Такие изображения множеств и операций над ними называют диаграммами Эйлера – Венна.
X
Y
Y
X
Определение: Объединением множеств X и Y называют множество XυY, состоящее из элементов, которые принадлежат хотя бы одному из множеств X,Y.
Определение: Разностью множеств X и Y называется множество X\Y, состоящее из всех элементов множества X, не принадлежащие множеству Y.
XυY
Алгебра множеств.
Операции над множествами обладают свойствами, которые отчасти напоминают свойства
Алгебра множеств.
Операции над множествами обладают свойствами, которые отчасти напоминают свойства
Для любых множеств X и Y выполняются равенства
XυY=YυX и 1’) X∩Y=Y∩X.
II. Для любых трех множеств X, Y, Z выполняются равенства
2) (XυY)υZ=Xυ(YυZ) и 2’) (X∩Y)∩Z=X∩(Y∩Z)
3) (XυY)∩Z=(X∩Z)υ(Y∩Z) и 3’) (X∩Y)υZ=(XυZ)∩(YυZ)
III. Для любого множества X U имеет место равенство
4) (X’)’=X
Y
C
X
IV. Выполняются равенства
5) ø’=U и 5’) U’=ø,
V. Для любых двух
IV. Выполняются равенства
5) ø’=U и 5’) U’=ø,
V. Для любых двух
6) (X∩Y)’=X’υY’ и 6’) (XυY)’=X’∩Y’.
Поскольку для любого множества X справедливо ø X и X X, то всегда верны равенства ø∩X=ø, øυX=X, X∩X=X, XυX=X.
Если два выражения имеют одинаковую нормальную форму (с точностью до перестановки), то они тождественно равны – при подстановке вместо букв любых множеств из них получается одно и то же множество.
Разбиение множества на подмножества.
Определение: Пусть U – некоторое множество и Xα,
Разбиение множества на подмножества.
Определение: Пусть U – некоторое множество и Xα,
а) объединение всех множеств Xα совпадает с U, U=υαXα;
б) если α=β, то пересечение множеств Xα и Xβ пусто:
Xα∩Xβ=ø.
Тогда говорят, что множество U разбито на части Xα, αЄА.
Пример: Если X – подмножество в U, то U разбивается на множества X и X’ (дополнение к X).
Кортежи и декартово произведение множеств.
Определение: Пусть даны множества X1, …, Xn.
Кортежем
Кортежи и декартово произведение множеств.
Определение: Пусть даны множества X1, …, Xn.
Кортежем
Пример: Любое слово является кортежем, составленным из букв, десятичная запись любого натурального числа – кортежем, составленным из цифр, и т.д.
Определение: Два кортежа равны в том и только в том случае, когда они имеют одинаковую длину, причем их координаты, стоящие на местах с одинаковыми номерами, равны.
Кортежи длины 2 называют упорядоченными парами, длины 3 –упорядоченными тройками, …, длины n – упорядоченными n-ками. Для краткости речи слово «упорядоченные» часто опускают
Пример:Кортежи (12,22,32) и ( 1, 16, 81) равны, поскольку 12= 1, 22= 16, 32= 81.
Отличия понятия кортежа и множества:
Кортежи
отличающиеся порядком элементов, различны даже в случае,
Отличия понятия кортежа и множества:
Кортежи
отличающиеся порядком элементов, различны даже в случае,
Координаты могут повторяться.
Кортежи – в круглые скобки
Множества
Порядок элементов не играет роли.
Все элементы различны.
Множества – в фигурные скобки.
Определение: Пусть A1, …, An – некоторые множества. Их декартовым произведением называют множество, состоящее из всех кортежей вида (a1, …, an), где akЄAk, 1<=k<=n. Декартово произведение множеств A1, …, An обозначают A1, …, An обозначают A1X … X An.
Пример: Декартово произведение RXR состоит из пар (x, y) действительных чисел, причем (x1, y1)=(x2, y2) в том и только в том случае, когда x1=x2, y1=y2. Каждой такой паре соответствует точка M (x; y) на плоскости, для которой числа x и y являются декартовыми координатами ( отсюда название «декартово произведение»). Декартово произведение RXRXR состоит из троек чисел (x, y, z), которые можно рассматривать как координаты точки M (x; y; z) в трехмерном пространстве. Декартово произведение RXRX…XR (n множителей) называют n-мерным арифметическим пространством. Его обозначают Rn.
Отображение множеств.
Определение: Соответствие, сопоставляющее каждому элементу x множества X один и
Отображение множеств.
Определение: Соответствие, сопоставляющее каждому элементу x множества X один и
Определение: Если при отображении f различные элементы множества X переходят в
Определение: Если при отображении f различные элементы множества X переходят в
Определение: Если при отображении f каждый элемент множества Y является образом хотя бы одного элемента из X (т.е. если все полные прообразы f-1(y), yЄY не пусты), то f называют отображением X на Y, а не X в Y.
Определение: Обратимое отображение множества X на множество Y называют взаимно однозначным отображением X на Y.
Пример: Отображение, при котором каждому пальто сопоставляется крючок, на котором оно висит, является обратимым, если на каждом крючке висит не более одного пальто (некоторые крючки могут быть пустыми). Оно является отображением множества пальто X на множество крючков Y, если на каждом крючке висит хоть одно пальто (на некоторых крючках может быть несколько пальто). Наконец, оно является взаимно однозначным отображением X на Y если на каждом крючке висит ровно одно пальто.