Дискретная математика. Азарнова Т.В - 24 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Теория множеств
24
Решение. Для доказательства проверим три свойства данного
отношения: рефлексивность, антисимметричность, транзитивность.
1. Рефлексивность.
()
ρ
∈⇒=∈∀
xxxxRx
,
.
2. Антисимметричность.
Пусть
()
ρ
∈
yx
,
и
()
yx
xy
yx
xy =⇒
≤
≤
⇒∈
ρ
,.
3. Транзитивность.
Пусть
()
ρ
∈
yx
,
и
() ()
ρρ
∈⇒≤⇒
≤
≤
⇒∈ zxzx
zy
yx
zy
,,.
Данное отношение является отношением линейного порядка, так как
для любых
Ryx ∈
, выполнено либо
yx ≤
, либо
xy ≤
.
Задача 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
=
ρ
ρ
ο
не является отношением частичного порядка, так как для него нарушено
свойство транзитивности (
()
12
2,5
ρ
ρ
ο
∈
,
()
12
3,2
ρ
ρ
ο
∈
,
()
12
3,5
ρ
ρ
ο
∉
).
Задача 9.
Для следующих двух отношений частичного порядка
построить диаграммы Хассе.
1.
{}
3,2,1
=
Α
ΑΑ
Α
,
( ) () (){}
yxyx
⊆×∈=
:,
1
Α
ΑΑ
ΑΡ
ΡΡ
ΡΑ
ΑΑ
ΑΡ
ΡΡ
Ρ
ρ
.
2.
{}
30,15,10,6,5,3,2,1
=
Α
ΑΑ
Α
,
(){}
xнаделитсяyyx
:,
2
Α
ΑΑ
ΑΑ
ΑΑ
Α
×∈=
ρ
.
Решение.
{1,2,3}
{1,3}
{1}{2}
{2,3}
{3}
{1,2}
30
10
2
1
15
6
5
3
1.
2. 
                                               24
Теория множеств
     Решение. Для доказательства проверим три свойства данного
отношения: рефлексивность, антисимметричность, транзитивность.
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}.

Решение.

                             {1,2,3}                                    30


    {2,3}              {1,2}           {1,3}   15                   6          10

                       {3}
                                                                    5

            {2}                         {1}                                    2
                                                    3

                                                                        1
                     1.                                        2.

Страницы