2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему
 
 Свойства бинарных отношений.
Сообщение05.05.2013, 12:29 


26/03/13
30
Здравствуйте. Не могу разобраться с свойствами антисимметричности и транзитивности. Помогите.
Есть множество $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 


09/12/09
74
Новосибирск
Странно, что отношение не диагональ, но одновременно симметрично и антисимметрично.

 Профиль  
                  
 
 Re: Свойства бинарных отношений.
Сообщение06.05.2013, 05:23 


26/03/13
30
Получается, что оно не антисимметрично?

 Профиль  
                  
 
 Re: Свойства бинарных отношений.
Сообщение06.05.2013, 05:54 


09/12/09
74
Новосибирск
Получается. Можете это даже доказать.

 Профиль  
                  
 
 Re: Свойства бинарных отношений.
Сообщение06.05.2013, 05:57 


26/03/13
30
А свойство транзитивности правильно определено?

 Профиль  
                  
 
 Re: Свойства бинарных отношений.
Сообщение06.05.2013, 06:01 


09/12/09
74
Новосибирск
Так написано же определение транзитивности. Методом перебора можно убедиться, что отношение транзитивно.

 Профиль  
                  
 
 Re: Свойства бинарных отношений.
Сообщение06.05.2013, 06:21 


26/03/13
30
alex-omsk в сообщении #720262 писал(а):
Так написано же определение транзитивности. Методом перебора можно убедиться, что отношение транзитивно.

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

 Профиль  
                  
 
 Re: Свойства бинарных отношений.
Сообщение06.05.2013, 06:41 
Заслуженный участник


11/11/07
1198
Москва
С транзитивностью у вас все правильно, отношение не транзитивно.

 Профиль  
                  
 
 Re: Свойства бинарных отношений.
Сообщение06.05.2013, 09:32 


09/12/09
74
Новосибирск
да, почему-то предлог не исчез из поста)

 Профиль  
                  
 
 Re: Свойства бинарных отношений.
Сообщение06.05.2013, 23:28 
Заслуженный участник
Аватара пользователя


18/01/13
12065
Казань
Если вы не хотите производить проверку транзитивности перебором (например, матрица большая), можно использовать (булево) умножение матрицы смежности. Отношение $R$ будет транзитивным тогда и только тогда, когда $R^2\subset R$, для матрицы $A$ этого отношения это сводится к $A^2\le A$ (умножение матриц бинарное)

 Профиль  
                  
 
 Re: Свойства бинарных отношений.
Сообщение07.05.2013, 11:33 
Заслуженный участник
Аватара пользователя


21/12/05
5932
Новосибирск
provincialka в сообщении #720620 писал(а):
можно использовать (булево) умножение матрицы смежности

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

 Профиль  
                  
 
 Re: Свойства бинарных отношений.
Сообщение07.05.2013, 12:38 
Заслуженный участник
Аватара пользователя


18/01/13
12065
Казань
bot в сообщении #720727 писал(а):
provincialka в сообщении #720620 писал(а):
можно использовать (булево) умножение матрицы смежности

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group