ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.06.2021

Просмотров: 164

Скачиваний: 5

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

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

Лекция 1



Цель: рассмотреть основные понятия теории множеств, изучить свойства множеств; операции над множествами

План:


1. Основные определения теории множеств

2. Парадокс Рассела

3. Отношения между множествами

4. Операции над множествами.

  1. Свойства операций над множествами. Алгебра теории множеств


Литература:

1. Нефедов В.Н., Осипова В.А. Курс дискретной математики. М.: МАИ, 1992. 262 с.

2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988.

Кто-то выдвинул робко отчаянный план:

Рассадить их по двум кораблям.

Но решительно не пожелал капитан

Экипаж свой делить пополам.

Льюис Кэрролл. Охота на Снарка.


  1. Основные определения теории множеств


Определение. Под множеством будем понимать совокупность каких-либо вполне различаемых объектов, обладающими общими для всех их и только их свойствами, и рассматриваемых как единое целое. Эти объекты называются элементами множества.


Предполагается, что для данного элемента a и множества А всегда можно определить, принадлежит элемент a множеству А (пишется: аА) или элемент а не принадлежит множеству А (пишется: аА).

Множества, как правило, обозначаются большими латинскими буквами (A, B, С,…), а его элементы маленькими (a,b,c,…).


Определение. Множество, не содержащее ни одного элемента называется пустым и обозначается .

Н
апример
: множество действительных корней уравнения

пустое.


Определение. Множество U, содержащее все элементы, рассматриваемые в данной задаче, называется универсальным множеством (универсум).

Рассматривая множество целых положительных чисел, в качестве универсального множества можно взять и множество целых чисел, и множество действительных чисел, и множество комплексных чисел, и само множество целых положительных чисел.


Определение. Множество называется конечным, если оно содержит конечное число элементов.

Определение. Если между элементами бесконечного множества можно установить взаимооднозначное соответствие с элементами множества положительных целых чисел, то говорят, что множество счетно.

Например:

множество действительных чисел, множество частных решений дифференциального уравнения - бесконечные множества.

множество чисел, делящихся без остатка на 3 – счетное множество,

множество букв русского алфавита, множество отличников вашей группы – конечно.


Множество задают обычно двумя способами:

- перечислением: A={1,2,3}; перечислением можно задать лишь конечные множества, которые имеют «небольшое количество» элементов.

- путем описания свойств, общих для всех элементов этого множества, и только этого множества. Это свойство называется характеристическим свойством, а такой способ задания множества описанием. А = {X | P(X)} (А - это множество тех и только тех элементов X для которых P от X есть истинное предложение).


Примеры |

  1. А={1,2,3,4,5,6,7,8};

А- есть множество всех Х, таких, что Х-целое и Х>0 и Х<9;

А={X | X - целое, 0<X<9}.

A= {состоит из арабских цифр от 1 до 9}.

  1. A={(x,y)|x2+y2=1, xR, yR};

A= {точки единичной окружности на плоскости}


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

  1. Элементы во множестве не повторяются.

  2. Порядок элементов во множестве не важен.

Множества {а, в, с} и {а, с, в} одинаковы.



  1. Парадокс Рассела

Описанные выше понятия теории множеств с успехом могут быть использованы в началах анализа, алгебры, математической логики и т. д. Однако при более строгих рассмотрениях такое интуитивное восприятие может оказаться неудовлетворительным.

Приведем в качестве примера парадокс Рассела.

Можно указать такие множества, которые принадлежат самим себе как элементы, например, множество всех множеств.

Можно также указать множества, которые не являются элементами самих себя, например, множество {1,2}, элементами которого являются числа 1 и 2 (других элементов нет).

Рассмотрим теперь множество А всех таких множеств Х, что Х не есть элемент Х.

Тогда, если это полученное множество А не есть элемент А (самого себя), то по определению, А также есть элемент А.

С другой стороны, если А есть элемент А, то А – одно из тех множеств Х, которые не есть элементы самих себя, т.е. А не есть элемент А (не принадлежит A).

В любом случае А есть элемент А и А не есть элемент А.

Парадокс. Тем самым, интуитивная теория множеств – противоречива. Существует боле строгая формализация теории множеств.

Мы лишь укажем, что к парадоксам приводит в ряде случаев попытка объять необъятное: множество всех множеств (существующих в природе и в нашем сознании).


  1. Отношения между множествами


Определение. Множества А и В считаются равными, если они состоят из одинаковых элементов. Обозначение: А=В.

Примечание. Хотя 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. Операции над множествами


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 (обозначается AB) называется множество, элементы которого принадлежат А, или B, но не обоим сразу.

1. A∆B= (A\B)U(B\A).

2. A∆B= (AUB)\(BA).




  1. Свойства операций над множествами. Алгебра теории множеств



Закон

Объединение

Пересечение

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. Доказать эквивалентность соотношений

  1. AB;

  2. AB=A;

  3. 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.

Доказать тождества:

а)


б)


в)


г)


д)