9957

Сколько студентов сдали все три дисциплины на отлично, если запрос на объединение результатов трех запросов возвращает 37 записей?

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

Сколько человек попадает в каждую из следующих категорий:

26.Пользуясь свойствами операций над множествами доказать равенства:

1)(A Ç B Ç X )È (A Ç B Ç C Ç X ÇY )È (A Ç X Ç A)= A Ç B Ç X

2)(A Ç B Ç C ) È (A Ç B Ç C )È B È C =U

27.Каждое из следующих утверждений либо докажите, либо покажите при помощи диаграмм Эйлера, что оно не всегда верно:

а) (A È B) \ (A Ç B) = (A \ B) È (B \ A)

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

в) (A \ B) È (B \ A) È (A Ç B) = A È B

22

28. Доказать равенства:

a)Найдите количество участников конференций первокурсников от вуза М, окончивших среднюю школу в прошлом учебном году.

b)Установите соответствие между множествами, заданными перечислением и соответствующими им диаграммами ЭйлераВенна:

1) {n1, n5 , n7 , n8 , n12 , т2 , т4 , т7 , т8 , т10 }; 2) {т6 , т9 }

3) {n6 , n9 , т3 , т5 , k1, k4 }

23

1.2.Отношения и их свойства.

Отношения между элементами множеств имеют основополагающее значение в теории множеств, а также в теории систем. Понятие «отношение» объединяет такие понятия как «соответствие», «отображение», «функция».

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

Определение. Пара элементов (x, y), взятых в определенном порядке,

называется упорядоченной парой.

Определение. Кортеж – это совокупность элементов, в которой каждый элемент занимает определенное место. Например, множество людей, стоящих в очереди, множество слов в предложении, множество букв в слове, и т.п. Длиной кортежа называется число элементов в кортеже. Кортежи обычно обозначают последовательностью в круглых скобках (или в угловых скобках) (а1, а2 ,…, an ).

Декартовым (прямым) произведением множеств А× В называется множество всех упорядоченных пар (всех кортежей), в которых первый элемент принадлежит множеству А, а второй элемент принадлежит множеству В.

Теорема. Мощность произведения двух конечных множеств равна произведению их мощностей: | А× В |=|A|×|В|.

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

Пример 1.15. Пусть А = {1, 2, 3}, В = {3, 4, 5}, U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Тогда А \ В = {1, 2}, B \ A = {4, 5}, A = {0, 4, 5, 6, 7, 8, 9}, B = {0, 1, 2, 6, 7, 8, 9},

A × B = {(1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,3), (3,4), (3,5)}; | А× В |=9.

Произведение трех или более множеств можно определить аналогично, как множество, элементами которого являются соответственно тройки или совокупности из n объектов: А1 ×А2 × А3 = {(а1, а2 , а3 )а1 А1 , а2 А2 , а3 А3},

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

Пусть S = {s1, s2 ,…, sn }. Если A S . То поставим ему в соответствие n-

битную строку (b1,b2 ,…,bn ), где bi =1, если si Î A и bi = 0 в противном случае.

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

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

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

25

отношения: «жить в одном городе», «работать в одной организации», «быть моложе», «быть однокурсниками» и т.п.).

Определение. Бинарным отношением называется любое подмножество прямого произведения множеств ρ А× В, при этом множество А называется

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

Если ρ М × М , то говорят, что отношение ρ определено на множестве

М. Если пара (х, у) входит в ρ , т.е. (х, у) ρ , то пишут хρу , что читается «х

Способы задания бинарных отношений.

1.Характеристическим свойством;

2.Перечислением пар, для которых это отношение выполняется;

пересечении i-й строки и j-го столбца, равен 1, если элемент ai находится

в данном отношении ρ с элементом b j );

4.Графом, где точками (вершинами) задаются элементы множества, ребрами (линиями, соединяющими эти вершины) – отношение между элементами;

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

Пример 1.18. Пусть Х = {1, 2, 3} и У = {1, 2}. Бинарное отношение

ρ Х × У определим следующим образом: ρ = {(1,1),(3,2)}.

26

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

этом случае хρу означает: «элементы х и у находятся в отношении друг к другу,

как координаты одного из концов некоторой дуги».

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

Пример 1.19. На множестве M натуральных чисел от 1 до 5 построим бинарное отношение R={(a,b)|mod(a,b)=0}.

Решение. На множестве натуральных чисел M строим такие пары (a, b), что, а делится на b без остатка (mod(a,b)=0). Получаем R={(1,1), (2,2), (3,3),

(4,4), (5,5), (2,1), (3,1), (4,1), (5,1), (4,2)}.

Граф и матрица данного бинарного отношения:

Пример 1.20. Пусть М = {1, 2, 3, 4,5,6}. Тогда отношение ρ М × М , если

отношение означает «быть строго больше», можно задать:

1.Характеристическим свойством: ρ = {(а,в) а,в М; а > в}.

2.Перечислением ρ = {(2,1),(3,1), (4,1), (5,1), (6,1), (3,2), (4,2), (5,2), (6,2),

(4,3),(5,3),(6,3),(5,4),(6,4),(5,6)}.

Рис. 1.2. Граф отношения

5. График указанного отношения:

Рис.1.3. График отношения

Пример 1.21. Пусть некоторая программа читает два числа из множества М={1,2,3,4,5}, обозначаемых х и у, и, если х< у, печатает число z (также из М) такое, что х≤ z<у. В любом случае программа останавливается после считывания всех чисел на множестве М.

Построим описанное отношение R={((x,y),z): х<у, х≤ z<у} (перечислим его элементы).

R={((1,2),1); ((1,3),1); ((1,3),2); ((1,4),1); ((1,4),2); ((1,4),3); ((1,5),1);

((1,5),2); ((1,5),3); ((1,5),4); ((2,3),2); ((2,4),2); ((2,4),3); ((2,5),2); ((2,5),3);

((2,5),4); ((3,4),3); ((3,5),3); ((3,5),4); ((4,5),4)}. Всего 20 элементов.

Укажем область определения и область значений отношений.

Область определения: D(R)={(1,2), (1,3); (1,4), (1,5); (2,3), (2,4); (2,5),

(3,4); (3,5), (4,5)}. Всего 10 элементов.

29

нерефлексивных бинарных отношений на множестве M={a,b,c,d}.

Примерами нерефлексивных отношений являются: «быть сыном», «нервировать», «быть начальником».

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

1) если первый отрезок параллелен второму отрезку, то и второй отрезок параллелен первому; 2) если первый отрезок перпендикулярен второму, то и второй отрезок перпендикулярен первому; 3) если первый отрезок равен второму отрезку, то и второй отрезок равен первому.

Про отношения параллельности, перпендикулярности и равенства говорят, что они обладают свойством симметричности или, просто, симметричны.

Определение. Бинарное отношение ρ на множестве М называется

симметричным, если из того, что элемент х находится в отношении ρ с

элементом у, следует, что и элемент у находится в отношении ρ с элементом х,

т.е. ρ симметрично на М тогда и только тогда, когда для любых х, у М если

хρ у , то и уρ х.

Примерами симметричных отношений являются равенство (=), неравенство (≠), подобие, одновременность, некоторые отношения родства (например, отношение братства).

В матрице, представляющей симметричное отношение, элементы, симметрично расположенные относительно главной диагонали, равны между собой aij = a ji . В соответствующем графе вместе с каждой стрелкой, идущей из вершины ai в вершину a j , существует и противоположно направленная

стрелка.

Существуют отношения, которые свойством симметричности не обладают. Таким, например, является отношение «длиннее» для отрезков.