Выяснить какими свойствами обладает бинарное отношение

Рассмотрим отношение «уважать», определенное на множестве всех людей %%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~R~a%%.
$$
begin{array}{l}
forall ain M~~a~R~a text{ или}\
forall ain M~~(a,a) in R.
end{array}
$$

Примеры

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

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

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

$$
begin{array}{l}
forall a,bin M~~a~R~b rightarrow b~R~a text{ или}\
forall a,bin M~~(a,b) in R rightarrow (b,a) in R.
end{array}
$$

Примеры

Рассмотрим отношение больше на множестве действительных чисел. Является ли отношение больше симметричным? Оно не является симметричным, так как если %%a > b%%, то условие %%b > a%% не выполняется. Поэтому отношение больше не симметрично.
Пусть %%R%% — отношение, определенное на множестве %%M = {a,b,c}%%. При этом %%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~R~b%% и %%b~R~c%% следует условие %%a~R~c%%.

$$
begin{array}{l}
forall a,b,cin M~~a~R~b land b~R~c rightarrow a~R~c text{ или}\
forall a,b,cin M~~(a,b) in R land (b,c) in R rightarrow (a,c) in R.
end{array}
$$

Пример

Рассмотрим отношение больше на множестве дейтсвительных чисел. Оно является транзитивным, так как для любых элементов выполняется условние %%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~R~b%% и %%b~R~a%% следует условие %%a = b%%.

$$
begin{array}{l}
forall a,b,cin M~~a~R~b land b~R~a rightarrow a = b text{ или}\
forall a,bin M~~(a,b) in R land (b,a) in R rightarrow a = b.
end{array}
$$

Пример

Отношение больше или равно на множестве действительных чисел антисимметрично. Действительно, если %%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~R~a%%. Тогда рассмотрим отрицание рефлексивности как истинное высказывание %%overline{forall a in M~~a~R~a}%%. Используем равносильность %%overline{forall x P(x)} equiv exists x overline {P(x)}%%. В нашем случае получаем %%forall a in M~~a~R~a equiv exists ain M~~a~nottext{R }~a%%, что и нужно.

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

%%R%% не рефлексивно тогда и только тогда, когда
$$
exists a in M~~a~not R~a
$$
%%R%% не симметрично тогда и только тогда, когда
$$
exists a, b in M~~ a~R~b land b~not R~a
$$
%%R%% не транзитивно тогда и только тогда, когда
$$
exists a, b, c in M a~R~b land b~R~c land a~not R~c
$$
%%R%% не антисимметрично тогда и только тогда, когда
$$
exists a, b in M~~ a~R~b land b~R~a land a neq b.
$$

Источник

Пусть
задано на множестве,
.

1.
Рефлексивность:

Отношение на
множествеXназываетсярефлексивным, если для любогоимеет место,
то есть каждый элемент находится в
отношениик
самому себе.

Матрица рефлексивного отношения имеет
единичную главную диагональ, а граф
рефлексивного отношения – имеет петлю
возле каждого своего элемента.

Например:

На множестве людей: “быть родственником”,
”обучаться в одной студенческой группе
”.

На множестве множеств: AB, A=B.

2. Антирефлексивность: .

Отношение на
множествеXназываетсяантирефлексивным, если не
существуеттакого, чтоимеет место,
то есть ни один элемент не находится
в отношениик самому себе.

Матрица антирефлексивного отношения
имеет нулевую главную диагональ, а граф
– не имеет ни одной петли.

Например:

На множестве людей: “быть родителем”,
”быть ребенком”.

На множестве множеств: AB, AB.

3. Нерефлексивность:.

4. Симметричность: .

Отношение на
множествеXназываетсясимметричным, если для всехииз Х, из принадлежности(x,y)
отношениюследует, чтои
принадлежит отношению.

Матрица симметричного отношения
симметрична относительно главной
диагонали, а граф – для
каждой дуги (x,y)
существует обратная дуга(y,x).

Выяснить какими свойствами обладает бинарное отношение

Например:

На множестве людей: “быть родственником”,
”обучаться в одной студенческой группе
”. Отношение
«брат»
является симметричным
на множестве
мужчин и не является
симметричным на
множествевсех людей.

На множестве множеств:
,.

5. Антисимметричность: .

Отношение на
множествеXназываетсяантисимметричным, если для всехииз Х, из принадлежности(x,y)
и(y,x)
отношениюследует, что.

