Множества. Операции над ними. Комбинаторика

1.

БГТУ им. В.Г. Шухова
Кафедра информационных технологий
Дискретная
математика
Коломыцева Елена Павловна, 2020

2.

Тема 1
Множества

3.

Множества
Понятие множества относится к неопределяемым понятиям.
Множество состоит из некоторых объектов различных и
различаемых, которые называются элементами множества.
Например:
N- Множество натуральных чисел.
N 0 - множество натуральных чисел и 0.
Z- Множество целых чисел.
Q - Множество рациональных чисел. Множество Q так же можно
представить в виде множества дробей
p
, где p и q – целые числа.
q
R- Множество действительных чисел.
Одинаковые элементы, входящие во множество, не различаются и
считаются один раз.
Порядок элементов во множестве не определен.
Множество, не содержащее ни одного элемента, называется
пустым - Ǿ.
Способы задания множества:
1) Перечислением всех элементов множества. А={3,1,2,5}.
2) С помощью характеристического свойства.
В={x R/ (x+3)<4} или
В={x (-∞;1)}.
3) Процедурой. A={x2 /x N}

4.

Подмножества
Пусть задано множество А. Множество В, состоящее из элементов
множества А, называется подмножеством А.
Например. А={a, w, b, c} и В={w, a,b}, тогда В А или А В (В
включается в А или А включается в В).
Множество А является собственным подмножеством.
Множество, не содержащее ни одного элемента, называется
пустым Ø.
Пустое множество является подмножеством любого множества.

5.

Равенство множеств
Два множества называются равными, если они состоят из одних и
тех же элементов.
А={3, 2, а}. В={а, 3, а, 3, 2, а}. Имеем А=В.
Теорема. Множество А ровняется множеству В, если А является
подмножеством В, а В является подмножеством А.
Доказательство:
1) Пусть х А и А В. По определению подмножества х В.
Так как х- произвольный элемент А, то все элементы множества А
множеству В.
2) Пусть х В и В А. По определению подмножества х А.
Так как х- произвольный элемент В, то все элементы множества В
множеству А.
3) Так как все элементы множества А множеству В, а все
элементы множества В множеству А, то по определению равенства
множеств А=В.
Что и требовалось доказать.
Все множества рассматриваются как подмножества некоторого
универсального множества U.

6.

Мощность множеств
Количество элементов, входящих во множество, называется его
мощностью.
Для бесконечных множеств говорить о количестве элементов не
имеет смысла, но говорить о мощности множества можно.
Два множества называются равномощными, если существует метод,
позволяющий каждому элементу одного множества поставить в
соответствие элемент другого множества.
Пример:
Имеется множество натуральных чисел и имеется множество четных
чисел. Равномощны ли они?
Ответ: Да.
1 2 3 4 5…
↓ ↓ ↓ ↓ ↓
2 4 6 8 10…
Множества, равномощные множеству натуральных чисел,
называются счетными.

7.

Алгебра множеств. Операции над множествами.
Условимся U изображать в виде прямоугольника
а множество А-
(круги Эйлера-Венна)
А
Рис.1. Множества А и U.

8.

1).Объединение множеств.
А U B.
Объединением множеств А и В называется множество, состоящее
из элементов, входящих или в А, или в В.
3).Разность. А\B.
Разностью множеств А и В называется множество, состоящее из
элементов, входящих в А, но не входящих в В.
Рис.2. Объединение множеств.
2).Пересечение.
А∩В.
Пересечением двух множеств называется множество, состоящее из
элементов, входящих и в А, и в В.
Рис.4.Разность множеств.
1) Дополнение. Ā.
Дополнением множества А называется множество, состоящее из
элементов не входящих в А.
Рис.5.Дополнение множества А.

9.

5.Симметрическая разность A ∆ B.
Симметрической разностью множеств А и В называется
множество, состоящее из тех элементов множества А, которые не
принадлежат множеству В и тех элементов множества В, которые
не принадлежат множеству А.
Рис.4.Симметрическая разность множеств.

10.

