Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Klausur

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Wählen Sie eines der Themen A,B,C (Aufsatzthemen) oder D (Einzelaufgaben) aus. Zum Bestehen: Bei den Themen A,B,C sollte deutlich werden, dass Sie die Theorien in ihren Grundzügen verstanden haben und darüber sachgerecht und detailliert referieren können. Bei D sollten Sie die Hälfte der insgesamt 32 Punkte erhalten.


Thema A: Schildern Sie den Aufbau einer prädikatenlogischen Sprache einschließlich der Semantik und eines Ableitungskalküls.

Thema B: Beschreiben Sie Registermaschinen und das Halteproblem einschließlich einer Beweisskizze für dessen Unlösbarkeit.

Thema C: Erläutern Sie die Unentscheidbarkeit der Arithmetik, und skizzieren Sie einen Beweis dafür.



D - Einzelaufgaben

Aufgabe (3 Punkte)

Eine Grundtermmenge sei durch die Variablenmenge , eine Konstantenmenge , die einstelligen Funktionssymbole und die zweistelligen Funktionssymbole gegeben. Entwerfe einen Termstammbaum für den Term


Aufgabe (3 Punkte)

Formuliere die folgenden Beziehungen (ein- oder mehrstellige Prädikate) innerhalb der natürlichen Zahlen allein mittels Gleichheit, den Konstanten und , Addition, Multiplikation und unter Verwendung von aussagenlogischen Junktoren und Quantoren.

  1. .
  2. ist ein Vielfaches von .
  3. ist ein Vielfaches von .
  4. ist eine dritte Potenz.
  5. ist keine Primzahl.
  6. und besitzen die gleichen Primfaktoren.


Aufgabe * (2 Punkte)

Formalisiere in der arithmetischen Sprache die (wahre) Aussage, dass es unendlich viele Primzahlen gibt.


Aufgabe (1 Punkt)

Erstelle einen prädikatenlogischen Ausdruck , der in einer Struktur genau dann gilt, wenn die Grundmenge der Struktur genau Elemente besitzt.


Aufgabe * (4 Punkte)

Es sei das arithmetische Alphabet zusammen mit der Variablenmenge gegeben. Interpretiere den Term

unter den folgenden Interpretationen, wobei die Grundmenge der Interpretation bezeichne.

  1. mit der Standardinterpretation und der Variablenbelegung und .
  2. mit der Standardinterpretation

    und der üblichen Matrizenaddition und Matrizenmultiplikation und der Variablenbelegung und .

  3. , mit

    und wo sowohl als auch als Subtraktion interpretiert werden.

  4. Potenzmenge von mit

    und wo als und als interpretiert wird.


Aufgabe (3 Punkte)

Es sei eine Ausdrucksmenge und ein Ausdruck in einer Sprache erster Stufe. Zeige, dass genau dann gilt, wenn nicht erfüllbar ist.


Aufgabe (6 (1+2+3) Punkte)

a) Formuliere die Existenzeinführung im Sukzedens.

b) Formuliere die Existenzeinführung im Antezedens.

c) Zeige durch ein Beispiel, dass die Bedingung an die Variable in der Existenzeinführung im Antezedens wesentlich ist.


Aufgabe (4 Punkte)

Entwerfe ein Programm für eine Registermaschine, das nach und nach alle Primzahlen ausdruckt.


Aufgabe (4 Punkte)

Entwerfe ein Programm für eine Registermaschine, das die Potenz berechnet (und ausgibt), wobei bzw. die Registerinhalte der Register , , sind.


Aufgabe (2 Punkte)

Was besagt die Repräsentierbarkeit einer Abbildung

durch eine Menge von arithmetischen Ausdrücken?

Zur pdf-Version der Klausur