Конспект_лекций_по_курсу_Дискретная_математика

2.Пусть А = {б, д}, B = {а, о}, C = {к, т}, тогда А B C = {(б, а, к), (б, а, т), (б, о, к), (б, о, т), {(д, а, к), (д, а, т), (д, о, к), (д, о, т)}.

3.Пусть A = {a, b, c, d, e, f, g, h}, B = {1, 2, 3, 4, 5, 6, 7, 8}, тогда множество

A B описывает множество клеток шахматной доски.

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

венных чисел: A = [а1, а2], B = [b1, b2]. Отложим отрезок A на оси абсцисс, отрезок

B на оси ординат. Тогда пара чисел (a, b), где a A, а b B, определяет точку на плоскости, а декартово произведение A B образует множество точек прямоуголь-

ника со сторонами A и B (рис. 1.5).

y

b2

B

b1

-12-

Декартово произведение трех множеств может быть тоже представлено гео-

метрически, но уже не на плоскости, а в пространстве.

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

Определение. Совокупность всех множеств, входящих в универсальное мно-

жество I, совместно с операциями объединения ( ), пересечения ( ) и дополне-

ния называется булевой алгеброй множеств.

Как и всякая алгебра, булева алгебра множеств имеет дело с некоторыми объ-

ектами, объединяемыми по определенным правилам в формулы с помощью зна-

ков операций и скобок.

В обычной алгебре этими объектами являются числа или заменяющие их символы, в алгебре множеств – это множества или заменяющие их символы.

Формулы алгебры множеств строятся по следующим правилам:

1)всякий символ, обозначающий множество, есть формула алгебры множеств;

2)если и Θ – формулы алгебры множеств, то ( ),( ) ( ),( ) ( ) – тоже

формулы алгебры множеств.

Пример 1.3.1. 1. А; 2. В; 3. (А) (В); 4. (А) (В); 5. ((A) (B)) ((A) (B)) .

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

Кроме того, как и в обычной алгебре, вводят правило старшинства операций. В

частности, принято, что при отсутствии скобок первыми выполняются дополне-

ния, относящиеся к отдельным множествам, затем пересечения, после них объеди-

нения. В последнюю очередь выполняются дополнения, относящиеся к комбина-

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

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

-13-

Обычно одно и то же множество можно представить несколькими различны-

ми формулами, например, А В = В А.

Различные формулы, представляющие одно и то же множество, называются

эквивалентными. Алгебра множеств занимается правилами эквивалентного или

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

Все тождественные преобразования формул алгебры множеств основаны на следующих основных тождественных соотношениях:

1)A B = B A – коммутативность объединения;

2)A B = B A – коммутативность пересечения;

3)А (В С) = (А В) С – ассоциативность объединения;

4)А (В С) = (А В) С – ассоциативность пересечения;

5)A A = A – идемпотентность объединения;

6)А А = А – идемпотентность пересечения;

7)(А В) С = (А С) (В С) – дистрибутивность пересечения относительно объ-

единения (1-й дистрибутивный закон);

8) (А В) С = (А С) (В С) – дистрибутивность объединения относительно пе-

ресечения (2-й дистрибутивный закон);

9)A B A B – 1-е правило де Моргана;

10)A B A B – 2-е правило де Моргана;

11)A A – закон двойного дополнения;

12)А (А В) = А – 1-й закон поглощения;

13)А (А В) = А – 2-й закон поглощения;

14)A A I ;

15)A A ;

16)А = А;

17)А = ;

18)A I = I;

19)A I = A;

-14-

20)I ;

21)I ;

Нетрудно видеть, что соотношения 1 – 4, 7, 8 и 16 – 19 представляют собой уже знакомые нам свойства операций объединения и пересечения. Справедливость остальных соотношений легко проверяется с помощью диаграмм Эйлера-Венна

(сделайте это самостоятельно).

Рассмотрим примеры применения этих соотношений для упрощения формул алгебры множеств. В процессе преобразований в случае необходимости использу-

ется также соотношение A \ B A B . Под знаками равенства написаны номера используемых при преобразованиях тождественных соотношений.

Пример 1.3.2.

