Tentin tekstisisältö

MAT-02650 Algoritmimatematiikka / Hirvonen
Tentti 21.10.2016
Fi 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 = £1,3,6,8). Määritellään joukossa A x A relaatiot R ja S siten, että

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

aSb jos ja vain jos amodbz70

(a) Esitä alkioittain joukko R! n S.

(b) Muodosta yhdistetty relaatio R o S. Onko se refleksiivinen? Onko symmetrinen?
Onko transitiivinen?

2. (a) Olkoon A = £0,1,2,3,4,5). Onko funktio f : A > A, f (2) = (5x) mod6 injektio?
Entä surjektio?
(b) Merkitään + (z,y) = z + y ja div (2,4) = 5: Sievennä (kaikki välivaiheet esittäen)
f (3,4), kun
f =divo(+ o (div, div o (2,1)) , 1) .

3. Alla on erään teorian inferenssitodistus ilman perusteluita. Kopioi tämä vastauspaperiisi
ja täydennä puuttuvat perustelut. Mikä teoria tässä on todistettu?

 

1 45B

2 BC

3. 2 (4> 0)
4 AN-C

5 A

6. B

T. =C

8 DB

9. BN-B
10. e

11 430

M.O.T. 12,11! CP

4. (a) Todista, että kahden peräkkäisen kokonaisluvun summa on parillinen.

(b) Todista induktiotodistuksella, että n (n +1)(n +2) on jaollinen kuudella kaikille
neEN.
 

Loogisia ekvivalensseja eli tautologioita

 

Negaatio

Disjunktio | Konjunktio | Implikaatio Ekvivalenssi

 

PP

 

 

pvt=t |pAt=p |p>t=t P&a=(P> g) A (9—>p)

pVe=p |pie=e p > e= p
PVPp=P |pAp=p |t>p=p

 

PV-p=t|pit-p=e|e>p=t De Morganin lait

 

p>p=t "(p Ag) =-pV-g
P>a=pVd |-(pVg)=-pAg
P>d="9> 0

 

 

 

Vai!

 

hdantalait | Liitäntälait

Osittelulait

 

PAN
PV

 

9=49Np | PA(JAr)=(pMg
9=gVP | PV(aVr)=(pvg

 

 

AT |PAJVr)= (pAg) V(pAr)
VT |PV(gAr) = (pV9) Alp Vr)

 

 

 

Inferenssisääntöjä

 

MP MT
ÄÄ B| AB

Conj Simp
A,B ANB

 

SB EA

J ANB EA

 

Add DS
A AV B,-B

HS
AS B,B>C

 

 

 

= ANI EA

 

 

AC

 

muista rajoitukset

Ekvivalensseja

 

UI UG
Va W f(z) W (2)

EG EI
W(t) 32 W (z)

 

 

 

 

 

 

 

 

 

Vaz W (z) = 37 -W (x)

3z (A(x) V B(z)) = 3z A(z) V 3z B(z)
3z (A(z) > B(z)) = Vx A(x) > 3z B(z)
37 Jy W (x,y) = Jy Ar W (x,y)

37 W (x) = Ve -W(z)
Vx (A(x) A B(z)) = Vx A(z) A Vz B(z)
Va Yy W (x,y) = Vy Yz W (2,4)

 

 

 

 

Vz (CV A(z)) = CV Vx A(x)
3z (CV A(z)) = CV 3z Alx)
Vx (C > A(z)) = C > Vx Alx)
Vz (A(x) > C) = Ax A(z) > C

 

Vz (CN Al(z)) = CN Vz A(x)
Ax (CA A(z)) =C A3z A(x)
3Az (C > A(z)) =C > 3x A(x)
3z (A(z) > C) = Vz A(z) > C

 

 

 

 

Implikaatioita
Vz A(x) > J3x A(z) Jr (A(z) A B(z)) > 3z A(z) A3z B(x)
Ve A(x) V Vz B(z) > Vx (A(x) V B(z)) | Ve (A(x) > B(z)) > Vx A(x) > Vr B(z)
Jy Ya W (x,y) > Ve 3y W (x,y)