ДМ_Конспект

С помощью диаграмм Эйлера-Венна можно графически показать, принадлежит ли некоторый элемент x U рассматриваемым множествам или нет, однако реальные отношения включения, установленные между множествами, отразить нельзя. Можно рассматривать отношения включения только в общем случае.

Пример. На рис. 1.1 элемент x1 принадлежит A и не принадлежит B ; x2 принадлежит A и B ; x3 принадлежит B и не принадлежит A ; x4 не принадлежит ни A , ни B . Любой элемент принадлежит универсальному множеству U .

Рисунок 1.1 – Диаграмма Венна для двух множеств A и B

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

(рис. 1.2).

Рисунок 1.2 – Изображение множеств, не имеющих общих элементов, с помощью кругов Эйлера

Множества, имеющие общие элементы, изображают пересекающимися фигурами (рис. 1.3).

21

Рисунок 1.3 – Изображение множеств, имеющих общие элементы, с помощью кругов Эйлера

Отношение включения на множествах изображают, располагая одну фигуру вложенной в другую (рис. 1.4).

Рисунок 1.4 – Изображение отношения включения на множествах с помощью кругов Эйлера

2.2 Операции на множествах

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

Рассмотрим операции на множествах. Пусть имеются два множества A и B .

Определение. Объединением (суммой) множеств A и B называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы

одному из множеств A или B .			Объединение множеств		A и B обозначается
A B . Данное определение можно записать A B ={x | x X или x B].
Пример:
а)	если	A {1, 2, 6, 7}, а	B {2, 3, 5, 6}, тогда		A B {1, 2, 3, 5, 6, 7}.
Объединение A B образовано из A и B путем соединения вместе элементов
A и B .
б)	если	A={x | x политик},		B {x | x выпускник вуза}, то

A B ={x | x политик или выпускник вуза].

Аналогично определяется объединение произвольной (в том числе бесконечной) совокупности множеств. Если совокупность содержит небольшое

22

количество множеств, то объединение данных множеств описывается явно, т.е.

A B C D и т.д.
В общем случае используется обозначение A,				которое читается так:
			A S
«объединение всех множеств A , принадлежащих совокупности S ».
Если же все множества совокупности занумерованы индексами, то
используются другие варианты обозначений:
k	для случая, когда S = A1 , A2 ,..., Ak		;
а) Ai
i 1
б) Ai	для случая, когда S – бесконечная совокупность и еѐ множества
i 1
занумерованы подряд натуральными числами;
в) Ai	для случая, когда набор индексов множеств задан множеством
i I
I {1, 2, 3, ...}.
Определение. Пересечением множеств A и B называется множество,
состоящее из всех тех и только тех элементов, которые принадлежат и A ,					и B .
Пересечение множеств A и B обозначается A B .
Сформулированное		определение	можно	записать	как
A B = x | x A и x B .		Если A B = , то	A и	B – непересекающиеся
множества.
Пример:
1. Если A {1, 2, 3, 4, 5} и B {1, 3, 5, 7, 9}, тогда A B {1, 3, 5}.
2. Если C {x | x имеет рост выше 180 см} и
D {x | x любит играть в шахматы}, тогда
C D {x | x имеет рост выше 180 см и			любит играть в шахматы}.

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

Определение. Система множеств, в которой все попарные пересечения множеств пусты, называется разбиением множества D всех элементов этих множеств, а множества такой системы называются классами или блоками разбиения. Всякий элемент множества D входит только в один класс разбиения.

Пример:

Множество всех групп направления (потока) «Компьютерные науки» является разбиением множества всех студентов, поступивших в университет на

23

направление «Компьютерные науки». Классы этого направления – группы. Всякий студент может входить только в одну группу.

Определение. Разность A и B (обозначается A B или A \ B ) это множество, состоящее из тех и только тех элементов, которые принадлежат A и не принадлежат B , т.е. A B {x | x A и x B}.

Пример: A {1, 2, 3}; B {2, 3, 4}; тогда A B {1}, B A {4}.

Определение. Если A U , то множество U A называется дополнением

(абсолютным дополнением, отрицанием) множества A .
		Дополнение множества A , обозначаемое А (читается «не				A »), – это
множество элементов универсума, которые не принадлежат					A , следовательно,
	A= U A= {x | x U и x A}. Дополнение A определяется					отрицанием
