Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Arbeitsblatt 3/kontrolle

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Übungsaufgaben

Aufgabe Referenznummer erstellen

Beweise mittels Wahrheitstabellen, dass die folgenden Aussagen Tautologien sind.[1]

  1. .
  2. .
  3. .
  4. .
  5. .


Aufgabe Referenznummer erstellen

Man beweise mittels Wahrheitstabellen die Regeln von de Morgan, nämlich dass

und

Tautologien sind.


Aufgabe Referenznummer erstellen

Es seien Aussagenvariablen und Aussagen. Zeige, dass man, wenn man in einer allgemeingültigen Aussage jedes Vorkommen von durch ersetzt, wieder eine allgemeingültige Aussage erhält. Zeige, dass die Umkehrung davon nicht gilt.


Aufgabe Referenznummer erstellen

Zeige, dass eine Aussage genau dann eine Kontradiktion ist, wenn eine Tautologie ist.


Aufgabe Referenznummer erstellen

Man gebe möglichst viele Beispiele für aussagenlogische Kontradiktionen an.


Die folgenden Aufgaben verwenden den Begriff einer Äquivalenzrelation. Dieser ist für viele Konstruktionen in der Mathematik und in der mathematischen Logik entscheidend. Siehe Äquivalenzrelation/Einführung/Textabschnitt.


Eine Äquivalenzrelation auf einer Menge ist eine Relation , die die folgenden drei Eigenschaften besitzt (für beliebige ).

  1. Es ist (reflexiv).
  2. Aus folgt (symmetrisch).
  3. Aus und folgt (transitiv).

Dabei bedeutet , dass das Paar zu gehört.


Aufgabe Referenznummer erstellen

Auf den ganzen Zahlen lebe eine Kolonie von Flöhen, und jeder Flohsprung geht fünf Einheiten weit (in beide Richtungen). Wie viele Flohpopulationen gibt es? Wie kann man einfach charakterisieren, ob zwei Flöhe zur gleichen Population gehören oder nicht?


Aufgabe Referenznummer erstellen

Sei ein Blatt Papier (oder ein Taschentuch). Man versuche, sich die folgenden Äquivalenzrelationen auf und die zugehörige Identifizierungsabbildungen vorzustellen (möglichst geometrisch).

  1. Die vier Eckpunkte sind untereinander äquivalent, ansonsten sind die Punkte nur zu sich selbst äquivalent.
  2. Alle Randpunkte sind untereinander äquivalent, ansonsten sind die Punkte nur zu sich selbst äquivalent.
  3. Jeder Punkt des linken Randes ist äquivalent zu seinem horizontal gegenüber liegenden Punkt am rechten Rand, ansonsten sind die Punkte nur zu sich selbst äquivalent.
  4. Jeder Punkt des linken Randes ist äquivalent zu seinem horizontal gegenüber liegenden Punkt am rechten Rand und jeder Punkt des oberen Randes ist äquivalent zu seinem vertikal gegenüber liegenden Punkt, ansonsten sind die Punkte nur zu sich selbst äquivalent.
  5. Jeder Punkt des Randes ist äquivalent zu seinem punktsymmetrisch (bezüglich des Mittelpunktes des Blattes) gegenüber liegenden Punkt, ansonsten sind die Punkte nur zu sich selbst äquivalent.
  6. Sei ein Kreis (d.h. eine Kreislinie) auf dem Blatt. Alle Kreispunkte seien untereinander äquivalent, ansonsten sind die Punkte nur zu sich selbst äquivalent.
  7. Es gebe zwei Punkte , die untereinander äquivalent seien, ansonsten sind die Punkte nur zu sich selbst äquivalent.
  8. Sei die horizontale Halbierungsgerade des Blattes. Zwei Punkte sind genau dann äquivalent, wenn sie achsensymmetrisch zu sind.


Aufgabe Aufgabe 3.8 ändern

Zeige, dass die Beziehung

eine Äquivalenzrelation auf definiert. Zeige, dass sowohl alle Tautologien als auch alle Kontradiktionen eine Äquivalenzklasse bilden. Wie viele Äquivalenzklassen besitzt diese Äquivalenzrelation, falls Elemente besitzt?


Aufgabe Referenznummer erstellen

Es sei die in Aufgabe 3.8 diskutierte Äquivalenzrelation auf . Zeige, dass jede Äquivalenzklasse einen Repräsentanten in disjunktiver Normalform[2] besitzt.


Aufgabe Referenznummer erstellen

