2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Свойства бинарных отношений.
Сообщение05.05.2013, 12:29 
Здравствуйте. Не могу разобраться с свойствами антисимметричности и транзитивности. Помогите.
Есть множество $B=\{1,2,3,4\}$.
Есть бинарное отношение $P \subseteq B^2$. $P=\{(1,1),(1,2),(1,4),(2,1),(2,2),(2,3),(3,3),(3,2),(3,4),(4,3),(4,4),(4,1)\}$.
Проверить, является ли отношение Р рефлексивным, симметричным, антисимметричным, транзитивным.

$P$ рефлексивно, т.к. $ \forall x \in B, (x,x) \in P $.
$P$ симметрично, т.к. $ \forall x,y \in B, (x,y) \in P \to (y,x) \in P $
$P$ антисимметрично, т.к. $ \forall x,y \in B, (x,y) \in P, (y,x) \in P  \rightarrow x=y $
$P$ не транзитивно, т.к. $ \forall x,y,z \in B, (x,y) \in P, (y,z) \in P  \rightarrow (x,z) \in P $ (например, для пар $(1,2)$ и $(2,3)$ пары $(1,3)$ нету в отношении $P$).

Правильно ли определены свойства? Подскажите.

 
 
 
 Re: Свойства бинарных отношений.
Сообщение05.05.2013, 12:32 
Странно, что отношение не диагональ, но одновременно симметрично и антисимметрично.

 
 
 
 Re: Свойства бинарных отношений.
Сообщение06.05.2013, 05:23 
Получается, что оно не антисимметрично?

 
 
 
 Re: Свойства бинарных отношений.
Сообщение06.05.2013, 05:54 
Получается. Можете это даже доказать.

 
 
 
 Re: Свойства бинарных отношений.
Сообщение06.05.2013, 05:57 
А свойство транзитивности правильно определено?

 
 
 
 Re: Свойства бинарных отношений.
Сообщение06.05.2013, 06:01 
Так написано же определение транзитивности. Методом перебора можно убедиться, что отношение транзитивно.

 
 
 
 Re: Свойства бинарных отношений.
Сообщение06.05.2013, 06:21 
alex-omsk в сообщении #720262 писал(а):
Так написано же определение транзитивности. Методом перебора можно убедиться, что отношение транзитивно.

Объясните, пожалуйста, "на пальцах". Не понимаю как.

 
 
 
 Re: Свойства бинарных отношений.
Сообщение06.05.2013, 06:41 
С транзитивностью у вас все правильно, отношение не транзитивно.

 
 
 
 Re: Свойства бинарных отношений.
Сообщение06.05.2013, 09:32 
да, почему-то предлог не исчез из поста)

 
 
 
 Re: Свойства бинарных отношений.
Сообщение06.05.2013, 23:28 
Аватара пользователя
Если вы не хотите производить проверку транзитивности перебором (например, матрица большая), можно использовать (булево) умножение матрицы смежности. Отношение $R$ будет транзитивным тогда и только тогда, когда $R^2\subset R$, для матрицы $A$ этого отношения это сводится к $A^2\le A$ (умножение матриц бинарное)

 
 
 
 Re: Свойства бинарных отношений.
Сообщение07.05.2013, 11:33 
Аватара пользователя
provincialka в сообщении #720620 писал(а):
можно использовать (булево) умножение матрицы смежности

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

 
 
 
 Re: Свойства бинарных отношений.
Сообщение07.05.2013, 12:38 
Аватара пользователя
bot в сообщении #720727 писал(а):
provincialka в сообщении #720620 писал(а):
можно использовать (булево) умножение матрицы смежности

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

Согласна, это важнее для проверки транзитивности. Особенно, если отношение изначально задано с помощью матрицы.

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group