Logik:Klausuren/01.02.2002/A.7 Aufgabe

1. Aufgabenstellung

a) Betrachten Sie die folgende Formel $ F\; $ und die gegebenen Substitionen $ \sigma\; $ und $ \theta\; $.

$ F = (\exists Z)((\forall X)(p(X,Y) \rightarrow q(Y)) \and p(X,Z)) \; $
$ \sigma = \{X \mapsto Z, Y \mapsto f(Z), Z \mapsto Y\}\; $
$ \theta = \{Z \mapsto f(a), W \mapsto X, Y \mapsto Z\}\; $

Geben Sie $ F\sigma\; $ und $ \sigma\theta\; $ an und markieren sie deutlich die Vorkommen von freien Variablen in $ F\; $ und $ F\sigma\; $.

b) Definieren Sie durch strukturelle Rekursion eine Funktion $ f\; $ , die jeder prädikatenlogischen Formel $ F\; $ eine ganze Zahl zuordnet. Dabei soll $ f(F)\; $ gleich der Anzahl der Vorkommen universeller Quantoren in$ F\; $ abzüglich der Anzahl der Vorkommen existentieller Quantoren in $ F\; $ sein.

4. Alternativen/Diskussion/Hinweise etc.

---

zur Klausur 01.02.2002
Aufgaben-Kategorie PL - SubstitutionenAufgaben-Kategorie PL - SyntaxAufgaben-Kategorie Rekursion