Включение множеств
Множество А, все элементы которого принадлежат множеству В,
называется подмножеством множества В.
Обозначение. Нестрогое включение обозначается
, означает,
что А - несобственное подмножество множества В, возможно
совпадающее с В. Строгое включение обозначается
, и означает,
что А - подмножество множества В, не совпадающее с
B.
читается "А включено в В".
Отличия
и
заключается
в
том,
что
отношение
допускает и тождественность (А=В), т.е. любое
множество можно рассматривать как подмножество самого
себя
,
в
то
время
как
символ строгого
включения
ставится тогда, когда мы хотим подчеркнуть,
что
, то есть во множестве В содержатся не только элементы
множества А. Выполнение соотношений
и
возможно
только при А=В. И обратно, А=В, если
и
. Эти
соотношения являются признаком равенства множеств через
отношение включения. Заметим, что иногда в литературе
символом ⊂ обозначают "нестрогое" включение, допускающее и
равенство множеств. В этом случае символ ⊆ не используется, а
строгое
включение
записывают
двумя
соотношениями
,
.

11.

Свойства операций
1)
2)
3)
4)
Коммутативность.
АUB=BUA.
A∩B=B∩A.
Ассоциативность.
АU(BUC)=(AUB)UC.
A∩ (B∩C) = (A∩B) ∩C.
Дистрибутивность.
А∩(BUC)=(A∩B)U(A∩C). AU (B∩C) = (AUB) ∩ (AUC).
Законы Де-Моргана.
A B= AUB
AUB = A ∩ B
5)
6)
7)
AUA=A A∩A=A
AUØ=A A∩Ø= Ø
A U=U A∩U=A
8)
A
A U
A A
10) A\B= В А
9)
A
A Ø

12.

Разбиение множества на классы
Пусть задано некоторое множество, например множество
треугольников. В этом множестве выделим свойство (например, быть
прямоугольным). Тогда множество разбивается на два класса:
прямоугольные и непрямоугольные.
Разбиение множества на классы (классификация) означает, что
данное множество А разбивается на подмножества k 1 , k 2 ,.., k m таких,
что
1) Эти подмножества попарно не пересекаются, то есть
k i k j Ø
(i, j=1,…m, i≠j)
2)
Объединение всех подмножеств дает множество А
m
k
i
A
i 1
3) Ни одно из подмножеств не пусто
ki ≠ Ø

13.

Пример: Пусть имеется А - множество всех грибов.
Свойства:
1) 1 -быть съедобным грибом.
2) 2 -быть трубчатым грибом.
Таким образом, с помощью этих свойств мы получаем 4
подмножества:
съедобные и несъедобные
трубчатые и не трубчатые
Такое разбиение классификацией не является, так как эти
подмножества могут пересекаться, и пересечение не пусто.
Пусть В-множество съедобных грибов, а С - множество трубчатых.
k1 =B∩C-съедобные и трубчатые.
k 2 =B∩ С -съедобные и не трубчатые.
k 3 = В ∩C-несъедобные и трубчатые
k 4 = В ∩ С -несъедобные и не трубчатые.

14.

Декартово (прямое) произведение множеств
а1 и а 2 . Пара ( а1 , а 2 ) называется
упорядоченной. 1-ый элемент ее - а1 , 2-ой- а 2 .
Пары ( а1 , а 2 ) и ( b1 , b2 ) считаются равными, если а1 = b1 , а а 2 = b2 ;
Пара ( а1 , а 2 )=( а 2 , а1 ), если только а1 = а 2 .
Пусть у нас имеется два элемента
Пример1
Пусть заданы два множества
А={ à1 , à 2 ,…, à n } и В={ b1 , b2 ,… bm }.
Декартовым или прямым произведением множества А на множество В
называется множество упорядоченных пар, 1-ый элемент которых принадлежит
множеству А , а 2-ой множеству В.
Обозначается декартово произведение знаком Х.
Для данных множеств получим
АхВ={( à1 , b1 ),( à1 , b2 ),…,( à1 , bm ),…,( a 2 , b1 ),…,( à n , bm )}
Мощность декартового произведения равна nm.
Обозначение: |A X B|=nm.
Пример:
A= {1, 4} и В {2, 3, 4}. A X B={(1,2),(1,3),(1,4),(4,2),(4,3),(4,4)}
Геометрически каждой паре чисел соответствует точка координатной плоскости.
Рис.8. Декартово произведение А Х В для конечных А и В.

