Ім'я файлу: Дискретна математика. Методичний посібник.pdf
Розширення: pdf
Розмір: 1376кб.
Дата: 22.04.2021
скачати

23
Розв’язок.
Відношення R є рефлексивним. Перевіримо, чи є воно антисиметричним. Знайдемо обернене йому відношення
     

       

1
,
, ,
,
,
,
,
,
,
, ,
,
,
A
R
d b
e a
b a
d a
d c
e b
c a
I



. Тоді
1
A
R
R
I

 
, а, отже, відношення R є антисиметричним. Перевіримо транзитивність.
                    
  


2
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
, ,
R
a a
a b
a c
a d
a e
b b
b d
b e
c c
c d
d d
e e
R


Тому відношення R є транзитивним.
Отже, відношення R є відношенням часткового порядку.
Зобразимо діаграму Хассе частково впорядкованої множини


,
A R . Відповідна діа- грама наведена на рис. 11.
Рис. 11. Діаграма Хассе
З діаграми Хассе видно, що елемент а є найменшим елементом впорядкованої множини


,
A R
, а, отже, єдиним мінімальним елементом.
Елементи e та d — максимальні елементи впорядкованої множини


,
A R
, а най- більший елемент не існує.
Оскільки
 
sup
,
e d не існує, то впорядкована множина


,
A R не є ґраткою.
Нарешті, з діаграми Хассе видно, що
 
 
inf
,
, sup
,
b c
a
b c
d


2.6. Задачі для самостійного розв’язування
1. Операції над відношеннями
1) Нехай






, , ,
,
1,2,5,7,8 ,
, , , ,
A
k l m n
B
C
a b c d e



,
         
{ ,1 ,
,2 ,
,1 , ,5 , ,8 ,
R
k
n
n
l
l


 
  
,2 ,
,8 ,
,7 }
m
m
k
,
       


2,
, 7,
, 8,
, 5,
S
b
c
b
e

, T
S R

. Задати відношення Т за допомогою матриці та графу і знайти
 




1 2
\
,
\ pr
A T
c e
C
T






2) Нехай






, , ,
,
1,2,3,4 ,
, , , , ,
A
k l m n
B
C
x y z t u v



,
       

1,
, 2,
, 2,
, 2, ,
S
u
x
z
t

 
4,
,
x
 

4,v
, T
S R

і матриця відношення R має вигляд

24
 
0 1
1 1
0 0
0 0
1 0
0 0
1 0
1 0
M R













Задати відношення T за допомогою графу і знайти
 




1 2
\
,
\ пр
C T
l n
A
T






3) Нехай






, , , ,
,
1,2,5,7,8 ,
, , , ,
A
k l m n p
B
C
a b c d e



,
     

   
,1 ,
,2 ,
,1 , ,5 , ,8 ,
R
k
n
n
l
l


 
  

,2 ,
,8 ,
,7
m
m
k
,
       


2,
, 7,
, 8,
, 5,
S
b
c
b
c

, T
S R

. Задати відношення Т за допомогою матриці та графу і знайти
 




1 2
\
\ pr
A T
b
C
T


4) Нехай






, , ,
,
1,2,5,7,8 ,
, , , ,
A
k l m n
B
C
a b c d e



,
        

{ ,2 ,
,1 ,
,2 , ,1 ,
,2 ,
R
k
n
n
l
m


  
,8 ,
,8 }
m
k
, відношення
S
B C
 
задане за допомогою матриці
 
0 0
0 0
0 1
1 0
0 0
0 0
0 0
1 0
0 1
0 1
0 1
0 0
0
M S

















,
T
S R

. Задати відношення Т за допомогою матриці та графу і знайти
 




1
\
2,5
\ pr
C T
A
T





5) Нехай






, , , ,
,
1,2,5,7,8 ,
, , , ,
A
k l m n p
B
C
a b c d e



,
     

   
1,
, 2,
, 1,
, 5, , 8, ,
R
k
n
n
l
l


 
  

2,
, 8,
, 7,
m
m
k
,
       


2,
, 7,
, 8,
, 5,
S
b
c
b
c

,
1
T
S R


. Задати відношення Т за допомогою матриці та графу і знайти
 




1 1
\
,
\ pr
A T
k p
C
T






6) Нехай R — однорідне бінарне відношення на множині


1,2,4,5,7,8
A

, задане за до- помогою матриці
 
0 1
0 1
1 1
0 0
0 0
0 0
1 0
0 0
1 0
0 0
1 0
0 0
0 0
0 0
1 1
1 0
0 0
0 0
M S








 









