Обратное отношение дискретная математика

Обратное отношение дискретная математика

При помощи отношений в математике отображают некоторые связи между элементами множеств. Простейшими примерами отношений, уже рассмотренных раньше, являются отношения принадлежности х е X элемента х множеству X и отношения включения А с В, А с В подмножества А в подмножество В.

По количеству элементов, между которыми определены связи, отношения делятся на унарные (одноместные), бинарные (двухместные), тернарные (трехместные) и /7-арные (/7-местные). В унарном отношении участвует один элемент. Эти отношения называются свойствами и отождествляются с подмножеством элементов, которые этим свойством обладают. Так, например, в множестве всех положительных чисел отношение или свойство «быть четным» отождествляется с подмножеством чисел 2, 4, 6, .

В бинарных отношениях участвуют пары элементов множеств, так называемые упорядоченные пары , > х,, х2. е X, у,, у2. е ?. Упорядоченность понимается как то, что в записи на первом месте всегда стоит х е X, а на втором у е ?. Иными словами, х предшествует у.

Определение 15.1. Прямым (декартовым) произведением множеств А и В, обозначаемым Ах В, называется множество упорядоченных пар, такое, что первая координата каждой пары — элемент А, а вторая координата — элемент В, т.е. Ах В = — < аеАиЬе В>. Например, А — <1, 2>, В = <а, Ь, с).

Тогда А х В — < , , , , , >. Декартово произведение В х А — < , , , , , >. Декартово произведение А х А — < , , , >называется декартовым квадратом множества А.

Если множество А включает т различных элементов, а множество В — п элементов, то произведения множеств Ах В и В х А имеет тхп элементов. Пусть А- <1>, а В = <1,2,3>. Тогда Ах В -< , , >. Если А -0, а В — <1,2,3>. Тогда Ах В = В х А = 0.

В целях наглядного представления декартовых произведений удобно использовать язык геометрии. Для этого множества X, ? представляются осями координат. Элементы х е X, у е ? — соответственно абсциссами и ординатами. Само произведение X х ? — точками плоскости Х0?. В качестве примера на рис. 1.4 показано декартово произведение множеств X = <1, 2, 3>, ? = <1, 2>.

Рис. 1.4. Декартово произве дение множеств X, У

По аналогии с декартовым произведением двух множеств X, ? можно построить декартово произведение X х ? х Z трех множеств X, ?, Zи вообще декартово произведение X, хХ2 х . хХп п множеств X!, Х2, Xп.

Определение 16.1. Декартовым произведением 1х>"х2 трех множеств X,

?, Z называется множество всех упорядоченных троек > , составленных из элементов этих множеств так, что X х? х! = < , х е X, у е ?, г е Z>. Декартовым произведением Х хХ2 х, . хХп п множеств Хх, Х2,

Определение 17.1. Любое непустое подмножество R декартова произведения X х У множеств X, Yназывается бинарным отношением между X и У.

Записывается это так: R с X хУ, или так: xRy, или так: ? R. Слово «бинарный» происходит от английского binary, что в переводе означает «двойной».

Любое непустое подмножество X х X является бинарным отношением на X. В частности, множество X х X называется универсальным отношением на X.

Определение 18.1. Любое непустое подмножество Г декартова произведения X хУ х Z множеств X, У, Z называется тернарным отношением между X, У и Z и записывается так: Т с X хУ х Z.

Определение 19.1. Любое непустое подмножество Nдекартова произведения Хх х Х2 х, . хХп множеств Хх, X2, . Xп называется /z-арным отношением между Хх, Х2, . Х3 и записывается

Бинарное отношение R с X хУ может отражать разный смысл. Например, значениями множества X можно закодировать названия книжных издательств, а элементами множества У — всех фирм некоторого региона, которые занимаются продажей этих книг. Тогда отношению R с X хУ можно придать смысл множества заключенных договоров между издательствами и торгующими фирмами. Пусть ЛГ = <1,2, 3>, У — <1, 2>рассматриваются как три издательства и два магазина, продающие книги. Тогда отношение R — < , , >означает, что издательство 1 заключило договор с магазином 1, издательство 2 — с магазином 2, издательство 3 — с этим же магазином 2.

