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

Aus Wikiversity



Übungsaufgaben

Aufgabe

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

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


Aufgabe

Es sei ein Symbolalphabet und eine - Interpretation auf einer Menge mit der zugehörigen Terminterpretation. Zeige, dass man diese Terminterpretationsabbildung durch die Hinzunahme von Variablen (oder durch die Hinzunahme von Konstanten) surjektiv machen kann.


Aufgabe

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


Aufgabe *

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

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.5 impliziert.


Aufgabe

Das Symbolalphabet bestehe neben Variablen aus einer Konstanten und einem einstelligen Funktionssymbol . Wir betrachten die Teilmengen

mit

Es seien die zugehörigen Äquivalenzrelationen gemäß Konstruktion 14.7 auf der Termmenge.

  1. Gelten die Äquivalenzen
  2. Gelten die Äquivalenzen
  3. Welche Inklusionsbeziehungen bestehen zwischen ?
  4. Wie viele Termklassen gibt es zu , wenn die Variablenmenge nur aus besteht?


Aufgabe

Das Symbolalphabet bestehe neben Variablen aus einer Konstanten und einem zweistelligen Funktionssymbol . Es sei die Menge aller Ableitungen aus dem Axiomensystem

Es sei die zugehörige Äquivalenzrelation gemäß Konstruktion 14.7. Zeige für jedes Variablenpaar .


Aufgabe

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

Es sei eine widersprüchliche, unter Ableitungen abgeschlossene Teilmenge. Zeige, dass es nur eine Termklasse im Sinne von Konstruktion 14.7 gibt.


Aufgabe

Es sei eine unter Ableitungen abgeschlossene Teilmenge, die zu je zwei Termen die Gleichheit enthalte. Wie viele Termklassen im Sinne von Konstruktion 14.7 gibt es? Ist widersprüchlich?


Aufgabe

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.


Aufgabe

Es sei eine Variablenmenge und eine Äquivalenzrelation auf mit der Quotientenmenge . Es sei ein erststufiges Symbolalphabet mit als Variablenmenge und

Es sei die zugehörige Äquivalenzrelation auf der Termmenge gemäß Konstruktion 14.7. Zeige, dass die Termklassenmenge zu in kanonischer Weise mit der Termmenge zum Symbolalphabet in Bijektion steht, wobei aus entsteht, indem man die Variablenmenge durch ersetzt.


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

Aufgabe

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

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


Aufgabe

Bestimme den Rang der folgenden Ausdrücke.

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


Aufgabe

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


Aufgabe

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




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

Es sei die Peano-Arithmetik, also die Menge aller aus den erststufigen Peano-Axiomen ableitbaren Ausdrücke. Zeige, dass jeder variablenfreie Term im Sinne von Konstruktion 14.7 äquivalent zu einem Term ist, bei dem das Multiplikationszeichen nicht mehr vorkommt.


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 2021) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)