Übungen
Übung 1 (Aussagen und Junktoren, I (L))
Sie stehen vor zwei verschlossenen Türen. Hinter der einen Türe ist ein Schatz, hinter der anderen eine Ziege. Zwischen den beiden Türen sitzt ein Zwerg, der weiß, wo der Schatz ist. Der Zwerg hat die Eigenart, stets zu lügen oder stets die Wahrheit zu sagen. Er ist allwissend, und insbesondere weiß er, ob er ein Lügner ist oder nicht.
Sie dürfen dem Zwerg genau eine aussagenlogische Frage stellen, die er Ihnen mit „ja“ oder mit „nein“ beantworten wird. (Z. B. „Ist der Schatz links, wenn er rechts ist?“) Welche Frage stellen Sie, um zu erfahren, hinter welcher Türe der Schatz liegt?
Übung 2 (Aussagen und Junktoren, II)
Der Zwerg aus obiger Aufgabe sitzt nun an einer Weggabelung. Der eine Weg führt zum Dorf der lügenden und der andere Weg zum Dorf der wahrheitssagenden Zwerge. Welche ja-nein-Frage, die diesmal keine Junktoren enthalten darf, können Sie stellen, um zu erfahren, welcher Weg zu welchem Dorf führt?
Übung 3 (Aussagen und Junktoren, III)
Sie stehen drei Personen A, B und C gegenüber. Jede Person ist entweder ein Lügner oder ein Wahrheitssager. Sie wissen, dass eine der drei Personen ein Wahrheitssager ist und heute Geburtstag hat.
A sagt zu Ihnen: „B ist ein Wahrheitssager.“
C sagt zu Ihnen: „Einer von uns ist ein Lügner.“
Welche Person hat Geburtstag?
Übung 4 (Aussagen und Junktoren, IV)
Sie stehen drei Personen mit den Schildern A, B und C gegenüber. Sie wissen, dass eine Person immer die Wahrheit sagt (der Wahrheitssager), eine Person immer lügt (der Lügner), und eine Person zufällig die Wahrheit sagt oder lügt (der Stochastiker). Die Personen A, B, C wissen jeweils, wer der Wahrheitssager, wer der Lügner und wer der Stochastiker ist.
Sie dürfen drei aussagenlogische Fragen stellen, um die drei Personen zu identifizieren. Welche Fragen stellen Sie?
[ Beispiel für eine Frage an Person B: „Ist A der Wahrheitssager, wenn C der Stochastiker ist?“ ]
Übung 5 (Semantik der Junktoren: Junktoren in der Umgangssprache, I (L))
In der Umgangssprache werden die beiden folgenden Sprechweisen gleichwertig gebraucht:
(a) | Hunde und Katzen dürfen nicht an Bord. |
(b) | Hunde oder Katzen dürfen nicht an Bord. |
Welche Tautologie wird hier verwendet?
Übung 6 (Semantik der Junktoren: Junktoren in der Umgangssprache, II)
„Wenn der Hahn kräht auf dem Mist, ändert sich das Wetter oder es bleibt wie es ist.“
Auf welche Tautologie wird hier angespielt?
Übung 7 (Semantik der Junktoren: Hierarchischer Aufbau der Junktoren, I)
Welche Bedeutung hat die verneinte Äquivalenz ¬ (A ↔ B) ?
Übung 8 (Semantik der Junktoren: Hierarchischer Aufbau der Junktoren, II)
Wir betrachten die beiden folgenden zweistelligen Junktoren:
| „nicht beide zugleich“, | in Zeichen: ↑, |
| „weder noch“, | in Zeichen: ↓. |
Der Junktor ↑ wird auch „nand“, „Sheffer-Strich“ oder „Unverträglichkeit“ genannt, der Junktor ↓ auch „nor“ oder „Nihilition“.
Die Wahrheitstafeln dieser Junktoren sind:
A | ↑ | B |
w | f | w |
w | w | f |
f | w | w |
f | w | f |
A | ↓ | B |
w | f | w |
w | f | f |
f | f | w |
f | w | f |
(a) | Definieren Sie ↑ und ↓ durch ¬ und ∧. |
(b) | Definieren Sie ¬ und ∧ jeweils durch ↑ bzw. ↓. |
Übung 9 (Semantik der Junktoren: Hier. Aufbau der Junktoren, III (L))
Lässt sich die Negation mit Hilfe der Junktoren →, ∧, ∨ (ohne Falsum) definieren?
Übung 10 (Semantik der Junktoren: Hier. Aufbau der Junktoren, IV (L))
Geben Sie die achtzeiligen Wahrheitstafeln für die dreistelligen Junktoren
∗≥ 2 = „mindestens zwei der drei“, ∗0, 3 = „wenn eines, dann alle drei“
an, und definieren Sie ∗≥ 2(A, B, C) und ∗0, 3(A, B, C) mit Hilfe der üblichen Junktoren.
Übung 11 (Semantik der Junktoren: Hierarchischer Aufbau der Junktoren, V)
Schreiben Sie eine „zufällige“ Wahrheitstafel für A, B, C an, also eine Tafel mit acht Zeilen und vier Spalten ∗, A, B, C, wobei die ∗-Spalte z. B. durch das Werfen einer Münze mit w oder f gefüllt wird. Die Tafel können Sie dann als einen dreistelligen Junktor ∗(A, B, C) ansehen. Definieren Sie nun den Junktor ∗ mit Hilfe der üblichen Junktoren.
Zeigen Sie nun allgemein, dass jeder n-stellige Junktor ∗(A1, …, An), n ≥ 1, mit Hilfe der üblichen Junktoren definiert werden kann.
[ Betrachten Sie eine Konjunktion von 2n Aussagen der Form L1 ∧ … ∧ Ln → L, wobei jedes Li entweder Ai oder ¬ Ai und L entweder ⊥ oder ¬ ⊥ ist.
Alternativ lässt sich die Behauptung auch durch Induktion nach n zeigen. ]
Übung 12 (Semantik der Junktoren: Junktoren und Wahrheitswerte, I (L))
Eine Aussage A heißt erfüllbar, wenn ¬ A keine Tautologie ist, d. h. wenn die Ergebnisspalte der Wahrheitstafel von A mindestens einmal den Wert „w“ enthält. Zeigen oder widerlegen Sie, dass für alle Aussagen A und B gilt:
(i) | Sind A und A → B erfüllbar, so ist B erfüllbar. |
(ii) | Ist A erfüllbar und ist A → B eine Tautologie, so ist B erfüllbar. |
(iii) | Ist A nicht erfüllbar und ist A ∨ B eine Tautologie, so ist B eine Tautologie. |
Übung 13 (Semantik der Junktoren: Junktoren und Wahrheitswerte, II)
Geben Sie Aussagen A, B, C an derart, dass gilt:
(i) | A ∧ B ∧ C ist nicht erfüllbar. |
(ii) | A ∧ B, A ∧ C, B ∧ C sind erfüllbar. |
Übung 14 (Semantik der Junktoren: Junktoren und Wahrheitswerte, III)
Welche Beziehung besteht zwischen der Erfüllbarkeit/Allgemeingültigkeit der Aussagen A, B, C, D und der Erfüllbarkeit/Allgemeingültigkeit der Aussage A ∨ B ∨ C ∨ D bzw. der Aussage A ∧ B ∧ C ∧ D?
Übung 15 (Semantik der Junktoren: Junktoren und Wahrheitswerte, IV)
Mit ∧ und ¬ als Basisjunktoren sei ⊥ definiert als A0 ∧ ¬ A0 für eine beliebige Aussage A0. Begründen Sie, dass die für die Widerspruchsbeweise verantwortliche Tautologie A → ⊥ ↔ ¬ A als Spezialfall des Kontrapositionsgesetzes aufgefasst werden kann.
Übung 16 (Semantik der Junktoren: Junktoren in math. Beweisen, I (L))
Beweisen Sie folgende Aussagen mit Hilfe der Schlussregeln (S1) − (S5):
(i) | (A → (B → C)) → (A ∧ B → C), |
(ii) | A → ¬ ¬ A, |
(iii) | ¬ ¬ ¬ A → ¬ A. |
Übung 17 (Semantik der Junktoren: Junktoren in mathematischen Beweisen, II)
Beweisen Sie folgende Aussagen mit Hilfe der Schlussregeln (S1) − (S7):
(i) | A ∨ ¬ A, |
(ii) | (¬ A → ¬B) → (B → A), |
(iii) | ((A → B) → A) → A. |
Übung 18 (Die Sprache der Mathematik, I)
Definieren Sie den Quantor „es gibt genau ein x mit A(x)“, in Zeichen ∃! x A(x), mit Hilfe des Existenz- und Allquantors und der Gleichheit.
Übung 19 (Die Sprache der Mathematik, II (L))
Formulieren Sie nur mit Hilfe der Quantoren, der Junktoren und der Gleichheit die Aussagen:
(a) | Es gibt mindestens drei verschiedene Objekte. |
(b) | Es gibt genau drei verschiedene Objekte. |
Übung 20 (Die Sprache der Mathematik, III (L))
Lesen Sie „∀x“ als „für alle x“, „M(x)“ als „x ist ein Mensch“, „Z(x)“ als „x ist ein Zeitpunkt“ und „L(x, y)“ als „x lügt zum Zeitpunkt y“.
Drücken Sie nun die folgenden Aussagen formal aus:
(i) | Manche Menschen lügen immer. |
(ii) | Alle Menschen lügen manchmal. |
(iii) | Manche Menschen sagen manchmal die Wahrheit. |
(iv) | Es gibt genau einen Menschen, der immer die Wahrheit sagt. |
(v) | Von je zwei verschiedenen Menschen sagt zu einem gewissen Zeitpunkt der eine die Wahrheit und der andere nicht. |
Übung 21 (Die Sprache der Mathematik, IV)
Lesen Sie „∀x“ als „für alle Menschen x“, „b“ als „der Butler“, „g“ als „der Gärtner“, „l“ als „der Lord“, „K(x, y)“ als „x hat y ermordet“, „A(x, y)“ als „x hat Angst vor y“, „H(x, y)“ als „x hasst y“, und formalisieren Sie die folgenden Aussagen:
(a) | Der Butler oder der Gärtner hat den Lord umgebracht, oder der Lord hat Selbstmord begangen. |
(b) | Man mordet nur die, die man hasst und vor denen man Angst hat. |
(c) | Diejenigen, die der Lord hasst, mag der Gärtner. |
(d) | Diejenigen, die der Lord hasst, hasst auch der Butler. |
(e) | Der Lord hasst sich selbst, und er hasst den Gärtner. |
(f) | Der Butler hasst alle, die Angst vor dem Lord haben. |
(g) | Jeder mag den Lord, den Butler oder den Gärtner. |
Nehmen Sie nun diese Informationen als gegeben an, und ermitteln Sie durch eine möglichst detaillierte logische Argumentation den Mörder des Lords.
Übung 22 (Aussagenlogische Tautologien)
Beweisen Sie einige der aussagenlogischen Tautologien der obigen Tabelle mit Hilfe von Wahrheitstafeln, semantisch (d. h. durch inhaltliche Argumentation), oder mit Hilfe der Schlussregeln.
Übung 23 (Quantorenregeln, I)
Beweisen Sie einige der Quantorenregeln der obigen Tabelle und geben Sie Gegenbeispiele für die fehlenden Implikationen an.
Übung 24 (Quantorenregeln, II)
Betrachten Sie ein Zweipersonenspiel, und lesen Sie xi als „der i-te Zug von Spieler I“ und yi als „der i-te Zug von Spieler II“. Die Anzahl der Züge wird auf ein festes n (z. B. 500) begrenzt, und für jede mögliche Partie x1, y1, x2, y2, …, …, xn, yn steht fest, ob Spieler I oder Spieler II diese Partie gewonnen hat (es gibt kein Unentschieden).
(a) | Formulieren Sie mit Hilfe der Quantoren ∀ und ∃ die Aussagen „Spieler I besitzt eine Gewinnstrategie“ und „Spieler II besitzt eine Gewinnstrategie“. |
(b) | Zeigen Sie mit Hilfe der Verneinungsregeln für die Quantoren, dass genau einer der beiden Spieler eine Gewinnstrategie besitzt. |
(c) | Was lässt sich sagen, wenn bestimmte Partien mit „Remis“ enden? |
(d) | Wie lassen sich die Ergebnisse auf das Schachspiel anwenden? |
[ Zu (c): Definieren Sie zwei Hilfsspiele, bei denen Spieler I bzw. Spieler II genau die Remispartien und seine Gewinnpartien des Originalspiels gewinnt. ]