Teknillinen korkeakoulu

Digitaalitekniikan laboratorio

Tik-79.149 Diskreetit rakenteet

tentti 17.5.1994

Tenttitilaisuudessa saa käyttää kurssin oppikirjaa, sekä Plotkinin prujua!

1. Olkoon 3 järjestetty joukko

tt

|

|

ff

Piirrä seuraavien järjestettyjen joukkojen diagrammit:

Kaavakuva

n

2. Plotkinin prujun ohjelmointikieleen Imp lisätään lause entangle B in C jonka semantiikan tulisi toteutaa yhtälö

entangle B in C = if B then C; entangle B in C; C else C

(a) Lisää kieleen entangle B in C määritelmä.

(b) Esitä lauseen määritelmä kiintopisteyhtälönä (F(x) = x).

(c) Esitä Kuva

(d) Minkä takia entagle lauseen toteutus ohjelmointikieleen voi käytännössä tuottaa

ongelmia (vrt. while-operaation toteutus)?

3. Mitkä seuraavista joukoista D ovat konsistentteja P:n osajoukkoja ja mitkä suunnattuja P:n osajoukkoja?

Kuva

Perustele!

4. Osoita, että osoittaiskuvausten (N --o--> N) CPO:n äärelliset alkiot ovat kuvaukset joilla on äärellinen alkukuva.