Отношения и бинарные отношения, область определения, область значения, обратные отношения. Произведение отношений

Множества. Основные операции над множествами и их свойства. Диаграммы Венна. Декартово произведение множеств.

 

Множество – это совокупность объектов, рассматриваемых как единое целое.

Способы задания множеств:

1) Перечисление элементов: М={0,1,2,…,9}

2) Указание свойств Р(х), которым элементы множества должны удовлетворять: М={x | P(x)}.

Неправильное заданные свойства могут привести к противоречию!

Парадокс Рассела:

Рассмотрим множество всех множеств, которые не являются своими собственными элементами: . Является ли тогда множество К своим элементом. Если КєК, то должно выполняться свойство, задающее множество К, т.е. К¢К, что приводит к противоречию. Если же К¢К, то, поскольку выполняется свойство, задающее К, то КєК, а это противоречит предположению. Таким образом, не всякое свойство приводит к осмысленному заданию множества.

Множество А называется подмножеством множества В, если все элементы А принадлежат В, т.е.

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

Совокупность всех подмножеств множества А называется его булеаном или множеством-степенью и обозначается Р(А), т.е. . Если |U|=n (множество U содержит n элементов), то |P(U)|=2n.

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

Множество, содержащее все элементы, находящиеся в рассмотрении, называется универсальным или универсумом U.

Операции над множествами:

1) объединение

2) пересечение

3) вычитание

4) кольцевая сумма (симметрическая разность)

5) дополнение

Свойства основных операций над множествами:

1) Ассоциативность:

2) Коммутативность:

3) Идемпотентность:

4) Дистрибутивность:

5) Поглощение:

6) Законы де Моргана:

7) Законы нуля и единицы: 0=ø, 1=U

8) Закон двойного отрицания:

Упорядоченную последовательность (х1, х2,…,хn) называют кортежем длины n.

 

Декартовым (прямым) произведением множеств А1, А2,…, Аn называется множество {(x1, x2,…, xn) | x1 є A1,…, xn є An}.

Если А1=А2=…=Аn, то – n-ная декартова степень множества А.

А0 = ø

 

Отношения и бинарные отношения, область определения, область значения, обратные отношения. Произведение отношений.

n-местным отношением или n-местным предикатом Р на множествах А1, А2,…, Аn называется любое подмножество прямого произведения . Другими словами, элементы х1, х2,…, хn (где хi є Ai) связаны соотношением Р тогда и только тогда, когда (х1, х2,…, хn) є Р. При n=1 отношение Р является подмножеством множества А1 и называется унарным отношением или свойством.

При n=2 отношение Р называется бинарным отношением или соответствием.

Пример: Если А={2,3,4,5,6,7,8}, то бинарное отношение Р={(x,y) | x,y є A, x делит y и х≤3} можно записать в виде Р = {(2,2),(2,4),(2,6),(2,8),(3,3),(3,6)}.

Если Р={(x, y) | x, y є R, x≤y}, то запись xPy означает, что x≤y. idA = {(x,x) | x є A} – тождественное отношение, idA принадлежит А2.

U = A2 – универсальное отношение. Пусть Р – некоторое бинарное отношение. Областью определения отношения Р называется множество δР = {x | (x,y) є P для некоторого у}. Областью значений отношения Р называют множество ρР = {y | (x,y) є P для некторого х}. Обратным отношением называется множество Р-1 = {(y,x) | (x,y) є P}.

Образом множества Х относительно предиката Р называется множество Р(Х)={y | (x,y) є P для некоторого х є Х}

Прообразом множества относительно предиката Р называется множество Р-1(Х) или, другими словами, образ множества Х относительно предиката Р-1.

Произведением бинарных отношений и или композицией Р1 и Р2 называется множество Р1•Р2 = {(x,y) | x є A, y є C, и найдется элемент z є B такой, что (x,z) є Р1 и (z,y) є P2}.

Свойства:

1) Ассоциативность композиции: (P•Q)•R=P•(Q•R)

Доказательство: Пусть (x,y) є (P•Q)•R. Тогда для некоторых u и v имеем (x,u) є P, (u,v) є Q, (v,y) є R. Тогда (u,y) є Q•R и (x,y) є P•(Q•R). Включение P•(Q•R) є (P•Q)•R доказывается аналогично.

2) (P•Q)-1=Q-1•P-1

Доказательство: Предположим, что (x,y) є (P•Q)-1. Тогда (y,x) є P•Q, и, следовательно, (y,z) є P и (z,x) є Q для некоторого элемента z. Значит (x,z) є Q-1, (z,y) є P-1 и тогда (x,y) є Q-1•P-1. Обратное включение доказывается аналогично.

3) P•Q ≠ Q•P

4) (P-1)-1=P

Доказательство: Если (x,y) є P, то (y,x) є Р-1, но тогда (x,y) є (Р-1)-1.