Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по математике

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 761 RSS
←   Август 2009   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru
Открыта: 14-07-2005

Автор
Калашников О.А.

Статистика

761 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Математика


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный платный хостинг на базе Windows 2008

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Чемпионы рейтинга экспертов в этой рассылке

Гордиенко Андрей Владимирович
Статус: Специалист
Рейтинг: 1316
∙ повысить рейтинг >> 		Kom906
Статус: 5-й класс
Рейтинг: 1272
∙ повысить рейтинг >> 		_Ayl_
Статус: Студент
Рейтинг: 961
∙ повысить рейтинг >>

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Математика

Номер выпуска:983
Дата выхода:08.08.2009, 16:05
Администратор рассылки:Tigran K. Kalaidjian, Профессионал
Подписчиков / экспертов:227 / 135
Вопросов / ответов:1 / 1

Вопрос № 171017: Здравствуйте эксперты, подскажите что такое бинарные отношения, и помогите с задачкой пожалуйста: Саша дружит с Олей, Коля и Юра дружат с Машей. Саша учится с Олей в одной группе, а Коля учится в одной группе с Викой. Вика учится вместе с Юрой и д...

Вопрос № 171017:

Здравствуйте эксперты, подскажите что такое бинарные отношения, и помогите с задачкой пожалуйста:
Саша дружит с Олей, Коля и Юра дружат с Машей. Саша учится с Олей в одной группе, а Коля учится в одной группе с Викой. Вика учится вместе с Юрой и дружит с ним. Ввести бинарное отношение T1 "Учатся вместе", а также T2 "быть другом". Построить матрицу смежности для T1 и T2. Определить свойства обеих бинарных отношений.
Помогите кто чем может. Заранее спасибо.

Отправлен: 03.08.2009, 17:44
Вопрос задал: Tribak, Студент
Всего ответов: 1
Страница вопроса >>

Отвечает _Ayl_, Студент :
Здравствуйте, Tribak.

Бинарное отношение - это любое множество упорядоченных пар.

В данной задачке у нас есть множество из 6-ти элементов: {Саша, Оля, Коля, Юра, Маша, Вика}
Над этим множеством мы хотим ввести два отношения: T1 (учатся вместе) и T2 (быть другом) и исследовать их свойства.
Матрица смежности в данном примере - это квадратная матрица, в качестве строк и столбцов которой выступают элементы заданного множества (x и y), а элементами матрицы является признак, входят эти элементы в отношении или нет. В качестве признака я буду использовать цифру 1, если элементы множества входят в отношение и 0 в противном случае.
В приложении приведены матрицы смежности для заданных отношений. Что нужно написать вместо дефисов будет объяснено ниже.

Теперь определим свойства отношений.
О тношение T1: "Учатся вместе"

Рефлексивность. Отношение называется рефлексивным, если для любого элемента x множества пара (x, x) входит в отношение. В данном случае любой человек учится вместе с самим собой, то есть отношение рефлексивно. В матрице смежности признаком рефлексивного отношения является заполненность главной диагонали цифрой 1. В приложении элементы главной диагонали обозначены дефисами для наглядности, их нужно заменить на 1.

Антирефлексивность. Т.к. отношение рефлексивно, проверять не требуется. Не является.

Симметричность. Отношение называется симметричным, если для любых элементов x и y множества, в случае, если пара (x, y) входит в отношение, то в отношение входит и пара (y, x). Признаком симметричного отнощения является симметричность матрицы относительно главной диагонали. В нашем случае отношение является симметричным. В самом деле, если человек x учится вместе с человеком y, то человек y, в свою очередь, учится с человеко м x.

Антисимметричность. Не является, т.к. является симметричным. !!! Бинарное отношение может быть одновременно и симметричным и антисимметричным.

Транзитивность. Отношение является транзитивным в том случае, если для любых трех элементов x, y и z множества из того, что пары (x, y) и (y, z) входят в отношение, следует, что и пара (x, z) входит в отношение. Наше отношение транзитивно, т.к. если x учится вместе с y, а y учится вместе с z, то x также учится вместе с z. На основании этого свойства в матрице смежности были заполнены элементы "Коля-Юра" и "Юра-Коля", т.к. они оба учатся вместе с Викой.

Антитранзитивность. Не является, т.к. является транзитивным.

