ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.06.2021
Просмотров: 164
Скачиваний: 5
Тема 1: Множества
Лекция 1
Цель: рассмотреть основные понятия теории множеств, изучить свойства множеств; операции над множествами
План:
1. Основные определения теории множеств
2. Парадокс Рассела
3. Отношения между множествами
4. Операции над множествами.
-
Свойства операций над множествами. Алгебра теории множеств
Литература:
1. Нефедов В.Н., Осипова В.А. Курс дискретной математики. М.: МАИ, 1992. 262 с.
2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988.
Кто-то выдвинул робко отчаянный план:
Рассадить их по двум кораблям.
Но решительно не пожелал капитан
Экипаж свой делить пополам.
Льюис Кэрролл. Охота на Снарка.
-
Основные определения теории множеств
Определение. Под множеством будем понимать совокупность каких-либо вполне различаемых объектов, обладающими общими для всех их и только их свойствами, и рассматриваемых как единое целое. Эти объекты называются элементами множества.
Предполагается, что для данного элемента a и множества А всегда можно определить, принадлежит элемент a множеству А (пишется: аА) или элемент а не принадлежит множеству А (пишется: аА).
Множества, как правило, обозначаются большими латинскими буквами (A, B, С,…), а его элементы маленькими (a,b,c,…).
Определение. Множество, не содержащее ни одного элемента называется пустым и обозначается .
Н
апример:
множество действительных корней
уравнения
пустое.
Определение. Множество U, содержащее все элементы, рассматриваемые в данной задаче, называется универсальным множеством (универсум).
Рассматривая множество целых положительных чисел, в качестве универсального множества можно взять и множество целых чисел, и множество действительных чисел, и множество комплексных чисел, и само множество целых положительных чисел.
Определение. Множество называется конечным, если оно содержит конечное число элементов.
Определение. Если между элементами бесконечного множества можно установить взаимооднозначное соответствие с элементами множества положительных целых чисел, то говорят, что множество счетно.
Например:
множество действительных чисел, множество частных решений дифференциального уравнения - бесконечные множества.
множество чисел, делящихся без остатка на 3 – счетное множество,
множество букв русского алфавита, множество отличников вашей группы – конечно.
Множество задают обычно двумя способами:
- перечислением: A={1,2,3}; перечислением можно задать лишь конечные множества, которые имеют «небольшое количество» элементов.
- путем описания свойств, общих для всех элементов этого множества, и только этого множества. Это свойство называется характеристическим свойством, а такой способ задания множества описанием. А = {X | P(X)} (А - это множество тех и только тех элементов X для которых P от X есть истинное предложение).
Примеры |
-
А={1,2,3,4,5,6,7,8};
А- есть множество всех Х, таких, что Х-целое и Х>0 и Х<9;
А={X | X - целое, 0<X<9}.
A= {состоит из арабских цифр от 1 до 9}.
-
A={(x,y)|x2+y2=1, xR, yR};
A= {точки единичной окружности на плоскости}
Свойств множества:
-
Элементы во множестве не повторяются.
-
Порядок элементов во множестве не важен.
Множества {а, в, с} и {а, с, в} одинаковы.
-
Парадокс Рассела
Описанные выше понятия теории множеств с успехом могут быть использованы в началах анализа, алгебры, математической логики и т. д. Однако при более строгих рассмотрениях такое интуитивное восприятие может оказаться неудовлетворительным.
Приведем в качестве примера парадокс Рассела.
Можно указать такие множества, которые принадлежат самим себе как элементы, например, множество всех множеств.
Можно также указать множества, которые не являются элементами самих себя, например, множество {1,2}, элементами которого являются числа 1 и 2 (других элементов нет).
Рассмотрим теперь множество А всех таких множеств Х, что Х не есть элемент Х.
Тогда, если это полученное множество А не есть элемент А (самого себя), то по определению, А также есть элемент А.
С другой стороны, если А есть элемент А, то А – одно из тех множеств Х, которые не есть элементы самих себя, т.е. А не есть элемент А (не принадлежит A).
В любом случае А есть элемент А и А не есть элемент А.
Парадокс. Тем самым, интуитивная теория множеств – противоречива. Существует боле строгая формализация теории множеств.
Мы лишь укажем, что к парадоксам приводит в ряде случаев попытка объять необъятное: множество всех множеств (существующих в природе и в нашем сознании).
-
Отношения между множествами
Определение. Множества А и В считаются равными, если они состоят из одинаковых элементов. Обозначение: А=В.
Примечание. Хотя 1{1}, {1}{{1}}, но 1{{1}}, так как единственным элементом {{1}} является {1}. То есть элемент не считается равным множеству, если даже множество состоит только из этого элемента.
Определение. Говорят, что А содержится в B или что A есть подмножество множества В, если каждый элемент множества А есть элемент множества В.
Д ля пояснения различных соотношений между множествами используются диаграммы Венна (круги Эйлера), где множества изображаются в виде совокупностей точек на плоскости ограниченных некоторой замкнутой кривой. Так диаграмма Венна для изображения подмножества (AB) может выглядеть следующим образом
Отношение включения между множествами (A содержится в B) обозначается знаком , т.е. AB.
Пустое множество есть подмножество любого множества.
Определение. Если AB и AB, то А есть собственное подмножество В и пишут АВ ||.
Например, {1,2}{1,2,3,4}, множество четных чисел есть собственное подмножество множества целых чисел и т.д.
Свойства отношения включения:
- ХХ; (свойство рефлексивности);
- если XY, YZ, то XZ, (свойство транзитивности);
- если XY, YX, то X=Y (свойство антисимметрии).
Определение. Количество элементов, составляющих множество, называется мощностью множества.
Определение. Множество всех подмножеств A называют множеством - степенью или Булеаном и обозначается B(A).
Утверждение: если A состоит из n элементов, то B(A) состоит из 2n элементов.
Пример.
Пусть A={a,b,c}. Тогда n=|A|=3 и
B(А) = 2n=23={ ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}=8.
-
Операции над множествами
1) Объединением множеств А и В называется множество всех элементов, которые являются элементами хотя бы одного множества А или В:
AB={x | xA или xB}
Некоторые свойства: AAB, BAB.
Диаграммы Эйлера-Венна. Вводится понятие универсального множества U (множества, содержащего все возможные элементы). Этот универсум обозначается квадратом. Другие множества обозначаются кругами внутри этого квадрата.:
2) Пересечением множеств А и В называется множество всех элементов, которые являются элементами обоих множеств А и В:
AB={x | xA и xB}
Некоторые свойства: ABAAB, ABBAB.
3) Дополнением множества A (обозначается A ) называется множество, элементы которого не принадлежат А: = {x | x A}
= U \ A
4) Вычитание множеств или относительное дополнение множества А до множества B: B\A={x | xB, xA}.
Э та операция может быть осуществлена с помощью пересечения и дополнения: B\A=B.
5) Симметричной разностью двух множеств A и B (обозначается A∆B) называется множество, элементы которого принадлежат А, или B, но не обоим сразу.
1. A∆B= (A\B)U(B\A).
2. A∆B= (AUB)\(BA).
-
Свойства операций над множествами. Алгебра теории множеств
|
Закон |
Объединение |
Пересечение |
1 |
Закон коммутативности |
AВ=BA |
AB=BA |
2 |
Закон ассоциативности |
A(BC)=(AB)C; |
A(BC)=(AB)C; |
3 |
Закон дистрибутивности |
A(BC)=(AB)(AC) |
A(BC)=(AB)(AC) |
4 |
Закон поглощения |
A(AB)=A |
A(AB)=A |
5 |
Закон де Моргана |
= |
= |
6 |
Закон идемпотентности |
AA=A; |
AA=A; |
7 |
Закон инволютивности |
|
|
8 |
Свойство нуля |
A=A; |
A=; |
9 |
Свойство дополнения |
A=U; |
A=; |
10 |
Свойство единицы |
AU=U; |
AU=A; |
Доказательство свойства 3 (с помощью свойства антисимметрии )
Во-первых, A(BC)(AB)(AC).
Действительно, если xA(BC), то xA или xBC.
Если xA, то xAB и xAC. Тогда x(AB)(AC).
Если xBC, то xB и xC. Тогда xBA и xCA, а значит, x(AB)(AC).
Во-вторых, (AB)(AC)A(BC).
На самом деле, если x(AB)(AC), то xAB и xAC. Тогда xA или (xB и (одновременно) xC), т.е. (xВC). Тем самым, xA(BC).
Из первого и второго следует справедливость утверждения.
Доказательство свойства 8 ( = ).
Пусть x . Тогда xU и xAB xA и xB x и x x .
Пусть x . Тогда x и x xU и xA и xB xAB, т.е. x .
В силу справедливости того и другого справедливо и доказываемое утверждение.
Задание
1. Доказать эквивалентность соотношений
-
AB;
-
AB=A;
-
AB=B.
A
B
2. Доказать
а) (AC)(BD)(AB)(CD);
б) (B\C)\(B\A)A\C;
в) A\C(A\B)(B\C);
3. A\(B\C)=(A\B)(AC);
(A\B)C=(AС)\(BC)=(AС)\B.
4. Следует ли из A\B=C равенство A=BC ?
из A=BC равенство A\B=C ?
5. Верны ли равенства
A\(BC)=(A\B)\C ;
A(B\C)=(AB)\C ;
Существуют ли множества?
AB, AC=, (AB)\C=
Решение: AB=B(A)=BA.
Доказать тождества:
а)
б)
в)
г)
д)