MAT1030 – Diskret matematikk Plenumsregning 7: Ukeoppgaver fra kapittel 5 & 6, mm. Roger Antonsen

(1)

MAT1030 – Diskret matematikk

Plenumsregning 7: Ukeoppgaver fra kapittel 5 & 6, mm.

Roger Antonsen

Matematisk Institutt, Universitetet i Oslo

28. februar 2008

(2)

Oppgave 5.16

La

R

være relasjonen p˚ a

{a,b,c,d}

definert av følgende matrise.







1 2 3 4

1 T F T F

2 F T T F

3 F T T F

4 F F F T







(a)

Tegn den grafiske representasjonen av

R.

(b)

Finn ut, og gi grunner for hvorvidt,

R

er refleksiv, symmetrisk eller transitiv.

MAT1030 – Diskret matematikk 28. februar 2008 2

(3)

Oppgave 5.16

La

R

være relasjonen p˚ a

{a,b,c,d}

definert av følgende matrise.







1 2 3 4

1 T F T F

2 F T T F

3 F T T F

4 F F F T







(a)

Tegn den grafiske representasjonen av

R.

(b)

Finn ut, og gi grunner for hvorvidt,

R

er refleksiv, symmetrisk eller transitiv.

(4)

Oppgave 5.16

La

R

være relasjonen p˚ a

{a,b,c,d}

definert av følgende matrise.







1 2 3 4

1 T F T F

2 F T T F

3 F T T F

4 F F F T







(a)

Tegn den grafiske representasjonen av

R.

(b)

Finn ut, og gi grunner for hvorvidt,

R

er refleksiv, symmetrisk eller transitiv.

(5)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(6)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(7)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(8)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(9)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(10)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(11)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(12)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(13)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(14)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(15)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor?

Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(16)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T.

Og fordi alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(17)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T.

Og fordi alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(18)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(19)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(20)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(21)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke?

Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(22)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen .

Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(23)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen .

Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(24)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen .

Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(25)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(26)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(27)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(28)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke?

Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(29)

Løsning







a b c d

a T F T F

b F T T F

c F T T F

d F F F T







a b

d c

Er

R

refleksiv?

Ja

Hvorfor? Fordi alle p˚ a diagonalen er

T. Og fordi

alle nodene har en pil til seg selv.

Er

R

symmetrisk?

Nei

Hvorfor ikke? Fordi matrisen ikke kan speiles om diagonalen . Vi har (a,

c

)

∈R, menikke

(c,

a)∈R.

Er

R

transitiv?

Nei

Hvorfor ikke? Vi har (a,

c

)

∈R

og (c,

b)∈R,

men ikke (a,

b)∈R.

(30)

Oppgave 5.17

Er matriserepresentasjonen av en relasjon unik eller kan den samme relasjonen representeres av to forskjellige matriser?

Løsning

Representasjonen er ikke unik, siden den samme relasjonen kan representeres av to forskjellige matriser.

a b

a F T

b T T

b a

b T T

a T F

Begge matrisene representerer relasjonen

{(a,b),

(b,

a),

(b,

b)}.

(31)

Oppgave 5.17

Er matriserepresentasjonen av en relasjon unik eller kan den samme relasjonen representeres av to forskjellige matriser?

Løsning

Representasjonen er ikke unik, siden den samme relasjonen kan representeres av to forskjellige matriser.

a b

a F T

b T T

b a

b T T

a T F

Begge matrisene representerer relasjonen

{(a,b),

(b,

a),

(b,

b)}.

(32)

Oppgave 5.17

Er matriserepresentasjonen av en relasjon unik eller kan den samme relasjonen representeres av to forskjellige matriser?

Løsning

Representasjonen er ikke unik, siden den samme relasjonen kan representeres av to forskjellige matriser.

a b

a F T

b T T

b a

b T T

a T F

Begge matrisene representerer relasjonen

{(a,b),

(b,

a),

(b,

b)}.

(33)

Oppgave 5.17

Er matriserepresentasjonen av en relasjon unik eller kan den samme relasjonen representeres av to forskjellige matriser?

