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.

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

а)

б)

в)

г)

д)


 

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

22052. Пастораль, городской роман, шельмовской (плутовской) роман 49.5 KB
  Пастораль городской роман шельмовской плутовской роман Пастораль Пастораль франц. Жанровые формы Ппасторали многообразны: эклога поэма роман; после стихотворной драмы Сказание об Орфее Полициано 1480 развивается драматическая Пастораль принятая особенно в 16 17 вв. Систему поэтики немецкой романной пасторали XVII в. В немалой мере такому положению способствовала также устойчивая репутация пасторального романа как если не вторичной периферийной то все же некой побочной маргинальной ветви в системе немецкого романа XVII в.
22053. Пиетизм 30 KB
  Основателем Пиетизма является Ф. Становление и развитие Пиетизма таким образом детерминировано теми же факторами которые обусловили в свое время оформление протестантизма в целом и которые питают историческую эволюцию мистической традиции см. Основателями и лидерами пиетизма были Ф. Движение Пиетизма началось с молитвенных собраний в доме Шпенера.
22054. Рококо 37 KB
  Рококо Особую сложность при изучении литературных направлений XVIII века представляет анализ литературы рококо. Недостаточно изученное в литературоведении рококо характеризуется в учебниках и справочных изданиях поверхностно и архаично большей частью негативно. Сохраняется предрассудок как назвали бы это просветители отношения к рококо как только к малому искусству к нему наши ученые обычно причисляют небольшой круг средней по художественным достоинствам литературы. В зарубежном литературоведении между тем преобладает другая крайность: к...
22055. Просвещение 36.5 KB
  Просвещение XVIII столетие вошло в историю культуры и литературы как век Просвещения. XVIII век часто называют веком Разума. Таким образом первое что отличает рационализм XVIII века от его предшественника картезианского рационализма эмпирический характер критика всякой физической спекулятивности. Дедуктивным гипотетическим системным построениям прежней науки мыслители XVIII века предпочитают индуктивное познание фактов.
22056. Движение «Бури и натиска» 32 KB
  Гёте 17491832 и Ф. Художественным открытием века явилась лирика молодого Гёте и его первая немецкая историческая драма Гёц фон Берлихинген 1773; мировую славу завоевал его сентиментальный роман Страдания юного Вертера 1774 выражающий протест против закрепощения личности сословноабсолютистским общественным строем. У Гёте в Прафаусте до 1776 речь идет о матереубийстве и детоубийстве однако у него эти проблемы поднимаются высоко над бытовым...
22057. Классицизм 37 KB
  При изучении классицизма необходимо проследить как преломляются в классицистической литературе XVII века традиции ренессансного классицизма обратить внимание на то как античность из объекта подражания и точного воссоздания возрождения превращается в пример правильного соблюдения вечных законов искусства и объект соревнования. Можно также встретить утверждения что философской основой классицизма явилась философия Декарта. В то же время заслуживают внимания несомненные декартовские принципы в поэтике классицизма разделение трудностей в...
22058. И. Гете, Ф. Шиллер 39 KB
  Гете Ф. Занятие юриспруденцией мало привлекало Гете гораздо более интересовавшегося медициной этот интерес привел его впоследствии к занятиям анатомией и остеологией и литературой. Писать Гете начал рано. Гете дает ряд тонких произведений не открывающих однако его самобытного творческого лица.
22059. Романтизм 41.5 KB
  Зыбкость текучесть составляла самую суть романтизма проводившего идею недостижимой цели вечно манящей поэта. Здесь будет уместно сказать несколько слов об идеалах романтизма поскольку художественноэстетическая система есть ни что иное как система художественных и эстетических идеалов. В основе романтизма лежит система идеальных ценностей т. Эта система ценностей вступает в противоречие с системой ценностей реального мира и тем самым вызывает к жизни второй постулат романтизма как художественноэстетической системы и романтизма как...
22060. Авторы и произведения эпохи Романтизма 36.5 KB
  Авторы и произведения эпохи Романтизма Историкохудожественное значение Романтизма исключительно велико. была причиной противоречивого характера всего немецкого Романтизма. Большое влияние на развитие прогрессивных тенденций немецкого Романтизма. Так выразитель позднего немецкого Романтизма Э.