свойства P( A) , с помощью которого определяется A .
		Пример:
		Если U – множество положительных целых чисел, а			A {2, 4, 6, 8, ...} –

множество всех положительных четных чисел, то А {1, 3, 5, 7, ...} – множество всех положительных нечетных чисел.

Определение. Дизъюнктивная сумма (симметрическая разность) –

это множество, состоящее из всех элементов A , не принадлежащих B , и всех элементов B , не принадлежащих A , и не содержащее никаких других элементов, т.е. A B = x | (x A) (x B) (A B) (B A) .

Симметрическая разность, обозначаемая как A B , либо A B , либо A+ B , получается объединением элементов множеств за исключением тех, которые встречаются дважды.

Пример: A {1, 2, 3}; B {2, 3, 4}; A B {1, 4}.

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

Введенные операции называются теоретико-множественными операциями.

Все данные операции на множествах можно проиллюстрировать с помощью диаграмм Эйлера-Венна (рис. 1.5), в которых круги представляют соответствующие множества, участвующие в операциях (например, множество A ), а заштрихованная часть плоскости является результатом выполнения операций (например, A B , A B , A B , A , A B ).

24

а) A

б) A B

в) A B

г) A B

д) A B
	е) A

Рисунок 1.5 Применение диаграмм Эйлера-Венна для иллюстрации операций на множествах

2.3 Общее определение алгебры

Алгебра в широком понимании может быть определена как наука (учение) о системах объектов той или иной природы, в которых установлены алгебраические операции. Для современной алгебры характерно то, что в центре внимания оказываются свойства операций, а не объектов, над которыми производятся эти операции. Алгебра классифицирует системы с заданными на них алгебраическими операциями по их свойствам и изучает различные задачи, естественно возникающие в этих системах.

Введем формализованное понятие алгебры.

25

Определение. Множество M вместе с заданной на нем совокупностью

операций {1 , 2 , ...,m }, т.е. система	A= (M ; 1 , 2 , ...,m ) , называется
алгеброй. Множество M – это основное, или несущее, множество (или просто

носитель) алгебры. {1 , 2 , ...,m } называется сигнатурой и представляет

собой множество операций с элементами множества	M . Функция типа:
: M n M называется n -арной операцией. Вектор	арностей операций
алгебры называется еѐ типом.

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

Определение. Операция, заданная на некотором множестве, называется унарной, если она действует на один элемент множества и еѐ результатом является элемент этого же множества.

Нульарные операции – это фиксированные элементы множества M ,

называются также выделенными элементами, иногда нулями.
Определение.		Множество	M ' M	называется			замкнутым
относительно n -арной операции на M ,				если	(M 'n M ' ) ,			т.е. если
значения	на аргументах из M ' принадлежат				M ' .	Если	M '	замкнуто
относительно	всех	операций	1 , 2 , ...,m	алгебры		A ,	то	система