Løsning

Representasjonen er ikke unik, siden den samme relasjonen kan representeres av to forskjellige matriser.

a b

a F T

b T T

b a

b T T

a T F

Begge matrisene representerer relasjonen

{(a,b),

(b,

a),

(b,

b)}.

(34)

Oppgave 5.17

Er matriserepresentasjonen av en relasjon unik eller kan den samme relasjonen representeres av to forskjellige matriser?

Løsning

Representasjonen er ikke unik, siden den samme relasjonen kan representeres av to forskjellige matriser.

a b

a F T

b T T

b a

b T T

a T F

Begge matrisene representerer relasjonen

{(a,b),

(b,

a),

(b,

b)}.

(35)

Oppgave 5.17

Er matriserepresentasjonen av en relasjon unik eller kan den samme relasjonen representeres av to forskjellige matriser?

Løsning

Representasjonen er ikke unik, siden den samme relasjonen kan representeres av to forskjellige matriser.

a b

a F T

b T T

b a

b T T

a T F

Begge matrisene representerer relasjonen

{(a,b),

(b,

a),

(b,

b)}.

(36)

Oppgave 5.18

Avgjør om følgende relasjoner refleksive, irrefleksive, symmetriske, antisymmetriske eller transitive.

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

(b)

“er sønnen til”, p˚ a mengden av alle mennesker

(c)

“er større enn”, p˚ a mengden av reelle tall

(d)

relasjonen

R

p˚ a reelle tall definert ved

xRy

hvis

x²

=

y² (e)

“har samme heltallsdel som”, p˚ a mengden av reelle tall

(f)

“er et multippel av”, p˚ a mengden av positive heltall

Oppgave 5.19

Avgjør hvilke av relasjonene i Oppgave 5.18 som er ekvivalensrelasjoner. For de som er ekvivalensrelasjoner, beskriv ekvivalensklassene.

Oppgave 5.20

Avgjør hvilke av relasjonene i Oppgave 5.18 som er partielle ordninger.

(37)

Oppgave 5.18

Avgjør om følgende relasjoner refleksive, irrefleksive, symmetriske, antisymmetriske eller transitive.

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

(b)

“er sønnen til”, p˚ a mengden av alle mennesker

(c)

“er større enn”, p˚ a mengden av reelle tall

(d)

relasjonen

R

p˚ a reelle tall definert ved

xRy

hvis

x²

=

y² (e)

“har samme heltallsdel som”, p˚ a mengden av reelle tall

(f)

“er et multippel av”, p˚ a mengden av positive heltall

Oppgave 5.19

Avgjør hvilke av relasjonene i Oppgave 5.18 som er ekvivalensrelasjoner. For de som er ekvivalensrelasjoner, beskriv ekvivalensklassene.

Oppgave 5.20

Avgjør hvilke av relasjonene i Oppgave 5.18 som er partielle ordninger.

(38)

Oppgave 5.18

Avgjør om følgende relasjoner refleksive, irrefleksive, symmetriske, antisymmetriske eller transitive.

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

(b)

“er sønnen til”, p˚ a mengden av alle mennesker

(c)

“er større enn”, p˚ a mengden av reelle tall

(d)

relasjonen

R

p˚ a reelle tall definert ved

xRy

hvis

x²

=

y² (e)

“har samme heltallsdel som”, p˚ a mengden av reelle tall

(f)

“er et multippel av”, p˚ a mengden av positive heltall

Oppgave 5.19

Avgjør hvilke av relasjonene i Oppgave 5.18 som er ekvivalensrelasjoner. For de som er ekvivalensrelasjoner, beskriv ekvivalensklassene.

Oppgave 5.20

Avgjør hvilke av relasjonene i Oppgave 5.18 som er partielle ordninger.

(39)

Oppgave 5.18

Avgjør om følgende relasjoner refleksive, irrefleksive, symmetriske, antisymmetriske eller transitive.

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

(b)

“er sønnen til”, p˚ a mengden av alle mennesker

(c)

“er større enn”, p˚ a mengden av reelle tall

(d)

relasjonen

R

