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



Übungsaufgaben

Aufgabe

Ersetze in den folgenden aussagenlogischen Tautologien

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


Aufgabe

Unterscheide zwischen den verschiedenen Bedeutungen von Gleichheit.

  1. Gleichheit von Elementen in einer Menge.
  2. Gleichheit von Zeichenketten.
  3. Das Gleichheitssymbol in einer erststufigen Sprache.


Aufgabe

Es sei ein Symbolalphabet einer Sprache erster Stufe. Es seien - Terme mit

gegeben. Zeige, dass es sich bei und um eine identische Zeichenreihe handelt.


Aufgabe

Es sei ein Symbolalphabet und seien - Terme. Zeige die Ableitbarkeit


Aufgabe *

Es seien Terme und ein -stelliges Funktionssymbol. Zeige, dass die Ableitbarkeit

gilt.


Aufgabe

Zeige direkt (ohne die Verwendung der Ableitungsbeziehung), dass die folgenden Ausdrücke allgemeingültig sind (dabei seien Terme, ein -stelliges Funktionssymbol und ein -stelliges Relationssymbol).


Aufgabe *

Es seien Variablen, Terme und ein Ausdruck in einer prädikatenlogischen Sprache . Zeige, dass

allgemeingültig ist.


Aufgabe

Es seien Terme einer prädikatenlogischen Sprache und sei eine Variable. Zeige durch ein Beispiel, dass

nicht ableitbar sein muss.[1]


Aufgabe *

Zeige durch ein Beispiel, dass für Terme und eine Variable einer prädikatenlogischen Sprache der Ausdruck

nicht ableitbar sein muss.


Aufgabe

Es sei ein Symbolalphabet einer prädikatenlogischen Sprache mit einer leeren Variablenmenge. Zeige, dass man für Terme im Allgemeinen nicht ableiten kann.




Aufgaben zum Abgeben

Aufgabe (2 Punkte)

Es seien Konstanten, es sei ein zweistelliges Funktionssysmbol und es ein dreistelliges Relationssymbol. Man erläutere, wie man die prädikatenlogische Tautologie

aus einer aussagenlogischen Tautologie im Sinne von Lemma 10.2 erhält.


Aufgabe (4 Punkte)

Es seien Terme einer prädikatenlogischen Sprache und seien verschiedene Variablen. Zeige durch Induktion über den Aufbau des Termes die Ableitbarkeit


Aufgabe (4 Punkte)

Es seien Terme einer prädikatenlogischen Sprache und seien verschiedene Variablen.

  1. Es sei ein -stelliges Relationssymbol und seien Terme. Zeige die Ableitbarkeit
  2. Es seien und Terme. Zeige die Ableitbarkeit

Tipp: Verwende Aufgabe 10.12

Aufgabe (4 Punkte)

Es sei ein Symbolalphabet, seien - Terme, verschiedene Variablen und sei ein - Ausdruck. Zeige die Allgemeingültigkeit


Aufgabe (4 Punkte)

Zeige durch ein Beispiel, dass bei einem ableitbaren Ausdruck der Form

die durch die Existenzquantoren gebundenen Variablen (nach der durchgeführten Substitution) nicht übereinstimmen müssen.




Die Aufgabe zum Aufgeben

Aufgabe (6 Punkte)

Wir betrachten eine Variante des Ableitungskalkül (geschrieben ) der Aussagenlogik, bei dem die Grundtautologien aus Axiom 3.8 unverändert übernommen werden, bei der aber der Modus ponens durch die Schlussregel

Wenn , dann ist

ersetzt wird. Stimmen  und überein?




Fußnoten
  1. Die Nicht-Ableitbarkeit wird durch die Angabe eines Modells gezeigt; dies verwendet die Korrektheit des Ableitungskalküls, den wir noch nicht vollständig behandelt haben.


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

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)