ДМ_тема 3. Краткое содержание 2 Конечные и бесконечные множества. 1 2 3 4 5 6 Семейства множеств
 Скачать 0.98 Mb.
|
|
Дискретная математика Конечные и бесконечные множества Наталья Викторовна Пермякова Краткое содержание 2 3. Конечные и бесконечные множества. 3.1 3.2 3.3 3.4 3.5 3.6 Семейства множеств 3 . Булеан множества Х - множество всех подмножеств множества Х Пример. Теорема. Если множество состоит из n элементов, то его булеан - из элементов. 4 Семейства множеств Разбиение множества Х - есть множество непустых непересекающихся подмножеств множества Х, в объединении дающих множество Х. U X1 X2 Xk X 5 Семейства множеств Покрытие множества Х - есть множество непустых подмножеств множества Х, в объединении дающих множество Х. 6 Внимание, вопрос Укажите верные высказывания:
7 Отношение эквивалентности X – множество всех треугольников. Отношение S – множество пар треугольников (∆x, ∆y) таких, что площадь ∆x равна площади ∆y. Y – жители г. N. Отношение Н содержит пары такие, что х и у носят шляпы одинакового размера.
Свойства отношений ≡ 8 Отношение эквивалентности : . Отношение R на множестве Х называется отношением эквивалентности, если оно обладает свойствами рефлексивности, симметричности, транзитивности. Классом эквивалентности, порожденным элементом , называется подмножество [x]множества Х, для элементов которого выполняется условие . Таким образом, класс эквивалентности 9 Отношение эквивалентности Отношение М задано на множестве X = {1,2,3,4,5,6,7}. [1] = {1,4,7} = [4] = [7] [2] = {2,5} = [5] [3] = {3,6} = [6] U [1] [2] [3] X 1 4 7 2 5 3 6 Классы эквивалентности образуют разбиение множества Х Множество различных классов эквивалентности множества X по отношению R называется фактор-множеством и обозначается X│R. 10 Отношение эквивалентности Теорема. Пусть R – отношение эквивалентности на множестве X и X│R – совокупность всех различных классов эквивалентности по отношению R. Тогда X│R – разбиение множества X. Теорема. Всякое разбиение множества X порождает на X отношение эквивалентности. X│M = {[1],[2],[3]} = R(X) 11 Внимание, вопрос Выберите отношения эквивалентности:
12 Равномощные множества Пример. Доказать, что множества [1,3] и [-1,4] равномощны. 1 2 2 1 3 3 4 4 5 5 Биекция : 2.5x-3.5 = y -1 -1 4 1 3 Равномощные множества 13 Отношение равномощности является отношением эквивалентности разбиение на непересекающиеся классы равномощных множеств 1) X ≡ X 2) X ≡ Y, Y ≡ X 3) X ≡ Y, Y ≡ Z → X ≡ Z Классы эквивалентности равномощных множеств 0 1 2 n 0 1 2 … … … Сравнение множеств по мощности 14 1)X=Y - множества X и Y попадают в один класс эквивалентности; 2)X<Y- класс эквивалентности множества X находится левее класса эквивалентности множества Y; 3)X>Y- класс эквивалентности множества X находится правее класса эквивалентности множества Y; 4) случай, когда множества X и Y несравнимы по мощности, невозможен 15 Сравнение множеств по мощности Теорема Кантора-Бернштейна. Пусть X и Y два бесконечных множества. Если во множестве X есть подмножество, равномощное множеству Y, а во множестве Y есть подмножество, равномощное X, то множества X и Y равномощны. X X1 X1 X Y Y1 Y1 Y 16 Внимание, вопрос Выберите верные утверждения:
17 Конечные множества Х - конечное множество, если 1) Х – пустое или Теорема 1 правило суммы X = R({1,4,7}, {2,5}, {3,6}) │X │= │{1,4,7}│+ │{2,5}│+ │{3,6}│= = 3 + 2 + 2 = 7 Конечные множества 18 Теорема 2 правило произведения U Y Z W 1 4 7 3 6 2 5 X = Z × Y × W = { (1,5,3), (1,2,3), (1,5,6),(1,2,6), (4,5,3), (4,2,3), (4,5,6),(4,2,6), (7,5,3), (7,2,3), (7,5,6),(7,2,6)} │X│= │Z│•│Y│•│W │= 3 •2 •2 = 12 19 Конечные множества Теорема 3 о булеане конечного множества Доказательство Множество X конечно, Зафиксируем порядок элементов множества и рассмотрим множество V всех упорядоченных наборов длины n, состоящих из нулей и единиц: Конечные множества 20 Установим биекцию следующим образом: элементу сопоставляем множество , содержащее те и только те элементы , для которых . Таким образом, множество V и B(X) равномощны. Но множество V = E × E ×… × E = En, E = {0,1}. По теореме о мощности произведения Следовательно, │B(X)│ = 2n Конечные множества 21 U X 1 4 7
B(X) = {Ø, {7}, {4}, {4,7}, {1}, {1,7}, {1,4}, {1,4,7} } Конечные множества 22 Теорема 4 обобщенная теорема включения-исключения Пусть Х и Xi - конечные множества и Тогда U Y Z W 1 4 7 3 6 2 5 8 9 10 11 12 │Z │= 5, │W │= 7, │Y │= 6, │Z∩Y│ = 2, │Z∩W│ = 2, │W∩Y│ = 3, │Z∩Y∩W│ = 1 │ZUYUW│ = │Z │+│W │+│Y │- │Z∩Y│ - │Z∩W│ - │W∩Y│ + │Z∩Y∩W│ 5 + 7 + 6 – 2 – 2 – 3 + 1 = 12 23 Внимание, вопрос Выберите верные утверждения:
24 Счетные множества Множество Х называется счетным Пример 1. Множество Z счетно. │X│ = 0 25 Счетные множества 1, 2, … n 0 1 2, … классы конечных множеств класс счетных множеств классы других бесконечных множеств Ряд мощностей множеств 26 Счетные множества Свойства счетных множеств Теорема 1. Любое подмножество счетного множества конечно или счетно. Теорема 2. Любое бесконечное множество имеет счетное подмножество. Теорема 3. Объединение двух счетных множеств счетно. Теорема 4. Пусть Х – бесконечное множество, Y – счетное. Тогда Теорема 31. Объединение не более чем счетного количества не более чем счетных множеств не более чем счетно 27 Счетные множества Пример. Даны множества X = {0,1,2,3,7}, Y = {2n+1, n ∈ N}. Найдите │X∩Y│,│XUY│, │X×Y│. Y = {3,5,7,…,2n+1,…} X∩Y = {3,7} – конечное множество, │X∩Y│ = 2. XUY = {0,1,2,3,5,7,…}. По теореме 31 XUY – счетно. Покажем счетность множества XUY, построив биекцию f: XUY → N. Пронумеруем элементы: 0 → 1, 1 → 2, 2 → 3, для нумерации всех следующих элементов подберем функцию an + b, при этом a•4 + b = 3, a•5 + b = 5. Решим систему уравнений: 28 Счетные множества Биекция элементов множества XUY на ряд натуральных чисел │XUY│= 0 Счетные множества 29 Докажем, что X×Y – счетно. Занумеруем элементы множества:
│X×Y│= 0 30 Внимание, вопрос Выберите верные утверждения:
Спасибо за внимание! |