Logik:Klausuren/27.02.2004/2.5 Aufgabe
Inhaltsverzeichnis
1. Aufgabenstellung
Wie beschränken uns in dieser Aufgabe auf aussagenlogische Formeln, in denen nur die
Junktoren $ \neg \ $ und $ \wedge \ $ vorkommen.
Wir nennen eine Menge $ \mathcal{M} $ aussagenlogischer Formeln eine M-Menge, wenn sie die fol-
genden Bedingungen erfüllt:
(1) Ist $ F\ $ eine atomare Formel, dann ist nicht gleichzeitig $ F \in \mathcal{M} $ und $ \neg F \in \mathcal{M}. $
(2) Wenn $ \neg \neg F \in \mathcal{M} $, dann ist auch $ F \in \mathcal{M}. $
(3) Wenn $ (F \wedge G) \in \mathcal{M} $, dann ist sowohl $ F \in \mathcal{M} $ als auch $ G \in \mathcal{M}. $
(4) Wenn $ \neg (F \wedge G) \in \mathcal{M} $, dann ist $ \neg F \in \mathcal{M} $ oder $ \neg G \in \mathcal{M} $ (oder beides).
Beweisen Sie mittels struktureller Induktion die folgende Aussage:
Wenn $ \mathcal{M} $ eine M-Menge aussagenlogischer Formeln ist, dann gilt nicht gleichzeitig
$ F \in H $ und $ \neg F \in H. $
(Achtung, hier ist der Grund warum diese Klausur wiederholt wurde!!! Statt $ H $ sollte $ \mathcal{M} $ stehen.)
