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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

(
)
{
}
(
)
{
}
2:,,2:,
22
≤+==≤+∃= yxyxyzzxzyx ;
(
)
(
)
(
)
{
}
=
∈
∈
∃
=
2112
,,,:,
ρ
ρ
ρ
ρ
yzzxzyxo
()
{}
()
=
≤+−
≤+
≥=≤+=∃=
2
2
,0:,2,:,
2
yx
yx
xyxyzzxzyx
(
)
{
}
2,0:, ≤+−≥= yxxyx
;
(
)
(
)
(
)
{
}
=
∈
∈
=
2332
,,,:,
ρ
ρ
ρ
ρ
yzzxzyxo
(
)
{
}
=
≤
+
∈
+
∃
=
2,:, yzzxzyx
Ζ
(
)
{
}
(
)
{
}
RRyxkkyxyzkzxzyx
×
=
≤
+
−
∈
=
≤
+
∈
=
+
=
2:,2,:,
Ζ
Ζ
(
)
(
)
(
)
{
}
=
∈
∈
∃
=
3223
,,,:,
ρ
ρ
ρ
ρ
yzzxzyxo
(
)
{
}
RRyzzxzyx
×
=
∈
+
≤
+
∃
=
Ζ
,2:, .
Остальные композиции постройте самостоятельно.
Пример 10. Пусть
Χ
- произвольное множество, обозначим симво-
лом
Χ
Ι
отношение на множестве
Χ
вида
(
)
{
}
(
)
{
}
Χ
Ι
Χ
∈
=
=
=
xxxyxyx :,:, .
Докажите, что для любого бинарного отношения
ρ
между элементами
множеств
Α
и
Β
выполняются равенства :
ρ
ρ
ρ
ρ
=
=
ΑΒ
Ι
Ι
oo , .
Решение.
(
)
(
)
(
)
{
}
=
∈
∈
∈
∃
×
∈
=
ΒΒ
Ι
Β
Β
Α
Ι
yzzxzyx ,,,:,
ρ
ρ
o
(
)
(
)
{
}
(
)
(
)
{
}
;,:,,,:,
ρ
ρ
ρ
=
∈
×
∈
=
=
∈
∈
×
∈
=
yxyxyzzxzyx
Β
Α
Β
Β
Α
(
)
(
)
(
)
{
}
=
∈
∈
∈
∃
×
∈
=
ρ
ρ
yzzxzyx ,,,:,
ΑΑ
Ι
Α
Β
Α
Ι
o
(
)
(
)
{
}
(
)
(
)
{
}
.,:,,,:,
ρ
ρ
ρ
=
∈
×
∈
=
∈
=
∈
×
∈
=
yxyxyzzxzyx
Β
Α
Α
Β
Α
Пример 11. Пусть
χ
φ
ϕ
,
,
бинарные отношения, определенные на
множестве
Χ
. Докажите следующие утверждения:
1) если
φ
ϕ
,
- симметричные (антисимметричные ) отношения, то
(
)
1
−
∩φϕ - симметричное (антисимметричное) отношение;
2)
(
)
(
)
(
)
χ
φ
χ
ϕ
χ
φ
ϕ
ooo \\
⊇
.
Решение. 1. Пусть
φ
ϕ
,
- симметричные отношения, докажем , что
(
)
1−
∩φϕ
- симметричное отношение. Пусть
()()()
(
)
()
⇒
∈
∈
⇒∩∈⇒∩∈
−
φ
ϕ
φϕφϕ
xy
xy
xyyx
,
,
,,
1
(
)
()
()()()
;,,
,
,
1
,
−
∩∈⇒∩∈⇒
∈
∈
⇒ φϕφϕ
φ
ϕ
φϕ
xyyx
yx
yx
остьсимметричн
Пусть
φ
ϕ
,
- антисимметричные отношения, докажем , что
(
)
1−
∩φϕ
-
антисимметричное отношение. Пусть 
  {                              }{                  }
= (x, y ) : ∃z x +z ≤2, z = y 2 = (x, y ) : x + y 2 ≤2 ;
ρ2  ρ1 ={(x, y ) : ∃z (x, z )∈ρ1 , (z, y )∈ρ2 }=
                                      ��               � x +y ≤2 ��
  {                              }
= (x, y ) : ∃z x =z 2 , z + y ≤2 =� (x , y ) : x ≥0, �                � =
                                         ��             � − x +y ≤2��
  {
= (x, y ) : x ≥0, − x +y ≤2 ;}
ρ2  ρ3 ={(x , y ) : ∃z (x, z )∈ ρ3 , (z , y )∈ ρ 2 }=
={(x, y ): ∃z x +z ∈Ζ , z +y ≤2}=
={(x , y ): ∃z x +z =k ∈Ζ , z +y ≤2}={(x, y ) : ∃k ∈Ζ k −x +y ≤2}=R ×R
ρ3  ρ2 ={(x, y ) : ∃z (x, z )∈ρ2 , (z , y )∈ρ3 }=
={(x, y ) : ∃z x +z ≤2, z +y ∈Ζ }=R ×R .
       Остальные композиции постройте самостоятельно.

       Пример 10. Пусть Χ - произвольное множество, обозначим симво-
лом Ι Χ отношение на множестве Χ вида
                      Ι Χ ={(x, y ) : x =y}={(x, x ) : x ∈Χ }.
Докажите, что для любого бинарного отношения ρ между элементами
множеств Α и Β выполняются равенства:
                          Ι Β  ρ =ρ ,      ρ  Ι Α =ρ .
       Решение. Ι Β  ρ ={(x, y )∈Α ×Β : ∃z ∈Β (x, z )∈ρ, (z, y )∈Ι Β }=
={(x , y )∈Α ×Β : ∃z ∈Β (x , z )∈ ρ, z = y}={(x, y )∈Α ×Β : (x, y )∈ ρ}=ρ;
ρ  Ι Α ={(x, y )∈Α ×Β : ∃z ∈Α (x, z )∈Ι Α , (z , y )∈ρ}=
={(x , y )∈Α ×Β : ∃z ∈Α x =z, (z, y ) ∈ρ}={(x, y )∈Α ×Β : (x, y )∈ ρ}=ρ.

     Пример 11. Пусть ϕ , φ, χ бинарные отношения, определенные на
множестве Χ . Докажите следующие утверждения:
1)   если ϕ, φ - симметричные (антисимметричные) отношения, то
(ϕ ∩ φ)−1 - симметричное (антисимметричное) отношение;
2)    (ϕ \ φ) χ ⊇ (ϕ  χ ) \ (φ  χ ).
      Решение. 1. Пусть ϕ, φ - симметричные отношения, докажем, что
(ϕ ∩ φ)−1 - симметричное отношение. Пусть
                                                     � (y , x )∈ϕ
    (x, y )∈(ϕ ∩ φ)−1 ⇒ (y, x)∈ϕ ∩ φ ⇒ �                             ⇒
                                                      � ( y , x ) ∈φ
                              � (x , y )∈ϕ
     ⇒ симметричн ость ϕ ,φ �               ⇒ (x , y )∈ϕ ∩ φ ⇒ (y , x )∈(ϕ ∩ φ)−1 ;
                               � (x , y )∈φ
   Пусть ϕ, φ - антисимметричные отношения, докажем, что (ϕ ∩ φ)−1                    -
антисимметричное отношение. Пусть

Страницы