T. Kärkkäinen
Kurssi: Formaalit menetelmät 2002

Harjoitus 3

Näiden tehtävien tekemiseen ei demoaika taatusti riitä, mutta niiden yrittäminenkin on hyödyllistä. Tehtävien tekemistä saatetaan osittain jatkaa myös neljänsissä harjoituksissa.

Tehtävä 1

Tee ohjelma, joka muodostaa annetuista alkeismerkeistä kaikki mahdolliset k:n mittaiset merkkijonot. Kokeile ohjelmaasi binääriaakkosille {0, 1} k:n arvoilla k = 1, 2, 3, 4.

Tehtävä 2

Tee tehtävän 1 ohjelman avulla ohjelma, joka muodostaa ja tulostaa annetulle, korkeintaan neljästä peruspropositiosta muodostuvalle lausekkeelle sitä vastaavan totuustaulun (tulkittavan lausekkeen syöttämistä ei tarvitse ohjelmoida yleiselle tapaukselle, vaan se voidaan sopivassa syntaksissa pultata ohjelmaan kiinni).

Tehtävä 3

Olkoon meille annettu predikaattilogiikan lauseke P (x) (jonka syöttämistä ei tarvitse ohjelmoida yleiselle tapaukselle, vaan se voidaan sopivassa syntaksissa pultata ohjelmaan kiinni). Toteuta mahdollisimman yksinkertainen ohjelma, joka palauttaa totuusarvon siitä, päteekö lauseke ja

Testaa ohjelmaasi tapauksissa, joissa

1. annetulle reaalilukuvektorille x halutaan selvittää,

   "Onko x:n jokainen komponentti suurempi kuin nolla?"

   "Onko x:ssä nollaa suurempi komponentti?"

2. annetulle joukolle merkkijonoja halutaan selvittää,

   ``Alkaako jokainen merkkijono kirjaimella K/k?"

   ``Alkaako jokin merkkijono kirjaimella K/k?"