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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Übungsaufgaben

Aufgabe Referenznummer erstellen

Zeige durch ein Beispiel, dass Lemma 14.5 ohne die Voraussetzung, dass eine surjektive Terminterpretation vorliegt, nicht gelten muss.


Aufgabe Referenznummer erstellen

Es seien Symbolalphabete und seien die zugehörigen Sprachen Es sei eine Ausdrucksmenge.

  1. sei widerspruchsfrei. Ist dann auch , aufgefasst in , widerspruchsfrei?
  2. sei maximal widerspruchsfrei. Ist dann auch , aufgefasst in , maximal widerspruchsfrei?


Aufgabe * Aufgabe 14.3 ändern

Es sei ein Symbolalphabet und die zugehörige Sprache und die zugehörige Termmenge. Es sei eine Ausdrucksmenge.

  1. Zeige, dass durch

    eine Äquivalenzrelation auf definiert wird.

  2. Wenn man vergrößert, werden dann die Äquivalenzklassen größer oder kleiner?


Aufgabe Referenznummer erstellen

Es sei ein Symbolalphabet, die zugehörige Termmenge und die zugehörige Sprache. Es sei eine Ausdrucksmenge. Zeige, dass die Äquivalenzrelation aus Konstruktion 14.7 die semantische Äquivalenz aus Aufgabe 14.3 impliziert.


Aufgabe Referenznummer erstellen

Es sei ein Symbolalphabet und die zugehörige Sprache. Zeige, dass zu

die in Konstruktion 14.7 eingeführte Äquivalenzrelation die Identität ist.


Aufgabe Referenznummer erstellen

Es sei ein Symbolalphabet und die zugehörige Sprache. Die Ausdrucksmenge bestehe aus , wobei verschiedene Variablen seien. Zeige, dass zwei Terme genau dann äquivalent im Sinne von Konstruktion 14.7 sind, wenn es eine Kette von Termen

derart gibt, dass beim Übergang von nach genau ein Vorkommen von (bzw. ) in durch (bzw. ) ersetzt wird.


In der folgenden Aufgabe sollen die Variablen verschieden sein. Dennoch gibt es zwei Interpretationen für Teil (2), die aber inhaltlich äquivalent sind.

Aufgabe Referenznummer erstellen

Es sei ein Symbolalphabet und die zugehörige Sprache. Es sei eine Ausdrucksmenge. Zu fixiertem sei die Menge der -stelligen Funktionssymbole. Zeige die folgenden Aussagen.

  1. Durch

    wird eine Äquivalenzrelation auf definiert.

  2. Durch

    wird eine Äquivalenzrelation auf definiert.

  3. Die Äquivalenzrelation impliziert die Äquivalenzrelation .
  4. Es sei die zu gehörende formale Äquivalenzrelation auf der Termmenge im Sinne von Konstruktion 14.7. Dann gilt für Terme und Funktionssymbole mit die Beziehung


Aufgabe Referenznummer erstellen

Es sei ein atomarer Ausdruck, der zugleich eine Tautologie ist, also . Zeige, dass gleich mit einem -Term ist.


Aufgabe Referenznummer erstellen

Bestimme den Rang der folgenden Ausdrücke.

  1. ,
  2. ,
  3. ,
  4. .


Aufgabe Aufgabe 14.10 ändern

Zeige durch Induktion über den Aufbau der Ausdrücke, dass sich bei einer Termsubstitution der Rang eines Ausdrucks nicht ändert.


Aufgabe Referenznummer erstellen

Warum führt man im Beweis zum Satz von Henkin nicht Induktion über den Aufbau der Ausdrücke?


Aufgabe Referenznummer erstellen

Das Symbolalphabet bestehe aus einer einzigen Variablen und einem einzigen einstelligen Relationssymbol . Zeige, dass zu einer Interpretation die Gültigkeitsmenge keine Beispiele enthalten muss.




Aufgaben zum Abgeben

Aufgabe (3 Punkte)Referenznummer erstellen

Es sei eine Menge an -Ausdrücken (über einem Symbolalphabet ), die folgende Eigenschaften erfüllt.

  1. Für jeden Ausdruck ist oder .
  2. Aus folgt , d.h. ist abgeschlossen unter Ableitungen.
  3. ist widerspruchsfrei.

Zeige, dass maximal widerspruchsfrei ist.


Aufgabe (4 Punkte)Referenznummer erstellen

Es sei ein Symbolalphabet und die zugehörige Sprache. Es seien verschiedene Terme. Zeige, dass es eine -Interpretation mit

gibt.


Aufgabe (8 (1+3+1+3) Punkte)Referenznummer erstellen

Es sei ein Symbolalphabet und die zugehörige Sprache. Es sei eine Ausdrucksmenge. Zu fixiertem sei die Menge der -stelligen Relationssymbole in . Zeige die folgenden Aussagen.

  1. Durch

    wird eine Äquivalenzrelation auf definiert.

  2. Durch

    wird eine Äquivalenzrelation auf definiert.

  3. Die Äquivalenzrelation impliziert die Äquivalenzrelation .
  4. Es sei die zu gehörende Äquivalenzrelation auf der Termmenge im Sinne von Konstruktion 14.7. Dann gilt für Terme mit und Relationsssymbole mit die Beziehung


Aufgabe (2 Punkte)Referenznummer erstellen

Bestimme den Rang der folgenden Ausdrücke.

  1. ,
  2. ,
  3. ,
  4. .



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

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)