Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Arbeitsblatt 9

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Übungsaufgaben

Aufgabe

Bestimme die freien Variablen in den folgenden Ausdrücken, wobei Variablen seien und ein einstelliges Funktionssymbol und ein zweistelliges Relationssymbol sei.

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


Aufgabe

Es sei ein Satz einer erststufigen Sprache über einem Symbolalphabet . Es sei eine -Struktur mit Trägermenge gegeben und und zwei auf definierte -Interpretationen. Zeige genau dann, wenn gilt.


Aufgabe

Es seien Konstanten einer erststufigen Sprache, Variablen, ein einstelliges und zweistellige Funktionssymbole. Bestimme die Substitution


Aufgabe

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben. Es seien paarweise verschiedene Variablen und fixierte -Terme.

a) Interpretiere die Termsubstitution als Abbildung.

b) Interpretiere die Substitution von Ausdrücken als Abbildung.


Aufgabe *

Es seien Variablen (mit der angegebenen Reihenfolge), eine Konstante und ein einstelliges Funktionssymbol.

  1. Bestimme
  2. Bestimme
  3. Bestimme


Aufgabe *

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben.

  1. Zeige, dass die Substitution für die Terme die Identität ist.
  2. Zeige, dass die Substitution für die Ausdrücke die Identität ist.


Aufgabe

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben, es sei eine Variable und ein fixierter -Term. Gehört die Symbolkette (!) zu ?


Aufgabe

Es sei eine Konstante einer erststufigen Sprache, Variablen, ein einstelliges Funktionssymbol, zweistellige Funktionssymbole und ein zweistelliges Relationssymbol. Bestimme die Substitution


Aufgabe

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben. Man gebe ein Beispiel für eine Substitution und einen -Ausdruck derart, dass die sukzessive substituierten Ausdrücke

immer länger werden.


Aufgabe *

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben. Es seien paarweise verschiedene Variablen und fixierte -Terme. Zeige, dass für jeden -Satz die Gleichheit

gilt.


Aufgabe

Es sei . Zeige, dass die Gleichheit

im Allgemeinen nicht gilt.


Aufgabe *

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

im Allgemeinen nicht allgemeingültig ist.


Aufgabe *

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

im Allgemeinen nicht allgemeingültig ist.


Aufgabe *

Es seien Variablen, Terme und ein Ausdruck in einer prädikatenlogischen Sprache. Es seien neue Variablen, die weder in noch in noch in vorkommen. Zeige, dass

allgemeingültig ist, wobei der Ausdruck rechts als die Hintereinanderausführung von vier Einzelsubstitutionen (von links nach rechts) zu lesen ist.


Aufgabe *

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben, und eine Interpretation mit . Zeige durch ein Beispiel, dass daraus nicht im Allgemeinen die Gültigkeit unter einer Substitution folgt.


Aufgabe

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben. Es seien paarweise verschiedene Variablen und fixierte -Terme. Zeige, dass zu einem allgemeingültigen Ausdruck auch die Substitution allgemeingültig ist. Gilt hiervon auch die Umkehrung?




Aufgaben zum Abgeben

Aufgabe (2 Punkte)

Es sei ein -Ausdruck. Zeige, dass es einen -Ausdruck der Form derart gibt, dass

gilt.


Aufgabe (2 Punkte)

Es seien Konstanten einer erststufigen Sprache, Variablen (in dieser Reihenfolge), ein einstelliges Funktionssymbol, ein zweistelliges Funktionssymbol und einstellige Relationssymbole. Bestimme die Substitution


Aufgabe (3 Punkte)

Man gebe für jedes ein Beispiel für eine Substitution und einen -Ausdruck derart, dass die sukzessive substituierten Ausdrücke

eine Periode der Länge besitzen.


Aufgabe (3 Punkte)

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben. Es seien paarweise verschiedene Variablen und fixierte -Terme. Zeige, dass für Terme , in denen nicht vorkommen, die Gleichheit

gilt.


Aufgabe (2 Punkte)

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben. Es seien paarweise verschiedene Variablen und fixierte -Terme. Zeige durch ein Beispiel, dass für Terme die Gleichheit

nicht gelten muss.


Aufgabe (4 Punkte)

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben. Es seien paarweise verschiedene Variablen und fixierte -Terme. Zeige durch ein Beispiel, dass für Ausdrücke die Gleichheit (von Ausdrücken)

nicht gelten muss.


Aufgabe (3 Punkte)

Es sei ein Symbolalphabet einer Sprache erster Stufe gegeben. Es seien verschiedene Variablen, ein -Term und ein -Ausdruck, wobei weder in noch in vorkomme. Gilt dann die Gleichheit



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

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)