Es sei die in Aufgabe 3.8 diskutierte Äquivalenzrelation auf und sei die zugehörige Quotientenmenge. Es sei eine Wahrheitsbelegung auf . Zeige, dass dies eine wohldefinierte Abbildung auf induziert.


Aufgabe Referenznummer erstellen

Es sei eine Menge von Aussagenvariablen und eine Aussage in der zugehörigen formalen Sprache . Es sei

eine Abbildung und es sei diejenige Aussage, die entsteht, wenn man in jede Aussagenvariable durch ersetzt. Zeige die folgenden Aussagen.

  1. Wenn eine Tautologie ist, so ist auch eine Tautologie.
  2. Wenn injektiv ist, so ist genau dann eine Tautologie, wenn dies für gilt.
  3. kann eine Tautologie sein, auch wenn keine Tautologie ist.
  4. Die Aussagen gelten ebenso, wenn man überall Tautologie durch Kontradiktion ersetzt.


Aufgabe Referenznummer erstellen

Interpretiere die Wahrheitstabellen zu den Junktoren als Wertetabellen von Funktionen. Was sind die Definitions-, die Werte- und die Bildmengen dieser Funktionen?


Aufgabe Aufgabe 3.13 ändern

Zeige, dass die axiomatisch fixierten syntaktischen Grundtautologien allgemeingültig sind


Aufgabe * Aufgabe 3.14 ändern

Beweise die aussagenlogische Tautologie

aus den aussagenlogischen Axiomen.


Aufgabe Aufgabe 3.15 ändern

Zeige das Assoziativgesetz für die Konjunktion, also


Aufgabe Referenznummer erstellen

Es seien Ausdrücke und es seien Elemente aus . Zeige, dass

gilt.


Aufgabe Referenznummer erstellen

Zeige, dass aus und die Ableitbarkeit folgt.


Aufgabe * Referenznummer erstellen

Zeige, dass eine Regel der Form

Wenn , dann gelten kann, ohne dass gilt.


Aufgabe Referenznummer erstellen

Es seien Aussagenvariablen und Aussagen. Zeige, dass man, wenn man in einer syntaktischen Tautologie jedes Vorkommen von durch ersetzt, wieder eine Tautologie erhält.




Aufgaben zum Abgeben

Aufgabe (3 Punkte)Referenznummer erstellen

Zeige, dass in einer aussagenlogischen Tautologie (und ebenso in einer aussagenlogischen Kontradiktion) mindestens eine Aussagenvariable mehrfach vorkommen muss.


Aufgabe (2 Punkte)Referenznummer erstellen

Es sei eine Aussagenmenge derart, dass in keiner Aussage das Negationszeichen vorkommt. Zeige, dass dann die Wahrheitsbelegung, die jeder Aussagenvariablen den Wert zuweist, zu einer Interpretation mit führt.


Aufgabe (2 Punkte)Referenznummer erstellen

Zeige, dass die Aussage

allgemeingültig ist.


Aufgabe (3 Punkte)Referenznummer erstellen

Zeige


Aufgabe (2 Punkte)Aufgabe 3.24 ändern

Begründe die folgende Ableitungsregel: Aus und folgt .


Aufgabe (3 Punkte)Referenznummer erstellen

Zeige, dass folgende rekursive Definition zur gleichen Menge an syntaktischen Tautologien führt:

Die Grundtautologien werden nur mit Aussagenvariablen formuliert.

Neben dem Modus ponens gibt es die Ersetzungsregel, d.h. wenn , so ist auch , wobei ein Ausdruck ist, der entsteht, wenn man in Aussagenvariablen durch beliebige Aussagen ersetzt.

Zeige, dass ohne diese Ersetzungsregel nicht die gleiche Menge beschrieben wird.




Fußnoten
  1. Wir verzichten hier und im Folgenden häufig auf Klammern, um die Lesbarkeit zu erhöhen. Gemeint sind immer die korrekt geklammerten Aussagen.
  2. Unter einer disjunktiven Normalform versteht man einen Ausdruck, der eine -Vereinigung von Ausdrücken der Form Fehler beim Parsen (Syntaxfehler): {\displaystyle {{}} \pm p_1 {{<span class="error">Expansion depth limit exceeded</span>}} \ldots {{<span class="error">Expansion depth limit exceeded</span>}} \pm p_n} ist, wobei bedeutet, dass entweder die Aussagenvariable direkt oder in ihrer Negation genommen wird.


<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2014) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)