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

Aus Wikiversity



Übungsaufgaben

Aufgabe

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

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


Aufgabe

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

und

Tautologien sind.


Aufgabe

Skizziere ein Entscheidungsverfahren, das für eine gegebene Aussage entscheidet, ob es sich um eine aussagenlogische Tautologie handelt oder nicht.


Aufgabe

Zu einer Aussage und bezeichne die -fache Negation von . Zeige, dass genau dann allgemeingültig ist, wenn ein Vielfaches von ist.


Aufgabe

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

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


Aufgabe

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


Aufgabe

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

Es sei eine Teilmenge, die ausschließlich aus Aussagenvariablen oder aus negierten Aussagenvariablen besteht, wobei jede Aussagenvariable höchstens direkt oder in ihrer Negation auftritt. Zeige, dass erfüllbar ist.


Aufgabe *

Wenn Karl an Susanne denkt, bekommt er feuchte Hände, einen Kloß im Hals und einen roten Kopf. Einen roten Kopf bekommt er genau dann, wenn er an Susanne denkt oder wenn er das leere Tor nicht trifft. Wenn Karl das leere Tor trifft, bekommt er feuchte Hände. Karl bekommt den Ball vor dem leeren Tor. Kurz darauf bekommt er feuchte Hände, einen roten Kopf, aber keinen Kloß im Hals. Hat er an Susanne gedacht? Hat er das leere Tor getroffen?


Aufgabe *

Folgende Aussagen seien bekannt.

  1. Der frühe Vogel fängt den Wurm.
  2. Doro wird nicht von Lilly gefangen.
  3. Lilly ist ein Vogel oder ein Igel.
  4. Für Igel ist 5 Uhr am Morgen spät.
  5. Doro ist ein Wurm.
  6. Für Vögel ist 5 Uhr am Morgen früh.
  7. Lilly schläft bis 5 Uhr am Morgen und ist ab 5 Uhr unterwegs.

Beantworte folgende Fragen.

  1. Ist Lilly ein Vogel oder ein Igel?
  2. Ist sie ein frühes oder ein spätes Tier?
  3. Fängt der späte Igel den Wurm?


Aufgabe *

Professor Knopfloch kommt gelegentlich mit verschiedenen Socken und/oder mit verschiedenen Schuhen in die Universität. Er legt folgende Definitionen fest.

  1. Ein Tag heißt sockenzerstreut, wenn er verschiedene Socken anhat.
  2. Ein Tag heißt schuhzerstreut, wenn er verschiedene Schuhe anhat.
  3. Ein Tag heißt zerstreut, wenn er sockenzerstreut oder schuhzerstreut ist.
  4. Ein Tag heißt total zerstreut, wenn er sowohl sockenzerstreut als auch schuhzerstreut ist.

a) Vom Jahr weiß man, dass Tage sockenzerstreut und Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal zerstreut? Wie viele Tage waren in diesem Jahr maximal total zerstreut und wie viele Tage waren minimal total zerstreut?

b) Vom Jahr weiß man, dass Tage sockenzerstreut und Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal total zerstreut?

c) Erstelle eine Formel, die die Anzahl der sockenzerstreuten, der schuhzerstreuten, der zerstreuten und der total zerstreuten Tage in einem Jahr miteinander in Verbindung bringt.


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

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

Wir betrachten die ganzen Zahlen und eine fixierte natürliche Zahl . Zeige, dass auf durch

eine Äquivalenzrelation definiert wird. Wie viele Äquivalenzklassen gibt es?


Aufgabe

Es sei ein Körper, ein - Vektorraum und ein Untervektorraum. Wir betrachten die Relation auf , die durch

definiert ist. Zeige, dass diese Relation eine Äquivalenzrelation ist.


Aufgabe

Es sei ein Körper und ein - Vektorraum. Zeige, dass die Relation auf , die durch

eine Äquivalenzrelation ist. Was sind die Äquivalenzklassen?


Aufgabe

Wir betrachten für je zwei Teilmengen die symmetrische Differenz

Wir setzen , falls endlich ist. Zeige, dass dadurch eine Äquivalenzrelation auf definiert wird.


Aufgabe *

Betrachte auf die Relation

a) Zeige, dass eine Äquivalenzrelation ist.

b) Zeige, dass es zu jedem ein äquivalentes Paar mit gibt.

c) Es sei die Menge der Äquivalenzklassen dieser Äquivalenzrelation. Wir definieren eine Abbildung