Задати відношення
2
\
R
R за допомогою матриці та графу та вказати його проекції.
7) Нехай R — бінарне відношення "<", визначене на множині
. Знайти
m
R , де m

8) Нехай R — бінарне відношення подільності на множині
. Знайти
m
R , де m

9) Навести приклад непорожнього бінарного відношення, квадрат якого — порожня множина.

25 10) Навести приклад бінарного відношення R, такого що
2 2
,
R
R
R
 
  
2. Властивості однорідних бінарних відношень
1) Встановити властивості однорідного бінарного відношення
 


2 2
,
|
1
R
x y
x
y



, заданого на множині .
2) Встановити властивості наступних однорідних бінарних відношень на множині дійсних чисел а)
 


,
|
R
x y
x
y


; б)
 


,
|
1
R
x y
xy


; в)
 


,
|
0
R
x y
xy


; г)
 


2 2
,
|
R
x y
x
y


3) Задати однорідні бінарні відношення, діаграми яких наведені на рис. 12, переліком їх елементів та встановити їх властивості.
Рис. 12.
4) Задати за допомогою матриці та графу мінімальне за кількістю елементів бінарне від- ношення R на множині


, , , , ,
A
a b c d e f

, яке є антирефлексивним, не є симетричним та не є транзитивним. Знайти першу та другу проекції відношення
2
\
R
R та вказати фактор-множину множини А за відношенням R.
5) Задати за допомогою матриці та графу мінімальне за кількістю елементів бінарне від- ношення R на множині


, , , , ,
A
a b c d e f

, яке є рефлексивним, симетричним та не є транзитивним. Знайти першу та другу проекції відношення
2
\
R
R та вказати фактор- множину множини А за відношенням R.
6) Для однорідного бінарного відношення
     


1,2 , 1,3 , 2,5
R

, визначеного на мно- жині


1,2,3,4,5
A

, побудувати його замикання S, яке є симетричним та транзи- тивним одночасно. Вказати матрицю замикання та знайти
 
1, 4
S




7) Для однорідного бінарного відношення
             


,
,
,
,
,
,
,
,
,
, ,
,
,
R
a a
a b
b c
b d
c e
e d
c b

, визначеного на множині


, , , , ,
A
a b c d e f

, побудувати його замикання, яке є рефлексивним та транзитивним одночасно. Вказати матрицю відношення
1
S

та знайти


, ,
S
b d f





26 8) Побудувати рефлексивне, антисиметричне та транзитивне замикання S однорідного бінарного відношення
     


,
,
,
,
,
R
a b
b c
c a

, визначеного на множині


, , ,
a b c d .
9) Зобразити графи
1) симетричного;
2) рефлексивного та транзитивного;
3) лінійного замикань бінарних відношень, графи яких зображені на рис. 13.
Рис. 13.
10) Для однорідного бінарного відношення
        



,
,
,
,
,
,
,
,
,
R
d b
a a
a b
b d
c f

, визна- ченого на множині


, , , , ,
A
a b c d e f

, побудувати його симетричне та транзитивне замикання S. Вказати матрицю відношення
1
\
T
S R


та знайти


, ,
T
a e f




3. Відношення еквівалентності
1) З’ясувати, які з наступних бінарних відношень є відношеннями еквівалентності, та вказати для них класи еквівалентності: а) паралельність площин у просторі; б) відношення знайомства на множині людей; в) відношення бути "одногрупниками"; г) відношення рівнопотужності.
2) Задати за допомогою графа та матриці бінарне відношення еквівалентності R на мно- жині


, , , , , ,
A
a b c d e f g

, якщо фактор-множина A/R рівна

      


, ,
,
,
,
,
a e f
b d
c
g
3) Визначити, які з графів, наведених на рис. 14, відповідають відношенням еквіва- лентності.
Рис. 14.

27 4) Перевірити, чи є визначене на множині


, , , , , ,
A
x y z t u v w

бінарне відношення
      
 
     
 
   
 
  

,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
R
u x
u u
y z
w w
y y
z y
z z
z w
y w
x u
w y
w z
x x

   

,
, ,
v v
t t
відношенням еквівалентності. Якщо так, то знайти фактор-множину A/R
множини А за відношенням R.
5) Перевірити, чи є визначене на множині


, , , , , ,
A
a b c d e f g

бінарне відношення
     
            
        


b
f
a
a
e
e
b
c
f
f
f
c
g
g
c
c
a
g
c
b
d
d
c
f
b
b
g
a
f
b
R
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
),
,
(
,
,
,
,
,
,

відношенням еквівалентності. Якщо так, то знайти фактор-множину A/R.
6) Перевірити, чи є визначене на множині


, , , , , ,
A
a b c d e f g

