zadania_Relacje.pdf
(
78 KB
)
Pobierz
678781548 UNPDF
Matematykadyskretna-zadania
Zadanie1.
Sprawdzi¢,czydlaka»dejrelacjiokre±lonejwzbiorzeniepustymprawdziwes¡na-
st¦pujacezdania:
(a)je±lirelacjajestantysymetryczna,tojestantyzwrotna
(b)je±lirelacjajestsłaboantysymetryczna,tojestzwrotna
(c)je±lirelacjajestsłaboantysymetryczna,tojestantysymetryczna
(d)je±lirelacjajestantysymetryczna,tojestsłaboantysymetryczna
Rozwi¡zanie:
(a)
Załó»my,»erelacjajestantysymetryczna:dlaka»dych
x,y
2
X
jest(
x,y
)
2
)
(
y,x
)
/
2
.Wszczególno±cidla
x
=
y
dostajemyzdaniesprzeczne:(
x,x
)
2
)
(
x,x
)
/
2
,wi¦cpara(
x,x
)nienale»ydorelacji
.Azatemrelacjajestantyzwrotna.
(b)
Nie.Kontrprzykład:
Rozwa»myzbiór
X
=
{
1
,
2
}
irelacj¦
=
{
(1
,
2)
,
(2
,
2)
}
.Takokre±lonarelacjajest
słaboantysymetryczna,leczniejestzwrotna.
(c)
Nie.Kontrprzykład:
Rozwa»myzbiór
X
=
{
1
,
2
}
irelacj¦
=
{
(1
,
2)
,
(2
,
2)
}
.Takokre±lonarelacjajest
słaboantysymetryczna,leczniejestantysymetryczna.
(d)
Je±lirelacjajestantysymetryczna,to(
x,y
)
2
)
(
y,x
)
/
2
dlaka»dych
x,y
2
X
.
Wówczasnigdyniejestspełnionypoprzednikimplikacji(
x,y
)
2
^
(
y,x
)
2
w
okre±leniusłabejantysymetrii.St¡dimplikacjajestzawszeprawdziwa.
Zadanie2.
Pokaza¢,»erelacja
wzbiorzeXjestprzechodnia,gdy
.
Czymo»liwajestrówno±¢:
=
Rozwi¡zanie:(
)
)
Załó»my,»erelacja
jestprzechodnia.Niech(
a,b
)
2
.Wtedy:
_
ac
^
cb
c
2
X
Aleponiewa»
jestrelacj¡przechodni¡,to(
a,b
)
2
.Awi¦c
.
(
(
)
Załó»my,»e:
.Niech(
x,y
)
2
,awi¦c:
_
(
xz
^
zy
)
,
x
(
)
y
z
2
X
Alezzał.wynika,»e(
x,y
)nale»ydo
,awi¦c:(
xz
^
zy
)
)
xy
Równo±¢
=
jestmo»liwa.Np.dlarelacji
R
N
×
N
okre±lonejwnast¦puj¡cy
sposób:
xRy
,
2
|
x
+
y
.
Zadanie3.
Niechdanyb¦dzie
n
-elementowyzbiór
X
.
Ilemo»nawtymzbiorzezdefiniowa¢relacji:
a)zwrotnych,b)symetrycznych,c)antyzwrotnych,d)antysymetrycznych
e)słaboantysymetrycznych,f)zwrotnychisymetrycznych
g)antyzwrotnychisymetrycznych,h)zwrotnychisłaboantysymetrycznych
Rozwi¡zanie:(a)
Wszystkichrelacji,któremo»nazdefiniowa¢w
n
-elementowymzbiorze
X
jesttyle,
ilejestpodzbiorówzbioru
X
×
X
,awi¦c2
nn
.Je±lirelacjajestzwrotna,toka»dy
elementpostaci(
x,x
)nale»ydorelacji.Awi¦cmo»liwychrelacjizwrotnychjest:
2
n
(
n
−
1)
.
(b)
Niechrelacja
X
×
X
b¦dziesymetryczna.Wtedy
xy
)
yx
,dladowolnych
x,y
2
X
.Poł¡czmyelementyzbioru
X
×
X
wpary,takabydoka»dejparynale»ały
elementy(
x,y
)oraz(
y,x
)-dladowolnych
x,y
2
X
.Jest
n
elementów,którenie
posiadaj¡pary-s¡toelementypostaci(
x,x
).
Zatemliczbamo»liwychrelacjisymetrycznychwzbiorze
X
wynosi:2
n
+[
n
(
n
−
1)
/
2]
(c)
Je±lirelacjajestantyzwrotna,to»adenelementpostaci(
x,x
)nienale»ydorelacji.
Awi¦cwszystkichmo»liwychdozdefiniowaniawzbiorze
n
-elementowymrelacjian-
tyzwrotnychjest:2
n
(
n
−
1)
(d)
Niechrelacja
X
×
X
b¦dzieantysymetryczna.Wtedy
xy
)
(
yx
),dlado-
wolnych
x,y
2
X
.Poł¡czmyelementyzbioru
X
×
X
wpary,takabydoka»dejpary
nale»ałyelementy(
x,y
)oraz(
y,x
)-dladowolnych
x,y
2
X
.
n
elementównieposiadapary-s¡toelementypostaci(
x,x
).Jednakteelementynie
mog¡nale»e¢dorelacjiantysymetrycznej(por.zad.1.a)
Defiuniuj¡crelacjeantysymetrycznenale»ypami¦ta¢,i»zka»dejparymo»emywy-
bra¢tylkojedenelement:(
x,y
)albo(
y,x
),b¡d¹niewybra¢»adnego.Wszystkich
parjest
n
(
n
−
1)
/
2.St¡dwszystkichrelacjiantysymetrycznychjest:3
[
n
(
n
−
1)
/
2]
(e)
Je±lirelacjajestsłaboantysymetryczna,toniemog¡doniejnale»e¢jednocze±nie
pary(
x,y
)i(
y,x
)dla
x
6
=
y
.Poł¡czmyzatemelementyzbioru
X
×
X
wpary,tak
abydoka»dejparynale»ałyelementy(
x,y
)oraz(
y,x
)-dladowolnych
x,y
2
X
.
n
elementówniemaj¡cychpary.
Doka»dejrelacjisłaboantysymetrycznejmo»nawybra¢tylkojedenelementzpary
lubniewybra¢»adnego.Mo»nawybra¢te»elementpostaci(
x,x
).
St¡dwszystkichrelacjisłaboantysymetrycznychjest:2
n
·
3
n
(
n
−
1)
/
2
(f)
Dorelacjizwrotnejisymetrycznejnale»y
n
parpostaci(
x,x
).Ponadtoprzynale»no±¢
dorelacjipary(
x,y
)poci¡gaprzynale»no±¢pary(
y,x
).Poł¡czmyzatemelementy
zbioru
X
×
X
wpary,takjakwzadaniu2.b.
St¡dwszystkichrelacjizwrotnychisymetrycznychjest:2
n
(
n
−
1)
/
2
.
(g)
Rozumowaniejestanalogicznejakwpoprzednimprzypadku.Tymrazem»adnaz
parpostaci(
x,x
)nienale»ydorelacji.Pozostałeł¡czymywparyidostajemyw
konsekwencji,»ewszystkichrelacjiantyzwrotnychisymetrycznychjest:2
[
n
(
n
−
1)
/
2]
.
(h)
Dorelacjizwrotnejisłaboantysymetrycznejnale»¡wszystkieparypostaci(
x,x
)i
conajwy»ejjedenzparyelementów:(
x,y
)
,
(
y,x
).
St¡drelacjizwrotnychisłaboantysymetrycznychjest:3
n
(
n
−
1)
/
2
Zadanie4.
Zbada¢,któredziałaniawzbiorzerelacjizachowuj¡własno±cirelacji.
Rozwi¡znie:
Niech
R,S
b¦d¡relacjamiokre±lonymiwniepustymzbiorze
X
×
X
.
(a)
Sumadwóchrelacjizwrotnychjestrelacj¡zwrotn¡.
Niech
R,S
b¦d¡relacjamizwrotnymi,wówczas:(
x,x
)
2
R
i(
x,x
)
2
S
.Zatem
(
x,x
)
2
R
[
S
.
(b)
Sumadwóchrelacjisymetrycznychjestrelacj¡symetryczn¡.
Niech
R,S
b¦d¡relacjamisymetrycznymiiniech(
x,y
)
2
R
[
S
.Wtedy(
x,y
)
2
R
lub(
x,y
)
2
S
.Załó»my,»e(
x,y
)
2
R
,wtedy(
y,x
)
2
R
,awi¦c(
y,x
)
2
R
[
S
.
Analogiczniedlaprzypadku(
x,y
)
2
S
.
(c)
Sumadwóchrelacjiantyzwrotnychjestrelacj¡antyzwrotn¡.
Niech
R,S
b¦d¡relacjamiantyzwrotnymi,wówczas:(
x,x
)
/
2
R
i(
x,x
)
/
2
S
.Zatem
(
x,x
)
/
2
R
[
S
.
(d)
Sumarelacjiantysymetrycznychniemusiby¢relacj¡antysymetryczn¡.
Przykład:Niech
X
=
{
1
,
2
}
iniech
R
=
{
(1
,
2)
}
,S
=
{
(2
,
1)
}
.Obierelacjes¡anty-
symetryczne,za±
R
[
S
=
{
(1
,
2)
,
(2
,
1)
}
niejestrelacj¡antysymetryczn¡.
(e)
Sumarelacjisłaboantysymetrycznychniemusiby¢relacj¡słaboantysymetryczn¡.
Przykład.Jakwprzypadku(d).Sumarelacji
R
[
S
niejestsłaboantysymetryczna.
(f)
Sumadwóchrelacjiprzechodnichniemusiby¢relacj¡przechodni¡.
Przykład:Niech
X
=
{
1
,
2
,
3
}
i
R
=
{
(1
,
2)
,
(1
,
3)
,
(2
,
3)
}
,S
=
{
(2
,
1)
,
(1
,
3)
,
(2
,
3)
}
.
Obierelacjes¡przechodnie.Ichsuma
R
[
S
=
{
(1
,
2)
,
(1
,
3)
,
(2
,
1)
,
(2
,
3)
}
niejest
relacj¡przechodni¡-brakujeelementu(1
,
1).
(g)
Przekrójdwóchrelacjizwrotnychjestrelacj¡zwrotn¡.
Poniewa»relacje
R,S
s¡zwrotne,toka»dapara(
x,x
)nale»ydotychrelacji,awi¦c
nale»ytak»edocz¦±ciwspólnejtychrelacji.
(h)
Przekrójdwóchrelacjiantyzwrotnychjestrelacj¡antyzwrotn¡.
Poniewa»relacje
R,S
s¡antyzwrotne,to»adnapara(
x,x
)nienale»ydotychrelacji,
awi¦ctak»e»adnapara(
x,x
)nienale»ydocz¦±ciwspólnej.
(i)
Przekrójdwóchrelacjisymetrycznychjestrelacj¡symetryczn¡.
Niech
R,S
b¦d¡relacjamisymetrycznymi.Niech(
x,y
)
2
R
\
S
.Wtedy(
x,y
)
2
R
i
(
x,y
)
2
S
.Wi¦c(
y,x
)
2
R
i(
y,x
)
2
S
,st¡d(
y,x
)
2
R
\
S
(j)
Przekrójdwóchrelacjiantysymetrycznychjestrelacj¡antysymetryczn¡.
Niech
R,S
b¦d¡relacjamiantysymetrycznymi.Niech(
x,y
)
2
R
\
S
.Wtedy(
x,y
)
2
R
i(
x,y
)
2
S
.Ponadto(
y,x
)
/
2
R
i(
y,x
)
/
2
S
,awi¦c(
y,x
)
/
2
R
\
S
.
(k)
Przekrójdwóchrelacjiprzechodnichjestrelacj¡przechodni¡.
Niech
R,S
b¦d¡relacjamiprzechodnimii(
x,y
)
2
R
\
S
oraz(
y,z
)
2
R
\
S
.Wtedy
(
x,y
)i(
y,z
)nale»¡zarównodo
R
jakido
S
.Poniewa»obierelacjes¡przechodnie,
todooburelacjinale»yte»para(
x,z
).Awi¦cdoprzekroju
R
\
S
nale»yelement
(
x,z
).
Zadanie6.
Znale¹¢przechodniedomkni¦cierelacjinast¦pnikawzbiorzeliczbnaturalnych.
Niech
R
oznaczarelacj¦nast¦pnika.
R
=
{
(
x,y
)
2
X
×
X
:
x
=
y
+1
}
.
Ponadto:
R
(2)
=
{
(
x,y
)
2
X
×
X
:
x
=
y
+2
}
...
R
(
n
)
=
{
(
x,y
)
2
X
×
X
:
x
=
y
+
n
}
Korzystaj¡czlematuudowodnionegowzadaniu6wnioskujemy,»e:
R
=
{
(
x,y
)
2
X
×
X
:
x>y
}
Zadanie7.
Niechdaneb¦d¡relacje
R,S
X
×
X
.Je±li
R,S
s¡relacjamirównowa»no±ci,to:
(a)
Sumadwóchrelacjirównowa»no±ciniejestrelacj¡równowa»no±ci.
Przykład.Niech
R,S
N
×
N
b¦d¡takimirelacjami,»e
xRy
,
2
|
x
−
y
oraz
xSy
,
3
|
x
+
y
.Jakłatwosprawdzi¢,obieterelacjes¡relacjamirównowa»no±cio-
wymi.Dosumytychrelacjinale»¡pary(3
,
1)
,
(1
,
4).Natomiastpara(3
,
4)doniej
nienale»y.Niejestwi¦czachowanaprzechodnio±¢.
(b)
Iloczyndwóchrelacjirównowa»no±cijestrelacj¡równowa»no±ci.
Istotnie.Iloczyndwóchrelacjizwrotnychjestrelacj¡zwrotn¡.Iloczyndwóchrelacji
symetrycznychjestrelacj¡symetryczn¡.Iloczyndwóchrelacjiprzechodnichjestre-
lacj¡przechodni¡.(por.zad.3).
(c)
Zło»eniedwóchrelacjirównowa»no±ciniejestrelacj¡równowa»no±ci.
Przykład.Niech
X
=
{
1
,
2
,
3
}
iniech
R
=
{
(1
,
1)
,
(2
,
2)
,
(3
,
3)
,
(1
,
3)
,
(3
,
1)
}
i
S
=
{
(1
,
1)
,
(2
,
2)
,
(3
,
3)
,
(1
,
2)
,
(2
,
1)
}
.Obierelacjes¡relacjamirównowa»no±ci.Jednak
dozło»eniatychrelacjinale»ypara(3
,
2),za±para(2
,
3)dozło»enianienale»y.Nie
jestwi¦cspełnionywaruneksymetryczno±ci.
Zadanie8.
Przechodniedomkni¦cierelacjizwrotnejisymetrycznejjestrelacj¡równowa»no±ci.
Niech
R
X
×
X
b¦dziezwrotnaisymetryczna.Wtedydlaka»dego
x
2
X
jest:
(
x,x
)
2
R
=
R
(1)
1
[
R
(
n
)
n
=1
cooznacza,»eprzechodnedomkni¦cierelacji
R
jestrelacj¡zwrotn¡.
Poka»emysymetryczno±¢przechodniegodomkni¦ciarelacji
R
.
(
x,y
)
2
1
[
R
(
n
)
,
_
m
2
N
(
x,y
)
2
R
(
m
)
n
=1
awi¦cistniej¡takie
v
1
,...,v
m
−
1
2
X
,»e:(
x,v
1
)
2
R
^
...
^
(
v
m
−
1
,y
)
2
R
Zewzgl¦dunasymetryczno±¢relacji
R
jesttak»e:
(
v
1
,x
)
2
R
^
...
^
(
y,v
m
−
1
)
2
R
,
(
y,v
m
−
1
)
2
R
^
...
^
(
v
1
,x
)
2
R
Powy»szakoniunkcjaoznaczajednak,»e(
y,x
)
2
R
(
m
)
.
Dlapokazaniaprzechodnio±ciprzechodniegodomkni¦ciarelacji
R
wystarczyzauwa-
»y¢,»eprzechodniedomkni¦cieka»dejrelacjijestrelacj¡przechodni¡.
Wmy±lpowy»szychrozwa»a«przechodniedomkni¦cierelacjizwrotnejisymetrycz-
nejjestrelacj¡równowa»no±ci.
Zadanie9.
Pokaza¢,»eje»eli
R
i
S
s¡relacjamirównowa»no±citoprzechodniedomkni¦cie
R
[
S
jestrelacj¡równowa»no±ci.
Rozwi¡zanie.
Najpierwpoka»emyzwrotno±¢.Zauwa»my,»e(
x,x
)
2
R
i(
x,x
)
2
S
,wi¦c:
(
x,x
)
2
R
[
S
=(
R
[
S
)
(1)
1
[
(
R
[
S
)
(
n
)
n
=1
Symetriarównie»zachodzi.Je±lipara(
x,y
)nale»ydoprzechodniegodomkni¦cia
R
[
S
,toistniejetakie
m
2
N
,»e(
x,y
)
2
(
R
[
S
)
(
m
)
.Tozkoleioznacza,»eistniej¡
takieelementy
v
1
,...,v
m
−
1
,»e:
(
x,v
1
)
2
R
[
S
^
...
^
(
v
m
−
1
,y
)
2
R
[
S
,
,
((
x,v
1
)
2
R
_
(
x,v
1
)
2
S
)
^
...
^
((
v
m
−
1
,y
)
2
R
_
(
v
m
−
1
,y
)
2
S
)
Ka»dazpar(
x,v
1
)
,...,
(
v
m
−
1
,y
)nale»ydoconajmniejjednejzrelacji
R
i
S
.Wtedy
ka»dazpar(
y,v
m
−
1
)
,...,
(
v
1
,x
),namocysymetrii,nale»ydoconajmniejjednejz
relacji
R
i
S
.Awi¦c:
(
y,v
m
−
1
)
2
R
[
S
^
...
^
(
v
1
,x
)
2
R
[
S
cooznacza,»e(
y,x
)
2
(
R
[
S
)
(
m
)
.
Poka»emyprzechodnio±¢.Niechdoprzechodniegodomkni¦cia
R
[
S
nale»¡pary(
x,y
)
i(
y,z
).Wówczasistniej¡takie
r,m
2
N
,»e:(
x,y
)
2
(
R
[
S
)
(
r
)
oraz(
y,z
)
2
(
R
[
S
)
(
m
)
.
St¡dju»bardzołatwopokaza¢,»e(
x,z
)
2
(
R
[
S
)
(
r
+
m
)
Zadanie10.
Niech
R
b¦dzierelacj¡równowa»no±cizzbiorzesko«czonym
X
.Załó»my,»eelemen-
tyzbioru
X
ponumerowanowtensposób,»eje±li
x
i
oraz
x
j
nale»¡dopewnejklasy
abstrakcjirelacji
R
oraz
i<k<j
,to
x
k
nale»ydotejsamejklasyabstrakcji.Opisa¢
posta¢macierzyrelacji
R
przytakimuporz¡dkowaniuelementówzbioru
X
.
Rozwi¡zanie.
Macierzrelacji
R
maposta¢:
x
1
···
x
a
v
1
···
v
b
z
1
···
z
c
···
x
1
1
···
10
···
00
···
0
···
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
x
a
1
···
10
···
00
···
0
···
v
1
0
···
01
···
10
···
0
···
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
v
b
0
···
01
···
10
···
0
···
z
1
0
···
00
···
01
···
1
···
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
z
c
0
···
00
···
01
···
1
···
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
przyzało»eniu»edoklasypierwszejklasyabstrakcji[
x
]nale»y
a
elementów,doklasy
abstrakcji[
v
]-
b
elementów,doklasyabstrakcji[
z
]-
c
elementówitd.
Plik z chomika:
heroinka94
Inne pliki z tego folderu:
Bobiński G - Matematyka dyskretna II. Zbiór zadań.pdf
(294 KB)
Bobiński G - Matematyka dyskretna. Wykład.pdf
(456 KB)
Bobiński G - Matematyka dyskretna I. Zbiór zadań.pdf
(167 KB)
Denisjuk A - Matematyka Dyskretna.pdf
(2753 KB)
Zakrzewski M - Matematyka dyskretna.pdf
(65684 KB)
Inne foldery tego chomika:
_Matematyka. Rozwiązania
_Matematyka. Serie
_VIDEO MatematykaTV
_VIDEO Szukając Einsteina. Matematyka
01 Działania
Zgłoś jeśli
naruszono regulamin