p˚ a reelle tall definert ved

xRy

hvis

x²

=

y² (e)

“har samme heltallsdel som”, p˚ a mengden av reelle tall

(f)

“er et multippel av”, p˚ a mengden av positive heltall

Oppgave 5.19

Avgjør hvilke av relasjonene i Oppgave 5.18 som er ekvivalensrelasjoner. For de som er ekvivalensrelasjoner, beskriv ekvivalensklassene.

Oppgave 5.20

Avgjør hvilke av relasjonene i Oppgave 5.18 som er partielle ordninger.

(40)

Oppgave 5.18

Avgjør om følgende relasjoner refleksive, irrefleksive, symmetriske, antisymmetriske eller transitive.

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

(b)

“er sønnen til”, p˚ a mengden av alle mennesker

(c)

“er større enn”, p˚ a mengden av reelle tall

(d)

relasjonen

R

p˚ a reelle tall definert ved

xRy

hvis

x²

=

y²

(e)

“har samme heltallsdel som”, p˚ a mengden av reelle tall

(f)

“er et multippel av”, p˚ a mengden av positive heltall

Oppgave 5.19

Avgjør hvilke av relasjonene i Oppgave 5.18 som er ekvivalensrelasjoner. For de som er ekvivalensrelasjoner, beskriv ekvivalensklassene.

Oppgave 5.20

Avgjør hvilke av relasjonene i Oppgave 5.18 som er partielle ordninger.

(41)

Oppgave 5.18

Avgjør om følgende relasjoner refleksive, irrefleksive, symmetriske, antisymmetriske eller transitive.

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

(b)

“er sønnen til”, p˚ a mengden av alle mennesker

(c)

“er større enn”, p˚ a mengden av reelle tall

(d)

relasjonen

R

p˚ a reelle tall definert ved

xRy

hvis

x²

=

y² (e)

“har samme heltallsdel som”, p˚ a mengden av reelle tall

(f)

“er et multippel av”, p˚ a mengden av positive heltall

Oppgave 5.19

Avgjør hvilke av relasjonene i Oppgave 5.18 som er ekvivalensrelasjoner. For de som er ekvivalensrelasjoner, beskriv ekvivalensklassene.

Oppgave 5.20

Avgjør hvilke av relasjonene i Oppgave 5.18 som er partielle ordninger.

(42)

Oppgave 5.18

Avgjør om følgende relasjoner refleksive, irrefleksive, symmetriske, antisymmetriske eller transitive.

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

(b)

“er sønnen til”, p˚ a mengden av alle mennesker

(c)

“er større enn”, p˚ a mengden av reelle tall

(d)

relasjonen

R

p˚ a reelle tall definert ved

xRy

hvis

x²

=

y² (e)

“har samme heltallsdel som”, p˚ a mengden av reelle tall

(f)

“er et multippel av”, p˚ a mengden av positive heltall

Oppgave 5.19

Avgjør hvilke av relasjonene i Oppgave 5.18 som er ekvivalensrelasjoner. For de som er ekvivalensrelasjoner, beskriv ekvivalensklassene.

Oppgave 5.20

Avgjør hvilke av relasjonene i Oppgave 5.18 som er partielle ordninger.

(43)

Oppgave 5.18

Avgjør om følgende relasjoner refleksive, irrefleksive, symmetriske, antisymmetriske eller transitive.

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

(b)

“er sønnen til”, p˚ a mengden av alle mennesker

(c)

“er større enn”, p˚ a mengden av reelle tall

(d)

relasjonen

R

p˚ a reelle tall definert ved

xRy

hvis

x²

=

y² (e)

“har samme heltallsdel som”, p˚ a mengden av reelle tall

(f)

“er et multippel av”, p˚ a mengden av positive heltall

Oppgave 5.19

Avgjør hvilke av relasjonene i Oppgave 5.18 som er ekvivalensrelasjoner.

For de som er ekvivalensrelasjoner, beskriv ekvivalensklassene.

Oppgave 5.20

Avgjør hvilke av relasjonene i Oppgave 5.18 som er partielle ordninger.

