Tentin tekstisisältö

 

 

Tentti(1) MAT-02650 Algoritmimatematiikka
10.5. 2019 Hansen

 

 

 

 

 

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 RC Ax A,SCAxA TECAxA, missä

R = ((1,2), (1,3), (1,1)], S = (02,1), (1, 2, (2,3)) ja T = (43, 1), (3,2), (1,3)

Laske
|((R 0 5) N (Ro TI.

(b) (3 pistettä) Tarkastellaan relaatiota R C Z<Z, missä a Rb 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 / : [1,00) > No, ja f(z) = [10g,(z) |.
1) Onko / injektio? (lyhyt perustelu)
2) Onko f surjektio? (lyhyt perustelu)
3) Laske f(a), kun a = 16V?.

(b) (3 pistettä) Muuta lauseke (g Vr) > p konjunktiiviseen normaalimuotoon (CNF)

3. (a) (3 pistettä) Osoita määritelmän nojalla, että (n? + 2)? = O(n').

(b) (3 pistettä) Osoita määritelmän nojalla, että n? — 4n + 2019 = 0(n3).

 

 

4. Osoita tautologioita ja päättelysääntöjä käyttäen (ilman totuustaulua), että
(CCVB)A(4+0)A (B+ D)) 3 AVD

on pätevä teoria.

KAAVAKOKOELMA JAETAAN.
Algoritmimatematiikka MAT-02650 Kaavakokoelma Henri Hansen

 

Ekvivalensseja ja päättelysääntöjä propositio- ja predikaattilogiikkaan

 

Disjunktio | Konjunktio | Implikaatio
pVTST |pAT&p |p-T6ST
PpVF&p |pAF&F |p>F< p
PpVpep PphApop T—>7&>p
pV-p&T|pA-pe&F|F+peT
popeT
Pp>ag>PVg
p>rag749> p
lp > 9) &PAa

 

 

 

 

 

De Morganin laki absorptiolait

(PA 9) > PV g | p A (p Va) p

"(pv a) > PA g | PV (p A 9) &p
PAD V 4) & (PAg)
PV (SPA) & (p V 9)

 

 

 

 

 

Vaihdannaisuus | Liitännäisyys Osittelu
PAJSINP —|PA(JAT) & (PAI) AT | p A (g Vr) & (PA) V(p Ar)
pYgogvp |pv(gVvr) &(pva) Vr|pv(gAr) > (pv) Alv)
Vx : W(z) > 3x : -W(z) dx : W(z) — Ve : "WW (z)

Az : (A(x) V B(z)) & Az : A(z) VAx : B(x) |Vx:(Alz) AB(xz)) & Vx : Alx) AVz : B(z)
Ax : (A(x) > B(x)) & Vx : Alx) > Jz : B(z) | Vx : Vy : W(z,y) & Vy : Va: W (x,y)

Ax : Jy : W(z,y) & Jy : Jr : W(z,y)
Vx: (CV A(z)) & CV Vx: A(z) |Vx:(CAA(z)) & CAvz: A(x)
Az : (CV A(z)) & CV Ar: A(z) |3x:(CAA(z)) & C AA: A(z)
Vx: (C > Alz)) & C > Vx: A(x) : (C > Alz)) & C > Az : Alx)
Vx: (A(z) > C) & Az : A(x) > C | 3x : (A(x) > C) & Vz : A(x) > C

 

 

 

 

 

 

 

 

 

 

 

 

U 1

 

 

 

 

Vx: A(x) > Ar : A(z) Az : (A(x) A B(z)) > Jx : A(x) AX Ax : B(z)
Vx : A(x) V Va : B(x) > Vz : (A(x) V B(z)) | Vz : (A(x) > B(z)) > (Vz : A(x) > Vx : B(z))
Jy : Vx: W(z,y) > Vx :3y : W(z,y)

 

 

 

 

 

 

 

 

 

 

 

 

 

Päättelysäännöt:

MP MT Conj. Simp | Add| DS HS

AAB oB.45B AB AAB A | AVBoB | A5B.B+C
EB -4 ANB A 3vB A 45C
UI UG EG EI

Va:A(a) A(t) A) 3x:A(2)
40) Va:Ala) 37:A(x) 10)

(mikä tahansa ?) | (mielivaltainen 7) | (mikä tahansa £) | (uusi £)

 

1