Logiikka tietotekniikassa: erityiskysymyksiä

Tentti

24.5.1995

Merkinnat: hakasulut --- nelio

Olkoon P, Q, R atomilauseita.

1. (a) Anna (mahdollisten maailmojen) malli, jossa lause

! [][](((P-->R)-->Q)-->(P-->Q)) on tosi muttei pätevä. ,

(b) Olkoon L kaikkien kehyksien joukko. Osoita, että [][]P ei seuraa loogisesti globaaleista premisseistä {P-->[]![]!P} ja lokaaleista premisseistä {[]P} kehysjoukon L suhteen, ts. että

{P-->[]![]!P} |=L {[]P==>[][]P (L alaindeksi)

ei päde

2. (a) Osoita taulumenetelmällä, että

{![]Q-->![]P} |=s5 {Q} ==> ! (*Q-->[]Q)--> []([]P-->[][]Q)

(*:llä merkitty kärjellään seisovaa vinoneliötä, s5 on alaindeksina)

pätee, missä S5 on refleksiivisten, symmetristen ja transitiivisten kehysten joukko.

(b) Anna lausejoukon

Sigma={L(P-->Q)-->(Qv!P),!L(!Q-->!P)-->(Q-->P)}

kaikki AE-laajennukset ja tutki mihin AE-laajennuksiin lause L!L(Pv!Q) kuuluu.

3. (a) Graafinväritysongelmassa on tarkoituksena värittää graafin G solmut värien

joukon V väreillä siten, että toisiinsa kytketyt solmut ovat eri väriset. Ongelman määrittelyä voidaan tarkentaa seuraavasti:

1. Jokaisella solmulla on korkeintaan yksi väri.

2. Jos solmujen välillä on kaari, ne ovat eri väriset.

3. Solmu on väritetty, jos sillä on ainakin yksi väri.

4. Graafi on väritetty, jos sen kaikilla solmuilla on väri.

Laadi näiden perusteella ATM-järjestelmä, joka ratkaisee väritysongehnan, kun värejä on kaksi (esim. p ja v) ja graafissa G on kolme solmua s1, s2 ja s3 kytkettynä seuraavasti:

s1 -- s2 -- s3

Vihje: käytä oletuksia pi ja vi (i kuuluu joukkoon{1, 2,3}) solmujen värien esittämiseen (esim. p1 on in, kun solmun s1 väri on p).

(b) Selvitä laatimasi ATM-järjestelmän solmujen kontekstit ja kerro, kuinka väritysongelman ratkaisut ovat saatavissa järjestelmästä.

4. (a) Alla on esitetty kaaviokuva eräästä digitaalipiiristä ja sille suoritetuista mittauksista. Käyt ä oletuslogiikkaa piirissä esiintyvien vikojen selvittämiseen.

(b) Karsi edellä määritettyjä diagnooseja seuraavien lisätietojen avulla (tarkastele jokaista kohtaa erikseen):

1. Komponentit vikaantuvat hyvin pienellä todennäköisyydellä.

2. Vikaantuneen and-portin output on aina 1.

3. Invertterin output on lisämittauksen perusteella 1.