(44)

Oppgave 5.18

Avgjør om følgende relasjoner refleksive, irrefleksive, symmetriske, antisymmetriske eller transitive.

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

(b)

“er sønnen til”, p˚ a mengden av alle mennesker

(c)

“er større enn”, p˚ a mengden av reelle tall

(d)

relasjonen

R

p˚ a reelle tall definert ved

xRy

hvis

x²

=

y² (e)

“har samme heltallsdel som”, p˚ a mengden av reelle tall

(f)

“er et multippel av”, p˚ a mengden av positive heltall

Oppgave 5.19

Avgjør hvilke av relasjonene i Oppgave 5.18 som er ekvivalensrelasjoner.

For de som er ekvivalensrelasjoner, beskriv ekvivalensklassene.

Oppgave 5.20

Avgjør hvilke av relasjonene i Oppgave 5.18 som er partielle ordninger.

(45)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Refleksiv?

Nei, det fins en som ikke er sin egen bror eller søster.

I Irrefleksiv?

Ja, ingen er sin egen bror eller søster.

I Symmetrisk?

Ja, hvisx er søsken tily, s˚a ery søsken tilx.

I Antisymmetrisk?

Nei, vi ha atx er søsken tily og at y søsken tilx, uten atx=y.

I Transitiv?

Nei, hvis vi tillater halvsøsken, s˚a kanavære søsken tilb, og bsøsken tilc, uten ataer søsken til c. En annen grunn er atakan være søsken tilbogbsøsken tila, men akan er ikke søsken tila. (Takk til oppmerksomme studenter!)

I Ekvivalensrelasjon?

Nei, den er ikke refleksiv

I Partiell ordning?

Nei, den er hverken refleksiv, antisymmetrisk eller transitiv.

(46)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Refleksiv?

I Irrefleksiv?

I Symmetrisk?

I Antisymmetrisk?

Nei, vi ha atx er søsken til y og at y søsken tilx, uten atx=y.

I Transitiv?

Nei, hvis vi tillater halvsøsken, s˚a kanavære søsken tilb, og bsøsken tilc, uten ataer søsken tilc. En annen grunn er atakan være søsken tilbogbsøsken tila, men akan er ikke søsken tila. (Takk til oppmerksomme studenter!)

I Partiell ordning?

(47)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Refleksiv?

I Irrefleksiv?

I Symmetrisk?

I Antisymmetrisk?

I Transitiv?

I Partiell ordning?

(48)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Refleksiv?Nei

, det fins en som ikke er sin egen bror eller søster.

I Irrefleksiv?

I Symmetrisk?

I Antisymmetrisk?

I Transitiv?

I Partiell ordning?

(49)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Refleksiv?Nei, det fins en som ikke er sin egen bror eller søster.

I Irrefleksiv?

I Symmetrisk?

I Antisymmetrisk?

I Transitiv?

I Partiell ordning?

(50)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Irrefleksiv?

I Symmetrisk?

I Antisymmetrisk?

I Transitiv?

I Partiell ordning?

(51)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Irrefleksiv?Ja

, ingen er sin egen bror eller søster.

I Symmetrisk?

I Antisymmetrisk?

I Transitiv?

I Partiell ordning?

(52)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Irrefleksiv?Ja, ingen er sin egen bror eller søster.

I Symmetrisk?

I Antisymmetrisk?

I Transitiv?

I Partiell ordning?

(53)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Symmetrisk?

I Antisymmetrisk?

I Transitiv?

I Partiell ordning?

(54)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Symmetrisk?Ja

, hvisx er søsken tily, s˚a ery søsken tilx.

I Antisymmetrisk?

I Transitiv?

I Partiell ordning?

(55)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Symmetrisk?Ja, hvisx er søsken tily, s˚a ery søsken tilx.

I Antisymmetrisk?

I Transitiv?

I Partiell ordning?

(56)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Antisymmetrisk?

I Transitiv?

I Partiell ordning?

(57)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Antisymmetrisk?Nei

, vi ha atx er søsken til y og at y søsken tilx, uten atx=y.