15.

Пример2
A={x R, \ x [-1; 2]};
B={y Z, \ y [-3; 3]};
Рис.9. А х В, где А - непрерывное множество.
Пример 3.
A={x R, \ x [-1; 2]};
B={y R, \ y [-3; +∞)};
Рис.10.Декатрово произведение А Х В. Оба множества непрерывны.

16.

Декартова степень.
Если в качестве множества В в декартовом произведении выбрать множество А,
мы будем говорить о декартовом квадрате.
А Х А=А
2
2
А Х А =А
…
n 1
3
n
АХА
=А
Набор n-элементов будем зазывать кортежем.
Декартовым произведением n-множеств
А 1 х А 2 х А 3 х…х А n будем называть множество упорядоченных кортежей, 1ый элемент которых принадлежит множеству А 1 , 2-ой множеству А 2 и т.д.

17.

Свойства Декартового произведения.
1)
2)
3)
4)
5)
6)
7)
8)
А Х В≠В Х А.
(А Х В) Х С≠А Х (В Х С).
А Х (В∩С)=(А Х В)∩(А Х С).
А Х (В С)=(А Х В) (А Х С).
(А∩В) Х С=(А Х С) ∩(В Х С).
(А В) Х С=(А Х С) (В Х С).
А Х (В\С)=(А Х В)\(А Х С).
(А\B) X C= (A X C)\ (B X C).

18.

Отношения.
Пусть заданы два множества А и В. Найдем А Х В.
Подмножество k А Х В называется отношением из множества А во
множество В.
Отношения задаются знаками =, <, >, ,
и т.д.
Пример:
А={2,3,4}, B={1,4,3}
A X B={(2,1),(2,4),(2,3),(3,1),(3,4),(3,3),(4,1),(4,4),(4,3)}
Выделим отношения больше > k1 ={(2,1),(3,1),(4,1),(4,3)}
и меньше <
k 2 ={(2,4),(2,3),(3,4)}
Рис.11. Отношение >.

19.

Композиция отношений.
Пусть отношение
k1 А Х С и отношение k 2 С Х В.
Композицией этих отношений является отношение k= k1 k 2 , где k A X B.
Композицией отношений из А в В называется множество пар (а,b) таких, что, а
А, b B и существует такое с С, что (а, с) k1 и (с,b) k 2 .
Пример:
А={2,3,4}, B={1,4,3}, С={2,5}
A X В={(2,1),(2,4),(2,3),(3,1),(3,4),(3,3),(4,1),(4,4),(4,3)}
A X C={(2,2),(2,5),(3,2),(3,5),(4,2),(4,5)}
C X B={(2,1),(5,1),(2,4),(5,4),(2,3),(5,3)}
Определим отношение
>: k1 A X C={(3,2),(4,2)} и отношение < k 2 C X B= {(2, 4), (2, 3)}
Возьмем пару (3,2) k1 . В k 2 есть пары, начинающиеся с 2. Это пары (2,4) и
(2,3). Значит пары (3, 4) и (3, 3) войдут в композицию k.
Берем пару (4,2) k1 . В k 2 есть пары, начинающиеся с 2. Это те же пары (2,4) и
(2,3). Значит пары (4, 4) и (4, 3) войдут в k.
Получим k= k1 k 2 =(k AXB)= {(3, 4), (3, 3), (4, 4), (4, 3)}
Таким образом, для элемента (2,4) А Х В, в k войдут {(2,х), (у,4)}, где (2,х)
k1 , а (у,4) k 2 для всех х и y.

20.