A' = (M ' ; 1 , 2 , ...,m ) называется подалгеброй A (при этом 1 , 2 , ...,m рассматриваются как операции на M ' ).

Примеры алгебр:

1. Алгебра (R; , ) называется полем действительных чисел. Несущее множество R – множество действительных чисел. Операции + и – бинарные операции, поэтому тип этой алгебры (2, 2) . Подалгеброй этой алгебры является, например, поле рациональных чисел.

2. Пусть задано множество U . Множество всех его подмножеств является

булеаном U		и обозначается P(U ) .			Алгебра		B = (P(U ); , , )		называется
булевой	алгеброй множеств		над	U ,	еѐ	тип (2, 2, 1) .		Элементами несущего
множества этой алгебры являются множества (подмножества U ). Для любого
U' U	B' = (P(U ' ); , , )		является			подалгеброй		B . Например, если
U {a, b, c, d},		то основное	множество алгебры B содержит 16						элементов;
алгебра	B' = (P({a, c}); , , )			– подалгебра			B ; еѐ	основное	множество

26

A, B, C,

содержит четыре элемента. Операции ( , ) являются бинарными, а операция отрицания ( ) является унарной.

2.4 Понятие алгебры множеств. Аксиомы алгебры множеств

Алгебра множеств представляет собой теоретико-множественный аналог обычной алгебры действительных чисел и основана на свойствах операций над множествами.

Определение. Алгебра множеств – непустая совокупность подмножеств некоторого множества M , замкнутая относительно теоретико-множественных операций (объединения, пересечения, разности, дополнения).

Для того чтобы некоторый класс подмножеств множества M был алгеброй множеств, достаточно (и необходимо), чтобы он был замкнут относительно образования объединений и дополнений.

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

1.Коммутативные законы

A B = B A, A B = B A.

2.Ассоциативные законы

A (B C) = (A B) C ,

A (B C) = (A B) C .

3. Дистрибутивные законы

A (B C) = (A B) (A C),

A (B C) = (A B) (A C).

4. Свойства пустого и универсального множеств

A = A, A = ,

A U = U , A U = A .

= U , U = .

5.Законы идемпотентности (самопоглощения)

27

A A = A,

A A = A.

6. Закон инволюции

A = A.

7.Закон противоречия

A A = .

8.Закон исключенного третьего

A A = U .

9. Законы элиминации (поглощения)

A (A B)= A.

A (A B)= A.

10.Законы де Моргана

A B = A B ,

A B = A B .

Свойствами дополнения, разности и равенства также являются:

11.Если A B = U и A B = , то B = A.

12.A= U A.

13.A B = A B .

В справедливости перечисленных выше свойств можно убедиться различными способами:

нарисовать диаграммы Эйлера-Венна для левой и правой частей равенства и убедиться, что они совпадают;

провести формальные рассуждения для каждого равенства.

2.5 Принцип двойственности

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

Определение. Соответствующие пары символов , и , U

называются двойственными (дуальными) символами.

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

28

Законы 11 и 12 не изменяются при замене символов дуальными, поэтому их называют самодвойственными.

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

2.6 Тождественные преобразования формул алгебры множеств

Пользуясь основными тождествами (законами) можно упрощать или преобразовывать к удобному виду различные сложные выражения, содержащие множества, аналогично тому, как проводится упрощение выражений в элементарной алгебре. Для выполнения подобных преобразований применяется следующая приоритетность операций относительно друг друга: A , A B ,

A B , A B .

Такие преобразования осуществляются последовательным применением соответствующих свойств операций над множествами.

Пример. Соотношение A A = A доказывается следующими преобразованиями с использованием рассмотренных законов

A A (A A) U (A A) (A A) A (A A) A A.

Пример. Упростить выражение (A B C) (A C) (B C) . Для упрощения используем законы алгебры множеств.

(A B C) ( A C) (B C)( A B C) [(A B) C] =[(A B) (A B)] C [(A B) (A B)] C U C C .

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

2.7 Контрольные вопросы и задания

1.Какие операции над множествами позволяют строить новые множества, используя уже существующие?

2.Какова приоритетность выполнения операций над множествами.

3.Какие способы графической иллюстрации операций над множествами Вы знаете?

29

4.Поясните обобщенное понятие алгебры. Приведите примеры алгебр.

5.Что такое алгебра множеств?

6.Какая операция над множествами называется бинарной?

7.Какая операция над множествами называется унарной?

8.Назовите основные аксиомы алгебры множеств.

9.Какими свойствами обладает пустое множество и универсальное множество U ?

10.Опишите принцип двойственности в алгебре множеств, приведите примеры двойственных символов.

11.Поясните способы преобразования формул алгебры множеств.

ЛЕКЦИЯ 3 ОТНОШЕНИЯ И ИХ СВОЙСТВА. ОТНОШЕНИЯ И ОПЕРАЦИИ

НАД НИМИ.

3.1 Декартово произведение множеств

Для формального определения понятия отношения используем понятие декартова (прямого) произведения множеств.

Определение. Декартовым (прямым) произведением множеств X и Y

называется множество, которое обозначается X Y и состоит из всех тех и только тех упорядоченных пар (x, y) , первая компонента (координата) которых

принадлежит множеству X , а вторая компонента (координата) принадлежит множеству Y , т.е. X Y {(x, y) | x X , y Y}.

Пример.

Пусть X {1, 2}, Y {1, 3}. Тогда X Y {(1,1),(1,3),(2,1),(2,3)}.

Порядок следования пар может быть произвольным, но размещение элементов в каждой паре определяется порядком следования перемножаемых множеств. Следовательно, декартово произведение изменяется при смене порядка сомножителей, и X Y Y X , если X Y .

Пример. Пусть X {a,b,c}, Y {d,e}.

X Y {(a,d),(b,d),(c,d),(a,e),(b,e),(c,e)}. Y X {(d,a),(d,b),(d,c),(e,a),(e,b),(e,c)}.

Следовательно, X Y Y X .

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

Определение.

30