Freitag, 17. Mai 2013

Panorama 17. 5. 2013

Den ersten Teil der Vorlesung werde ich im vorherigen Eintrag mit einarbeiten, da er dort inhaltlich hingehört. Hier aber die „Folien“ zur Einführung logischer Grundbegriffe.


Und damit Sie mal eine solche gesehen haben und weil ich offenbar zu viel Zeit habe, hier mit\begin{align*}
AG:=\{&\forall x\forall y (x+y=y+x),
\\&\forall x\forall y\forall z((x+y)+z=x+(y+z)),
\\&\forall x(0+x=x),
\\&\forall x\neg\forall y\neg (x+y=0)
\}\end{align*}eine Herleitung von $AG\vdash\neg(c+a=c+b\land\neg a=b)$. Dabei muss man sich noch für jede Zeile überlegen, mit welcher Regel sie aus welchen vorhergehenden folgt.
\begin{align*}
&&AG&\ \vdash\ \forall x\forall y (x+y=y+x)&&\\
&&AG&\ \vdash\ \forall y (c+y=y+c)&&\\
&&AG&\ \vdash\ c+d=d+c&&\\
&&AG,c+d=0&\ \vdash\ c+d=d+c&&\\
&&AG,c+d=0&\ \vdash\ c+d=0&&\\
&&AG,c+d=0&\ \vdash\ d+c=0&&\\
&&AG,c+a=c+b&\ \vdash\ d+(c+a)=d+(c+a)&&\\
&&AG,c+a=c+b&\ \vdash\ c+a=c+b&&\\
&&AG,c+a=c+b&\ \vdash\ d+(c+a)=d+(c+b)&&\\
&&AG&\ \vdash\ \forall x\forall y\forall z((x+y)+z=x+(y+z))&&\\
&&AG&\ \vdash\ \forall y\forall z((d+y)+z=d+(y+z))&&\\
&&AG&\ \vdash\ \forall z((d+c)+z=d+(c+z))&&\\
&&AG&\ \vdash\ (d+c)+a=d+(c+a)&&\\
&&AG&\ \vdash\ (d+c)+a=(d+c)+a&&\\
&&AG&\ \vdash\ d+(c+a)=(d+c)+a&&\\
&&AG&\ \vdash\ (d+c)+b=d+(c+b)&&\\
&&AG&\ \vdash\ (d+c)+b=(d+c)+b&&\\
&&AG&\ \vdash\ d+(c+b)=(d+c)+b&&\\
&&AG,c+a=c+b&\ \vdash\ d+(c+a)=(d+c)+a&&\\
&&AG,c+a=c+b&\ \vdash\ (d+c)+a=d+(c+b)&&\\
&&AG,c+a=c+b&\ \vdash\ d+(c+b)=(d+c)+b&&\\
&&AG,c+a=c+b&\ \vdash\ (d+c)+a=(d+c)+b&&\\
&&AG,c+d=0,c+a=c+b&\ \vdash\ (d+c)+a=(d+c)+b&&\\
&&AG,c+d=0,c+a=c+b&\ \vdash\ d+c=0&&\\
&&AG,c+d=0,c+a=c+b&\ \vdash\ 0+a=0+b&&\\
&&AG&\ \vdash\ \forall x(0+x=x)&&\\
&&AG&\ \vdash\ 0+a=a&&\\
&&AG&\ \vdash\ 0+b=b&&\\
&&AG,c+d=0,c+a=c+b&\ \vdash\ 0+a=a&&\\
&&AG,c+d=0,c+a=c+b&\ \vdash\ 0+b=b&&\\
&&AG,c+d=0,c+a=c+b&\ \vdash\ a=b&&\\
&&AG,c+d=0,c+a=c+b,\neg a=b&\ \vdash\ a=b&&\\
&&AG,c+d=0,c+a=c+b,\neg a=b&\ \vdash\ \neg a=b&&\\
&&AG,c+d=0,c+a=c+b,\neg a=b&\ \vdash\ \neg c+d=0&&\\
&&AG,\neg c+d=0,c+a=c+b,\neg a=b&\ \vdash\ \neg c+d=0&&\\
&&AG,c+a=c+b,\neg a=b&\ \vdash\ \neg c+d=0&&\\
&&AG,c+a=c+b,\neg a=b&\ \vdash\ \forall y\neg c+y=0&&\\
&&AG&\ \vdash\ \forall x\neg\forall y\neg x+y=0&&\\
&&AG&\ \vdash\ \neg\forall y\neg c+y=0&&\\
&&AG,c+a=c+b,\neg a=b&\ \vdash\ \neg\forall y\neg c+y=0&&\\
&&AG,c+a=c+b,\neg a=b&\ \vdash\ a=b\\
&&AG,c+a=c+b,a=b&\ \vdash\ a=b\\
&&AG,c+a=c+b&\ \vdash\ a=b\\
&&AG,c+a=c+b,c+a=c+b\land\neg a=b&\ \vdash\ a=b\\
&&AG,c+a=c+b,c+a=c+b\land\neg a=b&\ \vdash\ c+a=c+b\land\neg a=b\\
&&AG,c+a=c+b,c+a=c+b\land\neg a=b&\ \vdash\ \neg a=b\\
&&AG,c+a=c+b,c+a=c+b\land\neg a=b&\ \vdash\ \neg(c+a=c+b\land\neg a=b)\\
&&AG,\neg c+a=c+b,c+a=c+b\land\neg a=b&\ \vdash\ \neg c+a=c+b\\
&&AG,\neg c+a=c+b,c+a=c+b\land\neg a=b&\ \vdash\ c+a=c+b\land\neg a=b&&\\
&&AG,\neg c+a=c+b,c+a=c+b\land\neg a=b&\ \vdash\ c+a=c+b&&\\
&&AG,\neg c+a=c+b,c+a=c+b\land\neg a=b&\ \vdash\ \neg(c+a=c+b\land\neg a=b)&&\\
&&AG,c+a=c+b\land\neg a=b&\ \vdash\ \neg(c+a=c+b\land\neg a=b)&&\\
&&AG,\neg(c+a=c+b\land\neg a=b)&\ \vdash\ \neg(c+a=c+b\land\neg a=b)&&\\
&&AG&\ \vdash\ \neg(c+a=c+b\land\neg a=b)&&\\
\end{align*}
Durch Weglassen vieler Zeilen und Benutzung von Abkürzungen wird das fast lesbar.
\begin{align*}
&&AG&\ \vdash\ c+d=d+c&&\\
&&AG,c+d=0&\ \vdash\ d+c=0&&\\
&&c+a=c+b&\ \vdash\ d+(c+a)=d+(c+b)&&\\
&&AG&\ \vdash\ (d+c)+a=d+(c+a)&&\\
&&AG&\ \vdash\ (d+c)+b=d+(c+b)&&\\
&&AG,c+a=c+b&\ \vdash\ (d+c)+a=(d+c)+b&&\\
&&AG,c+d=0,c+a=c+b&\ \vdash\ 0+a=0+b&&\\
&&AG&\ \vdash\ 0+a=a&&\\
&&AG&\ \vdash\ 0+b=b&&\\
&&AG,c+d=0,c+a=c+b&\ \vdash\ a=b&&\\
&&AG&\ \vdash\ \exists y(c+y=0)&&\\
&&AG,c+a=c+b&\ \vdash\ a=b\\
&&AG&\ \vdash\ c+a=c+b\rightarrow a=b&&\\
\end{align*}


3 Kommentare:

  1. Hallo,

    ich wiederhole gerade Logik und hänge an einem Punkt: Stimmt es eigentlich, dass für eine Formelmenge X gilt:

    X konsistent gdw. es existiert ein Modell von X?

    Danke, das wars auch schon.

    AntwortenLöschen
    Antworten
    1. Ganz genau, das ist im wesentlichen der Gödelsche Vollständigkeitssatz von der letzten Folie.

      Dabei ist „hat X ein Modell, so ist X konsistent“ die einfache Richtung, nämlich die Korrektheit des Kalküls: Hat X ein Modell, so lassen sich aus X nur Formeln ableiten, die in diesem Modell gelten. Die Negation einer Formel ist in einem Modell aber genau dann erfüllt, wenn die Formel nicht erfüllt ist, sie können also nicht beide erfüllt sein.

      Die andere Richtung ist der Kern des Vollständigkeitssatzes. Auf der Folie heißt sie Modellexistenz, aber sie folgt aus der dort als Vollständigkeitssatz formulierten Aussage, denn hat X kein Modell, so ist jede Formel in jedem Modell von X erfüllt.

      Löschen