2. Соответствия Соответствие между множествами А и В определяется заданным правилом, согласно которому элементам одного множества сопоставляются элементы другого множества. Соответствием между множествами А и В называется множество - подмножество их прямого произведения: A x B и : A B Про элементы x A и y B говорят, что они находятся в соответствии, если пара (x,y). : x y, x A, y B. Если ( x, y), то иногда пишут x y, y называют образом x, а x - прообразом y.

Пример: Пусть дано множество студентов: A = {Jüri, Mari, Jaan, Juhan, Kati, Mati} и множество возможных оценок: B = { 1, 2, 3, 4, 5} : A B соответствие между множествами А и В, которое сопоставляет каждому студенту его оценку. Диаграмма (граф) соответствия: Jüri Mari Jaan Juhan Kati Mati A B = { (Jüri, 4), (Mari, 5), (Jaan, 1), (Juhan, 3), (Kati, 4), (Mati, 5)}

Пусть даны множества А и В А = { 2, 3, 8 } В = { 1, 2, 3, 4, 5, 6, 7 }. Соответствием между множествами А и В «число из А есть делитель числа из В» представляется множеством = {(2, 2), (2, 4), (2, 6), (3, 3), (3, 6)}, Пример: AB

Пусть A x B и : A B, тогда A называют областью отправления соответствия, В называют областью прибытия соответствия. Область определения соответствия (domain): Область значений соответствия (range): D( ) = { a A | b B: (a,b) } A R( ) = { b B | a A: (a,b) } B Пример:Пусть даны множества А и В А = { 2, 3, 8 }, В = { 1, 2, 3, 4, 5, 6, 7 }, = {(2, 2), (2, 4), (2, 6), (3, 3), (3, 6)} Тогда D( ) = {2, 3} A иR( ) = {2, 3, 4, 6} B

_ = { (a,b) A B | (a,b) } Операции с соответствиями: Дополнение соответствия: | | = |AxB| - | | Свойство: Обратное к соответствие: | 1 | = | | 1 = { (b,a) | (a,b) } B A Свойство:

Объединение соответствий: 1 2 = { (a,b) | (a,b) 1 (a,b) 2 } Пересечение соответствий: 1 2 = { (a,b) | (a,b) 1 & (a,b) 2 } 1 2 = { (a,c) | b B: (a,b) 1 & (b,c) 2 } A C, где 1 A B и 2 B C. Композиция соответствий:

Пример: A = { 1, 2, 3, 4 }, B = { a, b, c }, C = { u, v, w, x, y }, а также соответствия A × B и B × C = { ( 1, b ), ( 1, c ), ( 2, a ), ( 4, c ) }, = { ( a, u ), ( a, x ), ( b, w ), ( c, y ) }, тогда композиция соответствий и : ={ ( 1, w ), ( 1, y ), ( 2, u ), ( 2, x ),( 4, y ) } пусть даны множества a b c AB u v w x y C

Классификация соответствий: Соответствие A B всюду определенное, если D( ) = A. Соответствие A B на всю область значений определенное, если R( ) = B. AB AB

-1 ° = { (b,b) | b B } Соответствие A B однозначное, если a D( ) ! b R( ) : (a,b) Свойство: если соответствие A B – однозначное, то AB

° -1 = { (a,a) | a A } Однозначное соответствие A B взаимно однозначное, если b R( ) ! a D( ) : (a,b) AB Свойство: если соответствие A B – взаимно однозначное, то

Функция - всюду определенное и однозначное соответствие. AB Частично определенная функция – не всюду определенное однозначное соответствие. AB

Сюръекция - всюду и на всю область значений определенное однозначное соответствие. Инъекция - всюду определенное взаимно однозначное соответствие. AB A B AB A B

Биекция - всюду и на всю область значений определенное взаимно однозначное соответствие. AB A = B

Задача 1. Пусть даны множества A = {2,4,6,8}, B = {1,3,5,7}, C = {a,b,c,d} и соответствия = {(2,3), (2,7), (4,1),(4,3),(8,3)} A B, = {(1,c), (3,b), (7,d)} B C. Представить соответствия графически. Найти a)D( ), D( ), b) R( ), R( ), c),, d) -1, -1, e), f)( ) -1, Классифицировать соответствия.

Задача 2. Пусть даны множества A = {2,4,6,8}, B = {3,5,7}, C = {6,9,12,15} и соответствия = { (a,b) a b } A B, = {(b,c) c = 3b } B C. Представить соответствия графически. Найти a)D( ), D( ), b)R( ), R( ), c), d) -1, -1 e). Классифицировать соответствия.