Матрица антисимметричного отношения
не имеет ни одной симметричной единицы
относительно главной диагонали, а граф
– длякаждой
дуги (x,y)
не существует
обратная дуга(y,x)
и наоборот.

Выяснить какими свойствами обладает бинарное отношение

Свойства симметричности и антисимметричности
не являются взаимоисключающими, примером
может служить отношения равенства на
множестве натуральных чисел.

Например:

На множестве людей: “быть выше”, ”быть
равным”.

На множестве множеств:
,,.

6. Транзитивность: .

Отношение
на множественазываетсятранзитивным, если для
всехизмножества
,из принадлежностииотношениюследует, чтотакже принадлежит.

Выяснить какими свойствами обладает бинарное отношение

Например:

На множестве людей: “быть выше”,
”обучаться в одной студенческой группе”.

На множестве множеств:
,
,
.

Отношение rна множестве Xнеявляется
транзитивным,если
существует, хотя бы один пример того,что для некоторых х,y,zмножества Х
из принадлежности (x,y)
и(y,z)
отношениюrне
следует,что (x,z)такжепринадлежитr.

Например.

1)
.

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

2) Пусть задано двухэлементное
множество определим
все бинарные отношения на этом множестве:
.
Для всех отношений, заданных на множестве
,
определить наличие или отсутствие
основных свойств.

Введем следующие обозначения:

а) рефлексивность– Р;

б) антирефлексивность– АР;

в) симметричность– С;

г) антисимметричность– АС;

д) транзитивность– Т.

№	Р	АР	С	АС	Т
1	—	+	+	+	+
2	—	—	+	+	+
3	—	+	—	+	+
4	—	+	—	+	+
5	—	—	+	+	+
6	—	—	—	+	+
7	—	—	—	+	+
8	+	—	+	+	+
9	—	+	+	—	—
10	—	—	—	+	+
11	—	—	—	+	+
12	—	—	+	—	—
13	+	—	—	+	+
14	+	—	—	+	+
15	—	—	+	—	—
16	+	—	+	—	+

Отношение порядка– антисимметрично,
транзитивно.

Отношение нестрого порядка()
– рефлексивно,
антисимметрично,

транзитивно.

Например:

На множестве множеств:
,.

Отношение строгого порядка()
– антирефлексивно,
антисимметрично,

транзитивно.

Например:

На множестве множеств: “”.

— “xпредшествуетyв смысле
отношения строгого порядка”,

— “xпредшествуетyв смысле
отношения нестрогого
порядка”.

Два элементаи
некоторого упорядоченного множества
(множества, на котором существует
отношение порядка) сравнимы
между собой, если

предшествует
,
и/или
предшествует
в смыслеотношения
порядка.

Если в упорядоченном множестве
существует пара элементов xиy,
для которойни
непредшествует
,
ни
не предшествует
,
тогда говорят, что эти два элементанесравнимы
между собой в смысле этого.

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

Например:

Отношения полного порядка:

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

на множестве множеств:
,
,.

Отношение эквивалентности( 
) – рефлексивно,

симметрично,

транзитивно.

Класс эквивалентностидля элемента:.

Например:

На множестве людей: “иметь
одно имя”, ”обучаться в
одной студенческой группе”.

На множестве множеств:
.

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

Элементы, принадлежащие
одному классу, находятсямежду собой в отношении
эквивалентности, элементы из разных
классов в отношении эквивалентности
между собой не находятся.

Например:

Отношение
задано на множествесписком пар.

Область определения:
.

Область значений:
.

Отношение
– рефлексивно, симметрично, транзитивно,
следовательно, это отношение
эквивалентности.

Классы эквивалентности:

Например:

Отношение .

Это отношение называют отношением
сравнения по модулюна множестве натуральных чисел.

означает, чтоиимеют одинаковый остаток при делении
на.

Отрезок натурального ряда
.

Отношение сравнения по модулю 3 на
:

Область определения и область значений:

Отношение
– рефлексивно, симметрично, транзитивно.

Отношение
– отношение эквивалентности.

Классы эквивалентности:
.

Пусть

–некоторое
бинарное отношение.

Обратным отношением называется отношение, которое
определяется следующим образом:

Обратное отношение получается путём
перестановки значений в парах исходного
отношения.

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

