Tentin tekstisisältö

 

 

 

 

 

 

 

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.
Ratkaise tehtävät 1 ja 2 omalle paperilleen ja tehtävät 3 ja 4 omalle paperilleen.

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

1. (a) (3 pistettä) Olkoot RC AxB ja S,T € BxC. Osoita, että yhdistetylle binäärirelaatiolle
pätee

Ro(SNT)C(RoS)N(RorT).
0 (3 pistettä) Osoita määritelmän nojalla, että loga(n? — n) = %(log, (n).
x Vastaa lyhyesti (kyllä/ei) kohtien (a)-(f) kysymyksiin. Jokaisen kohdan oikeasta vastaukses-

ta saat yhden pisteen, väärästä vastauksesta väh nnetään yksi piste ja vastaamatta

jättäminen on nolla pistettä. Tehtävän kokonaispistemäärä ei kuitenkaan mene negatiiviseksi.
Tarkastellaan relaatiota

F:N6ON, f(n) =2n—1
(a) Onko relaatio-f-ekvivalenssirelaatio?
(b) Onko relaatio f transitiivinen?
(e) Onko relaatio f symmetrinen?
(4) Onko relaatio f funktio?
(€) Onko relaatio f injektio?
(ej Onko relaatio f surjektio?

x Osoita tautologioita ja päättelysääntöjä käyttäen (ilman totuustaulua), että
((4VBVO)MC> A) A(B + (4v0))) SA
on pätevä teoria.

k (2) (2 pistettä) Osoita, että AN (BU 4) = AVB.

&) (2 pistettä) Lausu predikaattilogiikkaa ja kvanttoreita käyttäen: Kaikille kokonaisluvuille
löytyy kokonaisluku siten, että näiden lukujen summa on 100.

(£) (2 pistettä) Osoita, että kvanttorein suljettu lause

3z € RW ER:z+y%41

on epätosi.

KAAVOJA ON PAPERIN TOISELLA PUOLELLA.

 
 

Loogisia ekvivalensseja eli tautologioita

 

Negaatio | Disjunktio | Konjunktio | Implikaatio Ekvivalenssi

 

 

 

 

 

p=p |pVt=t pAt=p pot=t
pVe=p phe=e pore=p
DD P PNP | (Pn
PpV-p=t|pAp=e |e>p=t
pop=t
p>a=pVa
Dea 39 =p

PpEg=(P>dNg>7)

 

 

 

Vaihdantalait | Liitäntälait

Osittelulait

 

 

 

PAI=INP | PA(JAT) = (PAAJAT | PA(JVr) = (PA) V (PAT)
PVa=aVp |Pv(gVr)=(pva) Vr | pV(gA7) = (pV9) A(evr)

 

 

 

 

 

De Morganin lait
=(pAg)=-pV-g
(PV 9) = Phd

 

 

 

 

 

 

 

 

 

 

 

 

 

Inferenssisääntöjä
MP MT Conj Simp
A, A>B A+ BB A, B ANB
vB 4 AAB A
Add DS HS
A AV B,-B A+ B,B>C
JAVB E SSÄSHG
muista rajoitukset
UI UG EG EI
Ya W (x) W(t) 1140) 37 W (x)
W) +. Y2W (x) 2. 37 W(z) 10)

 

 

 

 

 

 

Ekvivalensseja

 

Va W (x) = 37 -W (x)
3e (A(x) V B(z)) = 3z A(z) V 3x B(z)

So 3y W (x,y) = 3 32 W (2,4)

 

3r (A(x) > B(z)) = Vx A(z) > 3x B(z)

So W (x) = Va -W (x)
Vo (A(x) A B(z)) = Yz A(z) A Ve B(z)
Va Yy W (x,y) = Vy Ve W (x,y)

 

 

 

Va (CV A(z)) = CV Va A(x)
Jr (CV A(z)) =C V3z A(x)

 

Vz (C —> A(z)) = C > Vr A(x)
Ve (A(z) > C) = 3r A(x) > C

 

Yr (CAN A(xz)) =C NVYa A(x)
3Az (CA A(z)) = CA 3z A(z)
x (C > A(z)) = C + Ax A(x)
3z (A(z) > C) = Vx A(x) > C

 

 

Implikaatioita

 

Vx A(x) > 37 A(x)

 

Jy Yz W (2, y) > Ye Jy W (x,y)

Vx A(x) V Vx B(x) => Vx (A(x) V B(z))

 

Jo (A(x) A B(z)) > 3z A(x) A 3e B(z)
Vz (A(x) > B(z)) > Vx A(x) > Ve B(z)