Tentin tekstisisältö

Algoritmimatematiikka
Tentti 10.05.2011

Ei laskinta tai kirjallista materiaalia. Tautologia- ja interferenssikokoelma kääntöpuolella.

Esitä tehtävät 1 ja 2 yhdellä konseptilla ja tehtävät 3 ja 4 toisella.
Laita molempiin konsepteihin nimesi ja opiskelijanumerosi.
1. Olkoon A = (1,2,3), B= (x €N:z=?2n-1,n <3) ja C= (2,3,5)
(a) Esitä alkioittain joukko A? N B x (AUC). Kirjoita kaikki tarvittavat välivaiheet vas-
tauspaperiisi. (3p)
(b) Esittääkö kohdan (a) joukko funktiota? Perustele. (1p)
(c) Todista vastaesimerkillä (ei totuustaululla), että seuraava teoria ei ole pätevä. (2p)
(Va) + (+ 9) A(-r > 9).
2. Olkoon f : Lists [A] — A,
+] 0, jos L=
ra) = N
(head (2)) U f (tail (L)), — muulloin

(a) Esittele kaikki rekursion välivaiheet näyttäen, mitä on f((1,2,3,2,1,2)) sievennetyssä
muodossa. Vihje: () ovat joukkosulkeet. (3p)
(b) Olkoon funktio g esitetty sisä- eli infix-muodossa g (x) = x? ja funktio h ulko- eli prefix-

muodossa h = +0(g 0 cos, g 0 sin). Esitä lauseke h (x) sisämuodossa kaikki sievennyksen
välivaiheet näyttäen ja vastaa kysymykseen: mitä on h (0)? (3p)

Esitä tehtävät 1 ja 2 yhdellä konseptilla ja tehtävät 3 ja 4 toisella.
Laita molempiin konsepteihin nimesi ja opiskelijanumerosi.

3. Seuraavassa on aloitettu todistamaan epäsuoralla todistuksella erästä teoriaa, jonka johto-
päätös on AV B.

1 C>4 P
2. -C—B P
3. S(4VB) — P(IP)

(a) Mitkä ovat teorian premissit sekä teorian lauseke? (1p)

(b) Kirjoita todistus (interferenssitodistuksena) loppuun asti. (5p)
4. Olkoon D = (b,s,h,v,g).-

(a) Muodosta relaatiolle K : D + D, K = ((b,s),(v,h) , (9.9), (s, v)) refleksiivinen sul-
keuma, symmetrinen sulkeuma ja transitiivinen sulkeuma. (3p)

(b) Esitä alkioittain relaatio R : D + D, joka toteuttaa kaikki seuraavat ehdot: R on
irrefleksiivinen osittainen järjestys ja joukon R mahtavuus on 5. Piirrä osittaisesta
järjestyksestä R Hassen diagrammi. (3p)
Loogisia ekvivalensseja eli tautologioita

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Negaatio | Disjunktio | Konjunktio | Implikaatio
Sp=p | pVt=t |pAt=p |p—-t=t
pve=p phe=e poe= "op
PVP=P |PAPp=p top=p
PV-p=t|pn-p=e |e-p=t
pop=t
PS g4="pVg
PS g="9g—0p
(p > d=PMg
Vaihdantalait | Liitäntälait Osittelulait
phg=aNp | PAgAT) = (pAg)Ar | pA(aVr) = (PAg)V(pAr)
PVa=gVp | pV(gVr)=(pva) vr | pV(gAr)= (p vg) A(pvr)
De Morganin lait | Absorptio
"(p Ag) ="pV-g | pPA(pVg)=p
(p Va) =PA>g | PV (pAg)=p

 

PA(PVa)=pNg
PV(-PAg)=pVag

 

 

 

 

 

 

 

 

 

 

 

 

 

 

MP MT Conj Simp
A, A>B A—B,-B A,B ANB
8 TA J ANB J
Add DS HS
A AVB,-B A>B,B>C
J AVB N AG
muista rajoitukset
UI UG EG EI
Va Wiz) W(t) W(t) 32 W(z)
J Wt) s. Va W(z) 2.37 W(z) J Wt)

 

 

 

 

 

 

Ekvivalensseja

 

Ma W (2) = W (n)

3z (A(x) V B(z)) = 3z A(x) V 3z B(z)
3z (A(x) — B(z)) = Vx A(z) — 3x B(z)
3z3y W(z,y) = Jy 3z W(z,y)

 

SW (2) = Wa)
Vz (A(x) A B(z)) = Vz A(x) A Ve B(z)
Va Vy W (z,y) = Vy YT W (x,y)

 

 

 

Ya (CV A(z)) =CV Vx Al(z)
3x (CV A(z)) = CV 3r A(x)
Vz(C — A(xz)) = C — Vx A(x)
Vz (A(z) —> C) = 3x Alz) > C

 

ValCA AG) = CAV An)
Ax (CA A(x) = CA3z A(x)
3r (C — A(z)) = C — Ja A(x)

 

 

3z (A(z) > C) = Vz A(z) > C

 

Implikaatioita

 

Vz A(z) > 3z A(z)
Vz A(x) VVz B(z) > Vz (A(x) V B(z))
3y Va W (x,y) > Yz3y W (x, 4)

 

 

ST (42) A B(2)) = 32 An) A 3 Pix)
Vz (A(x) > B(z)) > Vx A(x) — Ye B(z)