3. Бинарные отношения Бинарные отношения можно рассматривать как частный случай соответствия, когда область прибытия совпадает с областью отправления: D( ) = R( ) = A. Обозначаем: R A A или R A 2. Множество A называется основанием отношения R.

Формы задания отношений: 1 форма: задание множества пар элементов, находящихся в отношении R R = { ( a, b ), ( b, a ), ( b, с ), ( с, е ), ( d, d ), ( е, с ) } 2 форма: задание посредством матрицы смежности

3 форма: при помощи графа отношения - т.е. графа, вершинами которого являются элементы множества A, а ребра обозначают связь между элементами. Пример: Пусть дано множество A = {2,3,4,5,6} и бинарное отношение R = {(2,2), (3,3), (4,2), (4,4), (5,5), (6,2),(6,3),(6,6)} A A

Т.к. бинарные отношения являются частным случаем соответствия, то для них определены все операции, выполняемые с соответствиями: дополнение, обратное отношение, композиция. Свойства бинарных отношений: Рефлексивность R - рефлексивно a A пара (a,a) R. Антирефлексивность R - антирефлексивно a A пара (a,a) R. Отношение, которое не является ни рефлексивным ни антирефлексивным называется нерефлексивным.

Симметрия R - симметрично a, b A если (a,b) R (b, a) R, где a b. Антисимметрия R - антисимметрично a, b A если (a,b) R (b, a) R, где a b. Отношение, которое не является ни симметричным ни антисимметричным называется несимметричным. Для симметричных отношений: R = R -1

Антитранзитивность R – антитранзитивно a, b, c A если (a,b) R & (b,c) R (a, c) R, где a b c. Отношение, которое не является ни транзитивным ни антитранзитивным называется нетранзитивным. Транзитивность R – транзитивно a, b, c A если (a,b) R & (b,c) R (a, c) R, где a b c. Для транзитивных отношений: R R R

Расстояние от отношения R до свойства d(R,i ) - расстояние от отношения R до свойства i = минимальное число пар, которое надо добавить или удалить из отношения R, чтобы отношение R приобрело свойство i. Пример: Пусть на множестве A = { a,b,c,d } определено бинарные отношение R = {( a, a), (a, b), (a, c), (b, d), (c, c), (c, d), (d, b), (d, c), (d, d)} A A. Найти расстояние от отношения R до каждого свойств.

Транзитивным замыканием отношения R называют минимальное транзитивное отношение, содержащее отношение R. Транзитивное замыкание отношения R где E = { (a, a) | a A }. Если R транзитивно, то Пример: Пусть на множестве A = { 1,2,3,4,5 } определено бинарные отношение R = {( 1, 3), (1, 4), (3, 4), (4, 5), (5, 2), (5, 3)} A A. Найти транзитивное замыкание отношения R.

Отношение эквивалентности Бинарное отношение R называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Классом эквивалентности элемента a A относительно отношения эквивалентности R называют множество K(a) = { b | (a,b) R } Отношение эквивалентности генерирует разбиение P на множестве A. Разбиение P состоит из всех классов эквивалентности K i, i=1,...,n. P = { K 1, K 2,..., K n }, i = 1,...,n, где K i K j =, i, j = 1,...,n, i j; K 1 K 2... K n = A.

Пусть на множестве A = { 1,2,3,4,5,6,7,8 } определено бинарное отношение R: Показать, что отношение R является отношением эквивалентности. Найти разбиение P. Пример:

Отношение порядка Бинарное отношение R называется отношением нестрогого порядка, R,, если оно рефлексивно, антисимметрично и транзитивно. Бинарное отношение R называется отношением строгого порядка, R,

Определить свойства отношения R, его дополнения и обратного отношения (рефлексивность, симметричность, транзитивность, антирефлексивность, антисимметричность, антитранзитивность). Если свойство отсутствует найти расстояние до этого свойства. Задача 1. Пусть на множестве A = { 1,2,3,4,5 } определено бинарное отношение R:

R = {(1,2), (1,3), (1,4), (2,2), (3,5), (4,3),(4,4),(5,3)} A A. Пусть на множестве A = { 1,2,3,4,5 } определено бинарное отношение R: Задача 2. Найти транзитивное замыкание отношения R. Ддобавить минимальное число пар, чтобы отношение R стало отношением эквивалентности. Найти разбиение P.