- •Математика
- •Пересечение множеств
- •Вычитание множеств
- •Свойства операций над множествами
- •Число элементов в объединении конечных множеств и в дополнении к подмножеству
- •Контрольные вопросы:
- •Способы задания декартова произведения двух множеств
- •Основные свойства декартова произведения.
- •Раздел II. Элементы комбинаторики
- •Контрольные вопросы:
- •Контрольные вопросы:
- •Перестановки без повторений
- •Бином Ньютона
- •Свойства сочетаний. Треугольник Паскаля.
- •1. Правило симметрии:
- •Раздел III. Математические утверждения и их структура
- •Контрольные вопросы:
- •Отношения между понятиями
- •Способы определения понятий
- •Требования к определению понятий
- •Контрольные вопросы:
- •Высказывания и операции над ними
- •Операции над высказываниями
- •Отрицание высказываний
- •Законы отрицания:
- •Конъюнкция двух высказываний
- •Импликация высказываний
- •Закон контрапозиции
- •Эквиваленция двух высказываний
- •Обращение предиката в высказывание
- •Операции над предикатами
- •Отрицание высказываний, содержащих кванторы
- •Отношение логического следования и равносильности на множестве предложений
- •Строение теоремы. Виды теорем
- •Закон контрапозиции. Теоремы
- •Умозаключения. Анализ рассуждений. Простейшие правила вывода
- •Простейшие схемы дедуктивных умозаключений
- •Способы установления истинности умозаключения
- •Индуктивные умозаключения
- •Раздел IV. Соответствия
- •Контрольные вопросы:
- •Полный образ и полный прообраз
- •Способы задания соответствий
- •Типы соответствий
- •Отображения
- •Виды отображений
- •Отношения
- •Свойства отношений на множестве
Свойства операций над множествами
Операции объединения, пересечения, разности множеств обладают следующими свойствами:
1. Коммутативность объединения: АВ = ВА
пересечения: AB = ВА
2. Ассоциативность объединения: (АВ) С = А (В С)
пересечения: (AB) С = A (BС)
3. Дистрибутивность объединения относительно пересечения:
А (BС) = (АВ) (АС)
или (AB) С = (АС) (ВС)
пересечения относительно объединения:
A (В С) = (AB) (АС)
или (АВ) С = (AС) (BС)
4. Идемпотентность объединения: АА= А
пересечения: AА = А
5. Поглощения объединения: АJ = J и АØ = А
пересечения: AJ = А и АØ = Ø
6. Если АВ, то АВ = В и AB = А
7. А (АВ) = А и A (АВ) = А
8. Законы де Моргана: (АВ) = AB
(AB) = AВ
9.
10. Закон двойного отрицания:
11. J Ø
12. .
Законы алгебры множеств по отношению к операциям пересечения и объединения подчиняются принципу двойственности: если в любом верном тождестве знаки пересечения заменить знаками объединения, а все знаки объединения заменить знаками пересечения (), знак универсального множества заменить знаком пустого множества, а знак пустого – знаком универсального множества Ø, то получим также верное равенство.
Например, - верное равенство. Тогда в силу принципа двойственности Ø – также верное равенство.
Доказательство некоторых свойств операций объединения и пересечения прямо следует из их определения, доказательство других свойств также можно провести.
Самостоятельно рассмотреть понятие пересечения, объединения «п» множеств.
Число элементов в объединении конечных множеств и в дополнении к подмножеству
Пусть А и В – два непустых конечных множества. Число элементов во множестве будем обозначать или . Например, если А = {a;b;c;d}, В = {m;n}, то = 4, а = 2.
Теорема: Число элементов в объединении двух конечных множеств равно сумме чисел элементов в каждом из них, уменьшенной на число элементов в их пересечении.
Доказательство:
Обозначим число элементов во множестве буквой , а во множестве буквой , т.е. .
1
B A
Штриховкой на диаграмме показано . Очевидно, что .
A B
2) Пусть Ø.
на диаграмме показано двойной штриховкой. Так как множества А и В – конечные множества и Ø, то также множество конечное. Пусть n( )= c, .
Очевидно, что состоит из трех попарно непересекающихся подмножеств: (на диаграмме показано двойной штриховкой), (на диаграмме показано горизонтальной штриховкой), (на диаграмме показано вертикальной штриховкой). Тогда = + + (смотри случай 1).
Пусть =, =. Тогда = +c+=(+c)+= (+c)++c - c = (+c)+(+c) – c = m + p – c = .
Теорема: Число элементов в объединении трех конечных множеств А, В, С, равно:
Доказательство:
В основе доказательства лежит свойство ассоциативности операции объединения множеств: А также тот факт, что равные множества состоят из одних и тех же элементов. Тогда . Доказать сам-но.
Теорема: Пусть даны конечные множества А и В. И пусть В – собственное подмножество множества А. Тогда n(A \ B) = n(A)-n(B).
Доказательство
Пусть даны множества А и В, где . Тогда , и Ø. Тогда . Отсюда .
Так как , то , где .
Лекция № 6. ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ.