Вы на НеОфициальном сайте факультета ЭиП

На нашем портале ежедневно выкладываются материалы способные помочь студентам. Курсовые, шпаргалки, ответы и еще куча всего что может понадобиться в учебе!
Главная Контакты Карта сайта
 
Где мы?

Реклама


Отношения

Просмотров: 4503 Автор: Angel
1. 3 Отношения

Отображение, заданное между элементами одного множества Х, называют отношением. 

Между математическими объектами такими отношениями могут быть {=, ?, ?, ?, <, ?}, а между “нематематическими” объектами {“x принадлежит y”, “x часть y”, “x смежный y”, “x родственник y”, “x родитель y”, “x находится рядом с y”,..}.

 Например, “2=2”, “3?2”, “факультет ЭиП часть университета ЮУрГУ”, “судно находится рядом с причалом ” и т.п.

Очевидно, что каждое отношение r=(xi, xj) или r=(x1, x2,..,xn) есть кортеж, а их множество есть подмножество X2 или Xn, т.е. 
R={(xi, xj)| xi, xj?X}?X2 или R={(x1, x2,..,xn)| xi?X}?Xn.

Если n=1, то отношение называют унарным или одноместным. Такое отношение r(x) равносильно заданию предиката Р(х) на области определения для формирования подмножества, удовлетворяющего заданному условию. 

Если n=2, то отношение называют бинарным или двухместным. Такое отношение позволяет сравнивать по заданному предикату P(xi, xj) элементы множества X.

Если n=n, то отношение называют n арным или nместным.

Бинарные отношения между элементами множества X удобно описывать матрицами (Х?Х), строки и столбцы которых есть элементы множества, а на пересечении iой строки и jго столбца ставят знак “1”, если задано отношение r(i, j) между iм и jм элементами и “0” в противном случае, т.е.
  1, если (xi,xj)?R;
  rij=  
0, если (xi,xj)?R.

Например, таблица на с прошлой лекции представляет также отношение r2(xi, xj) для предиката Р2(x1, x2): ”xi и xj имеют общий делитель”.

Отношения также удобно представлять в операторной форме:
r: X?X или r: Xn1?X. 

Каждому отношению r может быть найдено обратное r1.
r1: X?X или r1: X ?(X1?X2?..?Xn1). 

В этом случае R1={(x, x)|x?X}?X2 или R1={(x, x1, x2,..xn1)| xi?X}?Xn.
Анализ отношений позволяет выделить характерные свойства.

Бинарное отношение рефликсивно, если для каждого хi?Х имеем r(xi; xi)=1. 

Такими отношениями являются “..=..”, “..быть похожим..”, “..быть изоморфным..”, “..быть эквивалентным..” и т.п. При матричном описании такого отношения на главной диагонали матрицы будут только “1”, т.е. r(xi, xi)=1.


Бинарное отношение антирефлексивно, если для каждого хi?Х имеем 
r(xi, xi)=0. 

Такими отношениями являются “..?.. ”, “..<..”, “быть родителем” и т.п.

При матричном описании такого отношения на главной диагонали матрицы будут только “0”, т.е. r(xi, xi)=0.

Бинарное отношение симметрично, если для любой пары (xi, xj)?R имеем r(xi, xi)=r(xj, xi)=1. 

Такими отношениями являются “..?..”, “..быть похожим..”, “..быть эквивалентным..”, “..быть родственником..” и т.п.. 

При матричном задании такого отношения будет симметричное расположение “1” относительно главной диагонали, т.е. r(xi, xi)=r1(xj, xi).

Бинарное отношение антисимметрично, если для любой пары (xi, xj) при i?j имеем r(xi, xi)?r(xj, xi), а при i=j имеем r(xi, xi)=1. 

Такими отношениями являются “..?..”, “..?..” и т.п.. 

При матричном задании такого отношения это означает несимметричное расположение “1” относительно главной диагонали и наличие “1” на главной диагонали.

