Finkurier.ru

Журнал про Деньги
2 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Полное бинарное отношение

Бинарные отношения и их свойства

Основы дискретной математики.

Понятие множества. Отношение между множествами.

Множество – совокупность объектов, обладающих определенным свойством, объединенных в единое целое.

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

· Должно существовать правило, по которому моно определить принадлежит ли элемент к данной совокупности.

· Должно существовать правило, по которому элементы можно отличить друг от друга.

Множества обозначаются заглавными буквами, а его элементы маленькими. Способы задания множеств:

· Перечисление элементов множества. — для конечных множеств.

· Указание характеристического свойства .

Пустым множеством – называется множество, не содержащее ни одного элемента (Ø).

Два множества называются равными, если они состоят из одних и тех же элементов. , A=B

Множество B называется подмножеством множества А ( , тогда и только тогда когда все элементы множества B принадлежат множеству A.

Например: , B =>

Свойство:

Примечание: обычно рассматривают подмножество одного и того е множества, которое называется универсальным (u). Универсальное множество содержит все элементы.

Операции над множествами.

Н-р: , ,

2.Пересечением 2-х множеств называется новое множество, состоящее из элементов, одновременно принадлежат и первому и второму множеству.

Н-р: , ,

Свойство: операции объединения и пересечения.

· Коммутативность.

;

· Ассоциативность. ;

;

· Дистрибутивный. ;

;

MT1102: Линейная алгебра (введение в математику)

Рассмотрим отношение «уважать», определенное на множестве всех людей %%M%%. Для полной информации о том, кто кого уважает, составим следующее множество %%R%%. Переберем все пары %%(a, b)%%, где %%a, b%% пробегают множество всех людей. Если %%a%% уважает %%b%%, то пару %%(a,b)%% отнесем к множеству %%R%%, иначе — нет.

Этот список полностью отражает отношение «уважать». Если нужно узнать, уважает ли человек %%a%% человека %%b%%, то просмотрим множество %%R%%. Если пара %%(a, b) in R%%, то заключаем, что %%a%% уважает %%b%%. В случае %%(a,b) notin R%% — %%a%% не уважает %%b%%.

Определение

Бинарным отношением, определенным на множестве %%M%%, называется произвольное подмножество %%R%% из декартового произведения %%M^2%%.

Пример

Рассмотрим отношение больше на множестве %%M = <1, 2>%%. Тогда

$$ M^2 = big <(1, 1), (1,2), (2,1), (2,2)big>$$ Из него выбирем все пары %%(a,b)%%, где %%a > b%%. Получим $$ R = big <(2,1)big>$$

Виды бинарных отношений

Рефлексивное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется рефлексивным, если для любого элемента %%a%% из %%M%%, выполняется условие %%a

a%%. $$ begin forall ain M

a text< или>\ forall ain M

Примеры

  1. Рассмотрим отношение больше на множестве действительных чисел. Является ли отношение больше рефлексивным? Если да, то каждое число является больше самого себя, что неверно. Поэтому отношение больше не рефлексивно.
  2. Рассмотрим отношение равно на множестве действительных чисел. Оно является рефлексивным, так как каждое действительное число равно самому себе.

Симметричное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется симметричным, если для любых двух элементов %%a, b%% из %%M%%, из условия %%a

b%% следует условие %%b

a text< или>\ forall a,bin M

(a,b) in R rightarrow (b,a) in R. end $$

Примеры

  1. Рассмотрим отношение больше на множестве действительных чисел. Является ли отношение больше симметричным? Оно не является симметричным, так как если %%a > b%%, то условие %%b > a%% не выполняется. Поэтому отношение больше не симметрично.
  2. Пусть %%R%% — отношение, определенное на множестве %%M = %%. При этом %%R = big< (a,b), (b,c), (a,a), (b,a), (c,b)big>%%. Для этого отношения имеем %%forall x,y in M

(x,y) in R rightarrow (y,x) in R%%. По определению %%R%% симметрично.

Транзитивное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется транзитивным, если для любых элементов %%a, b, c%% из %%M%%, из условий %%a

c%% следует условие %%a

c text< или>\ forall a,b,cin M

(a,b) in R land (b,c) in R rightarrow (a,c) in R. end $$

Пример

Рассмотрим отношение больше на множестве дейтсвительных чисел. Оно является транзитивным, так как для любых элементов выполняется условние %%forall a,b,cin M

a > b land b > c rightarrow a > c%%. Так, например, подставив вместо %%a, b%% и %%c%% числа %%2, 1%% и %%0%% соответственно, получим: если %%2 > 1%% и %%1 > 0%%, то %%2 > 0%% — верное утверждение (вспомните импликацию, из истины следует истина).

Антисимметричное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется антисимметричным, если для любых элементов %%a, b%% из %%M%%, из условий %%a

a%% следует условие %%a = b%%.

a rightarrow a = b text< или>\ forall a,bin M

(a,b) in R land (b,a) in R rightarrow a = b. end $$

Пример

Отношение больше или равно на множестве действительных чисел антисимметрично. Действительно, если %%a geq b%% и %%b geq a%%, %%a = b%%.

Эквивалентное бинарное отношение

Бинарное отношение %%R%% на множестве %%M%% называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

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

Отношение частичного порядка

Бинарное отношение %%R%% на множестве %%M%% называется отношением частичного порядка, если оно рефлексивно, антисимметрично и транзитивно.

Отношение больше или равно на множестве действительных чисел является отношением частичного порядка.

Построение отрицаний

Пусть %%R%% — бинарное отношение на множестве %%M%%, и %%P%% — одно из следующих условий:

  • отношение %%R%% рефлексивно,
  • отношение %%R%% симметрично,
  • отношение %%R%% транзитивно,
  • отношение %%R%% антисимметрично.

Построим для каждого из них отрицание выполнения условия %%P%%.

Отрицание рефлексивности

По определению %%R%% рефлексивно, если каждый элемент множества %%M%% находится в отношении %%R%% к самому себе, то есть %%forall a in M

a%%. Тогда рассмотрим отрицание рефлексивности как истинное высказывание %%overline

a>%%. Используем равносильность %%overline equiv exists x overline%%. В нашем случае получаем %%forall a in M

a equiv exists ain M

Аналогично получаем и остальные отрицания. В итоге получаем следующие утверждения:

%%R%% не рефлексивно тогда и только тогда, когда

%%R%% не симметрично тогда и только тогда, когда

$$ exists a, b in M

%%R%% не транзитивно тогда и только тогда, когда

$$ exists a, b, c in M a

%%R%% не антисимметрично тогда и только тогда, когда

Бинарные отношения;

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

Если a и b находятся в отношении Q, это обычно записывается в виде aQb или ÎQ и читается как «a находится в отношении Q с b». Не следует забывать, что a и b здесь – элементы одного и того же множества.

Рассмотрим несколько примеров бинарных отношений на множестве натуральных чисел N.

Пример 1. Отношение «» выполняется для пар , и не выполняется для пары .

Пример 2. Отношение «иметь общий делитель, не равный единице» выполняется для пар , и не выполняется для пар , .

Пример 3. Отношение «быть делителем» выполняется для пар , и не выполняется для пар , .

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

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

1. Рефлексивность. Отношение Q рефлексивно, если оно выполняется между объектом и им самим, то есть для любого aÎA выполняется aQa. Например, на множестве людей отношения «быть похожим», «быть знакомым» являются рефлексивными (любой элемент похож на самого себя и знаком с самим собой).

2. Нерефлексивность. Отношение Q нерефлексивно, если хотя бы для одного aÎA отношение aQa не выполняется. На множестве людей нерефлексивными отношениями являются, например, «уметь лечить», «быть уверенным в», «любить», «уважать».

3. Антирефлексивность. Если отношение Q может выполняться лишь для несовпадающих объектов, то есть ни для какого элемента aÎA не выполняется aQa, то оно антирефлексивно. Например, на множестве людей отношение «быть братом» является антирефлексивным. Таковым же является и отношение «быть меньше» на множестве действительных чисел.

5. Антисимметричность. Отношение Q называется антисимметричным, если из двух отношений aQb и bQa хотя бы одно не выполнено. На множестве людей антисимметричными являются отношения «быть старше», «быть выше ростом», «быть потомком».

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

6. Транзитивность. Отношение Q называется транзитивным, если для любых a, b, c Î A из отношений aQb и bQc следует aQc. На множестве людей транзитивными являются отношения «быть равным по росту», «жить в одном городе», «быть богаче».

Следует подчеркнуть, что, в отличие от отношений рефлексивности и симметричности, для отношения транзитивности не формулируется противоположного понятия (антитранзитивности).

7. Транзитивное замыкание. Транзитивным замыканием отношения Q называется отношение, определяемое следующим образом. Если во множестве A существует цепочка из n элементов a=a1, a2, . an=b, в которой между двумя соседними элементами выполняется отношение Q (то есть aQa2, a2Qa3, . an-1Qb), то говорят, что существует транзитивное замыкание ab. При этом говорить о транзитивном замыкании имеет смысл лишь при n>2, то есть когда цепочка состоит минимум из трех элементов.

Пример 1. Задано множество чисел A=<1, 3, 5, 6, 7, 8, 9, 12, 15, 16, 20>. На нем можно определить бинарное отношение «меньше на единицу», которое будет включать следующие пары: Q=< , , , , >.

Можно заметить, что используя операцию «+1» (в математике данная операция называется инкрементом, а операция «-1» – декрементом), мы можем построить цепочку из числа 5 к числу 9. Данная цепочка будет состоять из элементов 5, 6, 7, 8, 9, причем между любыми двумя соседними элементами выполняется отношение Q, а элементы 5 и 9 являются крайними (граничными) в этой цепочке. То есть можно говорить о том, что «число 9 достижимо из числа 5 с помощью операции инкремента». Данную фразу можно рассматривать как новое отношение , законом которого является «достижимо с помощью инкремента из». Приняв a=9, b=5, можно записать, что ab. Таким образом, для элементов 9 и 5 мы получили новое отношение , базирующееся на составленном ранее отношении Q. Данное отношение, очевидно, является транзитивным замыканием.

Может показаться, что на множестве A= <1, 3, 5, 6, 7, 8, 9, 12, 15, 16, 20>обнаружить рассмотренное выше транзитивное замыкание слишком легко. Однако это лишь кажущаяся легкость. Элементы в исходном множестве не обязательно должны быть упорядочены по возрастанию (как это сделано в примере) и могут быть расположены хаотично: A=<12, 9, 5, 16, 7, 1, 20, 8, 15, 3, 6>. Здесь также существует рассмотренное транзитивное замыкание, однако обнаружить его уже не так просто. Если же мощность заданного множества измеряется сотнями тысяч, то поиск транзитивных замыканий возможен только с помощью компьютера и при этом требует значительных затрат времени и разработки специальных алгоритмов обработки.

Элементы 9 и 5 – не единственные во множестве A, которые находятся друг к другу в отношении «достижимо с помощью инкремента из». Можно зависать, что 75, 85, 86, 96, 97. Каждая из этих цепочек содержит больше двух элементов, поэтому является транзитивным замыканием. Между элементами 6 и 5 отношение выполняется, однако между ними нет транзитивного замыкания, поскольку длина цепочки равна 2. Хотя некоторые математики считают цепочки из двух элементов частными случаями транзитивных замыканий, однако практической пользы от этого нет.

Таким образом, полное множество пар элементов множества A, для которых выполняется транзитивное замыкание , можно записать так:

=< , , , , , >.

Пример 2. Задано множество членов королевской семьи:

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

Между крайними элементами данной цепочки можно установить новое отношение с законом «является предком по мужской линии»: «прадед»«праправнук». Данное отношение является транзитивным замыканием, поскольку между любыми двумя соседними элементами выполняется отношение Q. Это же замыкание выполняется и для других элементов, например: «прадед»«сын», «отец»«внук», «прадед»«правнук» и т.д. Отношения «отец»«сын», «прадед»«дед», «внук»«правнук» также выполняются, но транзитивными замыканиями не являются, поскольку длины их цепочек равны 2. Студентам предлагается самостоятельно найти полное множество пар, для которых выполняется транзитивное замыкание «является предком по мужской линии».

Замыкание является весьма общим математическим понятием. Упрощённо говоря, замкнутость означает, что многократное повторение допустимых шагов не выводит за определённые границы. Поэтому слово «замыкание» следует понимать не как «закольцовывание по кругу», а как «ограниченность чем-либо».

Полное бинарное отношение

Пусть > — нестрогое отношение предпочтения (полное и транзитивное бинарное отношение), заданное на X, а >- (х>у (х>у) и (у>х) ) и (х у (х>у) и (у>х)) — строгое отношение предпочтения и отношение эквивалентности, построенные на его основе. Каким свойствам будут удовлетворять отношения >- и [c.27]

Пусть > — нестрогое отношение предпочтения (полное и транзитивное бинарное отношение) заданное на X, а (х у (х >у и (у>х) ) — отношение эквивалентности. Рассмотрим семейство множеств (кривых) безразличия, построенных на основании . Как на основании порядка, задаваемого отношением >, корректно и непротиворечиво ввести порядок на этом семействе Какими свойствами он обладает [c.28]

Наиболее существенные по мнению конструктора признаки, главным образом измеряемые количественно, включатся в техническое задание на проектирование другие — учитываются как критерии или критериальные ограничения при выборе наиболее рационального варианта и оптимальных параметров объекта проектирования. Для автоматизированного выполнения процедуры нужно построить полные множества целей и признаков, что должно войти в банк знаний, установить бинарные отношения между элементами этих множеств и производить срез внутри этих отношений по выбранному подмножеству целей А0. [c.109]

Каждое полное бинарное отношение является рефлексивным. [c.18]

Покажите, что каждое полное бинарное отношение является рефлексивным. [c.20]

Пусть > — полное и транзитивное бинарное отношение, заданное на множестве X. Для каких из нижеприведенных множеств X это отношение может быть представлено некоторой функцией полезности [c.39]

Пусть Х- множество альтернатив, на котором задано полное и транзитивное бинарное отношение >. Докажите, что если множество кривых безразличия счетно, то существует функция полезности представляющая >. [c.39]

Пусть предпочтения потребителя заданы посредством полного и транзитивного бинарного отношения. Покажите, что предпочтения потребителя выпуклы тогда, и только тогда, когда выпукло множество нехудших элементов, т.е. множество L+(y)= x X x > [c.50]

Векторы х и у называются ортогональными, если их скалярное произведение равно нулю. Равенство В. — компонентное, т. е. два В. равны, если равны их соответствующие компоненты. Вектор 0 — (0,. . 0) нулевой и-мерный В. — положительный (х > 0), если все его компоненты х больше нуля, неотрицательный (х > 0), если все его компоненты х. больше 0 или равны нулю, т. е. х. > 0 и полуположительный, если при этом хотя бы одна компонента х > 0 (обозначение х > 0) если В. имеют равное количество компонент, возможно их упорядочение (полное или частичное), т. е. введение на множестве векторов бинарного отношения «>» х > у, х > у, х > у в зависимости от того, положительна, полуположительна или неотрицательна разность х — у. [c.42]

Данная группа методов характеризуется оригинальным подходом к сравнению альтернатив, предложенным впервые во Франции профессором Б.Руа и его сотрудниками. Связь между любой парой альтернатив определяется последовательностью бинарных отношений. Сильным бинарным отношениям соответствуют бьльшие требования к превосходству одной альтернативы над другой и, следовательно, бьльшее число несравнимых альтернатив. Самым сильным является требование полного доминирования одной альтернативы над другой. Более слабые бинарные отношения определяют условия, при которых, несмотря на противоречивые оценки, одна альтернатива определяется лучшей по сравнению с другой. [c.167]

2.2 Бинарные отношения и их свойства

Чтобы мотивировать и пояснить понятие бинарного отношения, рассмотрим известную детскую игру «камень-ножницы-бумага». Предполагается, что: камень побеждает ножницы (тупит), ножницы побеждают бумагу (режут), бумага побеждает камень (оборачивает), в остальных случаях (например, камень — камень) — боевая ничья.

Этот простой пример приводит нас к следующему определению бинарного отношения.

Пусть X — произвольное непустое множество. Декартовым квадратом множества X назовем множество, обозначаемое X х X, элементами которого являются всевозможные упорядоченные пары (x, y), где x, y пробегают все множество X. Под бинарным отношением R, заданным на множестве X, будем понимать, некоторое подмножество декартова квадрата X х X, т. е. формально Rc X х X.

Рис. 2.1. Бинарное отношение R, заданное на множестве X

Другими словами бинарное отношение — это некоторое множество упорядоченных пар (x, y), где x и y — элементы множества X. Понятие бинарного отношения имеет достаточно простую графическую иллюстрацию (см. Рис. 2.1).

При рассмотрении бинарных отношений в случае, когда пара (x, y) принадлежит множеству R, вместо (x, y) GR обычно пишут x R y и говорят, что x находится в отношении R к y.

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

Бинарное отношение R называется

рефлексивным, если Vx G X выполнено x R x

иррефлексивным , если x R x не выполняется ни при каком x G X (т. е. Vx G X (x R

симметричным, если Vx, y G X из x R y следует y R x;

асимметричным, если Vx, y G X из x R y следует, что y R x неверно;

транзитивным, если Vx, y, z G X выполнено

(x R y и y R z) ^ x R z;

отрицательно транзитивным, если Vx, y, z G X выполнено

p(x R y) и-I(y R z)) (x R z);

полным, если Vx, y G X выполнено либо x R y, либо y R x, либо и то и другое.

Проиллюстрируем эти свойства бинарных отношений на примерах.

Пусть X — множество студентов, учащихся в этом учебном году в Новосибирском Государственном Университете, R — отношение «выше ростом, чем» заданное на X.

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

Это отношение также является асимметричным и не является симметричным. Действительно, пусть h(a) — рост некоторого студента a, а h(b) — рост студента b, и a R b, т. е. студент a имеет больший рост, чем b (h(a) > h(b)). Тогда вполне понятно, что неверно (h(b) > h(a)), что и означает, что неверно b R a. Таким образом, с учетом произвольности выбора a и b получили желаемое.

Проверим теперь, что данное отношение является транзитивным. Из множества X возьмем трех произвольных студентов a, b, c, чей рост составляет h(a), h(b) и h(c) соответственно, причем выполнено следующее: h(a) > h(b) и h(b) > h(c). Очевидно, что по свойству сравнения действительных чисел мы имеем, что h(a) > h(c). Это в точности означает, что a R c и мы, таким образом, показали транзитивность R.

Выполнение свойства отрицательной транзитивности мы проверим чуть позже, а сейчас перейдем к проверке свойства полноты. Как несложно понять, данное отношение не является полным, если среди студентов есть хотя бы двое с одинаковым ростом. В этом случае ни один из этих двух студентов не будет выше другого и, таким образом, мы имеем нарушение полноты. Если же среди нашего множества X нет ни одной пары студентов с одинаковым ростом, то введенное на X отношение «выше ростом, чем» обладает свойством полноты. Д

Пусть на множестве X = R+ задано отношение R по правилу (xi,x2) R (yi,V2) ^ Xi + y2 ^ yi + X2. Перед тем как отвечать на вопрос о том, каким свойствам удовлетворяет данное бинарное отношение, заметим, что Xi + y2 ^ yi + X2 ^ Xi — X2 ^ yi — У2, т. е. (xi, X2) R (yi,y2) ^ Xi — X2 ^ yi — y2. Как несложно догадаться, данное бинарное отношение удовлетворяет тем же свойствам, что и отношение ^ на действительной прямой, т. е. полнота, транзитивность, рефлексивность. (Проверьте самостоятельно выполнение/невыполнение условий симметричности/асимметричности и отрицательной транзитивности.) Д

Замечание: При проверке указанных выше свойств предпочтений следует быть осторожным и не делать поспешных выводов. В частности, если окажется, что отношение не является рефлексивным, то из этого, вообще говоря, не следует, что отношение является иррефлексивным. Та же ситуация возникает при рассмотрении связки свойств симметричность/асимметричность.

Эти определения также легко проиллюстрировать графически в духе Рис. 2.1. Так, например, рефлексивность означает, что вся диагональ декартова квадрата X х X принадлежит R. Свойство симметричности означает, что множество R симметрично относительно диагонали декартова квадрата. Полнота означает, что если мы «согнем по диагонали» декартов квадрат, то в итоге получим треугольник без выколотых точек.

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

Каждое асимметричное бинарное отношение является иррефлексивным.

Каждое полное бинарное отношение является рефлексивным.

Каждое иррефлексивное и транзитивное бинарное отношение является асимметричным.

Отношение R является отрицательно транзитивным тогда и только тогда, когда J

Vx, y, z G X из x R y следует x R z или z R y. (a) Доказательство: Доказательство свойств тривиально. С целью демонстрации техники доказательства мы докажем только третий пункт теоремы.

Предположим противное, т. е. пусть отношение R иррефлексивно, транзитивно, но не является асимметричным. Тогда найдется пара x, y G X такая, что x R y и y R x. Так как отношение R транзитивно, то из x R y и y R x следует x R x. Получили противоречие с иррефлексивностью. ?

Пример 3 (продолжение Примера 1):

Нам осталось проверить свойство отрицательной транзитивности. Для его проверки воспользуемся представлением этого свойства из только что доказанного утверждения. Для этого из множества X возьмем трех произвольных студентов a, b, c, чей рост составляет h(a), h(b) и h(c) соответственно, причем выполнено h(a) > h(b). Очевидно, что каким бы ни был h(c), должно быть выполнено хотя бы одно из неравенств h(a) > h(c) или h(c) > h(b). Таким образом, видим, что для данного отношения R выполнено свойство отрицательной транзитивности. Д

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

Читать еще:  Игра на акциях на бирже
Ссылка на основную публикацию
ВсеИнструменты
Adblock
detector
×
×