67592

ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

Лекция

Математика и математический анализ

Множества и функции. Эти объекты называются элементами множества S. Множество задают специфицируют двумя способами: перечислением: ={123}; характеристикой свойств общих для элементов множества: А = {X PX} А это множество тех и только тех элементов X для которых P от X есть истинное предложение.

Русский

2014-09-12

142.5 KB

1 чел.

ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

Литература:

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

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

3. Кук Д., Бейз Г. Компьютерная математика. М. Наука, 1990. 384 с.479 с.

4. Бронштейн Е.М. Множества и функции. Методические указания. Уфа: УГАТУ. 1988.

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

Существенной деталью является то, что для любого объекта можно установить, принадлежит он данному множеству S или нет.

Множество задают (специфицируют) двумя способами:

-перечислением: 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}.

Если элемент Х принадлежит множеству А, то записывают XA, если не принадлежит, то XA. Например, 7А, 6А.

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

Например,

{1,2,3} = {2,1,3} = {2,1,1,3}

2 {1,2},   {{1,2}} {1,2} (Оболочка!)

То есть элемент не считается равным множеству, если даже множество состоит только из этого элемента.

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

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

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

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

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

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

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

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

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

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

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

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

Определение. Говорят, что А содержится в B или что A есть подмножество множества В, если каждый элемент множества А есть элемент множества В.

Отношение включения между множествами (A содержится в B) обозначается знаком , т.е. AB.

Определение. Если AB и AB, то А есть собственное подмножество В и пишут АВ ||.

Например, {1,2}{1,2,3,4}, множество четных чисел есть собственное подмножество множества целых чисел и т.д.

Свойства отношения включения:

- ХХ; (свойство рефлексивности);

- если XY, YZ, то XZ, (свойство транзитивности);

- если XY, YX, то X=Y (свойство антисимметрии).

Примечание. Не надо путать отношения и . Хотя 1{1}, {1}{{1}}, но 1{{1}}, так как единственным элементом {{1}} является {1}.

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

Определение. Множество всех подмножеств A называют множеством - степенью или Булеаном и обозначается B(A).

Пример.

Если А={1,2,3}, то B(А)={,{1},{2},{3},{1,2},{1,3},{2,3},А}.

Утверждение: если A состоит из n элементов, то B(A) состоит из 2n элементов.

Доказательство:

Перенумеруем все элементы множества А. Введем описание подмножества множества А в виде строки из n бит (ячеек, содержащих цифры 0 или 1). 0 на i-том месте означает, что i-тый элемент не принадлежит данному подмножеству, 1- что принадлежит.

0

1

0

0

1

0

1

Например, пустое множество обозначается строкой нулей, само А – строкой единиц.

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

Действия над множествами

1) Объединением множеств А и В называется множество всех элементов, которые являются элементами хотя бы одного множества А или В:

AB={x | xA или xB}

Некоторые свойства: AAB, BAB.

Диаграммы Эйлера-Венна. Вводится понятие универсального множества U (множества, содержащего все возможные элементы). Этот универсум обозначается квадратом. Другие множества обозначаются кругами внутри этого квадрата.:

       

2) Пересечением множеств А и В называется множество всех элементов, которые являются элементами обоих множеств А и В:

AB={x | xA и xB}

Некоторые свойства: ABAAB,  ABBAB.

3) Абсолютное дополнение (множество всех элементов, не принадлежащих множеству А):   = {x | x  A}

4) Вычитание множеств или относительное дополнение множества А до множества B:   B\A={x | xB, xA}.

Эта операция может быть осуществлена с помощью пересечения и дополнения: B\A=B.

5) Симметрическая разность: A+B=(A\B)(B\A)

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

1

AВ=BA (коммутативность объединения );

1

AB=BA (коммутативность пересечения);

2

A(BC)=(AB)C (ассоциативность );

2

A(BC)=(AB)C (ассоциативность );

3

A(BC)=(AB)(AC) (дистрибутивность

относительно );

3

A(BC)=(AB)(AC) (дистрибутивность

относительно );

4

A=A;

4

AU=A;

5

A=U;

5

A=;

6

AA=A;

6

AA=A;

7

AU=U;

7

A=;

8

=

(закон де Моргана);

8

=

(закон де Моргана);

9

A(AB)=A

(закон поглощения);

9

A(AB)=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.

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.

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

а)

б)

в)

г)

д)


 

А также другие работы, которые могут Вас заинтересовать