Равенство третьему. Отношение обладает свойством равенства третьему в том случае, если для любых трех элементов x, y и z множества из того, что пары (x, y) и (z, y) входят в отношение, следует, что в отношение входит пара (a, z). Свойство равенства третьему выполняется для всех симметричных и транзитивных отношений (в самом деле, допустим, что наше отношение симметрично и транзитивно. Возьмем три любых элемента множества x, y и z таких, что пары (x, y) и (z, y) входят в это отношение. Тогда из симметричности следует, что в отношение входит и пара (y, z), а тогда из транзитивности мы получаем требуемое).
Наше отношение транзитивно и симметрично, то есть обладает свойством равенства третьему.

Полнота. Отношение обладает свойством полноты, если для любых двух элементов x и y множества в отношение входит хотя бы одна из пар: (x, y) или (y, x). Наше отношение полным не является, т.к. существуют пары (например, Саша и Вика), которые не входят в отношение.

Т.о. отношение "учится вместе" обладает свойствами: рефлексивность, симметричность, транзитивность, равенство третьему. Такое отношение также называется отношением эквивалентности.

Разберем второе отношение.
Отношение T2: "Быть друг ом"

Рефлексивность. Здесь встает явно философский вопрос: является ли любой человек другом самому себе? В данном примере я буд у считать, что не является. Соответственно, в матрице смежности вместо дефисов нужно записать цифру 0.

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

Симметричность. Отношение является симметричным, т.к. если x является другом y, то y является другом x.

Антисимметричность. Не является, т.к. является симметричным. !!! Бинарное отношение может быть одновременно и симметричным и антисимметричным.

Транзитивность. Отношение не является транзитивным. Для доказательства возьмем трех человек: Колю, Юру и Машу. Из условия нам известно, что Коля и Юра дружат с Машей. Т.е. Коля дружит с Машей и Юра дружит с Машей. Из симметричности следует, что Маша дружит с Колей и с Юрой. Но при этом про дружбу Коли и Юры нам ничего не сказано.
Замечание. Если предположить, что фразу из условия "Коля и Юра д ружат с Машей" можно понять, что все трое дружат между собой, то отношение по-прежнему останется нетранзитивным, т.к. есть еще тройка Маша, Юра, Вика, в которой Юра дружит с обеими девушками, а сами девушки друг с другом не дружат.

Антитранзитивность. Для антитранзитивности требуется, чтобы в отношении не было бы ни одной транзитивной тройки. Поэтому в случае, если Коля и Юра не дружат, то отношение является антитранзитивным, а если дружат - то не является. Я считаю, что по условию между парнями дружбы нет, поэтому отношение антитранзитивно.

Равенство третьему. Допустим, что наше отношение обладает данным свойством. Возьмем любые элементы x, y и z такие, что (x, y) и (z, y) входят в отношение. Т.к. мы предположили, что отношение обладает свойством равенства третьему, то тогда и пара (x, z) должна входить в отношение. То есть в отношение входят пары (x, y), (z, y) и (x, z). Но данное отношение симметрично, т.е. т.к. пара (z, y) входит в отношение, то в отно шение входить и пара (y, z). Т.о., в отношение входят пары (x, y), (y, z) и (x, z). То есть данное отношение должно обладать свойством транзитивности. Однако, оно является антитранзитивным. Соответственно, мы пришли к противоречию, т.е. исходное предположение неверно, а значит, данное отношение свойством равенства третьему не обладает.

Полнота. Отношение полным не является, т.к. существуют пары (например, Саша и Вика), которые не входят в отношение.

Т.о. отношение "быть другом" обладает свойствами: антирефлексивность, симметричность, антитранзитивность. Специального названия у такого отношения нет.
Бинарное отношение может быть одновременно и симметричным и антисимметричным.
-----
∙ Отредактировал: Агапов Марсель, Академик
∙ Дата редактирования: 03.08.2009, 18:10 (время московское)

Приложение:

Ответ отправил: _Ayl_, Студент
Ответ отправлен: 03.08.2009, 17:58

Оценка ответа: 5

Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 252883 на номер 1151 (Россия) | Еще номера >>
  • Отправить WebMoney:
    • Вам помогли? Пожалуйста, поблагодарите эксперта за это!

    Оценить выпуск >>
    Нам очень важно Ваше мнение об этом выпуске рассылки!

    Задать вопрос экспертам этой рассылки >>

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)
    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров >>

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

    © 2001-2009, Портал RFpro.ru, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Автор: Калашников О.А. | Программирование: Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2009.6.6 от 21.07.2009
    В избранное