09. 02.2012

Множества и операции над множествами.

Основная операция над множествами. Мощность множества.

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

Множества состоящие из некоторых элементовдругого множества, называются подмножеством.

Универсальным называется множество U, состоящее из всех возможных элементов, обладающие данным признаком, например, планеты солнечной системы.

Заметим, что понятие универсального множества четко не определено. Универсальное множество всегда можно включить в другое множество W, которое тоже будет универсальным.

Множество является пустым, если оно не содержит элементов.

Множество, не являющееся пустым, называется непустым.

Равными называются два множества А и В, состоящие из одинаковых элементов (А=В).

Кортежи. Декартово произведение.

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

Пример.

∆АВС задается на плоскости кортежем из 6 чисел: <x₁,y₁;x₂,y₂;x₃,y₃>, где А(x₁,y₁), В(x₂,y₂), С(x₃,y₃) – координаты вершин.

Кортежем длины nиз элементов множества А называется упорядоченная конечная последовательность.

α= <a₁,a₂,…,a_n>, равная элементам этого множества.здесь элемент a_k – kкоордината или k компонент кортежа α.

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

Т.е. кортежи α =<x₁,…,x_m>

β = <y₁,…,y_n>

р авны m = n

x_k = y_k

Примечание.

Кортеж, не содержащий ни одного элемента, называется пустым.

Пусть заданы множества А₁, А₂, …, А_n. Декартовым (прямым) произведениемэтих множеств, называется множество А₁*А₂*…*А_n, состоящее из всех кортежей, вида <a₁,a₂,…,a_n> длины k, в которых a_kϵA_k, 1≤k≤n.

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

Отношения фундаментальных основ баз данных. Бинарные отношения и их свойства.

Соответствие между равными множествами называется отношением на данноммн-ве А.

Пусть А и В конечные множества, вспоминаем, что декартово произведение множества А и В состоит из всех упорядоченных пар а и b, где А принадлежит а ϵ А.

Бинарным отношением между элементами множества А и В называется подмножествоRс А*В.

Пример.

а и в находятся в отношении R

а≤в

Отношение эквивалентности.

Бинарное отношение Rназывается отношением эквивалентности, если оно одновременно обладает тремя свойствами: рефлективностью, симметричностью и транзитивностью.

Обозначим а Qbили a ~b

« а эквивалентно в в отношении R»

Не пересекающиеподмножества на которых разбивается множество М называется классами эквивалентности.

Отношение порядка.

Отношение Rназывается отношением порядка на множестве М, если оно обладает свойствами антисимметричности и транзитивности.

Отношение Rназывается множеством А²называется отношением порядка, если оно обладает рефлективностью, антисимметричностью и транзитивностью.

Антисимметричное транзитивное отношение называется отношением порядка.

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

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

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

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

Как правило отношение строгого порядка обозначается <, а отношение частичного порядка ≤.

В общем случае отношение порядка обозначается

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

Заметим, что для любых х,у =>x≤yт.е. любые два числа сравнимы между собой. Такие отношения называется полного порядка.

Предикат данного отношения есть x≤y

Пример.

Рассмотрим на множестве А сотрудников какого-либо учреждения. Отношения создадим следующим образом:

«сотрудник х предшествует сотруднику у» тогда и только тогда, когда выполняется одно из условий:

1. х = у

2. х – начальник у (н\о непосредственные)

Назовем такое отношение «быть начальников». Легко проверить, что данное отношение является отношением порядка.

В отличии от предыдущих примеров существуют такие пары сотрудников х и у для которых не выполняется х < у, ни х≤у (например, если х и у являются сослуживцами) это отношение частичного порядка.

Функциональные отношения.

Отношение Rнад А₁*А₂ называется функцией, если оно обладает следующими свойствами:

1. Если (х,у) ϵ Rи (х,у) ϵ R, то у = z(однозначность функций)

2. Остальные свойства аналогичны свойствам отношения порядка.

n-арные отношения (отношения степени n)

В математики n-арные рассматривают относительность редко, в отличии от БД, гденаиболее возможные являются равномерные, заданной на декартовом произведении более, чем 2х множеств.

Пример

В каком-либо университете учатся студенты Иванов, Петров и Сидоров, лекции им читает Иваненко, Петренко, Сидоренко. Известно: Иваненко читает лекции по ЛА и БД, соответственно 40 и 80 часов в семестр. Петренко читает лекции по МА 50 часов. Сидоренко читает лекции по МА и ЛА 40 и 50 часов. Студент Иванов посещает лекции по ЛА у Сидоренко и по БД у Иваненко, студент Петров ЛА-Иваненко, МА – Петренко, студент Сидоров МА – Петренко, БД – Иваненко.

Чтобы формально описать данную ситуацию( если предположим необходимо разобрать ИС, фиксир. ход учебного процесса), введем три множества.

1. Множество преподавателей А{Иваненко, Петренко, Сидоренко}

2. Множество предметов В{ЛА, МА, БД}

3. Множество студентов С{Иванов, Петров, Сидоров}

Имеющиеся факты можно разделить на 2 группы:

1. факты 1-3

2. факты 4-6

Чтобы отобразить факты 1-2 введем отношение R, на декартовом произведении

R₁с А*В*Q, где Q – множество рациональных чисел.

А именно упорядоченная тройка ([x,y,z) ϵR₁ преподаватель х читает предмет у в количество nчасов.

Назовет R₁– «читает лекции по R₁удобно представить в виде таблицы.

А (преподаватель)	В (предмет)	Q
Иваненко	ЛА	40
Иваненко	БД	80
Сидоренко	МА	50
Сидоренко	ЛА	40
Петренко	МА	50

Чтобы отобразить факты 4-6, введем R₂

R₂ с С*В*А

_{(z,y,x) ϵR2}

C (студент)	В (предмет)	А (преподаватель)

Рассмотрим R₂более подробно, оно задано на декартовом произведении

Ω = С*В*А

3*3*3 = 27 картежей

«Студенты, лекции, преподаватели»

Множество Ω - совокупность всех возможных вариантов посещений студентами лекций.

Отношение R₂отображает текущее состояние учебного процесса.

Очевидно, что R₂является изменяющимися со временем отношениями.

Итак, факты о ходе учебного процесса удалось отобразить в виде двух отношений степени 3 (3-арных), а сами отношения отобразить в виде двух таблиц с 3 столбцами.