j. géén relatie: 4 en 5 zijn geen geordende paren (ook geen geordende ééntallen)

binaire relatie mag leeg zijn!) g. binaire relatie (= een verzameling geordende paren). mogelijke Cartesische producten zijn: IN × IN, IN × IR, IR × IN, IR × IR,(uitleg: een binaire relatie mag leeg zijn! En de lege verzameling is deelverzameling van elke verzameling, dus ook van elk Cartesisch product) h. binaire relatie (= een verzameling geordende paren). mogelijke Cartesische producten zijn: IN × IN, IN × IR, IR × IN, IR × IR, (uitleg: bij IN × IN is het de zgn. universele relatie). i. unaire relatie, geen binaire relatie maar een unaire relatie (= een verzameling e´e´ntallen). j. ge´e´n relatie: 4 en 5 zijn geen geordende paren (ook geen geordende e´e´ntallen). 3.3.2 a. R = { (x , y )

J

(x > 0 ∧ y > 0) ∨ (x < 0 ∧ y < 0) }

Ook goed is natuurlijk: R = { (x , y ) b. R = { (x , y )

J

J

(x ∗ y > 0 }

x +y >0 }

c. R = { (x , y ) J x + y = ′even′ } (nog mooier: R = { (x , y ) J ∃ k [ k ∈ Z ∧ x + y = 2k ] }) d. R = { (x , y ) J J x − y J = ′even′ } (nog mooier: R = { (x , y ) J ∃ k [ k ∈ Z ∧

J

x − y J = 2k ] })

3.3.3 De gegeven bewering is onjuist: kies b.v. U = {a , b }, met A = {a }, B = {a , b } zodat: A × B = {(a , a ), (a , b )}; daar ∅ ⊆ A × B geldt dat R 1 = ∅ mogelijk is. 3.3.4 Voor al deze relaties geldt: R : A → A a. Ra = {(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 0), (1, 1), . . . (1, 5) }. b. Rb = {(4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), c. Rc = {(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 0), (1, 1), . . . (1, 5) . (4, 0), (4, 1), . . . (4, 5) }. d. Rd = {(4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5) . (2, 5) }.

- 31 -

3.4.1 a. niet reflexief (want: (d , d ) ∉ Ra ), wel symmetrisch, maar niet transitief (want (a , b ) ∈ Ra ∧ (b , c ) ∈ Ra

∧ (a , c ) ∉ Ra );

b. reflexief, symmetrisch, maar niet transitief (want (a , b ) ∈ Rb ∧ (b , c ) ∈ Rb

∧ (a , c ) ∉ Rb );

c. niet reflexief (want: (d , d ) ∉ Rc ), niet symmetrisch (want: (d , a ) ∈ Rc ∧ (a , d ) ∉ Rc ), en niet transitief (want (d , a ) ∈ Rc ∧ (a , b ) ∈ Rc ∧ (d , b ) ∉ Rc ); 3.4.2 a. R = {(a , a ), (b , b ), (c , c ), (d , d ), (e , e ), (a , b ) } niet symmetrisch, want (b , a ) ∉ R . b. R = {(a , a ), (b , b ), (c , c ), (d , d ), (e , e ), (a , b ), (b , a ) } c. R = {(a , a ), (b , b ), (a , b ), (b , a ) } d. R = {(a , a ), (b , b ), (c , c ), (d , d ), (e , e ), (a , b ) } ofwel: R = {(a , a ), (b , b ), (c , c ), (d , d ), (e , e ), (a , b ), (b , c ), (a , c ) } 3.4.3 a. Onjuist: kies: R 1 = {(a , a ), (b , b ), (c , c ), (d , d ) } ... (c , d ), (d , c ) } dan: A × A − R 1 = {(a , b ), (b , a ), . . . alle paren (a , a ) (d , d ) zitten er nu niet meer in. b. Onjuist: kies: R 1 = R 2 = {(a , a ), (b , b ), (c , c ), (d , d ) } dan geldt: R 1 − R 2 = ∅. Daar ∅ niet reflexief is, is de onjuistheid bewezen. c. Onjuist ( A , R1 ) ahhhhhhhhh b g

g

g

g

d a

c ( A , R2 )

g

b g c c c c

g

g

d

c

- 32 -

( A , R1 ∪ R2 ) ahhhhhhhhh b g

g c c c c

g

g

d

c

deze is niet transitief, want hhhhhhhhhhh a (R 1 ∪ R 2 ) b ∧ b (R 1 ∪ R 2 ) c ∧ a (R 1∪R 2)c d. ( A , R1 ) ahhhhhhhhh b g

g c c c c

g

g

d a

c ( A , R2 )

g

b g

g

g

d

c

( A , R1 − R2 ) ahhhhhhhhh b g

g c c c c

g

g

d deze a (R 1 − R 2) b

c

is niet ∧ b (R 1 − R 2) c ∧

transitief a (R 1 − R 2) c h hhhhhhhhhhhhh

3.4.4 a. reflectie: iiiiiiii We moeten onderzoeken of ∀ x [ xRx ] geldt, ∀ x [ x + x is even ]. Daar x + x = 2x en daar 2*natuurlijk getal altijd even is, ∀ x [ x + x is even ] en dus ∀ x [ xRx ]: R is reflexief.

want

ofwel geldt

symmetrie: i iiiiiiiiii We moeten onderzoeken of ∀ x ∀ y [ xRy ⇒ yRx ] geldt, ofwel ∀ x ∀ y [ (x + y is even ) ⇒ (y +x is even ) ]. - 33 -

Daar x + y = y + x , geldt ∀ x ∀ y [ (x + y is even ) ⇒ (y +x is even ) ] en dus ∀ x ∀ y [ xRy ⇒ yRx ]: R is symmetrisch. transitiviteit: i iiiiiiiiiiii We moeten onderzoeken of ∀ x ∀ y ∀ z [ (xRy ∧ yRz ) ⇒ xRz ] geldt, ofwel ∀ x ∀ y ∀ z [ ( (x + y is even ) ∧ (y + z is even ) ) ⇒ (x + z is even ) ]. Welnu: als x + y even is, zijn ofwel x en y beide even ofwel beide oneven. Hetzelfde geldt voor y + z . Daar y in zowel x + y als in x + z zit, geldt dus dat ofwel x , y , z allr drie even ofwel alle drie oneven zijn. Dus geldt dat x + z dan ook even is. Er geldt dus ∀ x ∀ y ∀ z [ ( (x + y is even ) ∧ (y + z is even ) ) ⇒ (x + z is even ) ]. Dus geldt ∀ x ∀ y ∀ z [ (xRy ∧ yRz ) ⇒ xRz ], dus R is transitief. Conclusie: i iiiiiiiii daar R reflexief, symmetrisch en transitief is, is R een equivalentierelatie. b. Dit gaat analoog aan het antwoord op opgave 3.4.4 a . Conclusie: i iiiiiiiii daar R reflexief, symmetrisch en transitief is, is R een equivalentierelatie. c. R is wel symmetrisch, maar niet reflexief en ook niet transitief: Tegenvoorbeeld i iiiiiiiiiiiiiiiiiiiiii reflexie: 1R1 geldt niet, want 1 + 1 = 2 en 2 is niet oneven maar even. R is dus niet reflexief. Tegenvoorbeeld i iiiiiiiiiiiiiiiiiiiiiiiiiii transitiviteit: 1R2 en 2R3 gelden beide, maar niet geldt 1R3 want 1 + 3 = 4 en 4 is niet oneven maar even. In de implicatie (1R 2 ∧ 2R 3) ⇒ (1R 3) is het linkerlid wel waar, maar het rechterlid niet: de implicatie is onwaar. R is dus ge´ e´ n equivalentierelatie. 3.5.1 a. R 1R 2 = {(a , c ), (c , a ), (e , e )} b. R 2R 1 = {(a , d ), (d , a ), (d , b ), (c , c )} c. R 1R 1 = R 12 = {(a , a ), (a , b ), (e , d )} d. R 2R 1R 2 = {(a , a ), (d , c ), (c , e )} (*zie antwoord a *) e. R 13 = R 1(R 12 ) = {(a , a ), (a , b )} (*zie antwoord c *)

- 34 -

3.5.2 a. ja: het Codomein van R 1 = het Domein van R 3 = B . b. neen: het Codomein van R 1 (= B ) ≠ het Domein van R 2 ( = A ). c. ja: het Codomein van R 3 = het Domein van R 1 = A . d. ja: het Codomein van R 1R 3 = het Domein van R 1R 3 = A . Voorbeeld: kies A = {a , b } en B = {1, 2, 3} met R 1 = {(a , 1), (b , 3)} en R 3 = {(1, b ), (2, b ), (3, a )} zodat: R 1R 3 = {(a , b ), (b , a )} en dus: (R 1R 3)2 = {(a , a ), (b , b )} zodat: (R 1R 3)3 = {(a , b ), (b , a )} 3.5.3 I. Kies: A = {Geert , Elise }, B = {Brussel , Essen , Amsterdam } en C = {Nederlands , Frans , Duits } en R 1 = {(Geert , Essen )} R 2 = {(Brussel , Frans ), (Brussel , Nederlands )} R 3 = {(Essen , Duits )} dan is voldaan aan: R 1 ⊆ A × B , R 2 ⊆ B × C , R 3 ⊆ B × C . a. R 1(R 2 ∪ R 3) = {(Geert , Duits )}; b. R 1R 2 ∪ R 1R 3 = {(Geert , Duits )}; c.

R 1(R 2 ∪ R 3) = R 1R 2 ∪ R 1R 3)}; Neen dit is ge´ e´ n verrassing (ge´ e´ n uitleg maar).

