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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Отношение T в множестве M называется антитранзитивным, если
(∃a, b, с ∈ M, a ≠ b, a ≠ c, b ≠ c) ((a, b) ∈ T и (b, c) ∈ T) и
(∀a, b, с ∈ M, a ≠ b, a ≠ c, b ≠ c) ((a, b) ∈ T, (b, c) ∈ T → (a, c) ∉ T).
Антитранзитивными бинарными отношениями в множестве M = {a, b, c} являются отношения, пред-
ставленные на рис. 7, г, н.
Отношение T в множестве M будем называть нетранзитивным, если оно не является ни транзитив-
ным, ни антитранзитивным. Нетранзитивными являются отношения на рис. 7, е, м.
Используя эти свойства, определим бинарное отношение упорядоченности, имеющее большое тео-
ретическое и практическое значение.
Бинарное отношение R в множестве M, обладающее свойствами рефлексивности, антисимметрич-
ности и транзитивности, называется отношением упорядоченности и обозначается символом ≤ . Отно-
шениями упорядоченности ≤ являются отношения, заданные графами на рис. 7, ж, з.
Бинарное отношение в множестве M, обладающее свойствами антирефлексивности, антисиммет-
ричности и транзитивности, называется отношением строгой упорядоченности и обозначается симво-
лом < . Отношения строгой упорядоченности представлены на рис. 7, д, и.
Отношение, обладающее свойствами рефлексивности и транзитивности, называется отношением
предпорядка. Отношение предпорядка задано графом на рис. 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
. Следовательно, отношение включения является отношением упорядоченности ≤ .
Множество M с заданным в нем отношением упорядоченности, называется упорядоченным этим от-
ношением.
Если любые два элемента m
i
и m
j
находятся в отношении упорядоченности, то это множество назы-
вают линейно упорядоченным, в противном случае – частично упорядоченным. Линейно упорядоченные
множества заданы на рис. 7, д, ж; частично упорядоченные – на рис. 7, з, и.
На рис. 8 приведен пример частично упорядоченного множества, при этом в качестве отношения
упорядоченности рассмотрено отношение включения множеств ⊂ .
Иногда частично упорядоченные отношением ≤ множества изображают в виде графов H = 〈V, ≤〉, у
которых удалены все петли и транзитивно замыкающие дуги. Граф H = 〈V, ≤〉, задающий частично упо-
рядоченное множество с удаленными петлями и транзитивно замыкающими дугами, называется диа-
граммой Хассе. Диаграмма Хассе H, задающая частично упорядоченное множество, которое показано на
рис. 8, изображена на рис. 9, а.
Под изоморфизмом между двумя упорядоченными множествами M и M
*
будем понимать взаимно
однозначное соответствие η между M и M
*
такое, что из m
i
≤ m
j
следует η(m
i
) ≤ η(m
j
) и из η(m
i
) ≤ η(m
j
)
следует m
i
≤ m
j
.
Два упорядоченных множества называются изоморфными тогда и только тогда, когда между ними
существует изоморфизм.
Под отношением
R , обратном R, понимают такое отношение, при котором (m
i
, m
j
)∈ R тогда и
только тогда, когда (m
j
, m
i
) ∈ R.
Принцип, в соответствии с которым отношение, обратное отношению упорядоченности, также яв-
ляется отношением упорядоченности, называется принципом двойственности.
1={y, x, a}
1={y, x, a}
1=
{
y
,
x
, a
}
{y, x}
{y, x}
{y, x}
{y, a}
{y, a}
{y, a}
{a, x}
{a, x}
{a, x}
{y}
{y}
{y}
{x}
{x}
{x}
{a}
{a}
{a}
∅
∅
∅
Рис.
Рис. 9
а)
б)

Страницы