бінарне відношення

 
   
   
   
 
 
    

,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,( , ),
R
b f
a g
b b
d d
b c
g a
c c
g g
c f
f f
c b
e e
f c

  


,
,
,
a a
f b відношенням еквівалентності. Якщо так, то знайти фактор-множину A/R.
7) Навести приклад визначеного на множині
 
0,1
бінарного відношення еквівалентності, яке має рівно 5 класів еквівалентності.
8) Навести приклад визначеного на множині бінарного відношення еквівалентності, яке має рівно 13 класів еквівалентності.
9) Вказати найменше за кількістю елементів бінарне відношення S, яке є відношенням еквівалентності на множині


1,2,3,4,5,6,7
та містить у собі відношення
         


2,1 , 1,5 , 3,6 , 7,5 , 3,3
R

. Знайти фактор-множину A/S.
10) Вказати найменше за кількістю елементів бінарне відношення S, яке є відношенням еквівалентності на множині


1,2,3,4,5,6,7
та містить у собі відношення
         


6,6 , 5,2 , 1,5 , 6,3 , 5,7
R

. Знайти фактор-множину A/S.
4. Відношення порядку
1) Вказати, які з наступних бінарних відношень є відношеннями порядку, часткового строгого та лінійного порядку. Відповідь обґрунтувати. а) відношення знайомства на множині людей; б) відношення "бути старшим"; в) відношення "бути сином"; г) відношення "бути предком".
2) Вказати, які з наступних бінарних відношень є відношеннями порядку, часткового строгого та лінійного порядку. Відповідь обґрунтувати. а) відношення "бути нащадком"; б) відношення "бути молодшим"; в) відношення "знаходитися на більшій відстані від початку координат" на множині точок площини; г) відношення "бути родичем" на множині людей.
3) Задати переліком елементів бінарне відношення часткового порядку, якому відповідає впорядкована множина


,
A R , діаграма Хассе якої наведена на рис. 15. Вказати екстремальні елементи відповідних множин. Знайти


sup 2,4,5 ,


inf 4,25 та ви- значити множину усіх нижніх граней множини


12, 20 і множину усіх верхніх граней множини, яка складається з максимальних елементів впорядкованої множини


,
A R .

28
Рис. 15.
4) На рис. 16 наведені діаграми Хассе частково впорядкованих множин. Які з цих мно- жин є ґратками?
Рис. 16.
5) Побудувати мінімальне за кількістю елементів бінарне відношення на множині
A



1,2,3,4

, яке було би відношенням: а) порядку; б) нестрогого порядку; в) строгого порядку; г) лінійного порядку та вказати екстремальні елементи множини А за побудованим відношенням.
6) Для однорідного бінарного відношення
     


,
,
,
,
,
R
c a
b d
d c

, визначеного на мно- жині


, , , ,
A
a b c d e

, побудувати мінімальне за кількістю елементів бінарне від- ношення S, яке б було відношенням: а) порядку; б) нестрогого порядку; в) строгого порядку; г) лінійного порядку та містило у собі відношення S. Вказати екстремальні елементи впорядкованої мно- жини


,
A S .
7) Перевірити, чи є бінарне відношення
         


2,1 , 4,1 , 1,3 , 5,1 , 4,3
A
R
I



     


2,3 , 5,3 , 5,4

відношенням часткового порядку на множині


1,2,3,4,5
A

Якщо так, то зобразити діаграму Хассе множини


,
A R та вказати її екстремальні еле- менти.
8) Перевірити, чи є бінарне відношення R з матрицею

29
 
0 1
0 0
0 0
0 0
0 0
0 1
0 0
0 1
1 0
0 1
1 1
0 0
0
M R

















відношенням строгого порядку на множині


, , , ,
A
x y z u v

. Якщо так, то зобразити діаграму Хассе відношення R та вказати екстремальні елементи множини А за відно- шенням нестрогого порядку, яке відповідає відношенню R.
9) Перевірити, чи є відношення


A
S
R
R
I


відношенням строгого порядку на мно- жині


, , , , , , ,
A
a b c d e f g h

, якщо
            



,
,
,
,
,
,
,
,
,
,
,
,
,
R
b g
a e
c g
b c
a b
c e
d f

Якщо так, то а) зобразити діаграму Хассе відношення S; б) вказати екстремальні елементи множини А за відношенням S; в) знайти


inf
, ,
b g e
та


sup
, ,
a b h
10) Знайти екстремальні елементи частково впорядкованої множини, діаграма Хассе якої наведена на рис. 17, знайти
 
sup
,
e i та
 
inf
,
i m .
Рис. 17. Діаграма Хассе

30

1   2   3   4   5   6   7

скачати