Курсовая работа: Элементы теории множеств

Дополнение ко множеству А (синее выделение):

Рис. 5

Симметрическая разность множеств А∆B (зеленое выделение):

Рис. 6

2.4. Прямое произведение множеств

Одним из способов конструирования новых объектов из уже имеющихся множеств является декартово (прямое) произведение множеств.

Пусть A и B - множества. Выражение вида (a, b) , где aA и bB, называется упорядоченной парой. Элемент а называют первой координатой (компонентой) пары, элемент b - второй координатой (компонентой) пары.

Равенство вида (a, b)=(c, d) означает, что a=c и b=d. В общем случае, можно рассматривать упорядоченную n-ку (a1, a2, a3, … ,an) из элементов a1A1, a2A2 … anAn. Упорядоченные n-ки иначе называют наборами или кортежами.

Определение прямого произведения множеств. Декартовым (прямым) произведением множеств A1, A2,… An называется множество упорядоченных наборов (кортежей) вида A1A2…An={( a1, a2,… an | aiAi}.

Из вышеприведенного определения следует, что для любых a1a2 справедливо (a1,a2) (a1,a2).

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

Определение степени прямого произведения. Степенью декартового произведения A1A2…An называется число множеств n, входящих в это декартово произведение.

Замечание. Если все множества Ai одинаковы, то используют обозначение

An=AA…A.

Выясним, какими свойствами обладает операция нахождения декартова произведения множеств. Так как декартовы произведения (a1, a2) (a2, a1), a1a2 состоят из различных элементов, то декартово умножение множеств свойством коммутативности не обладает.

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

(A U B)  C = ( A  C ) U ( B  C );

(A \ B) C = ( A C ) \ ( B  C ).

2.5. Отношения на множестве

Определение отношения степени n. Подмножество R декартового произведения множеств A1 A2… An называется отношением степени n (n-арным отношением).

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

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

Т.к. любое множество можно рассматривать как декартовое произведение степени 1, то любое подмножество, как и любое множество, можно считать отношением степени 1. Это не очень интересный пример, свидетельствующий лишь о том, что термины “отношение степени 1” и “подмножество” являются синонимами. Нетривиальность понятия отношения проявляется, когда степень отношения больше 1. Ключевыми здесь являются два момента:

Во-первых, все элементы отношения есть однотипные кортежи. Если же множество состоит из разнотипных числовых кортежей, то это множество не является отношением ни в R1, ни в R2, ни в Rn.

Во-вторых. За исключением крайнего случая, когда отношение есть само декартово произведение A1A2…An, отношение включает в себя не все возможные кортежи из декартового произведения. Это значит, что для каждого отношения имеется критерий, позволяющий определить, какие кортежи входят в отношение, а какие - нет. Этот критерий, по существу, определяет для нас смысл (семантику) отношения.

Действительно, каждому отношению можно поставить в соответствие некоторое логическое выражение P(x1 ,x2, … , xn), зависящее от n параметров и определяющее, будет ли кортеж (a1, a2, … ,an) принадлежать отношению R. Это логическое выражение называют предикатом отношения R. Более точно, кортеж (a1, a2, … ,an) принадлежит отношению R тогда и только тогда, когда предикат этого отношения P(a1, a2, … ,an) принимает значение “истина”. Таким образом, существует взаимно однозначное соответствие между n-арными отношениями и n-местными предикатами.

Примеры отношений.