Übungen zur

Einführung in die Logik und Mengenlehre (WS 98/99) Übungszettel 5 - Abgabe bis 10 Tagen nach Ausgabe

1. Man beweise mit dem aussagenlogischen Kompaktheitssatz: jede partielle (irreflexive) Ordnung einer Menge M kann zu einer totalen Ordnung von M erweitert werden^{1)}.

2. In der Vorlesung wurde ein vollständiger aussagenlogischer Kalkül in der logischen Signatur { ∧, ¬} vorgestellt und dessen Vollständigkeit bewiesen. Man verzichte nunmehr auf eine Definition von ∨ durch ∧, ¬, erweitere die Signatur statt dessen um den ∨-Funktor und beweise die Vollständigkeit des um die beiden folgenden Regeln erweiterten Kalkküls:

\frac{X ⊢ α}{X ⊢ α ∨ β, β ∨ α} ; \frac{X, α ⊢ γ X, β ⊢ γ}{X, α ∨ β ⊢ γ} .

Hinweis: Man gehe die Einzelschritte im Beweis für den ursprünglichen Kalkül durch und beschreibe die erforderlichen Ergänzungen.

Anmerkung: In der sogenannten intuitionistischen Logik ist ∨ tatsächlich nicht durch ∧, ¬ definierbar. Die Semantik dieser Logik wird z.B. in Rautenberg, Klassische und Nichtklassische Aussagenlogik beschrieben.

3. Wir schreiben Formeln in ¬, ∧ in dieser Übung in klammerfreier Notation, genauer, in RPN (Reverse Polish Notation). Zum Beispiel pq∨¬ statt ¬(p ∨ q).

Man beweise den Satz von der eindeutigen Lesbarkeit dieser Notation, d.h. die folgende Behauptung: Ist α kein Primterm (d.h. keine Variable), so ist α entweder von der Gestalt ¬β für eine eindeutig bestimmte Formel β, oder aber von der Gestalt βγ ∧ mit eindeutig bestimmten Formeln β, γ.

Hinweis: Kein echtes Ende einer Formel ist eine Formel. Dabei sei ein Ende (oder Endstück) einer Zeichenfolge in spiegelbildlicher Weise zum Begriff des Anfangs erklärt.

Anmerkung: In vielen Programmiersprachen wird in RPN programmiert. Das vielleicht prominenteste Beispiel ist POSTSRIPT, die (systemunabhängige) Programmiersprache für Printer.

1)Dies verallgemeinert die Ordnungsfähigkeit einer beliebigen Menge, weil die leere Relation stets eine partielle Ordnung von M ist.