Алгебра множеств

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

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

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

Множество, заведомо содержащее все рассматриваемые элементы, называется универсальным или универсумом - U.

Способы задания множеств:

A = {a, b, c, d} - задание множества явным перечислением элементов.

Например, гвардия = {Иванов, Петров, Сидоров}

B = {x | С(x)} - задание множества (характеристическим) свойством С(x).

Например, студенчество = {x | x - студент} - множество таких х, что х - студент

Отношение включения Í

Множество А включено в множество В (А Í В) или А есть подмножество множества В, если из х Î А следует х Î В.

Отношение строгого включения Ì

Если A Í B и A ¹ B, то можно написать A Ì B.

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

1. Рефлексивность: A Í A

2. Принцип объемности: A Í B и B Í A следует B = A (на основе этого принципа и доказывается равенство двух множеств).

3. Транзитивность: A Í B и B Í C следует A Í C

Полезные соотношения:

{ }= Æ; 1 ¹ { 1 }; {{ 1 }} ¹ { 1 }; { а, в } = { в, а }

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

1. Объединение A и B

A È B = { x | x Î A или x Î B }

(или - неисключающее)

2. Пересечение A и B

A Ç B = { x | x Î A и x Î B }

3. Разность множеств A и B

A \ B = { x | x Î A и x Ï B }

4. Симметрическая разность A и B

A D B = { x | (xÎA и xÏB) или (xÏA и xÎB)}=(A \ B) È (B \ A)

5. Дополнение множества A̅

A̅ = { x | x ÏA }

Пример.

Пусть А = {1, 2, 3} и B = {3,4}, тогда

A È B = {1, 2, 3, 4}

A Ç B = {3}

A \ B = {1, 2}

A D B = {1, 2, 4}

неА = множество чисел кроме 1, 2, 3.

Диаграммы Эйлера-Венна позволяют представить множества, как множества точек на плоскости, ограниченные замкнутыми кривыми. Прямоугольная рамка - универсум.

A(I), B(II), AÇB (III)

Алгебра множеств

Cоглашение о "силе": дополнение, пересечение, объединение. Остальные операции можно выразить через эти три.

1. Коммутативный:

A È B = B È A A Ç B = B Ç A

2. Ассоциативный:

A È (B È C) = (A È B) È C = A È BÈ C

A Ç (B Ç C) = (A Ç B) Ç C = A Ç B Ç С

3. Дистрибутивный:

A È (B Ç С) = (A È B) Ç (A È C)

A Ç (B È С) = (A Ç B) È (A Ç C)

4. Поглощения:

A È (A Ç B) = A A Ç (A È B) = A

5. Идемпотентности:

A È A = A A Ç A = A

6. Исключенного третьего:

A È A̅ = U A Ç A̅ = Æ

7. Противоречия:

A È Æ = A A Ç Æ = Æ

A È U = U A Ç U = A

8. Де Моргана:

̅(A È B) = A̅ Ç B̅

̅(A Ç B) = A̅ È B̅

A \ B = A Ç B̅

A D B = (A Ç B̅) È (A̅ Ç B)

4. Кортеж. График.

Кортеж - фундаментальное неопределяемое понятие.

В кортеже существенны не только элементы, но и порядок, в котором они располагаются. Следовательно, кортеж может содержать одинаковые элементы.Кортежем является вектор, заданный проекциями на оси.

Кортеж заключается в угловые скобки.

< a₁ ,a₂, a₃,..., a_n > - кортеж длиной n или упорядоченная n-ка.

< 1, 1, 1 > - упорядоченная тройка – единичный вектор.

< a, b > - упорядоченная двойка или пара.

График - множество пар.

Можно дать и более общее определение графика в n-мерном пространстве, как множества n-ок.

Примеры: G = { < a, b >, < c, a >, < d, b > }

Декартово (прямое) произведение множеств A и B:

A x B = {< a, b > | a Î A, bÎB}

В общем случае:

A₁ x A₂ x A₃ x...x A_n = {< a₁, a₂,..., a_n >|a₁ÎA₁, a₂ÎA₂,..., a_nÎA_n}

Пример:

Для A = { 1, 2 } и B= { 1, 2, 3 } декартово произведение А х В = {< 1, 1 >, < 1, 2 >, < 1, 3 >, < 2, 1 >, < 2, 2 >, <2, 3>}

График является полым, если он совпадает с декартовым произведением.

Композицией графиков P и Q называется график R = P · Q, если он состоит из таких пар < x, y > Î R, что для каждой пары найдется свое z, такое, что < x, z > Î P, < z, y > Î Q. Очевидно, что это некоммутативная операция.

Пример:

P = {< a, b >, < 1, r >, < c, 3 >, < a, 4 >}

Q = {< 2, 3 >, < 4, 5 >, < a, c >, < b, d >}

R = P · Q = {< a, d >, < a, 5 >}