Logiikka tietotekniikassa: erityiskysymyksiä

Tentti

26.5.1994

Merkinnät:

! ---- not

hakasulut ---- nelio

^ ---- and

v ----- or

1. a) Anna määritelmä kehykselle ja mallille modaalilogiikassa. Anna malli. jossa

lause ! []P^![]!P

on pätevä sekä kehys, jossa lause ! [] P <->[]P

on pätevä, missä P on atomilause.

b) Olkoon L joukko kehyksiä. Anna määritelmä sille, milloin lause P seuraa loogisesti globaaleista premisseistä Sigma ja lokaaleista premisseistä T kehysjoukon L suhteen (milloin Sigma |= L (L alaindeksinä) T ==> P pätee) sekä osoita, että

{![]!P} |= L (L alaindeksinä) {P} ==> []P

ei päde, missä L on symmetristen kehysten joukko ja P on atomilause.

2. a) Tutki päteekö {} |=s5 {} ==P -> (![] ![]P -> [] !P)

missä s5 on refleksiivisten, symmetristen ja transitiivisten kehysten joukko ja P atomilause. Jos väite pätee, anna taulutodistus. Jollei se päde, anna vastamalli.

b) Osoita, että { ! []![]P->(P->[]P)}|=s4 {} ==> (P^![]![]P)-> [][](![]!P v P)

pätee taulumenetelmällä, missä S4 on refleksiivisten ja transitiivisten kehysten joukko.

3. a) Määritä oletusteorian

				p:q^!r		p:r^!q

			< { ---------------, ----------------},{p,q,-->!p}>

				q		r

laajennukset. Perustele vastauksesi.

b) Formalisoi seuraavat väittämät oletusteoriaksi:

1. Normaalisti italialaiset juovat viiniä..

2. Normaalisti ranskalaiset juovat viiniä.

3. Jaques on italialainen tai ranskalainen.

Voidaanko ko. oletusteorian laajennuksista päätellä Jaquesin juovan viiniä?

4. a) Määritä yleisen logiikkaohjelman

p <-- q, ~h

q <-- ~r

h <-- ~r, ~p

stabiilit mallit.

b) Kuinka monta stabiilia laajennusta on alkuoletusten joukolla

n