II. Kies nu echter: R 1 = {(Geert , Essen ), (Geert , Amsterdam )} R 2 = {(Essen , Duits ), (Amsterdam , Nederlands )} R 3 = {(Essen , Duits ), (Essen , Nederlands )} Overigens zijn de relaties nu niet erg maatschappelijk relevant meer!! dan is voldaan aan: R ⊆ A × B , R 2 ⊆ B × C , R 3 ⊆ B × C . a. (R 2 ∩ R 3) = {(Essen , Duits )} R 1(R 2 ∩ R 3) = {(Geert , Duits )} b. R 1R 2 = {(Geert , Duits ), (Geert , Nederlands )}; R 1R 3 = {(Geert , Duits ), (Geert , Nederlands )}; R 1R 2 ∩ R 1R 3) = {(Geert , Duits ), (Geert , Nederlands )}; c.

R 1R 2 ∩ R 1R 3) ≠ R 1(R 2 ∩ R 3)

d.

zie IIc

- 35 -

3.5.4 Gegeven zijn R 1 en R 2 op A = {1, 2, 3, 4}. a. [ R 1 en R 2 zijn beide reflexief ] ⇒ [ R 1R 2 is symmetrisch ] is onjuist ; tegenvoorbeeld:

1

( A , R1 ) 2