Отношения на множестве.
Если в декартовом произведении в качестве множества В выбрать множество А (
2
2
то есть А Х А= А ), то отношение k из А называется отношением на множестве.
Для отношений на множестве вводятся понятия:
2
Обратное отношение-это множество пар (а,b) таких, что (b,a) А .
Обозначение
k
1
Дополнение-это множество пар (а,b) k. Обозначение k
Тождественное отношение-множество пар (а, а) таких, что, а А,
I= {(a, a), a A}
Универсальное отношение U={(a,b),a A, b А}

21.

Виды отношений
1) Инъекция.
Если каждый элемент множества А соответствует элементу из множества В, то
отношение f называется инъективным.
Рис.12.Инъекция.
1) 3) Биекция.
Если для каждого элемента y B существует ровно один элемент х А, которому
соответствует y , то такое отношение называется биективным.
Биективное отношение инъективно и сюръективно.
Биективное отношение имеет обратное отношение.
2) Сюръекция.
Если для каждого элемента y множества В существует элемент х А,
соответствующий элементу y, то такое отношение f называется сюръекцией.
Рис.14. Биекция.

22.

Функции.
Пусть заданы множества А и В. Найдем А Х В.
Выберем отношение f АХВ={( à1 , b1 ),( à 2 , b2 ),…}, состоящее из пар таких,
что
ài ≠ à j , i=1,2,3,…., то есть отношение, в которой все первые элементы пар
различны. Такие отношения называются функциями.
Способы задания:
B; b=f (a); a f b.
А В; f: A
Пример: А={2,3,4}, B={1,4,3}
A X В={(2,1),(2,4),(2,3),(3,1),(3,4),(3,3),(4,1),(4,4),(4,3)}
Выделим: функции f1 ={(2,1),(3,1),(4,1)} и f 2 ={(2,4),(3,1),(4,1)}
F
Рис.15.Функция
f1 .
Рис.16.Функция
f2.

23.

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

24.

Комбинаторика.
Задачи, в которых требуется определить количество возможных операций,
называется комбинаторными.
Пусть имеется группа некоторых объектов α1 , a 2 , a3 ,..., a m , которые мы будем
называть элементами.
Из этой группы элементов будем образовывать подгруппы. Такие подгруппы
будем называть соединениями.
Из этих соединений выделим классы, которые будем называть размещениями.

25.

Размещения.
Размещениями из m-элементов по n называются соединения, каждое из которых
содержит n элементов, взятых из данных m и которые отличаются друг от друга или
элементами, или их порядком.
Предполагается, что элементы водном размещении не повторяются.
Формула числа размещений без повторений.
1
Размещения из m по одному. Очевидно, что их число: А m =m
Составим размещения по 2:
α1, a2 , a1a3 , a1a4 ,..., a1am
-размещений (m-1)
a 2 a1 , a 2 a 3 , a 2 a 4 ,..., a 2 a m
a a , a a , a a ,..., a a
3 1 3 2 3 4
3 m
m-строк
...................................
a m a1 , a m a 2 , a m a 3 ,..., a m a m 1
Итого:
2
А m =m(m-1)

26.

Размещения.
Размещения по 3: В каждой строке будет (m-2) размещений
А2
m
a1 a 2 a 3 , a1 a 2 a 4 ,..., a1 a 2 a m
a a a , a a a ,..., a a a
1 3 2 1 3 4
1 3 m
-строк
...................................
a m a m 1 a1 , a m a m 1 a 2 ,..., a m a m 1 a m 2
Ясно, что
3
2
А m = А m (m-2)=m(m-1)(m-2)
4
А m = m(m-1)(m-2)(m-3)
………………………………
n
А m = m(m-1)(m-2)….(m-(n-1))
( *)

27.

Размещения.
Пример:
В группе 21 студент. Требуется выбрать старосту, профорга и физорга. Сколькими
способами это можно сделать?
Решение:
Каждая тройка студентов может отличаться от другой тройки или распределением
обязанностей, или хотя бы одним из студентов, то есть мы должны вычислить число
размещений из 21 по 3:
m=21, n=3.
3
А 21 =21*20*19=7980.

