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



Übungsaufgaben

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



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?



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?



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.



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

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



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.


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



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



Bestimme den Rang der folgenden Ausdrücke.

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



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



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



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)

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)

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)

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)

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)