Примерами трехместных отношений Т с X хУ х Z могут быть такие: 1) из х видов сырья у предприятий выпускают z видов продукции; 2) х покупателей покупают у товаров по г ценам; 3) по х бомбардировщикам у ракетно-зенитных комплексов дали залп z ракетами. Аналогичным образом может придаваться смысл и /7-местным отношениям А с А, хХ2 х . х Xп.

Читайте также:  Командная строка вывод дисков

Рассмотрим свойства бинарных отношений.

Определение 20.1. Отношение Я на множестве Сможет быть:

  • 1) рефлексивным;
  • 2) антирефлексивным;
  • 3) симметричным;
  • 4) асимметричным;
  • 5) антисимметричным;
  • 6) транзитивным.

Определение 21.1. Отношение Я на множестве X является рефлексивным, если оно выполняется между самим элементом, т.е. хЯх. Например, в отношениях «х имеет общий признак с у», «х похож на у» имеет место хЯх, так как элемент х похож на самого себя.

Определение 22.1. Отношение Я на множестве X является антирефлексивным, если хЯх не выполняется ни для одного х е X. Например, в отношениях «брат х старше брата у», «операция х выполняется раньше операции у», хЯх не выполняется, так как брат х не может быть старше себя, а операция х начаться раньше самой себя.

Определение 23.1. Отношение Я на множестве ^является симметричным, если для всех х, у е X из хЯу следует уЯх. Например,

в отношениях «х похож на у», «операция х несовместима с операцией у» имеет место как хЯу, так и уЯх. Действительно, если х похож на у, то у похож на х, если операция х несовместима с у, то операция у несовместима с х.

Определение 24.1. Отношение Я на множестве X является асимметричным, если из двух соотношений хЯу, уЯх одно не выполнено для всех х, у е X. Например, в отношениях «х подчиняется у», «операция х выполнена раньше операции у» имеет место хЯу, но не выполняется уЯх.

Определение 25.1. Отношение Я на множестве ^является ан-тисиммитричным, если соотношения хЯу и уЯх выполняются тогда и только тогда, когда х — у для всех х, у е X. Например, в отношении «операция х является частью операции у» имеет место хЯу и уЯх только тогда, когда х — у.

Определение 26.1. Отношение Я на множестве X является транзитивным, если для всех х, у, г. е X из соотношений хЯу, уЯ1

следует хЯг. Например, в отношении «операция х предшествует операции у, а операция у предшествует операции г» из хЯу и уЯ1 следует хЯ1.

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

По смыслу отношение эквивалентности определяется как «элементы х и у одинаковы», «элементы х и у взаимозаменяемы».

Определение 27.1. Отношение Я на множестве X называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Действительно, в этом отношении каждый элемент эквивалентен самому себе (рефлексивность). Если элемент х эквивалентен элементу у, то и элемент у эквивалентен элементу х (симметричность). Если элемент х эквивалентен элементу у, а элемент у эквивалентен элементу г, то элемент х эквивалентен элементу г. (транзитивность).

Типичным примером отношения эквивалентности является отношение равенства (=) на множестве чисел. Очевидно, что любое число а из множества действительных чисел равно самому себе. Если а — Ь, то Ь = а. Если а = Ь, а Ь = с, то а = с.

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

Это отношение разбивает любое множество на непересекаю-щиеся подмножества (классы эквивалентности). В данном случае все жители города разбиваются на жителей, живущих в одних и тех же домах. В результате получим столько классов эквивалентности, сколько домов, в которых проживают люди. Таким образом, если /’-й класс / е /, а М — множество жителей, то и/е/ М-, = М, М, П М> =0 для всех /, у е /, где / — множество классов.

Определение 28.1. Отношение Я на множестве ^называется отношением толерантности, если оно рефлексивно и симметрично.

Например, отношение «игрок х играет сам с собой в шахматы и с другом у» есть отношение толерантности, так как хЯх, а хЯу влечет уЯх.

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

Отношения на множестве чисел ^являются отношениями нестрогого порядка, так как любое число х е X равно самому себе (рефлексивность).

Для любой пары чисел х, у е X при а Ь не выполняется Ь> а (антисимметричность). Для любой тройки чисел х, у, I е X, если а Ь, Ь > с, то а > с (транзитивность).

Читайте также:  Просадка фпс в играх на ноутбуке

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

Отношения на множестве чисел ^являются отношениями строгого порядка, так как любое число х е X не может быть меньше или больше самого себя (антирефлексивность). Для любой пары чисел х, у е X при х у не выполняется у > х (антисимметричность). Для любой тройки чисел х, у, 1 е X, если х у, а у > г, то х > 1 (транзитивность).

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