28.

Размещения.
Другой вид формулы числа размещений.
Умножим числитель и знаменатель формулы ( * ) на (m-n)! Получим
n
Аm
m * (m 1) * (m n 1) * (m n) * (m n 1).....2 * 1
=
, или
(m n) * (m n 1)....2 * 1
n
Аm
m!
=
(m n)!
Каждое размещение содержит одно и то же количество элементов, взятых из
данных m.

29.

Перестановки.
Размещения из n-элементов по n, каждое из которых отличается друг от друга
только порядком элементов, называются перестановками.
Их число обозначается Pn :
Pn =А nn =n*(n-1)*(n-2)…..2*1, то есть
Pn =n!
Пример:
Сколькими способами могут сесть 6 человек на 6-местную лавочку?
Решение:
В данном случае каждое расположение лиц на лавочке отличается от другого
расположения только порядком. Поэтому мы имеем дело с перестановками:
P6 =6!=720.

30.

Сочетания.
Сочетания - это размещения, каждое из которых отличается от других хотя бы
одним элементом.
Другими словами: Сочетания - это соединения, содержащие n элементов из
данных m, отличающиеся хотя бы одним элементом.
n
Число сочетаний С m . Если мы имеем m- элементов, и из них составим
всевозможные сочетания по n и внутри каждого произведем перестановку, то
получим размещения.
n
n
С m * Pn = А m отсюда
n
A
m!
n
m
Сm=
=
Pn ( m n)! n!

31.

Сочетания.
Пример:
В группе 20 студентов. Требуется выбрать 5 делегатов на конференцию.
Сколькими способами это можно сделать?
Решение:
Так как внутри каждой пятерки делегатов перестановки дают одну и ту же
пятерку, то каждая пятерка должна отличаться от других хотя бы одним делегатом. В
данном случае мы должны посчитать число сочетаний из 20 по 5:
5
С 20 =
20!
=15504.
15!*5!

32.

Свойства сочетаний.
1)
m n
n
С m =С m
, достаточно выписать формулы левой и правой части равенства.
0!
1 , т.к. по определению 0!=1
(0 0)!0!
1!
0
1 , т.к. по определению 1!=1
3) С 1 =
1!*0!
2)
0
С0=
k 1
k
k
4) С n = С n 1 + С n 1
Доказательство:
(n 1)!
(n 1)!
+
=
(k 1)! (n 1 (k 1))! k! (n 1 k )!
(n 1)!*k (n 1)!*(n k )
(n 1)!*(k n k )
( n 1)!*n
=
=
=
k!*(n k )!
k!*(n k )!
k!*(n k )!
n!
k
=Сn
k!*(n k )!
k 1
k
С n 1 +
С n 1 =
Что и требовалось доказать.
1)
k 1
k
Сn =Сn
*
(n k 1)
k
Доказательство:
n!*(k 1)! (n (k 1))! (n k 1)
k
k 1
=
, следовательно, С n = С n
к 1
k
k!*(n k )!*n!
Cn
(n k 1)
*
.
k
С nk
=
Что и требовалось доказать.

33.

Размещения с повторениями.
До сих пор мы рассматривали комбинации элементов, которые в каждой
комбинации не повторялись. Рассмотрим размещения из m-элементов по n, в которых
каждый элемент может повторяться. Такие размещения называются размещениями
n
с повторениями: Ậ m .
Рассмотрим задачу.
В лифт 9 этажного дома на 1-ом этаже вошло 10 человек, каждый из которых
может выйти на любом этаже, начиная со второго. Сколькими способами они могут
выйти из лифта?
Решение:
Каждый из пассажиров может выйти 8 способами. Два пассажира могут выйти
2
2
10
Ậ 8 =8*8=8 =64. Десять человек могут выйти Ậ810 = 8 .
Таким образом, так как каждый элемент попадает в комбинацию m способами,
где n комбинаций, то
n
n
Ậm =m .

34.