I Transitiv?

I Partiell ordning?

(58)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Antisymmetrisk?Nei, vi ha atx er søsken til y og at y søsken tilx, uten atx=y.

I Transitiv?

I Partiell ordning?

(59)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Transitiv?

I Partiell ordning?

(60)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Transitiv?Nei

, hvis vi tillater halvsøsken, s˚a kanavære søsken tilb, og bsøsken tilc, uten ataer søsken tilc. En annen grunn er atakan være søsken tilbogbsøsken tila, men akan er ikke søsken tila. (Takk til oppmerksomme studenter!)

I Partiell ordning?

(61)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Transitiv?Nei, hvis vi tillater halvsøsken, s˚a kanavære søsken tilb, og bsøsken tilc, uten ataer søsken tilc.

En annen grunn er atakan være søsken tilbogbsøsken tila, men akan er ikke søsken tila. (Takk til oppmerksomme studenter!)

I Partiell ordning?

(62)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Transitiv?Nei, hvis vi tillater halvsøsken, s˚a kanavære søsken tilb, og bsøsken tilc, uten ataer søsken tilc. En annen grunn er atakan være søsken tilbogbsøsken tila, men akan er ikke søsken tila.

(Takk til oppmerksomme studenter!)

I Partiell ordning?

(63)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Partiell ordning?

(64)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Ekvivalensrelasjon?Nei

, den er ikke refleksiv

I Partiell ordning?

(65)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Ekvivalensrelasjon?Nei, den er ikke refleksiv

I Partiell ordning?

(66)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Partiell ordning?

(67)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Partiell ordning?Nei

, den er hverken refleksiv, antisymmetrisk eller transitiv.

(68)

Løsning

(a)

“er søsken (bror eller søster) til”, p˚ a mengden av alle mennesker

I Partiell ordning?Nei, den er hverken refleksiv, antisymmetrisk eller transitiv.

(69)

Løsning

(b)

“er sønnen til”, p˚ a mengden av alle mennesker

I Refleksiv?

Nei, det fins en som ikke er sin egen sønn.

I Irrefleksiv?

Ja, ingen er sin egen sønn.

I Symmetrisk?

Nei, fordi “X er sønnen til Y” ikke medfører at “Y er sønnen til X”.

I Antisymmetrisk?

Ja, fordi “X er sønnen til Y” og “Y er sønnen til X” aldri er sanne samtidig.

I Transitiv?

Nei, “X er sønnen til Y” og “Y er sønnen til Z” ikke medfører at “X er sønnen til Z”.

Nei, den er hverken refleksiv, symmetrisk eller transitiv.

I Partiell ordning?

Nei, den er hverken refleksiv eller transitiv.

(70)

Løsning

(b)

“er sønnen til”, p˚ a mengden av alle mennesker

I Refleksiv?

I Irrefleksiv?

I Symmetrisk?

I Antisymmetrisk?

I Transitiv?

I Partiell ordning?

(71)

Løsning

(b)

“er sønnen til”, p˚ a mengden av alle mennesker

I Refleksiv?

I Irrefleksiv?

I Symmetrisk?

I Antisymmetrisk?

I Transitiv?

I Partiell ordning?

(72)

Løsning

(b)

“er sønnen til”, p˚ a mengden av alle mennesker

I Refleksiv?Nei

, det fins en som ikke er sin egen sønn.

I Irrefleksiv?

I Symmetrisk?

I Antisymmetrisk?

I Transitiv?

I Partiell ordning?

(73)

Løsning

(b)

“er sønnen til”, p˚ a mengden av alle mennesker

I Refleksiv?Nei, det fins en som ikke er sin egen sønn.

I Irrefleksiv?

I Symmetrisk?

I Antisymmetrisk?

I Transitiv?

I Partiell ordning?

(74)

Løsning

(b)

“er sønnen til”, p˚ a mengden av alle mennesker

I Refleksiv?Nei, det fins en som ikke er sin egen sønn.

I Irrefleksiv?

I Symmetrisk?

I Antisymmetrisk?

I Transitiv?

I Partiell ordning?