1. A \ B (A B) A B (A B) (A B) (A B) (A B) (A B)

2.(A \ C) \ ((B \ C) \ (B \ A)) (A C) ((B C) (B A))

A C (B C (B A) A C (B C B) (B C A)

(10) (7,11)

A C (B C A) A C (B C A)

(15) (16,10)

(A C B) (A C C) (A C A) (A C B) A \ C \ B.

(7,11) (15) (16)

1.4. Соответствия

1.4.1. Определения Слово соответствие в нашем обычном разговорном языке означает соотно-

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

-15-

На строгом математическом языке соответствием называется тройка мно-

жеств q = <X,Y,Q>, где Х и Y – произвольные множества, а Q X Y.

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

в которых первый элемент x Х, а второй элемент y Y. При этом Х называется об-

ластью отправления соответствия, Y – областью прибытия соответствия, а Q –

графиком соответствия (иногда его называют просто соответствием).

Множество первых элементов пар (x, y), принадлежащих Q, называется обла-

стью определения или первой проекцией соответствия и обозначается Пр1Q.

Очевидно, что Пр1Q X.

Множество вторых элементов пар (x, y), принадлежащих Q, называется обла-

стью значений или второй проекцией соответствия и обозначается Пр2Q. Оче-

видно, что Пр2Q Y.

Пример 1.4.1. 1. Пусть Х – множество сотрудников университета, Y – множе-

ство учебных групп и пусть (x, y) Q тогда и только тогда, когда сотрудник х ве-

дет занятия в группе y, т.е. Q = {(x, y)|x Х, y Y и сотрудник х ведет занятия в группе y}. Пр1Q X – множество сотрудников НГТУ, участвующих в учебном процессе (обратите внимание, что в этой записи используется знак строгого вклю-

чения , так как не все сотрудники университета участвуют в учебном процессе),

Пр2Q = Y, так как в каждой учебной группе кто-то из сотрудников ведет занятия.

В этом примере Q устанавливает некоторое соответствие между множеством сотрудников университета и множеством учебных групп.

2.Пусть F={f(x)} – множество функций вещественной переменной f(x), R={r}

–множество вещественных чисел и пусть

J F R {( f , r) | f F, r R и r f (x)dx}

0

В этом примере J устанавливает соответствие между функциями веществен-

ной переменной и вещественными числами. Область определения этого соответст-

вия Пр1J F, так как указанный в примере интеграл существует не для любой

-16-

функции вещественной переменной. Область значений Пр2J = R, так как любое действительное число может быть значением данного интеграла.

1.4.2. Способы задания соответствий Для задания соответствия нужно, очевидно, определить все три множества Х,

Y и Q. Эти множества задаются так же, как и любые другие множества, например,

перечислением их элементов или заданием характеристического свойства, множе-

ство Q при конечном количестве его элементов может быть задано также в виде

матрицы или графически.

Пример 1.4.2. Пусть Х={Иванов, Петров, Сидоров} – некоторое подмножест-

во множества преподавателей университета, Y={ВИ-91, ВИ-81, АС-812, АС-813,

АС-814} – подмножество множества учебных групп, Q={(x, y)|x Х, y Y и x ведет занятия в группе y}. Так как число элементов в множествах Х и Y конечно, то это соответствие можно задать и перечислением элементов: Q={(Иванов, ВИ-91), (Иванов, ВИ-81), (Иванов, АС-812), (Иванов, АС-813), (Иванов, АС-814), (Петров,

АС-812), (Петров, АС-813), (Петров, АС-814), (Сидоров, ВИ-81)}.

1.4.2.1. Матричный способ задания

Для задания соответствия строится матрица, каждой строке которой ставится в соответствие ровно один элемент области отправления Х, а каждому столбцу – элемент области прибытия Y. На пересечении строки и столбца ставится 1, если соответствующие им элементы образуют пару, принадлежащую соответствию Q, в

противном случае ставится 0.

Пример 1.4.3. Соответствие из предыдущего примера в матричной форме

имеет вид:

-17-

1.4.2.2. Графический способ задания

При использовании этого способа для задания каждому элементу множеств X

и Y ставится в соответствие произвольная точка на плоскости. Если пара (x, y) Q,

то элементы x и y соединяются стрелкой, идущей от х к y.

Пример 1.4.4. Графическое представление соответствия из предыдущего

Рис. 1.7

1.4.3. Операции над соответствиями Так как соответствия являются множествами, то над ними можно выполнять

все те операции, что и над обычными множествами, в частности объединение и пересечение. Кроме того, имеются специфические для соответствий операции – симметризация и композиция.

1.4.3.1. Объединение соответствий

Пусть даны два соответствия q = <X, Y, Q> и s = <U, V, S>.

Соответствие p = <Z, W, P> будет объединением соответствий q и s (p = q s),

если Z = X U, W = Y V и P = Q S.

1.4.3.2. Пересечение соответствий

Пусть даны два соответствия q = <X, Y, Q> и s = <U, V, S>. Соответствие p = <Z, W, P> будет пересечением соответствий q и s (p = q s), если Z = X U, W = Y

V и P = Q S.

1.4.3.3. Симметризация соответствий

Пусть q = < X, Y, Q > некоторое соответствие. Соответствием, обратным

соответствию q, называется соответствие q 1 = (Y, X, Q 1), в котором Q 1 Y X и пара (y, x) Q 1 тогда и только тогда, когда пара (x, y) Q.

-18-

Операция получения обратного соответствия называется симметризацией.

Если соответствие задано перечислением входящих в него пар, то для полу-

чения обратного соответствия нужно просто переставить местами элементы в ка-

ждой паре.

Если соответствие задано в матричном виде, то для получения обратного со-

ответствия матрицу нужно транспонировать, т.е. поменять местами ее строки и столбцы.

Если соответствие задано графически, то для получения обратного соответст-

вия нужно изменить направление всех стрелок на противоположное.

Пример 1.4.5. Выполним симметризацию соответствия из примера 1.4.2.

Q 1 = {(ВИ-91, Иванов), (ВИ-81, Иванов), (АC-812, Иванов), (АC-813, Ива-

нов), (АC-814, Иванов), (АC-812,Петров), (АC-813, Петров), (АC-814, Петров),

(ВИ-81, Сидоров)}

В матричной форме:

Соответствие Q 1 в графической форме представлено на рис. 1.8

Рис. 1.8

1.4.3.4. Композиция соответствий

Пусть даны два соответствия q = <X, Y, Q>, Q X Y и p = <Y, Z, P>, P Y Z.

-19-

Композицией соответствий q и p называется соответствие s q p X , Z, S ,

S Q P X Z , состоящее из таких и только таких пар (x, z), x X, z Z, для кото-

рых существует хотя бы один элемент y Y, такой, что пара (x, y) Q, а пара

(y, z) P.

Из этого определения следует, что областью отправления композиции явля-

ется область отправления первого из соответствий, образующих композицию, а

областью прибытия – область прибытия второго соответствия. Для того чтобы па-

ра (x, z), x X, z Z, принадлежала композиции, должен существовать промежуточ-

ный элемент в множестве Y, образующий с элементами x и z пары, входящие в ис-

ходные соответствия. Это можно кратко записать таким образом:

Вформуле (1.1) использованы следующие обозначения:

"тогда и только тогда, когда";

"существует хотя бы один";

"и".

Пример 1.4.6. 1. Пусть Х – множество кафедр университета, Y – множество учебных дисциплин, входящих в учебные планы университета, Z - множество спе-

циальностей, по которым ведется подготовка, и пусть Q = {(x, y)| кафедра x может вести занятия по дисциплине y}, P = {(y, z)| дисциплина y входит в учебный план специальности z}. Тогда композиция Q P = {(x, z)| кафедра х может вести занятия для специальности z}, иначе говоря, пара (x, z) Q P тогда и только тогда, когда существует дисциплина y из множества учебных планов университета, которая входит в учебный план специальности z и которую может вести кафедра х.

2. Пусть Х = Y = Z = R - множество вещественных чисел и пусть

Q = {(x, y)| y = sin x}, P = {(y, z)| z = ln y}. Тогда S = Q P = {(x, z)| z = ln (sin x)}.

Проанализируем области определения и значений исходных соответствий Q

и P и их композиции.

-20-