Задача о числе подмножеств данного
множества.
Пусть имеется М={ à1 , a 2 , a 3 ,..., a n }. Пустое множество Ø входит в это
множество как подмножество. Одноэлементные множества тоже. Поставим каждому
подмножеству кортеж длиной n, состоящий из 0 и 1.
0-если соответствующий элемент не входит в подмножество.
1-если входит.
Например,
подмножеству
{ a2 , a4 }
будет
соответствовать
кортеж
010100000….0000…
Для вех подмножеств получим (0,0,0,…0), (1,0,0,…0), (0,1,0,0,...,0)… (1,1,1,…1)
Кортежей столько, сколько подмножеств. Это размещения, состоящие из двух
элементов (0 и 1) и отличающиеся друг от друга либо элементами, либо их порядком.
Это размещения с повторениями из двух по n: Получим
n
n
Ậ2 =2 .
Таким образом, мы доказали теорему:
Число подмножеств n-элементного множества равно
2n .
0
1
Следствие: Так как число пустых подмножеств С n (0)=1, одноэлементных-С n =n,
2
3
n
двухэлементных-С n , трехэлементных-С n , n-элементных С n , то сумма
n
k 1
k
n
Сn =2 .

35.

Перестановки с повторениями.
Пусть мы имеем n элементов
à1 , a 2 , a3 ,..., a n , Pn =n!. Пусть элемент à1
n
повторяется
k1 раз, элемент à 2 - k 2 раз,…., à n - k n раз, где
k
i 1
i
n . Тогда число
различных перестановок будет в
k1 ! меньше за счет одинаковых элементов à1 , в k 2
! раз меньше за счет одинаковых элементов à 2 ,…и в k n ! раз меньше за счет
одинаковых элементов à n . Тогда число различных перестановок будет равно:
n!
Pn ( k1 , k 2 ,…, k n )=
.
k1 !*k 2 !*... * k n !
Пример:
Сколько различных перестановок можно составить из слова МОЛОТОК?
Решение:
k1 (М)=1; k 2 (О)=3; k 3 (Л)=1; k 5 (Т)=1; k 7 (К)=1;
P7 (1,3,1,1,1)=
7!
=840.
1!*3!*1!*1!*1!

36.

Сочетания с повторениями.
Пример:
На почте имеются открытки четырех видов: красные, желтые, зеленые и синие.
Требуется 10 открыток. Сколькими способами можно их скомбинировать?
Решение:
Пусть мы отобрали 4 красных, 2 желтых, 2 зеленых и 2 синих открытки. Составим
кортеж из 0 и 1. Выпишем столько единиц, сколько красная открытка встречается в
нашем наборе, и поставим 0: 11110. Затем добавим кортеж для желтых -110. Получим
11110110. Добавим кортеж для зеленых и синих открыток. В последнем 0 не ставим.
Получим кортеж 1111011011011. В нем 10 единиц и 3 нуля. Общая длина кортежа –
13. Таких кортежей можно составить столько, сколько перестановок с повторениями
из 13.
13!
P13 (10,3)=
=286 – это и будет число сочетаний с повторениями из 4 по 10.
10!*3!
10
C
P13 (10,3)= C 1013 Таким образом, Ĉ 10
13 .
4
В общем случае.

37.

Сочетания с повторениями.
Пусть мы имеем n элементов
à1 , a 2 , a3 ,..., a n , из которых создаются сочетания с
повторениями, и каждое сочетание содержит k элементов. Составим кортеж, который
запишем вначале столько единиц, сколько элемент à1 входит в сочетание, затем
запишем 0. припишем кортеж из единиц и нуль для элемента
нуля. Получим: 111…1011…10…11…1
Единиц – k. Нулей – n-1. Длина кортежа n+ k-1
Общее число сочетаний с повторениями
(n k 1)!
k
Ĉ = Pn k 1 (k,n-(k-1))=
= C n k 1 ,
k!*(n (k 1))!
k
n
Итак,
k
Ĉ n =C
k
n k 1 ,
a 2 и т.д. без последнего

38.

БГТУ им. В.Г. Шухова
Кафедра информационных технологий
Спасибо за внимание!