Zeige, dass injektiv ist.

d) Definiere auf (aus Teil c) eine Verknüpfung derart, dass mit dieser Verknüpfung und mit als neutralem Element eine Gruppe wird, und dass für die Abbildung die Beziehung

für alle gilt.


Aufgabe *

Seien und Mengen und sei eine Abbildung. Zeige, dass durch die Festlegung

wenn

eine Äquivalenzrelation auf definiert wird.


Aufgabe *

Es sei die Menge der zweimal stetig differenzierbaren Funktionen von nach . Definiere auf eine Relation durch

a) Zeige, dass dies eine Äquivalenzrelation ist.

b) Finde für jede Äquivalenzklasse dieser Äquivalenzrelation einen polynomialen Vertreter.

c) Zeige, dass diese Äquivalenzrelation mit der Addition von Funktionen verträglich ist.

d) Zeige, dass diese Äquivalenzrelation nicht mit der Multiplikation von Funktionen verträglich ist.


Aufgabe

Es sei eine Teilmenge mit der induzierten Metrik. Betrachte die Relation auf , wobei bedeutet, dass es eine stetige Abbildung

mit und gibt. Zeige, dass dies eine Äquivalenzrelation auf ist.


Aufgabe

Es sei eine Menge und eine Äquivalenzrelation auf mit den Äquivalenzklassen . Es sei die Menge aller Äquivalenzklassen. Zeige folgende Aussagen.

  1. Es ist genau dann, wenn ist, und dies gilt genau dann, wenn .
  2. ist eine disjunkte Vereinigung.

Aufgabe

Es 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. Es 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. Es sei die horizontale Halbierungsgerade des Blattes. Zwei Punkte sind genau dann äquivalent, wenn sie achsensymmetrisch zu sind.


Aufgabe

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

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


Unter einer disjunktiven Normalform versteht man einen aussagenlogischen Ausdruck, der eine -Verknüpfung von Ausdrücken der Form ist, wobei bedeutet, dass entweder die Aussagenvariable direkt oder in ihrer Negation genommen wird.


Aufgabe *

Man bringe die Aussage

in disjunktive Normalform.


Aufgabe

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


Aufgabe

Es sei ein aussagenlogischer Ausdruck in disjunktive Normalform, in dem die Aussagenvariablen vorkommen. Zeige, dass genau dann eine Tautologie ist, wenn die -Verknüpfung von sämtlichen Kombinationen ist.


Aufgabe

Es sei die Menge aller Tautologien in einer aussagenlogischen Sprache . Zeige .


Aufgabe

Die Ausdrucksmenge enthalte eine Kontradiktion. Zeige .


Aufgabe

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


Aufgabe

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


Aufgabe *

Beweise die aussagenlogische Tautologie

aus den aussagenlogischen Axiomen.


Aufgabe

Zeige das Assoziativgesetz für die Konjunktion, also


Aufgrund der folgenden Ableitbarkeiten kann man die Implikation auf Negation und Konjunktion zurückführen.

Aufgabe *

Es seien und Aussagen.

  1. Zeige
  2. Zeige


Aufgabe

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

gilt.


Aufgabe *

Zeige

unter Verwendung von

(Lemma 3.14).


Aufgabe

Zu einer Aussage und bezeichne die -fache Negation von . Zeige, dass genau dann gilt, wenn ein Vielfaches von ist.


Aufgabe

Zeige die folgende Ableitungsregel für die Aussagenlogik.

Aus und folgt .


Aufgabe

Zeige, dass aus und die Ableitbarkeit folgt.


Aufgabe *

Zeige, dass eine Regel der Form

Wenn , dann gelten kann, ohne dass gilt.


Aufgabe

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


Aufgabe

Es sei eine ableitbare Tautologie. Zeige, dass es eine Ableitung für gibt, bei der in jedem Ableitungsschritt nur Aussagenvariablen auftreten, die in vorkommen.


Aufgabe

Skizziere ein Verfahren, wie man (bei abzählbar) eine Auflistung sämtlicher syntaktischer Tautologien aus erhalten kann.




Aufgaben zum Abgeben

Aufgabe (3 Punkte)

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


Aufgabe (2 Punkte)

Zeige, dass die Aussage

allgemeingültig ist.


Aufgabe (2 Punkte)

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 (3 Punkte)

Zeige


Aufgabe (2 Punkte)

Begründe die folgende Ableitungsregel: Aus und folgt .


Aufgabe (3 Punkte)

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.


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

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)