Композиция отношений

и
– это таке
бинарное отношение которое состоит из
упорядоченных пар
для которых существует
такой элемент, что выполняются
условия:

Выяснить какими свойствами обладает бинарное отношение

Например.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

Способы задания бинарного отношения

Определение бинарного отношения

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

Пусть среди трех людей: Андрей (А), Василий (В) и Сергей (С) двое знакомы друг с другом (Андрей и Василий) и знают третьего – Сергея, но Сергей их не знает. Как описать отношения между этими людьми?

Имеем исходное множество Х = {А, В, С}. Далее из элементов множества Х составим упорядоченные пары:
(А, В), (В, А), (А, С), (В, С). Это множество пар и описывает связи между элементами множества X. Кроме того, множество этих пар есть подмножество декартова произведения X ´ X.

Определение. На множестве X задано бинарное отношение R, если задано подмножество декартова произведения X ´ X (т. е. R Ì X ´ X).

Пример 1. Пусть X = {1, 2, 3, 4}. Зададим на X следующие отношения:

Т = {(х, у) | х, у Î Х; х = у} – отношение равенства;

Р = {(х, у) | х, у Î Х; х = у — 1} – отношение

предшествования;

Q = {(х, у) | х, у Î Х; х делится на у} – отношение

делимости.

Все эти отношения заданы с помощью характеристического свойства. Перечислим элементы этих отношений для заданного множества X = {1,2,3,4}:

Т = {(1,1), (2,2), (3,3), (4,4)};

P = {(1,2), (2,3), (3,4) };

Q = {(4,4), (4,2), (4,1), (3,3), (3,1), (2,2), (2,1), (1,1)}.

Тот факт, что пара (х, у) принадлежит данному отношению R, будем записывать: (х, у) Î R или xRy. Например, для отношения Q запись 4Q2 означает, что 4 делится на 2 нацело, т. е. (4,2) Î Q.

Областью определения Dr бинарного отношения R называется множество DR = {x | (х, у) Î R}.

Областью значений ЕR бинарного отношения R называется множество ЕR = {у| (х, у) Î R}.

В примере для отношения Р областью определения является множество DR = {1,2,3}, а областью значений является множество ЕR = {2,3,4}.

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

График отношения изображается в декартовой системе координат: на горизонтальной оси отмечается область определения, на вертикальной — область значений отношения. Элементу отношения (х, у) соответствует точка плоскости с этими координатами.

a б

Рис. 1.8. График отношения Q (а) и схема отношения Q (б)

Схема отношения изображается с помощью двух вертикальных прямых, левая из которых соответствует области определения отношения, а правая – множеству значений отношения. Если элемент (х, у) принадлежит отношению R, то соответствующие точки из DR и ЕR соединяются прямой.

Граф отношения R Ì X ´ X строится следующим образом. На плоскости в произвольном порядке изображаются точки — элементы множества X. Пара точек х и у соединяется дугой (линией со стрелкой) тогда и только тогда, когда пара (х, у) принадлежит отношению R.

Матрица отношения R Ì X ´ X – это квадратная таблица, каждая строка и столбец которой соответствует некоторому элементу множества X. На пересечении строки х и столбца у ставится 1, если пара (х, у) Î R; все остальные элементы матрицы заполняются нулями. Элементы матрицы нумеруются двумя индексами, первый равен номеру строки, второй – номеру столбца.

Пусть X = {х1, х2, …, хn} . Тогда матрица отношения
R Ì X ´ X имеет n строк и n столбцов, а ее элемент rij определяется по правилу:

1, если (xi, yj) Î R, где i = l, 2, …, n; j = l, 2, …, n.

0, если (xi, yj) Ï R.

Рис. 1.9. Граф отношения Q (а) и матрица отношения Q (б)

1. Отношение R на множестве X называется рефлексивным, если для всех х Î X выполняется условие (х, х) Î R. Отношение R на множестве Х называется нерефлексивным, если условие (х, х) Î R не выполняется хотя бы при одном х Î X .

2. Отношение R на множестве X называется симметричным, если из условия (х, у) Î R следует
(у, х) Î R. Отношение R на множестве X называется несимметричным, если для любых х, у Î X из условия (х, y) Î R следует (у, х) Ï R.

3. Отношение R на множестве X называется транзитивным, если для любых х, у, z Î R из одновременного выполнения условий (x, y) Î R и (у, z) Î R следует (х, z) Î R .