ghhhhhh

g

< 4

< 3

g

g

<

<

1

( A , R2 ) 2 g

( A , R 1R 2 ) 1hhhhhh 2 g

g

< 4

< 3

< 4

< 3

<

<

<

<

g

g

g

g

g

R 1 = {(1, 1), (1, 2), (2, 2), (3, 3), (4, 4)} R 2 = {(1, 1), (2, 2), (3, 3), (4, 4)} dan zijn R 1 en R 2 beide reflexief en R 1R 2 = {(1, 1), (1, 2), (2, 2), (3, 3), (4, 4)} dus R 1R 2 is niet symmetrisch. b. [ R 1 en R 2 zijn beide transitief ] ⇒ [ R 1R 2 is transitief ] is onjuist ; tegenvoorbeeld:

1

( A , R1 ) 2

ghhhhhh

g

4

g

hhhhhhg

3

1

( A , R2 ) 2

c

c c

c

g

g c

c g

g

4

3

1 g

g

4

( A , R 1R 2 ) 2 g

g

3

R 1 is transitief. R 2 ook. R 1R 2 = {(1, 3), (3, 1)} is niet transitief want dan zou o.a. ook (1, 1) ∈ R 1R 2 moeten gelden.

- 36 -

3.6.1 a. Meerdere (preciezer: 0 of meer). b. Aannemende dat reizigers en klanten hetzelfde is: Meerdere (preciezer: 0 of meer). c. radres h hhhhhhhhhhhhhhhhhh

h hhhhhhhhhhhhhhhhhh c

c

c

c

c

c

c

c

c

chhhhhh

c

c

Reisbureau

N

h hhhhhhhhhhhhhhhhhh

heeft

N

hhhhhh c

c

c c

c

klant

c

c

h hhhhhhhhhhhhhhhhhh

*

kadres

rnaam

- 37 -

* knaam

c

3.7.1 a.

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c

c

Tabel lezer

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c c cc c cc iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c c c iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii

Lcode

c

naam

c

1 c

c

19

c

B. Teeuwissen c

9 c

adres

c

c

c

c

c

jeugd c

Den Haag

c

jeugd c

Delft c

Straat 14

soort

Delft c

Plein 13 c

H. Weenink

c

Steegje 12 c

R. Vogels c

wpl

c

volw

c c

c iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c c c i iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c

c

Tabel boek

i c iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii i iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c

Bcode

c

25

c

titel

c

Alles over informatica

c

c

schrijver

i iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c i c c

c

47 c c

Sommen maken: hoe? c c

13

c

J. Studiemans c c

Alles over pech

c

J. Slimmans c

P. Dommans

c c

ci iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c

c

Tabel lening

ci iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii iiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c

c

Lcode

Bcode

c

25

c

c

datum_terug

ci c c c iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii iiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c

c

9 c

c

9 c c

19

c

47 c

c

c

890526 c c

52

c

890526 890526

c c

ciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii c c c

