Лекция 2. МНОЖЕСТВА И ОТНОШЕНИЯ

1 Лекция 2. МНОЖЕСТВА И ОТНОШЕНИЯ Цель лекции: изучить основы теории множеств, необходимые для введения фундаментального понятия "отношение", на котором строится дальнейшее изучение реляционной модели данных. Показать связь между понятиями "отношение" и "таблица". План лекции: 1 Основные понятия теории множеств 2 Операции над множествами 3 Декартово произведение множеств 4 Отношения 1 Основные понятия теории множеств Понятие "множество" является первичным и неопределяемым. Множество можно представить себе как совокупность элементов, обладающих некоторым общим свойством. Объекты любой природы (числа, люди, вещи и т. д.), составляющие множество, называют его элементами. Например, студент Иванов является элементом множества студентов IV курса, март элементом множества месяцев в году и т.д. Для того чтобы некоторую совокупность элементов можно было назвать множеством, необходимо, чтобы выполнялись следующие условия: - должно существовать правило, позволяющее определить, принадлежит ли указанный элемент данной совокупности; - должно существовать правило, позволяющее отличать элементы друг от друга (это означает, что множество не может содержать двух одинаковых элементов). Тот факт, что элемент a принадлежит множеству А записывается так: a, в противном случае пишем a. Для однозначного описания некоторого множества мы будем пользоваться следующими способами: перечислением всех его элементов. Например, множество, состоящее из объектов: a, b, c, d записывают так: = . Данный способ применим только для конечных множеств, число элементов которых невелико; указанием общего свойства элементов, принадлежащих множеству. В этом случае в фигурных скобках записывают обозначение произвольного элемента множества, ставят вертикальную черту, а затем свойство, характеризующее в точности все элементы множества. Например, множество K натуральных чисел, меньших 5 можно записать: K= или K=. Множества могут быть конечными или бесконечными. Например, множество работников предприятия конечно, а множество точек прямой бесконечно. Пустым множеством называют единственное множество, не содержащее ни одного элемента (обозначается символом ). Например, это множество транзисторов, изготовленных в 1930 году. 1

2 Множества и B считают равными, если они состоят из одних и тех же элементов (записывают = B). Например, равны следующие множества: А=. На кругах Эйлера объединение множеств А и В изображается в виде заштрихованной области. Например, пусть заданы три множества: А = , В = , C = . Тогда А В = , А С = . Определение 2. Пересечением двух множеств называется новое множество, состоящее из элементов, принадлежащих одновременно обеим множествам (обозначается: А В), т.е. А В = . Например, для заданных множеств А, B и С: А В = , В С = , А С =. 2

3 На кругах Эйлера пересечение множеств А и В изображается в виде заштрихованной области. Свойства операций объединения и пересечения. а) Коммутативность: для любых множеств и B верны равенства: А В=В А; А В=В А. б) Ассоциативность: для любых множеств А, В, С верны равенства: (А В) С= (В С); ( B) С= (В С). в) Дистрибутивность: для любых множеств А, B и С справедливы равенства: (B C)=( B) ( C); (B C)=( B) ( C). В частности, для любого множества имеем: =, =; =, = ; U=U, U=. Определение 3. Разностью двух множеств А и B называется новое множество, элементы которого принадлежат, но не принадлежат B (обозначают: А \ В), т.е. А \ В = . На кругах Эйлера разность множеств А и В изображается в виде заштрихованной области. Например, для заданных множеств А, B и С: А \ В = , В \ С = , А \ С = =. 3

4 Вопрос: каким операциям соответствует следующая диаграмма? Ответ: (А \ B) (B \ ), операция называется симметричной разностью множеств. Причем (А \ B) (B \ ) = (А B) \ (B ). Доказательство этого соотношения, как и любых других утверждений о равенстве множеств, состоит в том, чтобы предположив принадлежность некоторого элемента х множеству из левой части равенства, необходимо доказать, что этот же самый элемент принадлежит множеству, стоящему в правой части равенства и наоборот. Задание: доказать равенство (А \ B) (B \ ) = (А B) \ (B ). Определение 4. Если А подмножество множества U, то дополнением множества А до множества U есть множество, состоящее из тех и только тех элементов U, которые не принадлежат А, т.е. = U \ = . На кругах Эйлера дополнение изображается в виде заштрихованной области. Свойства операции дополнения: для любых подмножеств А и B универсального множества U имеют место следующие равенства: B B, B B; U, ;. Задача. За время отпуска 12 дней шел дождь, 8 дней дул сильный ветер, а 4 дня было холодно. Сколько дней была плохая погода, если: - дождливых и ветреных дней было 5; - дождливых и холодных 3 дня; - ветреных и холодных 2 дня; - дождливых, ветреных и холодных 1 день. 4

