Дискретная математика. Кулаков Ю.В - 17 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Двойственным к частично упорядоченному множеству называется частично упорядоченное множе-
ство, определенное на том же носителе с помощью обратного отношения. На рис. 9, б изображена диа-
грамма, являющаяся двойственной к диаграмме Хассе (рис. 9, а).
Другим важным бинарным отношением является отношение эквивалентности. Бинарное отноше-
ние, обладающее свойствами рефлексивности, симметричности и транзитивности, называется отноше-
нием эквивалентности и обозначается ∼ .
Классом эквивалентности K(m
a
) элемента m
a
называется множество всех элементов m
i
, каждый из
которых находится с этим элементом в отношении эквивалентности
K(m
a
) = { m
i
/ m
i
∼ m
a
}.
Два различных класса эквивалентности K(m
x
) и K(m
y
) не пересекаются: K(m
x
) ∩ K(m
y
) = ∅.
Представление множества M в виде попарно непересекающихся подмножеств {M
i
} будем называть
разбиением этого множества:
U
i
i
M
= M,
M
a
i
∩
M
b
i
= ∅, i
a
≠ i
b
.
Таким образом, классы эквивалентности образуют разбиение множества.
Тестом распознавания отношения эквивалентности, заданного матрицей смежности, может быть приве-
дение матрицы с помощью перестановки строк и столбцов к клеточному виду, когда около главной диа-
гонали расположены подматрицы, состоящие из единиц, а остальные элементы матрицы равны нулю.
На рис. 10 приведен пример клеточной матрицы, в которой подматрицы, состоя-
щие из единиц, заштрихованы. Каждая заштрихованная подматрица соответству-
ет классу эквивалентности. Следовательно, данная матрица представляет отно-
шение эквивалентности с тремя классами эквивалентности.
Графы, представленные на рис. 7, а, б, в, задают от-
ношения эквивалентности с тремя, двумя и одним классами соответственно.
Аналогично бинарному отношению определим n-арное отношение.
Декартово произведение n равных между собой множеств M называется n-й
степенью M
n
множества M. Под n-арным отношением T в множестве M пони-
мается подмножество T его n-й степени T ⊂ M
n
. Если элементы
1
i
m ,
2
i
m , ...,
n
i
m
принадлежат множеству M, последовательность (
1
i
m ,
2
i
m , ...,
n
i
m
) − множеству T, то говорят, что
элементы
1
i
m ,
2
i
m , ...,
n
i
m
находятся в отношении T. Любое n-арное отношение может быть задано пере-
числением элементов.
Рассмотрим свойство симметричности n-арных отношений, позволяющее эффективно использовать
n-арные отношения при формализации практических задач. Симметричным называется n-арное отно-
шение T в множестве M такое, что если последовательность (
1
i
m ,
2
i
m , ...,
n
i
m
) ∈ T, то и любая последова-
тельность (
1
j
m ,
2
j
m , ...,
n
j
m ), полученная из (
1
i
m ,
2
i
m , ...,
n
i
m ) перестановкой элементов, также принадле-
жит T.
По существу, n-арное отношение, обладающее свойством симметричности, задает подмножества,
которые состоят из n элементов – подмножества мощности n. В дальнейшем n-арное отношение, обла-
дающее свойством симметричности, будем называть S-ричным отношением или S-отно-шением. Эле-
менты множества M, в котором определено S-отношение, будем называть буквами, а подмножества, опре-
деляемые S-отношением, –
словами.
Однозначно задать S-отношение можно перечислением элементов, матрицей инцидентности, мо-
дельным графом (мографом), гиперграфом и двудольным графом.
Матрицей инцидентности Q = [q
ij
] называется двумерная матрица,
j-му столбцу которой взаимно однозначно соответствует буква m
j
, i-й строке – слово µ
i
, определяемое S-
отношением, и
q
ij
=
µ∈
.случаепротивномв,0
;если,1
ij
m
Рис. 10

Страницы