Nächste Seite: Aufgabe 6 Vorige Seite: Aufgabe 4

Aufgabe 5

Definiere eine Funktion gaG, die jede wohlgeformte Formel eines Prädikatenkalküls 1. Stufe in ihre gaG-Darstellung überführt. Dabei können die folgenden Hilfsfunktionen benutzt werden:

blatt(x,y) liefert NIL, wenn das Symbol x nicht in dem gaG y vorkommt, und einen Pointer auf den Knoten in y, der mit x markiert ist, wenn x in y vorkommt.

frei(x,y) liefert NIL, wenn die Variable x nicht frei in dem gaG y vorkommt, und einen Pointer auf den Knoten in y, der mit x markiert ist, wenn x in y frei vorkommt.

gebunden(x,y) liefert NIL, wenn die Variable x nicht gebunden in dem gaG y vorkommt, und einen Pointer auf den Knoten in y, der mit x markiert ist, wenn x in y gebunden vorkommt.

Hinweis: Definiere gaG induktiv über den Aufbau der Formeln. Zur Vereinfachung nehmen wir an, daß in unserem Kalkül nur einstellige Funktions- und Prädikatssymbole vorkommen.