Exam text content

 

MAT-02650 Algoritmimatematiikka / Hirvonen

Tentti 14.10.2014
Ei laskimia tai kirjallista materiaalia. Kaavakokoelma kääntöpuolella.

Missään tehtävässä pelkän lopputuloksen esittäminen ei riitä, vaan vastauspaperin tulee

sisältää päättely, jolla lopputulokseen päädytään.

1. Olkoon A = f1,3,6,8). Määritellään joukossa A x A relaatiot R ja S siten, että

aRb jos ja vain jos b on luvun a tekijä eli b|a

a9b jos ja vain jos amodb70

(a) Esitä alkioittain joukko R1N S.
(b) Muodosta yhdistetty relaatio R o S. Onko se refleksiivinen? Onko symmetrinen?

Onko transitiivinen?

2. Onko alla esitetty f : (5,00) > (—00, 3) injektio? Entä surjektio? Jos on, perustele
asiaa injektion ja surjektion määritelmien mukaisesti. Jos f on bijektio, esitä käänteis-

funktion lauseke.
3T

tj.

 

3. (a) Todista, että josn € N, niin 4 on luvun 1+(—1)” (2n — 1) tekijä.
(b) Olkoon a € O ja b € R — O. Todista epäsuoralla todistuksella, että a +b € R-— O.

4. Todista alla oleva teoria loogisen päättelyn keinoin ILMAN totuustaulua.

(4 > (BV O))A(B—+C) > (A4— 0).

 
Loogisia ekvivalensseja eli tautologioita

 

Negaatio | Disjunktio Konjunktio | Implikaatio
0=7P |pVt=t PAt=p pot=t
PVe=p |pie=e p>e= op
PVp=p |pAp=p |t—-p=p
PVp=t|pit-p=e|e>+p=t
P=Pp=t
P>a=pVg
Praia p
> 9) =pNg

 

 

 

 

 

 

 

 

Vaihdantalait | Liitäntälait Osittelulait
PAI=INP | PA(JAT) = (Ag) Ar PA (4 Vr) = (PAg)V(pAr)
PVa=aVP | PV(agVr)=(pvg) vr PV (4Ar) = (pV 9) A (pvr)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

De Morganin lait | Absorptio
"PA =PV-g| PAGRVa=p
"PV 9) =-PMg | PV (pAg) =p
PA(PVa)=pNg
PV(PA9)=pVg
Inferenssisääntöjä
MP MT Conj Simp
AAB | 45B,-B A,B ANB
Pi TA JJANB TA
=> Add =" DS HS
A AVB,-B AB B-C
J AVB JA < AC
muista rajoitukset
UI UG EG EI
Va W'(x) W(t) W(t) 30 W (x)
W +. Va W(z) 2.32 W (x) WG)
Ekvivalensseja

 

Va W (z) = 3z-W(x) 37 W(z) = Ve -W(z)

3z (A(x) V B(z)) = 3z A(x) V 3 B(x) Vz (A(x) A B(z)) = Va A(x) M Ve B(x)
3z (A(x) — B(z)) = Yr A(z) > Je B(x) | Ve Vy W (2,4) = Vy V= W(x,y)

Je Jy W (x,y) =3y3z W (x,y)

 

 

 

 

 

 

 

Ve (CV A(z)) = CV Vx A(z)
3z (CV A(z)) = CV 37 A(x)
Va (C— Alz)) =C > Vz A(z)
Vz (A(x) > C) = 3x Ala) > C

Va (CAAz)) = CA ve A(z)
3 (CN A(x) = CA3x A(n)
3z(C > A(z)) =C +» Az A(z)

 

 

3z (A(x) > C) = Vx Ala) > C

 

Implikaatioita

 

 

Vz A(x) > 3z A(x) Az (A(z) A B(z)) > Je A(z) X 3 B(z)
Vo Alz) V Ye B(z) > Vz (A(x) V B(z)) | Vx (A(x) > B(z)) > Vr A(z) > Ya B(z)
Jy Va W (x,y) >> Va Jy W (x,y)