Определение 32.1. Если для каждой пары х, у е X справедливо

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

Определение 33.1. Строгий или нестрогий порядок, заданный на полностью упорядоченном множестве , называется линейным порядком.

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

Множество букв русского или латинского алфавита линейно упорядочено отношением предшествования, или, что то же, отношением следования.

Отношение подчиненности на некотором предприятии определяет строгий частичный порядок, так как в нем несравнимы сотрудники разных отделов.

Для любых элементов a , b , c , d справедливо соотношение:

Определение. Декартовым произведением множеств А и В называется множество всех упорядоченных пар ( a , b ), где а Î А, b Î B .

Декартово произведение п равных множеств А будет называться п – й декартовой степенью множества А и обозначаться А n .

[an error occurred while processing this directive]

Определение. n мерным отношением R на непустом множестве А называется подмножество А n . Если R – n – мерное отношение на множестве А и (а12,…а n ) Î R , то говорят, что отношение R выполняется для элементов а12,…а n и записывают R а1а2…а n . Если n = 2, то такое отношение называется бинарным.

Для бинарного отношения вместо общей записи Ra 1 a 2 применяют запись а1 Ra 2 .

Свойства бинарных отношений.

Определение. Произведением двух бинарных отношений R и S , заданных на множестве А, называется множество

Знак | называется штрих Шеффера и обозначает антиконъюнкцию.

Определение. Обратным (инверсным) отношением к отношению R , заданному на множестве А, называется отношение R -1 , определяемое равенством:

Если R , S и T – бинарные отношения на множестве А, то выполняются следующие равентсва:

Определение. Бинарным отношением R называется подмножество пар (a,b)∈R декартова произведения A×B, т. е. R⊆A×B . При этом множество A называют областью определения отношения R, множество B – областью значений.

Обозначение: aRb (т. е. a и b находятся в отношении R ). /

Замечание: если A = B , то говорят, что R есть отношение на множестве A .

Способы задания бинарных отношений

1. Списком (перечислением пар), для которых это отношение выполняется.

2. Матрицей. Бинарному отношению R ∈ A × A , где A = (a1 , a2 . an), соответствует квадратная матрица порядка n , в которой элемент cij, стоящий на пересечении i-й строки и j-го столбца, равен 1, если между ai и aj имеет место отношение R , или 0, если оно отсутствует:

Пусть R – отношение на множестве A, R ∈ A×A . Тогда отношение R:

рефлексивно, если Ɐ a ∈ A: a R a (главная диагональ матрицы рефлексивного отношения содержит только единицы);

антирефлексивно, если Ɐ a ∈ A: a R a (главная диагональ матрицы рефле сивного отношения содержит только нули);

симметрично, если Ɐ a , b ∈ A: a R b ⇒ b R a (матрица такого отношения симметрична относительно главной диагонали, т.е. cij cji);

