42. Понятие множества

Df. 4.1: Под множеством понимают набор объектов произвольной природы, которые называют элементами множества.

Зам: Множества будем обозначать большими буквами латинского алфавита, элементы множества малыми.

Df. 4.2: Говорят, что любой элемент множества М принадлежит М и пишут .

Зам: Если множество А состоит из элементов , то пишут A={ }

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

Df. 4.4: Универсальным множеством(универсалом) называется множество, которому все элементы данного семейства множеств.

Df. 4.5: Два мн-ва А и В наз. равными, если они состоят из одних и тех же элементов (А=В).

Зам: Доказательство того, что два мн-ва А и В равны производится в два этапа:

1. Доказывается, что любой элемент множества А и множеству В.

2. Доказывается, что любой элемент множества В и множеству А.

Df.4.6: Говорят, что мн-во А является подмножеством множества В, если любой элемент множества А и множеству В.(А В).

Df.4.8: Говорят, что мн-во А явл собственным подмн-вом мн-ва В и пишут А В, если А В, А В.

Лемма 4.1: Пустое множество является подмножеством любого множества.

Д-во: Предположим, что нашлось такое множество А, что , это значит имеется такой элемент x, что x; но это противоречит тому, что не содержит ни одного элемента. Чтд

Df 4.8 Булеаном множества А называется семейство всех подмножеств множества А. Булеан множества А обозначается 2^А.

Замечание: При задании множества порядок перечисления элементов множества роли не играет {a,b}={b,a}

Df 4.9 Мощностью конечного множества называется число элементов этого множества и обозначается |A|.

Лемма 4.2: Если |A|=n, то |2^A|=2ⁿ

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

Df 4.10 Объединением 2-ух множеств А и В называется множество, обозначаемое АВ, которое состоит из тех и только тех элементов, которые принадлежат хотя бы одному из множеств А, В; т.е. АB={x|xA или xB}.

Df. 4.11 Пересеч 2-ух мн-в А и В называется множество АВ={x|xA }

Df. 4.12 Два множества А и В называются не пересекающимися, если АВ =.

Df. 4.13 Пусть Е={E₁,E₂, … , Е_n}- семейство подмн-в мн-ва А. Тогда Е наз. покрытием мн-ва А, если каждый элемент мн-ва А входит хотя бы в 1 подмножество Е₁,Е₂,…,Е_к.

Df. 4.14 Покрытие Е множества А называется разбиением множества А, если каждый элемент исходного множества А входит ровно в одно подмножество семейства Е.

Df. 4.15 Разностью двух множеств А и В называется множество А\В, которое состоит из только из тех элементов множества А, которые В, т.е. А\В = {x|xA;хB}

Df. 4.16 Симметричной разностью множеств А и В называется множество АB (или АB), которое состоит из тех элементов, которые ровно одному множеству, т.е. АB={x|xA и хB или xB хА}

Df. 4.17 Дополнением множества А называется множество, обозначаемое , которое состоит из тех элементов, которые А

={x|xА }

Лемма 4.3 А\В=А

Д-во:

1. Пусть xA\B. Тогда по определению разности xA хB, то x. Таким образом, xA и x. Следовательно xA

2. Пусть xA. Тогда, по определению операции пересечения xA и xТ.к. x, то хB. Таким образом, xA и хB. Тогда по определению разности xA\B Чтд

Св-ва операций над мн-ми

Пусть множества А,В,С являются подмн-ми универсального мн-ва U. Тогда справедливы след. свойства:

1⁰Идемпотентность, т.е. АА=А и AA=A

2⁰Коммутативность, т.е. АB= BA и AB= BA

3⁰ Ассоциативность, т.е. А(BС)= (АB)С , А(BС)= (АB)С

4⁰Дистрибутивность, т.е. А(BС)=(АB)(АС); А(BС)=(АB)(АС)

5⁰Свойство поглощения, т.е. . А(AB)=A ; А(AB)=A.

6⁰Свойство нуля, т.е. А=A; А=A;

7⁰Свойство единицы, т.е. А; А; =

8⁰Свойство де Моргана, т.е. = ; =

9⁰Инволютивность, т.е. =А

10⁰Свойство дополнения, т.е. А; А

Докажем, например, 2-ой закон дистрибутивности: А(BС)=(АB)(АС)

Д-во:

1. Пусть x А(BС). Тогда по определению пересечения: хА; хBC. Т.к. хBC, то хB или хС. Следовательно: хA и хB или хA и хС. Следовательно х(АB)(АС)

2. Пусть х(АB)(АС). Тогда хАB или хАС. Откуда следует (хА и хB) или (хA и хС) хA и хB или хC хA и хBC. Тогда x А(BС)

Чтд