Бинарное отношение асимметрично, если для любой пары (xi, xj) при i?j имеем r(xi, xi)?r(xj, xi), а при i=j имеем r(xi, xi)=0.. 

Такими отношениями являются “..?..”, “..<..”, “быть родителем” и т.п. 
При матричном задании такого отношения это означает несимметричное расположение “1” относительно главной диагонали и наличие “0” на главной диагонали.

Бинарное отношение транзитивно, если для любых элементов xi, xj, xk?Х существует r(xi, xi)=1 тогда и только тогда, когда существует r(xi, xk)=1 и r(xk, xi)=1. 

Такими отношениями являются “..?..”, “..<..”, “быть родителем”, “быть родственником” и т.п.. 

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

Бинарное отношение, удовлетворяющее условиям рефлексивности, симметричности и транзитивности называют отношением эквиваленции. Такими отношениями являются “..=..”, “..быть похожим..”, “..быть родственником..”. 

Отношение эквиваленции обозначают r~(xi, xi) или ~(xi, xi). Отношение r~ позволяет формировать классы эквиваленции по образцу х?, в виде подмножества множества X, т.е. K? ={x| r~(x, x?)=1, x, x??X}?X.

Два класса эквиваленции не имеют общих элементов множества Х. 

Попарно различимые классы эквиваленции K?1, K?2,...K?n позволяет выполнять разбиение множества Х на подмножества, т.е. Х={Х?1, Х?2,..,Х?n}.


Бинарные отношения, удовлетворяющие условиям рефлексивности, антисимметричности и транзитивности называют отношением частичного порядка. Такими отношениями являются “..?..”, “..?..”, “..быть не старше..” и т.п.. 

Отношение порядка обозначают для элементов множества: r?(xi, xi) или 
?( xi, xi), а для подмножеств множества: r?(Xi, Xj) или ?(Xi, Xj). Задание отношения ?(xi, xj) позволяет формировать частичный порядок элементов множества X, а задание отношения ?(Xi, Xj) – частичный порядок на подмножествах множества X. 

Например, пусть даны множества Х0={1, 2, 3, 4, 5, 6}, X1={1, 2, 3, 4}, 
X2={2, 3, 4, 5}, X3={2, 3, 4}, X4={3, 4, 5}, X5={2, 3}, X6={3, 4}, X7={4, 5},
X8={2, 4}. 

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

 Тогда X8?X3?X2?X0 или X8?X3?X1?X0, X7?X4?X2?X0, X6?X4?X2?X0 или X6?X3?X2?X0 или X6?X3?X1?X0, X5?X3?X2?X0, X5?X3?X1?X0.

Одной из важных характеристик упорядоченного множества является наличие граней. Если на множестве X задан частичный порядок ?(xi, xj), то среди элементов множества X найдется такой элемент x?, для которого выполняется условие ?(xi, x?) и ?(xj, x?) и найдется такой элемент x?, для которого выполняется условие ?(x?, xi) и ?(x?, xj).. 


В общем случае для некоторых элементов множества X могут не существовать x? и x? или быть неединственными. Тогда наименьший элемент x? формирует верхнюю грань для элементов xi и xj, что обозначают так: x?=Sup Xi, где Xi={xi, xj}?X, а наибольший элемент x? формирует нижнюю грань для элементов xi и xj, что обозгачают так: x?=Inf Xi, где Xi={xi, xj}?X. 

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

Такими отношениями являются “..?..”, “..<..”, “..быть родителем..”, “быть частью”, “быть подчиненным” и т.п. 

Отношение строгого порядка обозначают для элементов множества: r<(xi; xi) или <(xi; xi), а для подмножеств множества: r?(Xi;Xj) или ?(Xi;Xj).

 Примерами упорядоченных множеств являются целые числа, упорядоченные правилом n=(n+1) или буквы, упорядоченные алфавитом и т.п.



Информация

Комментировать статьи на нашем сайте возможно только в течении 60 дней со дня публикации.

Популярные новости

Статистика сайта



Rambler's Top100



 
Copyright © НеОфициальный сайт факультета ЭиП