Дискретная математика. Элементы теории задачи и упражнения. Булгакова И.Н - 24 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

(
)
(
)
(
)
(
)
(
)
(
)
(
)
{
}
1,22,1,5,5,4,4,3,3,2,2,1,1
1
=
ρ
;
(
)
(
)
(
)
(
)
(
)
(
)
(
)
{
}
3,22,3,5,5,4,4,3,3,2,2,1,1
1
=
ρ
.
Объединение данных отношений эквивалентности
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
{
}
3,2,2,3,1,22,1,5,5,4,4,3,3,2,2,1,1
21
=
∪
ρ
ρ
не является отношением эквивалентности, так как для него не выполнено
свойство транзитивности (
(
)
21
2,3
ρ
ρ
∪
∈
,
(
)
21
1,2
ρ
ρ
∪
∈
, а
(
)
21
1,3
ρ
ρ
∪
∉
).
Пример 7. Докажите, что отношение
(
)
{
}
yxRRyx
≤
×
∈
=
:,
ρ
явля-
ется отношением порядка на множестве
R
, является ли это отношение от -
ношением линейного порядка .
Решение. Для доказательства проверим три свойства данного отно-
шения: рефлексивность, антисимметричность, транзитивность.
1. Рефлексивность.
(
)
ρ
∈
⇒
=
∈
∀
xxxxRx , .
2. Антисимметричность.
Пусть
(
)
ρ
∈
yx , и
()
yx
xy
yx
xy =⇒
≤
≤
⇒∈ ρ, .
3. Транзитивность.
Пусть
(
)
ρ
∈
yx , и
()()
ρρ ∈⇒≤⇒
≤
≤
⇒∈ zxzx
zy
yx
zy ,, .
Данное отношение является отношением линейного порядка , так как
для любых
R
x
∈
,
выполнено либо
x
≤
, либо
x
≤
.
Пример 8. Покажите , что композиция двух отношений
частичного порядка может не являться отношением
частичного порядка.
Решение. На множестве
{
}
5,4,3,2,1
=
Α
рассмотрим два отношения
частичного порядка
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
{
}
3,1,3,2,2,1,5,5,4,4,3,3,2,2,1,1
1
=
ρ
;
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
{
}
2,1,2,5,5,1,5,5,4,4,3,3,2,2,1,1
2
=
ρ
.
Однако композиция
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
{
}
2,1,2,5,5,1,3,2,2,1,3,1,5,5,4,4,3,3,2,2,1,1
12
=
ρ
ρ
o
не является отношением частичного порядка , так как для него нарушено
свойство транзитивности (
(
)
12
2,5
ρ
ρ
o
∈
,
(
)
12
3,2
ρ
ρ
o
∈
,
(
)
12
3,5
ρ
ρ
o
∉
).
Пример 9. Для следующих двух отношений частичного порядка по -
строить диаграммы Хассе.
1.
{
}
3,2,1
=
Α
,
(
)
(
)
(
)
{
}
yxyx
⊆
×
∈
=
:,
1
Α
Ρ
Α
Ρ
ρ
.
2.
{
}
30,15,10,6,5,3,2,1
=
Α
,
(
)
{
}
xнаделитсяyyx :,
2
Α
Α
×
∈
=
ρ
. 
      ρ1 ={(1,1), (2,2), (3,3), (4,4 ), (5,5 ), (1,2 )(2,1)};
      ρ1 ={(1,1), (2,2 ), (3,3), (4, 4), (5,5), (3,2 )(2,3)}.
Объединение данных отношений эквивалентности
      ρ1 ∪ ρ2 ={(1,1), (2,2), (3,3), (4,4), (5,5), (1, 2)(2,1), (3,2 ), (2,3)}
не является отношением эквивалентности, так как для него не выполнено
свойство транзитивности ( (3,2 )∈ρ1 ∪ ρ2 , (2,1)∈ρ1 ∪ ρ2 , а (3,1)∉ρ1 ∪ ρ2 ).

      Пример 7. Докажите, что отношение ρ ={(x, y )∈R ×R : x ≤ y} явля-
ется отношением порядка на множестве R , является ли это отношение от-
ношением линейного порядка.
      Решение. Для доказательства проверим три свойства данного отно-
шения: рефлексивность, антисимметричность, транзитивность.
1.       Рефлексивность.
∀x ∈R x =x ⇒ (x, x)∈ρ .
2.       Антисимметричность.
                                    � x ≤y
Пусть (x, y )∈ρ и (y , x )∈ρ ⇒ �            ⇒ x =y .
                                     � y ≤x
3.       Транзитивность.
                                  � x ≤y
Пусть (x, y )∈ρ и (y , z )∈ ρ ⇒ �           ⇒ x ≤z ⇒ (x , z )∈ ρ .
                                   � y ≤z
      Данное отношение является отношением линейного порядка, так как
для любых x, y ∈R выполнено либо x ≤ y , либо y ≤x .

 Пример 8. Покажите, что композиция двух отношений
  частичного порядка может не являться отношением
                    частичного порядка.
    Решение. На множестве Α ={1,2,3,4,5} рассмотрим два отношения
частичного порядка
      ρ1 ={(1,1), (2,2 ), (3,3), (4,4 ), (5,5), (1,2 ), (2,3), (1,3)} ;
      ρ2 ={(1,1), (2,2 ), (3,3), (4, 4), (5,5), (1,5 ), (5,2 ), (1,2 )}.
      Однако композиция
      ρ2  ρ1 ={(1,1), (2,2 ), (3,3), (4, 4), (5,5), (1,3), (1,2 ), (2,3), (1,5), (5, 2), (1,2)}
не является отношением частичного порядка, так как для него нарушено
свойство транзитивности ( (5,2 )∈ρ2  ρ1 , (2,3)∈ρ2  ρ1 , (5,3)∉ρ2  ρ1 ).

     Пример 9. Для следующих двух отношений частичного порядка по-
строить диаграммы Хассе.
1. Α ={1,2,3}, ρ1 ={(x, y )∈Ρ (Α )×Ρ (Α ) : x ⊆ y}.
2.   Α ={1,2,3,5,6,10,15,30}, ρ2 ={(x, y )∈Α ×Α : y делится на x}.

Страницы