транзитивно, если Ɐ a, b, c ∈ A: a R b & b R c ⇒ a R c (в матрице такого отношения должно выполняться условие: если в i-й строке стоит единица, например в j-ой координате (столбце) строки, т. е. cij = 1 , то всем единицам в j-ой строке (пусть этим единицам соответствуют k е координаты такие, что, cjk = 1 ) должны соответствовать единицы в i-й строке в тех же k-х координатах, т. е. cik = 1 (и, может быть, ещё и в других координатах).

Задача 3.1. Определите свойства отношения R – «быть делителем», заданного на множестве натуральных чисел.

рефлексивно, не антирефлексивно, так как любое число делит само себя без остатка: a/a = 1 для всех a∈N ;

не симметрично, антисимметрично, например, 2 делитель 4, но 4 не является делителем 2;

транзитивно,таккакесли b/a ∈ N и c/b ∈ N, то c/a = b/a ⋅ c/b ∈ N, например, если 6/3 = 2∈N и 18/6 = 3∈N, то 18/3 = 18/6⋅6/3 = 6∈N.

Читайте также:  Часы трекер smart gps

Задача 3.2. Определите свойства отношения R – «быть братом», заданного на множестве людей.
Решение.

не рефлексивно, антирефлексивно из-за очевидного отсутствия aRa для всех a;

не симметрично, так как в общем случае между братом a и сестрой b имеет место aRb , но не bRa ;

не антисимметрично, так как если a и b –братья, то aRb и bRa, но a≠b;

транзитивно, если называть братьями людей, имеющих общих родителей (отца и мать).

Задача 3.3. Определите свойства отношения R – «быть начальником», заданного на множестве элементов структуры

  • не рефлексивно, антирефлексивно, если в конкретной интерпретации не имеет смысла;
  • не симметрично, антисимметрично, так как для всех a≠b не выполняется одновременно aRb и bRa;
  • транзитивно, так как если a начальник b и b начальник c , то a начальник c .

Задачи для самостоятельного решения

Определите свойства отношения Ri , заданного на множестве Mi матрицей, если:

Операции над бинарными отношениями

Пусть R1, R1 есть отношения, заданные на множестве A .

универсальное отношение U: = <(a;b)/a ∈ A & b ∈ A>. ;

дополнение R1 U R1, где U = A × A;

тождественное отношение I : = <(a;a) / a ∈ A>;

обратное отношение R -1 1 : R -1 1 = <(a,b) : (b,a) ∈ R1>;

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

Обозначение:

Определение. Если R ⊂ A × B , то R º R -1 называется ядром отношения R .

Теорема 3.1. Пусть R ⊂ A × A – отношение, заданное на множестве A .

  1. R рефлексивно тогда и только тогда, (далее используется знак ⇔) когда I ⊂ R.
  2. R симметрично ⇔ R = R -1 .
  3. R транзитивно ⇔ R º R ⊂ R
  4. R антисимметрично ⇔ R ⌒ R -1 ⊂ I .
  5. R антирефлексивно ⇔ R ⌒ I = ∅ .

Задача 3.4. Пусть R — отношение между множествами <1,2,3>и <1,2,3,4>, заданное перечислением пар: R = <(1,1), (2,3), (2,4), (3,1), (3,4)>. Кроме того, S — отношение между множествами S = <(1,1), (1,2), (2,1), (3,1), (4,2)>. Вычислите R -1 , S -1 и S º R. Проверьте, что ( S º R) -1 = R -1 , S -1 .

Задача 3.5. Пусть R отношение «. родитель. », а S отношение «. брат. » на множестве всех людей. Дайте краткое словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 и R º R.

R -1 — отношение«. ребёнок. »;

S -1 — отношение«. брат или сестра. »;

R º S — отношение «. родитель. »;

S -1 º R -1 — отношение «. ребёнок. »

R º R — отношение «. бабушка или дедушка. »

Задачи для самостоятельного решения

1) Пусть R — отношение «. отец. », а S — отношение «. сестра. » на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , R º R.

2) Пусть R — отношение «. брат. », а S — отношение «. мать. » на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , S º S.

3) Пусть R — отношение «. дед. », а S — отношение «. сын. » на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

4) Пусть R — отношение «. дочь. », а S — отношение «. бабушка. » на множе- стве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

5) Пусть R — отношение «. племянница. », а S — отношение «. отец. » на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

6) Пусть R — отношение «сестра. », а S — отношение «мать. » на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

7) Пусть R — отношение «. мать. », а S — отношение «. сестра. » на множе- стве всех людей. Дайте словесное описание отношениям:

R -1 , S1, R º S, S1 º R1, S º S.

8) Пусть R — отношение «. сын. », а S — отношение «. дед. » на множестве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

9) Пусть R — отношение «. сестра. », а S — отношение «. отец. » на множе- стве всех людей. Дайте словесное описание отношениям:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

10) Пусть R — отношение «. мать. », а S — отношение «. брат. » на множестве всех людей. Дайте словесное описание отношениям:

Ссылка на основную публикацию
Обновление видеокарты н видео
Driver Forum Automatic Driver Updates GeForce Experience automatically keeps your drivers up to date and your games super optimized. Learn...
Не слышу голосовые сообщения в вк
Многие из нас используют социальную сеть «Вконтакте» для коммуникации. Здесь мы активно общаемся с другими людьми, используя не только традиционные...
Не слышу собеседника в скайпе что делать
Современный скоростной интернет дает широкие возможности для общения, у которого нет никаких границ и преград. К сожалению, даже здесь могут...
Обновление для времени windows 7 x64
С 30 октября 2011 ненужно переводить часы. Чтобы привести работу Windows машин в соответствие с законом, нужно установить небольшие патчи....
Adblock detector