Logik:Klausuren/01.02.2002/A.3 Aufgabe

1. Aufgabenstellung

Gegeben sei folgende Definition von Mengen von Pseudoteilformeln: Sei $ H\; $ eine aussagenlogische Formel. Eine Menge von Pseudoteilformeln von $ H\; $ ist eine minimale Menge $ \mathcal{P}(H)\; $, die die folgenden Bedingungen erfüllt:

1. $ H \in \mathcal{P}(H)\; $
2. Wenn $ \neg F \in \mathcal{P}(H)\; $ ist, dann ist auch $ F \in \mathcal{P}(H)\; $.
3. Wenn $ (F \circ G) \in \mathcal{P}(H)\; $ ist (für einen binären Junktor $ \circ\; $), dann ist entweder $ F \in \mathcal{P}(H)\; $ oder $ G \in \mathcal{P}(H)\; $ (aber nicht beides).

Dabei heisst $ \mathcal{P}(H)\; $ minimal, wenn es keine andere Menge $ \mathcal{P}'(H)\; $ gibt, welche die Bedingungen 1.-3. erfüllt und für die $ \mathcal{P}'(H) \subset \mathcal{P}(H) \; $gilt.

a) Geben Sie für die Formel $ H = (((p \rightarrow \neg \neg q) \and \neg \neg \neg p) \rightarrow q)\; $ eine Menge von Pseudoteilformeln an.

b) Zeigen Sie, dass es nicht notwendigerweise eine kleinste Menge gibt, die die Bedingungen 1.-3. dieser Definition zu gegebener Formel $ H\; $ erfüllt.

c) Zeigen Sie mit struktureller Induktion, dass $ \mathcal{P}(H) \subseteq \mathcal{T}(H)\; $ für beliebige Formeln $ H\; $. (Bem.: $ \mathcal{T}(H)\; $ ist die Menge der Teilformeln von $ H\; $.)

2. Lösung

a)

$ \mathcal{P}(H)\ =\ \{(((p \rightarrow \neg\neg q) \and \neg\neg\neg p) \rightarrow q), q\}\; $

b)

Gegenbeispiel:

$ H = (p \and p)\; $
Minimale Mengen, die die Bedingung erfüllen: $ \mathcal{P}_1(H) =\{(p \and p), p\}\; $, $ \mathcal{P}_2(H) =\{(p \and p), p\}\; $

Aber es gilt $ \mathcal{P}_2 \subset \mathcal{P}_1\; $

c)

Induktionsanfang

Sei $ H\; $ atomar, dann ist $ \mathcal{P}(H)\ =\ \{H\}\; $ und $ \mathcal{T}(H)\ =\ \{H\}\; $, folglich $ \mathcal{P}(H) \subseteq \mathcal{T}(H)\; $

Induktionsschlüsse

Es gelte IV: $ \mathcal{P}(F) \subseteq \mathcal{T}(F)\; $ und $ \mathcal{P}(G) \subseteq \mathcal{T}(G)\; $

z.z.: $ \mathcal{P}(\neg F) \subseteq \mathcal{T}(\neg F)\; $

• $ \mathcal{P}(\neg F) \subseteq \{\neg F\} \cup \mathcal{P}(F)\; $ und $ \mathcal{T}(\neg F) = \{\neg F\} \cup \mathcal{T}(F)\; $
  

Wegen IV gilt $ \mathcal{P}(\neg F) \subseteq \mathcal{T}(\neg F)\; $

z.z.: $ \mathcal{P}((F \circ G)) \subseteq \mathcal{T}((F \circ G))\; $

• $ \mathcal{T}((F \circ G)) = \{(F \circ G)\} \cup \mathcal{T}(F) \cup \mathcal{T}(G) \; $
  
• für $ \mathcal{P}((F \circ G))\; $ gibt es zwei Möglichkeiten:
  • entweder $ \mathcal{P}((F \circ G)) \subseteq \{(F \circ G)\} \cup \mathcal{P}(F)\; $ oder (exlusiv-oder)
  • $ \mathcal{P}((F \circ G)) \subseteq \{(F \circ G)\} \cup \mathcal{P}(G)\; $

Wegen IV gilt in allen Fällen $ \mathcal{P}((F \circ G)) \subseteq \mathcal{T}((F \circ G))\; $

4. Alternativen/Diskussion/Hinweise etc.

---

zur Klausur 01.02.2002
Aufgaben-Kategorie SonstigeAufgaben-Kategorie InduktionAufgaben-Kategorie AL - Interpretationen und Modelle