Logik:Klausuren/28.02.2001/A.2 Aufgabe
Inhaltsverzeichnis
1. Aufgabenstellung[Bearbeiten]
a) Definieren Sie mit struktureller Rekursion eine Funktion $ h\; $, die die Anzahl der in einer prädikatenlogischen Formel vorkommenden Quantoren ermittelt (z.B. sollte $ h((\forall z)[(\exists y)(\neg P(y,x) \or (P(z,y) \and P(x,x))) \or (\forall x)(\exists v) P(x,v)]) = 4 sein) $. Sie können dabei davon ausgehen, dass die Formel syntaktisch korrekt ist.
b) Um prädikatenlogische Formeln als Prolog-Terme repräsentieren zu können, fehlt uns noch ein Hilfsmittel, zur Darstellung von Formeln der Art $ (Qx)F\; $ . Wir legen hier fest,
dass eine Formel der Art $ (\forall x)F\; $ durch den Prolog-Term $ \mathsf{all(x,F)}\; $ und eine Formel
der Art $ (\exists x)F\; $ entsprechend durch den Prolog-Term $ \mathsf{exist(x,F)}\; $ dargestellt wird.
Schreiben Sie die Formel $ (\forall x)(\exists z)(P(x,z) \or P(z,z)) $ als Prolog-Term. Dabei können Sie davon ausgehen, dass die Operatoren für die Junktoren wie gewohnt vordefiniert sind.
c) Schreiben Sie ein Prolog-Programm $ \mathsf{anz/2}\; $, das die Anzahl der durch einen Quantor gebundenen Variablen einer prädikatenlogischen Formel ermittelt. Verwenden Sie dabei die im Teil b) vorgeschlagene Repräsentation der Quantoren.
