Число элементов множества

Для любого конечного множества М, число элементов (мощность множества) будем обозначать n(M).

Пусть задано несколько множеств (подмножеств универсального множества): А,В,С,... с числом элементов в каждом соответственно n(A), n(B), n(C),.Решим задачу о количестве элементов в множестве, записанном в виде формулы, т.е. состоящем из нескольких множеств, связных операциями пересечения, объединения и дополнения.

Дано: A, B, n(A), n(B).

Определить: число элементов в объединении n(A U B).

Для непересекающихся множеств число элементов объединения равно сумме элементов в каждом из объединяемых множеств:

n(A U B) = n(A) + n(B).

Общий случай (два множества имеют общую область):

n(A U B) = n(A) + n(B) - n(A П B).

Общий случай (три множества имеют общую область):

n(AUBUC)=n(A)+n(B)+n(C)-n(A П B)-n(A П C)-n(B П C)+n(A П B П C).

Тема №2. Теория Отношений.

План

2.1Отношения.........................................

2.2. Свойства бинарных отношений.......................

2.3. Операции с бинарными отношениями..................

2.1.Подмножество R c M^n называется n-местным (n-арным) отношением на несущем множестве M. Множество М является несущим для отношений любой арности, которые на нем построены. Говорят, что элементы вектора (a1,a2,a3,...,an) находятся в отношении R, если этот вектор принадлежит множеству R. Для n=1 отношение называют унарным (по сути, такое отношение выделяет из множества М подмножество R по признаку); для n=2 - бинарным (т.е. отношением между двумя элементами множества М) и т.д.

Отношение - то же множество, элементами которого являются векторы размерности n или, при другой записи, цепочки длины n, составленные в алфавите М и отобранные в соответствии с отношением R

Пример: Построим бинарное отношение R, которое определим словами как "в латинском алфавите встречается раньше" на несущем множестве M={a,b,c,d}. Примерами элементов отношения R могут быть векторы (a,c), (c,d)... или цепочки ac, cd, bd..., такие, в которых на первом месте стоит буква, встречающаяся в латинском алфавите раньше по сравнению с буквой, стоящей на втором месте.

Отношение R является подмножеством множества M^2:

M^2 = {aa, ab, ac,...,cc}, из которого элементы отбираются в соответствии со следующей процедурой R={xy ¦ x "меньше" y}.

R={ab,ac,ad,bc,bd,cd}

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

а) с помощью матрицы смежности - квадратной матрицы, столбцы и строки которой обозначены элементами несущего множества, а элементы имеют следующие значения:

-- i\j¦ a ¦ b ¦ c ¦ d ¦

¦ 1, если ai R aj --+---+---+---+---+

Cij = ¦ a ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦

¦ 0,в противном случае --+---+---+---+---+

L- b ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦

--+---+---+---+---+

(строки-i, столбцы - j) c ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦

--+---+---+---+---+

d ¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦

--+---+---+---+----

На рисунке представлена матрица для отношения R из предыдущего примера.

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

Для каждого бинарного отношения R можно построить обратное отношение R^(-1) (читается: R в степени минус один), поменяв местами в каждом элементе R проекции векторов.