zadania_Relacje.pdf

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»nawtymzbiorzezdeﬁniowa¢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»nazdeﬁniowa¢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»liwychdozdeﬁniowaniawzbiorze 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)

Deﬁuniuj¡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:

Inne pliki z tego folderu:

Inne foldery tego chomika: