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.

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

а)

б)

в)

г)

д)


 

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

29058. Гражданские правоотношения: понятие, виды гражданских правоотношений. Субъекты и объекты гражданских правоотношений. Основания их возникновения 89.5 KB
  Иначе говоря специфические черты и признаки гражданских правоотношений предопределены особенностями самого гражданского права. Содержание гражданского правоотношения Содержание гражданского правоотношения составляют субъективные права и обязанности его участников. Юридические возможности как составные части содержания субъективного гражданского права называются правомочиями. При весьма большом разнообразии содержания субъективных гражданских прав можно обнаружить что оно является результатом разновариантных комбинаций трех правомочий: 1...
29059. Правосубъектность гражданина 49.5 KB
  Гражданская дееспособность определяется как способность гражданина своими действиями приобретать и осуществлять гражданские права создавать для себя гражданские обязанности и исполнять их ст. 21 ГК РФ можно определить содержание дееспособности которое понимается как предоставленная гражданину возможность реализации своей правоспособности собственными действиями и включает способность гражданина своими действиями: приобретать гражданские права; осуществлять гражданские права; создавать и исполнять гражданские обязанности; нести...
29060. Юридические лица: понятие, виды, создание и прекращение юридических лиц 77 KB
  Понятие юридического лица в ст. Законодатель убрал уточнение по имущественной обособленности на праве собственности праве хозяйственного ведения или оперативного управления Суть от этого особо не изменилась поскольку в обоих определениях указываются одни и те же признаки юридического лица. В данном определении указываются признаки юридического лица это такие внутренние присущие ему свойства каждое из которых необходимо а все вместе достаточны для того чтобы организация могла признаваться субъектом гражданского права. Правовая...
29061. Объекты гражданских прав 169.5 KB
  К объектам гражданских прав закон относит вещи включая деньги и ценные бумаги иное имущество в том числе имущественные права; работы и услуги; результаты интеллектуальной деятельности в том числе исключительные права на них интеллектуальная собственность; нематериальные блага ст. Таким образомобъекты гражданских прав подразделяются на материальные и нематериальные идеальные. К первой группе относят: вещи; работы и услуги а также их результаты имеющие овеществленный либо иной стоимостной эффект например ремонтные работы услуги по...
29062. Понятие и виды сделок. Требования, предъявляемые к форме сделок 245.5 KB
  Но поскольку субъектами сделок являются граждане и юридические лица муниципальные образования субъекты РФ государство иностранные граждане и иностранные юридические лица лица без гражданства а субъективные гражданские права и обязанности являются содержанием гражданского правоотношения то понятие сделки можно определить следующим образом: Сделка это осознанное волевое и юридически значимое действие субъектов гражданского права прямо направленное на возникновение изменение и прекращении гражданских правоотношний. С помощью сделки...
29063. Недействительные сделки: понятие, виды, последствия недействительности 206.5 KB
  Недействительными являются сделки не создающие правового результата прав и обязанностей к которому стремились стороны. Эти основания связаны с теми или иными нарушениями условий действительности сделок а именно: законность содержания сделки соответствие воли и волеизъявления соблюдение требуемой по закону формы сделки совершение сделки лицом обладающим необходимой дееспособностью. Основания недействительности должны иметь место одновременно с совершением сделки как юридического факта.
29064. Исковая давность в гражданском праве 100 KB
  Институт исковой давности имеет большое значение для защиты имущественных прав граждан и юридических лиц. С его помощью во многом обеспечивается стабильность гражданского оборота: участники гражданских отношений знают что по истечении исковой давности никто не может предъявить к ним требований и провести ревизию принадлежащих им прав. С истечением срока исковой давности право на принудительную судебную защиту не прекращается а приобретает условный характер: оно сохраняется если сторона в споре не заявит о применении исковой давности. При...
29065. Право собственности: понятие, содержание, основания возникновения и прекращения 51 KB
  Нормы образующие институт права собственности находятся в постоянном контакте и взаимодействии с нормами других правовых институтов например с обязательственным правом. Субъективное право собственности это закрепленная за собственником юридически обеспеченная возможность владеть пользоваться и распоряжаться принадлежащим ему имуществом по своему усмотрению и в своих интересах путем совершения в отношении этого имущества любых действий которые не противоречат закону и иным правовым актам и не нарушают права и охраняемые законом интересы...
29066. Вещно – правовые средства защиты права собственности и других вещных прав 37 KB
  виндикационный об истребовании имущества из чужого незаконного владенияи негаторный об устранении препятствий в пользовании имуществом не связанных с лишением владения вещью. Виндикационный иск Собственник который оказался лишенным принадлежащего ему имущества без необходимого правового основания может истребовать свое имущество из чужого незаконного владения. Виндикационные иски предъявляются в отношении индивидуальноопределенного имущества причем сохранившегося в натуре; в иных ситуациях надлежит требовать возмещения причиненных...