Дискретная математика. Громов Ю.Ю - 18 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

18
Бинарное отношение Т в множестве М называется симметричным
бинарным отношением, если
(∀ a, b ∈ M) ((a, b) ∈ T → (b, a) ∈ T
).
Матрица смежности симметричного отношения является симмет-
ричной относительно главной диагонали, а при задании отношения в
виде графа следствием симметричности является наличие между всякой
парой вершин, находящихся в отношении T, двух противоположно
направленных дуг (рис. 6, б). Симметричными бинарными отношения-
ми в множестве M = {a, b, c} являются отношения, представленные на
рис. 7, а, б, в.
Бинарное отношение Т в множестве М называется антисимметрич-
ным бинарным отношением, если
(∀ a, b ∈ M) ((a, b) ∈ T и (b, a) ∈ T → a = b).
Антисимметричными отношениями в множестве M = {a, b, c} явля-
ются бинарные отношения, представленные на рис. 7, д, ж, з, и, н.
Бинарное отношение T в множестве M называется транзитивным
бинарным отношением, если
(∀a, b, с ∈ M
) ((a, b) ∈ T и (b, c) ∈ T → (a, c) ∈ T
).
В графе, задающем транзитивное отношение T, для всякой пары дуг
таких, что конец первой совпадает с началом второй, существует третья
дуга, имеющая общее начало с первой и общий конец со второй дугой
(рис. 6, в), − транзитивно замыкающая дуга. Транзитивными бинарными
отношениями в множестве M = {a, b, c} являются все отношения, пред-
ставленные на рис. 7, кроме отношений г, е, м, н.
Используя эти свойства, определим бинарное отношение упорядочен-
ности, имеющее большое теоретическое и практическое значение.
Бинарное отношение R в множестве M, обладающее свойствами реф-
лексивности, антисимметричности и транзитивности, называется отноше-
нием упорядоченности и обозначается символом ≤ . Отношениями упоря-
доченности являются бинарные отношения, заданные на рис. 7, ж, з.
Бинарное отношение S в множестве M, обладающее свойствами анти-
рефлексивности, антисимметричности и транзитивности, называется от-
ношением строгой упорядоченности и обозначается символом < . Отно-
шения строгой упорядоченности представлены на рис. 7, д, и.
Рассмотрим отношение включения множеств ⊂ . Это отношение
рефлексивно: M
i
⊂ M
i
(множество M
i
включает само себя); антисимметрич-
но: если M
i
⊂ M
j
и M
j
⊂ M
i
, то M
i
= M
j
; транзитивно: если M
i
⊂ M
j
и M
j
⊂
M
k
, то M
i
⊂ M
k
. Следовательно, отношение включения множеств является
отношением упорядоченности.

Страницы