b. We kiezen de inhoud van de tabel lezer : R 1 = {(Lcode, 1), (naam, B. Teeuwissen), (adres, Steegje 12), (wpl, Delft), (soort, jeugd)}. R 2 = {(Lcode, 9), (naam, R. Vogels), (adres, Plein 13), (wpl, Delft), (soort, jeugd)}. R 3 = {(Lcode, 19), (naam, H. Weenink), (adres, Straat 14), (wpl, Den Haag), (soort, volw)}. c. de eerste eis geldt niet: er wordt nl een Bcode 52 uitgeleend aan Lcode 19. De tweede eis geldt wel. d. Ja dat lijkt me wel handig: men kan nu eenmaal geen boeken uitlenen die niet in de bieb aanwezig zijn; evenals men geen boeken aan een niet-bestaande lezer kan uitlenen. Waarschijnlijk betreft het hier een intikfoutje van de gebruiker: er is wel een Bcode 25 i.p.v. 52; zo kun je dus de gebruiker beschermen tegen intikfouten.

- 38 -

4 Functies

4.2.1 Merk op dat de opgave hoort bij de tabel uit § 4.1. a. Niet zinvolle uitdrukking: achter f 1 zou een attribuut-naam moeten staan en er staat een attribuut-waarde. b. Zinvolle uitdrukking: f 2 (adres ) = Maurits 33. c. Zinvolle uitdrukking: f 1 (woonplaats ) = Den Haag, f 3 (woonplaats ) = Delft. Er staat dus een (zinvolle) bewering die niet waar is.

terwijl

d. Zinvolle uitdrukking: f 1 (idcode ) = 88313. Dit is een natuurlijk getal. Er staat dus een (zinvolle) bewering die waar is. e. Geen zinvolle uitdrukking: f i (idcode ) stelt een attribuut-waarde voor die behoort bij het attribuut idcode. Achter een alkwantor moet een predicaat (een eigenschap dus) staan. f. Zinvolle uitdrukking: bijvoorbeeld geldt er dat f 1 (idcode ) = 88313. Dit is een natuurlijk getal. Ook voor alle andere idcode′s geldt dat ze natuurlijke getallen zijn. Er staat dus een (zinvolle) bewering die waar is. 4.2.2 a. Dit is een functie : elk element van het domein wordt afgebeeld op precies e´ e´ n element van het codomein. b. Ge´ e´ n functie en wel om twee redenen: — het element b wordt niet afgebeeld; — het element a heeft twee verschillende beelden: a en b ;

- 39 -

c. Ge´ e´ n functie en wel om de volgende reden: het element a heeft twee verschillende beelden (namelijk a en b ). d. Dit is een functie : elk element van het domein wordt afgebeeld op precies e´ e´ n element van het codomein. 4.2.3 a. Binaire relatie (te zien aan de geordende paren). Ge´ e´ n functie: niet alle originelen hebben een beeld (bijvoorbeeld 0 niet). b. Ge´ e´ n binaire relatie (wel een unaire). Geen functie dus ook. c. Ge´ e´ n binaire relatie (wel een unaire). Geen functie dus ook. d. Binaire relatie (te zien aan de geordende paren). Tevens een functie: elk origineel heeft precies e´ e´ n beeld. e. Binaire relatie (te zien aan de geordende paren). Ge´ e´ n functie: sommige originelen hebben twee beelden (bijvoorbeeld 0 heeft als d d en - √2). d d beelden √2 f. Binaire relatie (te zien aan de geordende paren). Tevens een functie: elk origineel heeft precies e´ e´ n beeld. g. Binaire relatie (te zien aan de geordende paren). Ge´ e´ n functie: niet alle originelen hebben een beeld (bijvoorbeeld 1 niet die zou als beeld 1⁄2 hebben, maar dat zit niet in Z). h. Binaire relatie (te zien aan de geordende paren). Tevens een functie: elk origineel heeft precies e´ e´ n beeld. 4.2.4 a. ge´ e´ n functie: b.v. 4 heeft twee beelden: 2 en -2; bovendien hebben vele getallen ge´ e´ n beeld (b.v. 0 heeft geen beeld). b. ge´ e´ n functie: vele getallen hebben ge´ e´ n beeld (b.v. 0 heeft geen beeld). c. ge´ e´ n functie: vele getallen hebben ge´ e´ n beeld (alle negatieve getallen hebben geen beeld). d. ge´ e´ n functie: vele getallen hebben ge´ e´ n beeld (alle negatieve getallen hebben geen beeld). Bovendien heeft b.v. 2 twee beelden. e. wel een functie: elk (ree¨ el) getal heeft een (ree¨ el) kwadraat. f. wel een functie: bij elk (ree¨ el) getal kan een ander (ree¨ el) getal worden berekend door het getal met 2 te vermenigvuldigen en er vervolgens 1 bij op te tellen.

- 40 -