Exam text content

 

 

 

 

 

 

 

 

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ä) Osoita, että relaatio R € O x O, joko on tai ei ole ekvivalenssirelaatio, kun
relaatio R määritellään aRb joss a — b € Z.

(b) (3 pistettä) Muuta lause p (4 A p) täyteen konjunktiiviseen normaalimuotoon (CNF)
2. Vastaa lyhyesti (kyllä/ei) kohtien (a)-(f) kysymyksiin. Jokaisen kohdan oikeasta vastaukses-
ta saat yhden pisteen, väärästä vastauksesta vähennetään yksi piste.ja vastaamatta
jättäminen on nolla pistettä. Tehtävän kokonaispistemäärä ei kuitenkaan mene negatiiviseksi.
Tarkastellaan joukkoa
A= ((n,-n) : nEZ) CZ xZ.

(a) Onko joukko A karteesinen tulo joukossa Z?

(b) Onko joukko A relaatio?

(e) Onko joukko A ekvivalenssirelaatio?

(d) Onko joukko A funktio?

(e) Onko joukko A injektio?

(£) Onko joukko A surjektio?

3. Osoita tautologioita ja päättelysääntöjä käyttäen (ilman totuustaulua), että
((4VBVO)n(4— (Bv 0) n (-0)) E

on pätevä teoria.

4. (a) (2 pistettä) Esitä funktio
f(a) = sin(z? — x)
prefix- eli ulkomuodossa (muuttuja/muuttujat annetaan vain kerran).
(b) (2 pistettä) Näytä, että nIn(n) = Am), ;
(c) (2 pistettä) Osoita, että e

x

v

(AU B)N(AUB)N(AUAUB)=0

KAAVOJA ON PAPERIN TOISELLA PUOLELLA.

 
Loogisia ekvivalensseja eli tautologioita

 

Negaatio | Disjunktio Konjunktio | Implikaatio Ekvivalenssi

 

—p=p | pvt=t |pAt=p |pt=t PO I=(P>DN4>7)
pVe=p phe=e Pp->e=p
PVPp=p |pip=p to>p=p
PV-p=t|ph-p=e ep=t
pop=t
La DVI
P>I=4>p

 

 

 

 

 

 

 

 

Vaihdantalait | Liitäntälait Osittelulait
PAI=AINp | PA(JAT)= (PADAT | PA VI) =GADV Pin
PVa=avp | pv (avr)=(pvg) Vr | pv (dar) = (pv a) A (pVr)

 

 

 

 

 

 

 

De Morganin lait
Na) =-pv-g
Tp Va) = -pA-g

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Inferenssisääntöjä
MP MT Conj Simp
A, 4>B | A4+B,-B A, B ANB
SB =d = ANB SA
Add DS HS
A AVB,-B A=+B,B+sC
SAV JA AC
muista rajoitukset
UI UG EG EI
Va Wiz) W(t) W(t) 37 W (x)
WO 2. Va W (x) =. W (x) WG)
Ekvivalensseja
Va W(z) = 37 -W(z) dx W (x) = Ve -W (x)

3z (A(x) V B(z)) = 3z A(x) V 37 B(x) Vz (A(x) A B(z)) = Vx A(x) A Vr B(x)
3z (A(x) > B(z)) = Va A(z) + o B(x) | Va Yy W(z,y) = Yy Va W (x,y)
37 3y W (2,4) = 3432 W (x, y)

 

 

 

 

Ya(0V AG) = CVeA0) | OA) -0N10)
3z (CV A(z)) = CV 3z A(x) 37 (CA A(x)) = C MA3z A(z)
Va(C— A(z)) = C+ Vx A(x) | 3x (C > A(z)) = C > 3z A(z)
Va (A(x) > C) = 3: A(a) + € | Ar (A(x) > C) = Va A(z) + C

 

 

 

Implikaatioita
Vx A(z) > Ja A(x) Ar (A(z) A B(x)) > 3x A(x) A 3 B(z)
Vz A(x) V Vx B(z) > Vx (A(x) V B(x)) | Va (A(x) > B(x)) > Vr A(x) > Ve B(x)
Jy Ve W (x,y) > Vr Jy Wl(z,y)