Zum Inhalt springen

Kurs:Einführung in die mathematische Logik/2/Klausur mit Lösungen

Aus Wikiversity


Aufgabe 1 2 3 4 5 6 7 8 9 10 11 12 13 ∑
Punkte 3 3 1 4 9 4 6 7 7 2 3 3 12 64




Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Die Ableitbarkeit eines Aussage α∈LV aus einer Aussagenmenge Γ⊆LV in der Sprache der Aussagenlogik zu einer Aussagevariablenmenge V.
  2. Eine n-stellige Relation auf einer Menge M.
  3. Die Folgerungsbeziehung Γ⊨α, wobei Γ eine Menge von S-Ausdrücken und α ein S-Ausdruck ist (und S ein Symbolalphabet.)
  4. Die Termsubstitution st1,…,tkx1,…,xk für S-Terme s (dabei sei S ein Symbolalphabet einer Sprache erster Stufe, x1,…,xk paarweise verschiedene Variablen und t1,…,tk fixierte S-Terme).
  5. Die Addition in einem Dedekind-Peano-Modell ℕ.
  6. Die Register-Entscheidbarkeit einer Teilmenge T⊆ℕ.
  1. Man sagt, dass α aus Γ ableitbar ist, wenn es endlich viele Ausdrücke α1,…,αn∈Γ derart gibt, dass
    ⊢α1∧…∧αn→α

    gilt.

  2. Unter einer n-stelligen Relation R auf M versteht man eine Teilmenge der n-fachen Produktmenge M×⋯×M.
  3. Man sagt, dass α aus Γ folgt, wenn für jede S-Interpretation I mit I⊨Γ auch I⊨α gilt.
  4. Die Termsubstitution st1,…,tkx1,…,xk wird rekursiv folgendermaßen definiert.
    1. Für eine Variable x ist
      xt1,…,tkx1,…,xk:={x, falls x≠xi für alle i,ti, falls x=xi.
    2. Für eine Konstante c ist
      ct1,…,tkx1,…,xk:=c.
    3. Für ein n-stelliges Funktionssymbol f und n Terme s1,…,sn ist
      fs1…snt1,…,tkx1,…,xk:=fs1t1,…,tkx1,…,xk…snt1,…,tkx1,…,xk.
  5. Die Addition n+k wird über die Addition αn mit festem n definiert, wobei αn die eindeutig bestimmte Abbildung
    αn:ℕ⟶ℕ,k⟼αn(k),

    ist, für die

    αn(0)=n und αn(k′)=(αn(k))′ für alle k∈ℕ

    gilt.

  6. Die Teilmenge T heißt Register-entscheidbar, wenn es ein Programm P für eine Registermaschine gibt, die bei jeder Eingabe anhält und für die die Äquivalenz
    n∈T genau dann, wenn P(n) die Ausgabe 0 besitzt

    gilt.


 


Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

  1. Das Substitutionslemma.
  2. Der Satz über das Halteproblem.
  3. Der Fixpunktsatz für arithmetische Ausdrücke.
  1. Es sei ein Symbolalphabet S einer Sprache erster Stufe gegeben und es seien x1,…,xk paarweise verschiedene Variablen und t1,…,tk fixierte S-Terme. Es sei eine S-Interpretation I gegeben. Dann gelten folgende Aussagen.
    1. Für jeden S-Term s gilt
      I(st1,…,tkx1,…,xk)=(II(t1),…,I(tk)x1,…,xk)(s).
    2. Für jeden S-Ausdruck α gilt
      I⊨αt1,…,tkx1,…,xk genau dann, wenn (II(t1),…,I(tk)x1,…,xk)⊨α.
  2. Die Menge
    {n∈ℕ∣n ist die Nummer eines Registerprogramms P und P(0) hält an}

    ist nicht

    R-entscheidbar.
  3. Es sei Γ⊆LAr eine Menge von arithmetischen Ausdrücken, die Repräsentierungen erlaube. Dann gibt es zu jedem α∈L1Ar einen Satz q∈L0Ar mit
    Γ⊢q⟷α(GN(q)).


 


Aufgabe * (1 Punkt)

Finde einen möglichst einfachen aussagenlogischen Ausdruck, der die folgende tabellarisch dargestellte Wahrheitsfunktion ergibt.

p q ?
w w f
w f f
f w w
f f f

¬p∧q.


 


Aufgabe * (4 (2+2) Punkte)

Es sei G eine unendliche Menge und  M⊂𝔓(G)  die Menge, die aus sämtlichen endlichen Teilmengen von G besteht.

  1. Ist (M,⊆) induktiv geordnet?
  2. Besitzt M maximale Elemente?
  1. Da G unendlich ist, gibt es darin insbesondere verschiedene Elemente xn zu n∈ℕ+. Wir betrachten die endlichen Teilmengen
    Gn:={x1,x2,…,xn}.

    Diese gehören zu M und es liegen die (echten) Inklusionen  Gn⊂Gn+1  vor, d.h. diese Mengen bilden eine Kette. Eine obere Schranke für diese Mengen muss aber alle Elemente xn enthalten, also unendlich sein, und eine solche gibt es nicht in M.

  2. Es gibt in M keine maximalen Elemente. Ein Element N∈M ist eine endliche Menge von G. Da G unendlich ist, gibt es ein Element x∈G mit x∉N. Dann ist N∪{x} eine ebenfalls endliche Teilmenge von G (gehört also zu M), die N echt umfasst, sodass N nicht maximal ist.


 


Aufgabe * (9 (1+3+2+1+2) Punkte)

Es sei LS die prädikatenlogische Sprache, die neben Variablen aus einem zweistelligen Relationssymbol A und einem dreistelligen Relationssymbol B bestehe. Wir betrachten S-Interpretationen I, wobei die Grundmenge jeweils aus einem Vektorraum V über einem Körper K bestehe und A als die lineare Unabhängigkeit von zwei und B als die lineare Unabhängigkeit von drei Vektoren interpretiert werde.

  1. Zeige
    I⊨Bxyz→Axy.
  2. Gilt
    I⊨Axy∧Axz∧Ayz→Bxyz

    für einen beliebigen Vektorraum?

  3. Gibt es Vektorräume, für die die Aussage in Teil 2 gilt?
  4. Es sei V=ℝ3 und e1,e2,e3 sei die Standardbasis. Gilt
    Ie1,e2,e3x,y,z⊨Bxyz?
  5. Es sei V=ℝ als ℚ-Vektorraum betrachtet. Gilt
    I1,2x,y⊨Axy?
  1. Wenn drei Vektoren linear unabhängig sind, so sind insbesondere je zwei davon linear unabhängig.
  2. Dies gilt im Allgemeinen nicht. Dazu sei V=ℝ2 und wir betrachten die drei Vektoren (1,0),(1,1),(0,1). Die drei Vektoren sind insgesamt linear abhängig, da in einem zweidimensionalen Vektorraum drei Vektoren immer linear abhängig sind. Dagegen ist jede Auswahl von zwei der Vektoren linear unabhängig, da keiner der Vektoren ein Vielfaches eines anderen ist.
  3. In einem eindimensionalen (oder nulldimensionalen) Vektorraum V gilt die Aussage, da es dort keine zwei linear unabhängigen Vektoren gibt und daher der Vordersatz stets falsch ist und somit die Gesamtaussage stimmt.
  4. Die Standardvektoren im ℝ3 sind eine Basis und insbesondere linear unabhängig, daher gilt die Aussage.
  5. Die 2 ist keine rationale Zahl, daher sind die beiden reellen Zahlen 1 und 2 über ℚ linear unabhängig, und daher gilt diese Aussage.


 


Aufgabe * (4 Punkte)

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

r1=r2→r1sx=r2sx

nicht ableitbar sein muss.

Wir betrachten r1=x, r2=y und s=c, wobei x,y Variablen seien und c eine Konstante sei. Dann ist  r1sx=c  und  r2sx=y.  Die Aussage lautet also in diesem Spezialfall

x=y→c=y.

Dieser Ausdruck ist aber nicht allgemeingültig, da man x und y durch ein gemeinsames, von cM verschiedenes Element belegen kann.


 


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

Es seien x,y,u,v Variablen und Γ={∀x∀y(x=y)} und Δ={x=y}.

  1. Zeige (ohne Bezug auf den Vollständigkeitssatz) Γ⊢u=v.
  2. Charakterisiere die Modelle M mit M⊨Γ.
  3. Zeige Δ⊬u=v.
  1. Nach der Allversion zu Axiom 11.1 (Einführung in die mathematische Logik (Osnabrück 2021)) ist
    ⊢∀x(∀y(x=y))→(∀y(x=y))ux

    eine Tautologie. Der Nachsatz ist ∀y(u=y). Aus dem gleichen Grund ist

    ⊢∀y(u=y)→(u=y)vy

    eine Tautologie. Der Nachsatz ist u=v. Mit Modus ponens gilt daher

    Γ⊢∀y(u=y)

    und

    Γ⊢u=v.
  2. Das bedeutet, dass die Grundmenge der Struktur einelementig sein muss, da alle Elemente gleich sind.
  3. Um die Nichtableitbarkeit Δ⊬u=v zu zeigen, genügt es aufgrund des Korrektheitssatzes, eine Interpretation I mit I⊨Δ, aber I⊭u=v anzugeben. Dazu sei  M={a,b}  eine zweielementige Menge und die Variablenbelegung sei durch  I(x)=I(y)=I(u)=a  und
    I(v)=b

    festgelegt.


 


Aufgabe * (7 Punkte)

Zeige, dass die Existenzeinführung im Antezedens eine korrekte Regel ist.

Es sei αyx→β allgemeingültig, d.h.

I⊨αyx→β

für jede S-Interpretation I. Wir müssen zeigen, dass dann auch ∃xα→β allgemeingültig ist (unter den gegebenen Voraussetzungen). Es sei dazu I eine Interpretation mit

I⊨∃xα.

Aufgrund der Modellbeziehung bedeutet dies, dass es ein  m∈M  (aus der Grundmenge der Interpretation) mit

Imx⊨α

gibt. Die Variable y kommt nach Voraussetzung in ∃xα nicht frei vor, d.h. bei  y≠x,  dass y in α nicht frei vorkommt. Wir können daher das Koinzidenzlemma anwenden und erhalten

(Imx)my⊨α.

Diese Aussage gilt trivialerweise auch bei  x=y.  Damit gilt auch

(Imy)mx⊨α.

Wir schreiben dies (etwas künstlich) als

(Imy)(Imy)(y)x⊨α.

Darauf können wir das Substitutionslemma (für die Interpretation J=Imy und den Term y) anwenden und erhalten

Imy⊨αyx.

Wegen der vorausgesetzten Allgemeingültigkeit von αyx→β folgt

Imy⊨β.

Da y in β nicht frei vorkommt, liefert das Koinzidenzlemma

I⊨β.


 


Aufgabe * (7 Punkte)

Es sei S ein Symbolalphabet und I eine S-Interpretation auf einer Menge M, wobei die Terminterpretation surjektiv sei. Zeige, dass die Gültigkeitsmenge Γ=I⊨ maximal widerspruchsfrei ist und Beispiele enthält.

Zunächst ist  Γ=I⊨  aufgrund des Korrektheitssatzes abgeschlossen unter Ableitungen. Für jeden S-Ausdruck α gilt die Alternative: Entweder  α∈Γ  oder  ¬α∈Γ.  Insbesondere ist Γ widerspruchsfrei. Wenn  α∉Γ  ist, so ist  ¬α∈Γ  und daher ist Γ∪{α} widersprüchlich. Also ist Γ maximal widerspruchsfrei.
Wir betrachten nun einen Ausdruck der Form  α=∃xβ.  Wenn  α∉Γ  gilt, so gilt ∃xβ→βtx in I für jeden Term t, da ja der Vordersatz nicht gilt. Wenn hingegen  α∈Γ  gilt, so gibt es aufgrund des semantischen Aufbaus der Gültigkeitbeziehung ein  m∈M  derart, dass Imx⊨β gilt. Wegen der vorausgesetzten Surjektivität der Belegung gibt es einen Term t, der durch m interpretiert wird. Daher gilt nach dem Substitutionslemma βtx in I. Also gilt ∃xβ→βtx in I.


 


Aufgabe (2 Punkte)

Man gebe ein Beispiel für eine mathematische Begriffsbildung, die als S-Homomorphismus zu einem geeigneten Symbolalphabet S verstanden werden kann.

S-Homomorphismus/Mathematisches Beispiel/Aufgabe/Lösung

 


Aufgabe (3 Punkte)

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

Registermaschine/Alle Primzahlen/Druckt/Aufgabe/Lösung

 


Aufgabe (3 Punkte)

Erläutere die Churchsche These.

Churchsche These/Erläutere/Aufgabe/Lösung

 


Aufgabe * (12 Punkte)

Es sei Γ⊆LAr eine arithmetische Ausdrucksmenge und R⊆ℕ eine Relation. Es seien α,β∈LAr Ausdrücke in einer freien Variablen x. Zeige, dass aus

Γ⊢α↔β

nicht folgt, dass α in Γ die Relation R genau dann repräsentiert, wenn β in Γ die Relation R repräsentiert.

Es sei R=ℕ, α=∃y(x=y+0) und β=∃y(x=y+1). Wir setzen

Γ={α↔β,α0x,α1x,α1+1x,α1+1+1x,etc}.

Der Ausdruck α repräsentiert in Γ die volle Relation R=ℕ, da ja für jedes n∈ℕ gilt n∈R, aber auch Γ⊢αnx. Ferner gilt Γ⊢α↔β. Wir behaupten, dass β nicht die Relation in Γ repräsentiert, wobei wir Γ⊬β0x nachweisen wollen. Um diese Nichtableitbarkeit zu zeigen, müssen wir aufgrund des Korrektheitssatzes eine Interpretation angeben, für die Γ gilt, aber β0x nicht gilt. Dazu wählen wir als Grundmenge ℤ, wobei wir die 0,1 und die Multiplikation (die keine Rolle spielt) natürlich interpretieren, und wo wir die Addition auf ℕ natürlich interpretieren und m+n=−2 setzen, sobald ein Summand negativ ist. Die Variable x wird als −1 interpretiert. Bei dieser Interpretation gilt dann weder α noch β, da −1 überhaupt nicht als Wert der gewählten Addition auftaucht. Daher gilt wiederum die Äquivalenz α↔β bei dieser Interpretation. Die Ausdrücke αnx für n∈ℕ gelten bei der Interpretation, der Ausdruck β0x bedeutet ∃y(0=y+1) und gilt hingegen nicht, da bei y≥0 der Wert von y+1 größer als 0 ist und bei y<0 der Wert nach Definition gleich −2≠0 ist.