Logik:Klausuren/28.02.2003/2.8 Aufgabe
Inhaltsverzeichnis
1. Aufgabenstellung
a) Definieren Sie eine rekursive Funktion $ g(F\,) $, die die Anzahl der Vorkommen der Rela-
tionssymbole, Quantoren und Junktoren der prädikatenlogischen Formel $ F\, $ ermittelt
(z.B. soll $ g((\neg((\forall X)p(f(X), a) \wedge p(a, a)) \wedge \neg(\exists Y )q(Y ))) = 9 $sein).
b) Die Menge der Teilformeln $ \mathcal{T}(F ) $ einer prädikatenlogischen Formel $ F\, $ ist die kleinste
Menge, die die folgenden Bedingungen erfüllt:
1. $ F\in \mathcal{T}(F ) $
2. Wenn $ \neg F \in \mathcal{T}(F ) $, dann ist auch $ F \in \mathcal{T}(F ) $.
3. Wenn $ (F \circ G) \in \mathcal{T}(F ) $, dann ist auch $ F \in \mathcal{T}(F ) $ und $ G \in \mathcal{T}(F ). $
4. Wenn $ (QX)F \in \mathcal{T}(F ) $, dann ist auch $ F \in \mathcal{T}(F ). $
Bezeichne $ \left|\mathcal{T}(F) \right| $ die Mächtigkeit der Menge $ \mathcal{T}(F). $ Beweisen Sie mit struktureller
Induktion, dass $ \left| \mathcal{T}(F) \right| \leq g(F) $ für beliebige aussagenlogische Formeln $ F\ $ gilt.
