Дискретная математика презентация

ДИСКРЕТНАЯ МАТЕМАТИКА Автор: Тихомирова Анна Николаевна

ЛЕКЦИЯ 6. МНОЖЕСТВА

Множества: определение и основные свойства

Множества: определение и основные свойства Множество, которое не имеет ни одного элемента, называется пустым и обозначается Ø. Единичное множество – множество, все элементы которого тождественны. Множество М1 называется подмножеством множества М тогда и только тогда, когда любой элемент множества М1 принадлежит множеству М. Множества называются равными, если они имеют одни и те же элементы. Подмножество М1 множества М называется собственным подмножеством множества М, если М1 является его подмножеством, но при этом существует хотя бы один элемент, принадлежащий М, но не принадлежащий М1.

Множества: определение и основные свойства Пусть А и В – два множества. Множество М=А U В такое, что его каждый элемент принадлежит А или В (а возможно и А и В), называется суммой или объединением множеств А и В. Пусть А и В – два множества. Множество М=А ∩ В такое, что его каждый элемент принадлежит и А и В одновременно, называется пересечением множеств А и В. Пусть А и В – два множества. Множество М=А \ В такое, что оно состоит из тех элементов множества А, которых нет во множестве В, называется разностью множеств А и В, или дополнением В до А.

Множества: определение и основные свойства Пусть А и В – два множества. Множество М=А × В такое, что оно образовано из всех пар (a, b) таких, что a принадлежит A и b принадлежит B, называется декартовым произведением множеств А и В. Пусть А = {а,b}; В = {m,n} Тогда А×В = {(a,m),(a,n),(b,m),(b,n)} Пусть А – множество. Множество М, элементами которого являются подмножества множества А, включая само А и пустое множество, называется множеством всех подмножеств множества А или булеаном А и обозначается Р(А). Пусть А = {а,b,c} Тогда M= Р(А)={Ø, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}

Множества: определение и основные свойства Отображением f множества А в множество В называется некое правило, по которому каждому элементу множества А ставят в соответствие элемент множества В. Множество всех отображений множества А в В обозначается как ВА (В в степени А). Пусть А = {а,b,c}; В = {m,n} Тогда ВА это набор функций fi приведенных в таблице

Равномощные множества и кардинальные числа

Кардинальное число Далее мощность будем называть кардинальным числом множества. Кардинальные числа некоторых множеств 1. Мощность пустого множества равна 0: | Ø |=0. 2. Мощность множества из одного элемента равна 1: |{a}|=1. 3. Если множества равномощны (A~B), то их кардинальные числа равны: |A|=|B|. 4. Мощность булеана множества А равна 2|А|: |P(A)|=2|А| 5. Мощность множества ВА всех отображений А в В равна|В||А|

Классификация множеств

Свойства множеств

Парадокс Галилея Хотя большинство натуральных чисел не является квадратами, всех натуральных чисел не больше, чем квадратов (если сравнивать эти множества по мощности)

Парадокс Гильберта