22751. Провал інтервенції на Кубі 1961 р. та Карибська криза 23 KB
  Поскольку он сразу занял антиамериканскую позицию США поддержали противников Кастро и помогли им организовать высадку на Кубе апрель 1961 г. США поддержали высадку контрреволюционных групп на территорию Кубы в 1961 году. Поскольку Куба была расположена в 90 милях от побережья США большая часть их территории оказалась бы в сфере досягаемости ракет. США узнали об этом только из данных военной разведки когда ракеты уже были установлены и на этот раз действовали весьма жестко.
22752. Американсько-радянські переговори і угоди на найвищому рівні у 1991 р. Договір СНО-1 22.5 KB
  Этот и другие недостатки Договора разный подход к ограничению охватываемых документом видов СНВ вывод за скобки установленных количественных пределов крылатых ракет морского базирования отказ США подтвердить свою приверженность Договору по ПРО по существу ставили под вопрос соответствие этого Договора принципу равенства и одинаковой безопасности США обеспечили себе возможность достижения военностратегического перевеса над СССР не выходя формально за рамки принятых обязательств. В соответствии с Договором СНВ1 более строгому...
22753. Участь УРСР у розвязанні територіальних проблем на Паризький мирній конференції 55.5 KB
  Підходи України до проблем реформування ООН. укладенням угоди про встановлення нового кордону між двома державами і поділом між ними зі згоди ООН Вільної території Трієст. Еритрея після проведення в ній референдуму за рішенням Генеральної Асамблеї ООН була приєднана до Ефіопії на федеративних засадах у 1952 р. Підходи України до проблем реформування ООН.
22754. Міжнародна громадськість про суть і значення конституційних змін в СРСР 1944р. Полеміка з цих питань 74 KB
  Становлення та розвиток відносин України з державами ЦСЄ. Миротворча діяльність України: досягнення та проблеми. При всьому тому членам КУК як українським патріотам імовірно імпонував вихід України на світову арену нехай і в такому ущемленому вигляді.Цегельський інформував громадськість що його делегація мала у СанФранціско зустрічі з усіма представниками Об'єднаних Націй домагаючись включення України в число учасників конференції .
22755. Участь делегації УРСР в роботі Дунайської конференції 73 KB
  право України було відновлено. У 19941996 роках ЄС ухвалив Спільну позицію щодо України 28 листопада 1994 р. Указом Президента України було затверджено Стратегію інтеграції України до ЄС розраховану на період до 2007 року. на Гельсінському самміті Євросоюзу була ухвалена Спільна стратегія ЄС щодо України яка спрямована на зміцнення стратегічного партнерства з Україною.
22756. Участь УРСР в роботі конференції в Сан-Франциско 55.5 KB
  Політика ЄС стосовно України. Основні проблеми безпеки України зовнішній аспект та механізми їх гарантування. Політика ЄС стосовно України. У 19941996 роках ЄС ухвалив Спільну позицію щодо України 28 листопада 1994 р.
22757. VI сесія (1944р.) Верховної Ради УРСР щодо формування союзного Наркомату закордонних справ 37 KB
  Наслідки розширення ЄС для зовнішньої політики України. питання про утворення НКЗС Українибуло розглянуто на Політбюро ЦК КПб України. Поперше було вирішено встановити дипломатичні відносини України з Великою Британією і США подруге з іншими країнами антигітлерівської коаліції. Наслідки розширення ЄС для зовнішньої політики України Розширення Європейського Союзу яке відбулося 1 травня 2004 року призвело до історичних змін політичних географічних та економічних умов для України та Євросоюзу.
22758. Діяльність УРСР в ООН 1945 - 1990 рр 38 KB
  Економічне співробітництво України та Росії: стан проблеми та механізми їх вирішення. Європейська політика України: концептуальні засади та практика. Виступивши проти зосередженості ЮНЕСКО тільки на фінансуванні та інших формах розв'язання проблеми встановлення причин ракових захворювань делегат від України Тульчинська порушила питання про негайне впровадження у життя вже одержаних результатів її пропозиція була схвалена більшістю делегацій 21 проти 18 при 7 що утрималися. Економічне співробітництво України та Росії: стан проблеми та...
22759. Участь УРСР в обговоренні ООН грецького та індонезійського питань 35.5 KB
  Питання делімітації та демаркації кордонів кордону України: досягнення і проблеми. Інтереси України в Балканському регіоні та механізми їх реалізації. Півстоліття назад саме міністр закордонних справ України Мануїльский із трибуни ООН проголосив Руки геть від Індонезії . Погана спадщина радянськоіндонезійських відносин що повністю дісталося Росії абсолютно не стосується України той самий випадок коли не варто шкодувати про усіх без винятку боргах й активах колишнього СРСР.