5 Ответ: 15 дней. Задача сводится к нахождению числа элементов в объединении нескольких множеств, зная число элементов в каждом из них, а также число элементов в каждом пересечении этих множеств. Определение 5. Количество элементов конечного множества называется его мощностью. Мощность множества А обозначается как. Мощность объединения трех множеств А, В и С равна: B C = + B + C - B - C - B C + B C. Вопрос: почему перед значением мощности пересечения трех множеств B C стоит знак "+"? 3 Декартово произведение множеств Пусть А и В множества. Выражение вида (а, b), где a и b B, называется упорядоченной парой. Равенство вида (a, b) = (c, d) означает, что a = c и b = d. В общем случае, можно рассматривать упорядоченную n-ку (a 1, a 2,, a n ) из элементов a 1 1, a 2 2,, a n n. Упорядоченные n-ки иначе называют наборами или кортежами. Определение 6. Декартовым (прямым) произведением множеств 1, 2,, n называется множество упорядоченных n-ок (наборов, кортежей) вида 1 2 n = . Определение 7. Степенью декартового произведения 1 2 n называется число множеств n, входящих в это декартово произведение. Если все множества 1, 2,, n одинаковы, то используют обозначение n =. Примеры декартовых произведений. а) Если А = , а В = , то В = множество, содержащее обозначения всех 64 клеток шахматной доски. б) Пусть А конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания и т.д.). Такие множества называются алфавитами, а элементы множества n называются словами длины n в алфавите А. 5

6 Например, множество 2 = содержит все возможные двухэлементные сочетания символов (слова из 2-х символов). Множество всех слов в алфавите А это множество i i N Теорема. Мощность декартового произведения 1 2 n равна произведению мощностей множеств 1, 2,, n : Следствие: n = n. 1 2 n = 1 2 n. 4 Отношения Пусть дано декартово произведение множеств 1 2 n. Определение 8. Подмножество R декартового произведения множеств 1 2 n называется отношением степени n (n-арным отношением) на множествах 1, 2,, n. Говорят, что элементы a 1, a 2. a n находятся в отношении R, если (a 1, a 2. a n ) R. Наиболее изучены и часто используются в математике бинарные отношения. Для них, наряду с записью (a 1, a 2 ) R, пишут также a 1 R a 2. Например, отношение выполняется для пар (7, 9) и (7, 7), но не выполняется для пары (9, 7). Отношение "иметь общий делитель, отличный от единицы" выполняется для пар (6, 9), (2, 4), (4, 4), но не выполняется для пар (7, 9) и (7, 7). Задание: для каких пар выполняются отношения "родиться в одном городе", "быть моложе", заданные на множестве S 2, где S множество студентов Вашей группы? Определение 9. Степень отношения это количество элементов в каждом кортеже отношения. Определение 10. Мощность отношения это количество кортежей отношения. Понятие отношения является очень важным не только с математической точки зрения. Понятие отношения фактически лежит в основе всей реляционной теории баз данных. Как будет показано ниже, отношения являются математическим аналогом таблиц. Сам термин "реляционное представление данных", впервые введенный Эдгаром Коддом в начале 1970-х, происходит от термина relation, понимаемом именно в смысле этого определения. Т.к. любое множество можно рассматривать как декартовое произведение степени 1, то любое подмножество можно считать отношением степени 1. Это не очень интересный пример, свидетельствующий лишь о том, что термины "отношение степени 1" и "подмножество" являются синонимами. Нетривиальность понятия отношения проявляется, когда степень отношения больше 1. Ключевыми здесь являются два момента: Во-первых, все элементы отношения есть однотипные кортежи. Однотипность кортежей позволяет считать их аналогами строк в простой таблице, т.е. в такой таблице, в которой все строки состоят из одинакового числа ячеек и в соответствующих ячейках содержатся одинаковые типы данных. Например, отношение, состоящее из трех следующих кортежей можно считать таблицей, 6

7 содержащей данные о студентах и их оценках за экзамен. Такая таблица будет иметь три строки и три колонки, причем в каждой колонке содержатся данные одного типа. Степень отношения является аналогом количества столбцов в таблице, мощность отношения аналогом количества строк в таблице. Во-вторых. За исключением крайнего случая, когда отношение есть само декартово произведение, отношение включает в себя не все возможные кортежи из декартового произведения. Это значит, что для каждого отношения имеется критерий, позволяющий определить, какие кортежи входят в отношение, а какие - нет. Этот критерий, по существу, определяет для нас смысл (семантику) отношения. Действительно, каждому отношению можно поставить в соответствие некоторое логическое выражение P(x 1, x 2,, x n ), зависящее от n параметров (n-местный предикат) и определяющее, будет ли кортеж (x 1, x 2,, x n ) принадлежать отношению R. Это логическое выражение называют предикатом отношения R. Более точно, кортеж (x 1, x 2,, x n ) принадлежит отношению R тогда и только тогда, когда предикат этого отношения P(x 1, x 2,, x n ) принимает значение "истина". В математике чаще всего используют бинарные отношения (отношения степени 2). В теории баз данных основными являются отношения степени n. В математике, как правило, отношения заданы на бесконечных множествах и имеют бесконечную мощность. В базах данных напротив, мощности отношений конечны (число хранимых строк в таблицах всегда конечно). На следующем занятии мы рассмотрим свойства отношений и некоторые примеры отношений как бинарных, так и n-арных. 7