Tentin tekstisisältö

 

 

Tentti(1) MAT-02650 Algoritmimatematiikka
9.5. 2017 Kaarakka

 

 

 

 

 

 

Vastaa jokaiseen kysymykseen ja perustele vastauksesi huolellisesti! Tentissä ei saa käyttää muistiin-
panoja, kirjallisuutta eikä laskinta. HUOM. Tehtävät EIVÄT ole vaikeusjärjestyksessä!

Kirjoita kaikkiin papereihin selkeästi nimesi, opiskelijanumerosi ja myös koulutusohjelmasi.

Muistathan antaa palautetta Kaiku-järjestelmän kautta saadaksesi opintosuorituksen.

1. (a) (3 pistettä) Olkoon A = [1,2,3) ja R:A+A4,9:A444,T:A+4A, missä

R= (1,2), (1,3), (1, 1), 5 = ((2,1), (1, 2), (2,3)) ja T= ((3,1), (3,2), (1,3))-

Laske
((R o S) N (RoT)I.

(b) (3 pistettä) Tarkastellaan relaatiota R : Z + Z, missä aRb jos ja vain jos a + b on
parillinen. Jos R on ekvivalenssirelaatio, niin todista se tai jos R ei ole ekvivalenssirelaatio,
niin todista se.

2. (a) (3 pistettä) Olkoon f : [1,00) + No, ja f(x) = [10g2 (x) |.

* Onko f injektio? (lyhyt perustelu)
* Onko f surjektio? (lyhyt perustelu)
* Laske f(a), kun a = 162.

(b) (3 pistettä) Muuta lause p V g täyteen (täydelliseen) disjunktiiviseen normaalimuotoon
(DNF).

3. (a) (3 pistettä) Osoita raja-arvotarkastelun avulla, että (n? + 2)? = o(n>).

(b) (3 pistettä) Osoita määritelmän nojalla, että n? — 4n + 2017 = 2(n).

4. Osoita tautologioita ja päättelysääntöjä käyttäen (ilman totuustaulua), että
(CVD) A (4 0) A (B+ D)) > -=AV-B

on pätevä teoria.

KAAVOJA ON PAPERIN TOISELLA PUOLELLA.

 
Loogisia ekvivalensseja eli tautologioita

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Negaatio | Disjunktio | Konjunktio | Implikaatio Ekvivalenssi
—p=p |pvt=t |pat=p |p>t=t Pp g=(P>a)A(4—>Pp)
pVve=p phe=e p>e=p
PVp=p |pAp=p top=p
PV-p=t|p-p=e |e>p=t
po>p=t
P>g="pVg
p>g=4>
Vaihdantalait | Liitäntälait Osittelulait
PAg=gNp | PAgAT)=(pAg)Ar | pA(gVr)=(pAg)V(pAr)
PVa=gVp | PV(gVr)=(pVa)Vr | PpV(aAr)= (p Va) AlpVr)
De Morganin lait Absorptio
"(PA 4) = PV a | PA(PVa)=p
"(p Va) = PM g | PV (pNg) =
PA(PVa)=pNg
PV(PAd)=rvg
Inferenssisääntöjä
MP MT Conj Simp
A,45>B | A+B,-B A, B ANB
BB JOTA J ANB JA
Add DS HS
A AVB,-B A>B,B>C
JAVB JA JAC
muista rajoitukset
UI UG EG EI
Ya W (x) W(1) W(t) 32 W(x)
W0 Va Wia) | WG) W0
Ekvivalensseja
Ya W (2) = W (a) W (2) = WG)
3z (A(x) V B(z)) = 3x A(x) V 3z B(z) Vr (A(z) A B(z)) = Vz A(z) A Vz B(z)
3Az (A(x) > B(z)) = Vz A(z) > 3z B(z) | Ve Vy W (x,y) = VyVz W (x,y)
37 3y W (x,y) = 34 37 W (x,y)
Vr (CV A(z)) = CV Vz A(z) Vz(CAAl(z)) = CAVzA(z)
Jr (CV A(z)) =C V Ar A(z) Ai Ea. )) = CA3rA(z)
Vz (C > A(z)) = C > Vz A(z) | 3z(C > A(z)) =C > Ax Alz)
Vz (A(x) > C) = 3z A(z) + CO | 3z (A(z) > C) = Vr Alz) > C

 

 

 

 

Implikaatioita

 

Vz A(x) > 3z A(z)

 

Vr A(z) V Vr B(z) > Vr (A(z) V B(z))
Jy Yz W(z,y) > Vz Jy W (x,y)

 

3z (A(x) A B(z)) > 3xz A(z) A 3 B(z)
Vr (A(z) > B(z)) > Vx A(z) > Vx B(z)