Пример. Рассмотрим следующие отношения на множестве X = {1,2,3,4,5,6,7}:

G = {(x, y) | х, у Î Х; х > у};

L = {(х, у) | х, у Î Х; х £ у};

M = {(x, y) | х, у Î X; (х — у) делится на 3};

К = {(х, y) | х, у Î Х; х2 + у2 £ 20}.

Исследуем, какими свойствами они обладают.

Среди приведенных в примере отношений рефлексивнымиявляются отношение L (т. к. х £ х справедливо при всех х Î X) и отношение М (т. к. х — х = 0 делится на 3, поэтому пара (х, х) принадлежит отношению М при всех х Î X).

Симметричными являются отношения М (если х — у делится на 3, то и у — х делится на 3) и К (если х2 + у2 £20, то и у2 + х2 £ 20).

Транзитивными являются отношения G, L, М.

Источник

Рассмотрим
специальные
свойства бинарных отношений на множестве
A.

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

1. Отношение 
на AA
называется рефлексивным,
если (a,a)
принадлежит 
для всех a
из A.

2. Отношение 
называется антирефлексивным,
если из (a,b)
следует ab.

3. Отношение 
симметрично,
если для a
и b,
принадлежащих A,
из (a,b)
следует, что (b,a).

4. Отношение 
называется антисимметричным,
если для a
и b
из A,
из принадлежности (a,b)
и (b,a)
отношению 
следует, что a=b.

5. Отношение 
транзитивно,
если для a,
b
и c
из A
из того, что (a,b)
и (b,c),
следует, что (a,c).

Пример ..

Отношения
«=» и «£»
являются рефлексивными отношениями
на множестве N, но отношение «<» таковым
не является.

Отношение
«=» является симметричным, а «<» и «£»
— нет.

Отношение
на N
«являются взаимно простыми» является
симметричным.

Отношения
«<», «£»
и «=» являются транзитивными, а отношение

= {(a,b):
a,b
ÎN
и b
= a+1}
– нет, так как 34
и 45,
но не 35.

Выяснить какими свойствами обладает бинарное отношение

Как по матрице представления определить свойства бинарного отношения

1. Рефлексивность:
на главной диагонали стоят все единицы,
звездочками обозначены нули или единицы.

Выяснить какими свойствами обладает бинарное отношение .

2.
Антирефлексивность:
на главной диагонали все нули.

3. Симметричность:
если
.

Антисииметричность:

Mij=1,
i
≠j,
Mji=0

Матрицы бинарных отношений

Рассмотрим
два конечных множества A
={a1,a2,…,am}
и B={b1,b2,…,bn}
и бинарное отношение
.

Определим
матрицу
размераm×n
бинарного отношения Р по следующему
правилу:

Выяснить какими свойствами обладает бинарное отношение

Полученная
матрица содержит полную информацию о
связях между элементами.Любая матрица,
состоящая из 0 и 1, является матрицей
некоторого бинарного отношения.

П Выяснить какими свойствами обладает бинарное отношение РИМЕР
1. Матрица бинарного отношения,A={1,2,3},
заданного на рисунке

имеет
вид Выяснить какими свойствами обладает бинарное отношение

Основные
свойства матриц бинарных отношений:

Если
тои
,
где сложение осуществляется по правилам
0+0=0, 1+1=0+1=1+0=1, а умножение – обычным
способом.

Итак,

Матрица
получается перемножением соответствующих
элементов изи:.
Если
,
то
,
где умножение матриц производится по
обычному правилу умножения матриц, но
произведение и сумма элементов – по
определённым в свойстве 1 правилам.
Матрица
обратного отношения Р-1
равна транспонированной матрице
отношения Р:
.
Если
,
то.
Матрица
тождественного отношения idA
единична:

Выяснить какими свойствами обладает бинарное отношение

ПРИМЕР
2. Пусть
— матрицы отношений P и Q. Тогда

ПРИМЕР
3.

Если
Выяснить какими свойствами обладает бинарное отношение ,
то

Рассмотрим
свойства отношений на языке матриц.

Пусть
Р – бинарное отношение на множестве
.

Отношение
Р:

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

ПРИМЕР
4. Проверим, какими свойствами обладает
отношение
Выяснить какими свойствами обладает бинарное отношение