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

Aus Wikiversity
Wechseln zu: Navigation, Suche



Übungsaufgaben

Aufgabe

Beweise allein aus der Existenzeinführung im Sukzedens und aussagenlogischen Gesetzen die Alleinführung im Antezedens, also dass für eine Variable , einen Term und einen Ausdruck

eine Tautologie ist.


Aufgabe

Zeige


Aufgabe

Zeige


Aufgabe

Beweise aus der Existenzeinführung im Antezedens die Alleinführung im Sukzedens. Sie besagt, dass man aus

unter der Bedingung, dass weder in noch in frei vorkommt, auf

schließen kann.


Aufgabe

Zeige, dass der Ausdruck

keine Tautologie ist (auch nicht, wenn weder in noch in frei vorkommt).


Aufgabe

Es sei ein Ausdruck in einer Sprache erster Stufe. Zeige, dass

keine Tautologie ist.


Aufgabe *

Zeige, dass mit

auch

gilt.



Aufgabe *

Zeige


Aufgabe *

Zeige


Aufgabe

a) Zeige

b) Zeige, dass

keine Tautologie ist.


Aufgabe

Es sei ein erststufiges Symbolalphabet und ein -stelliges Funktionssymbol. Erstelle eine Ableitung für den Ausdruck


Aufgabe *

Es seien einstellige Relationssymbole. Zeige, dass der Modus Barbara, also die Aussage

im Prädikatenkalkül ableitbar ist.


Aufgabe *

Es seien einstellige Relationssymbole. Zeige, dass der Modus Darii, also die Aussage

im Prädikatenkalkül ableitbar ist.


Aufgabe *

Es seien Variablen und und .

  1. Zeige (ohne Bezug auf den Vollständigkeitssatz) .
  2. Charakterisiere die Modelle mit .
  3. Zeige .


Aufgabe *

Es sei ein dreistelliges Relationssymbol und die zugehörige prädikatenlogische Sprache. Es sei die Interpretation, bei der die Grundmenge die euklidische Ebene ist und durch die dreistellige Relation interpretiert wird, bei der zutrifft, wenn die Punkte auf einer Geraden liegen.

  1. Zeige .
  2. Zeige .
  3. Es sei . Erstelle eine Ableitung für .
  4. Zeige, dass der Ausdruck bei der gegebenen Interpretation nicht bedeutet, dass die die freien Variablen belegenden Punkte auf einer Geraden liegen.
  5. Formuliere einen Ausdruck aus in vier freien Variablen, der bei der gegebenen Interpretation besagt, dass die die freien Variablen belegenden Punkte auf einer Geraden liegen.


Die beiden folgenden Aufgaben sind vermutlich mühselig.

Aufgabe

Man gebe einen formalen Beweis für die Aussage, dass die Hintereinanderschaltung von zwei surjektiven Abbildungen auf einer Menge wieder surjektiv ist.


Aufgabe

Man gebe einen formalen Beweis für die Aussage, dass die Hintereinanderschaltung von zwei injektiven Abbildungen auf einer Menge wieder injektiv ist.


Aufgabe

Es sei eine Ausdrucksmenge aus einer Sprache erster Stufe und ein weiterer Ausdruck. Es sei nicht aus ableitbar. Zeige, dass man aus keinen Widerspruch (also keinen Ausdruck der Form ) ableiten kann.


Aufgabe

Begründe die folgenden Ableitungsregeln (es seien Terme, Ausdrücke und eine Ausdrucksmenge).

  1. Wenn , dann ist auch ,
  2. Wenn , dann ist auch ,
  3. Wenn , dann ist auch , unter der Bedingung, dass nicht frei in vorkommt.




Aufgaben zum Abgeben

Aufgabe (2 Punkte)

Sei . Zeige die Ableitbarkeit


Aufgabe (4 Punkte)

Sei . Zeige die Ableitbarkeit

Zeige, dass

nicht ableitbar ist.


Aufgabe (5 (2+2+1) Punkte)

Es seien .

a) Zeige, dass

nicht allgemeingültig ist.

b) Zeige, dass

allgemeingültig ist.

c) Zeige, dass

nicht allgemeingültig wäre, wenn man auch leere Grundmengen zulassen würde.


Aufgabe (4 Punkte)

Formuliere mit dem zweistelligen Funktionssymbol die Aussage, dass wenn eine Zahl die Zahl teilt und die Zahl teilt, dass dann auch teilt.

Erstelle eine Ableitung für diese Aussage.


Aufgabe (3 Punkte)

Zeige, dass es eine Ausdrucksmenge mit der Eigenschaft gibt, dass für jede Interpretation genau dann gilt, wenn die Grundmenge der Interpretation unendlich ist.



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

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)