Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Forum

Information

• Information zum Inhalt
• Ort und Zeit
• Information zu Übungen
• Information zur Klausur
• Zu Wikiversity

Vorlesungen

• 1 - Probleme

• 2 - Formale Sprachen

• 3 - Tautologien

• 4 - Vollständigkeit der Aussagenlogik

• 5 - Das Lemma von Zorn

• 6 - Prädikatenlogik

• 7 - Semantik der Prädikatenlogik

• 8 - Folgerungen

• 9 - Substitution

• 10 - Ableitungskalkül

• 11 - Quantorenregeln

• 12 - Natürliche Zahlen

• 13 - Peano-Arithmetik

• 14 - Satz von Henkin

• 15 - Der Vollständigkeitssatz

• 16 - Elementare Äquivalenz I

• 17 - Elementare Äquivalenz II

• 18 - Registermaschinen

• 19 - Das Halteproblem

• 20 - Arithmetische Repräsentierungen

• 21 - Die Unentscheidbarkeit der Arithmetik

• 22 - Der Fixpunktsatz

• 23 - Die Unvollständigkeitssätze

• 24 - Modallogik I

• 25 - Modallogik II

• 26 - Semantik der Modallogik

• 27 - Vollständigkeit der Modallogik

Arbeitsblätter

• Arbeitsblatt 1

• Arbeitsblatt 2

• Arbeitsblatt 3

• Arbeitsblatt 4

• Arbeitsblatt 5

• Arbeitsblatt 6

• Arbeitsblatt 7

• Arbeitsblatt 8

• Arbeitsblatt 9

• Arbeitsblatt 10

• Arbeitsblatt 11

• Arbeitsblatt 12

• Arbeitsblatt 13

• Arbeitsblatt 14

• Arbeitsblatt 15

• Arbeitsblatt 16

• Arbeitsblatt 17

• Arbeitsblatt 18

• Arbeitsblatt 19

• Arbeitsblatt 20

• Arbeitsblatt 21

• Arbeitsblatt 22

• Arbeitsblatt 23

• Arbeitsblatt 24

• Arbeitsblatt 25

• Arbeitsblatt 26

• Arbeitsblatt 27

Weitere Materialien

• Definitionsliste

• Definitionsabfrage

• Wichtigste Aussagen

• Aussagen (Abfrage)

• Kurze Einführung zur Logik

• Mächtigkeiten

• Äquivalenzrelationen

• Testklausur

• Lösungen dazu

• Beispielklausur 1

• Lösungen dazu

• Beispielklausur 2

• Lösungen dazu

• BeispielKlausur 3

• Lösungen dazu

• Beispielklausur 4

• Lösungen dazu

• Beispielklausur 5

• Lösungen dazu

• Beispielklausur 6

• Lösungen dazu

• Beispielklausur 7

• Lösungen dazu

• Beispielklausur 8

• Lösungen dazu

• Beispielklausur 9

• Lösungen dazu

• Beispielklausur 10

• Lösungen dazu

• Beispielklausur 11

• Lösungen dazu

Forum

Literatur

Links

Neuer Beitrag

Vorlesung 3

In der dritten Vorlesung sollte unter "Ein Ableitungskalkül für die aussagenlogischen Tautologien" in dem Satz "Man könnte auch de Implikation $\alpha \rightarrow \beta$ durch $\neg \left(\alpha \wedge \beta \right)$ definieren," $\neg \left(\alpha \wedge \neg \beta \right)$ (und die statt de) stehen.

richtig, Danke

Was bedeutet $I^{\vDash }$?

steht direkt nach 3.7

Da ist es aber nur für Mengen definiert. Eine Interpretation ist ja eine Abbildung. Ist die Menge aller wahren Aussagen in der Interpretation I gemeint?

richtig, das ist gemeint, es steht jetzt ein Satz dazu in Vorlesung 2.

Aufgabe 5.26

Ist die Bedeutung von "nach oben wohlgeordnet" analog zu Definition 5.15 mit größtem statt kleinstem Element?

ja

Lemma 3.11

Hallo, ist folgende Ableitung richtig?

Wegen Axiom (1) gilt:

$\vdash \alpha \rightarrow (\alpha \rightarrow \alpha )$

Wegen Axiom (4) gilt:

$\vdash (\alpha \rightarrow (\alpha \rightarrow \alpha ))\rightarrow (\alpha \wedge \alpha \rightarrow \alpha )$

Nun gilt

$\alpha \wedge \alpha =\alpha$

Mit Modus Ponens erhalten wir somit

$\vdash \alpha \rightarrow \alpha$

Beste Grüße

Vorsicht, die Gleichheit

$\alpha \wedge \alpha =\alpha$

gilt nicht bzw. macht gar keinen Sinn. Es handelt sich um zwei verschiedende Ausdrücke, da es ja verschiedene Wörter sind. Es gilt zwar die Äquivalenz

$\vdash \alpha \wedge \alpha \leftrightarrow \alpha ,$

und damit kann man so schließen, doch muss auch diese Äquivalenz zuerst etabliert werden, was erst in 3.12 geschieht.

Lemma 3.19 (6)

Hi, im Skript steht zu Lemma 3.19(6), dass dies bereits aus Lemma 3.19 (3),(4) und (5) folgt. Mein Beweis sieht wie folgt aus:

$\vdash (\neg \beta \rightarrow \neg \alpha )\rightarrow (\neg \neg \alpha \rightarrow \neg \neg \beta )$

$\vdash \neg \neg \beta \rightarrow \beta .$

$\vdash (\neg \beta \rightarrow \neg \alpha )\rightarrow (\neg \neg \alpha \rightarrow \beta )$

Mit welchem Axiom bzw. welcher Schlußregel bekomme ich nun das

$\neg \neg \alpha \$

zu

$\alpha \$

es ist nach 3.8(2)

$\vdash (\alpha \rightarrow \neg \neg \alpha )\wedge (\neg \neg \alpha \rightarrow \beta )\rightarrow (\alpha \rightarrow \beta )$

Die erste Bedingung ist nach 3.19 (3) erfüllt, die zweite ist der Nachsatz aus Ihrer Ableitung.

Lemma 4.6

Hallo, besagt Lemma 4.6, dass bei einer maximal widerspruchfreien Teilmenge der Sprache der Aussagenlogik sich keine neuen Aussagen ableiten lassen?

das ist der Inhalt von Teil (2).

Satz 5.19

Hallo, ich habe 2 Fragen zu Satz 5.19.

1. Wo genau haben wir die Richtung von links nach rechts gezeigt?

die Korrektheitsüberlegungen haben wir im Anschluss an die Auflistung der Tautologien in 3.10 kurz besprochen (mit Aufgabe)

2. Warum folgt aus

$\Gamma \not \vdash \alpha .$

dass ${}\Gamma \cup \{\neg \alpha \}$ widerspruchsfrei ist

nehmen wir ${}\Gamma \cup \{\neg \alpha \}$ widersprüchlich an. Dann ist ${}\Gamma \cup \{\neg \alpha \}\vdash \alpha$. Nach einer Aufgabe (4.4) ist dann ${}\Gamma \vdash \neg \alpha \rightarrow \alpha$. Wegen ${}\vdash \alpha \rightarrow \alpha$ folgt nach Fallunterscheidungsregel ${}\Gamma \vdash \alpha$.

Vorlesung 7

Hallo, ich habe eine Frage und zwar welches Alphabet zur folgenden Sprache zugrunde gelegt wird

$L^{S}$

Besteht das Alphabt nur aus den Variablen, den Konstanten, den Funktionssymbolen und den Relationssymbolen?

das ist das (variable) Symbolalphabet S

Oder kommen auch noch die Junktoren, das Gleichheitszeichen, die Quantoren und die Klammern dazu?

das gehört stets zum (Gesamt)Alphabet der Sprache.

Das ist mir schon klar. Meine Frage war, welches Alphabet die Sprache

$L^{S}$

erzeugt? Nur die Menge S? Die Junktoren etc. gehören ja nach Definition nicht zu S

erzeugt haben wir nicht verwendet. Als Zeichenmenge, die die Wörtermenge festlegt, braucht man S zusammen mit den Junktoren. Insofern erzeugt S + Junktoren die Sprache (genauert die Wortmenge, worin die Sprache ein Teil ist). Da aber die Junktoren immer gleich ist, kommt es i.g.S. nur auf S an, insofern 'erzeugt' S.

Aufgabe 5.20 (Lösung)

Bei der Implikation, Sei $\alpha =\beta _{1}\rightarrow \beta _{2}$ heißt es: ${\text{Bei }}\vdash \gamma \rightarrow \beta _{1}{\text{ oder }}\vdash \gamma \rightarrow \neg \beta _{2}{\text{ ergibt sich die Ableitung}}\vdash \gamma \rightarrow \neg (\beta _{1}\rightarrow \beta _{2})$. Müsste es nicht ein ${\text{und}}$ sein?

Vorlesung 2 Alphabet

Ist jede Menge ein Alphabet? Bzw. kann jede Menge als Symbolmenge (kanonisch?) interpretiert werden?

ja

Vorlesung 10

Hallo, gelten die in der 3. Vorlesung eingeführten Schlussregeln auch im prädikatenlogischen Kalkül? In Lemma 3.18 (2) haben wir ja folgendes bewiesen:

Aus ${}\vdash \alpha$ und ${}\vdash \alpha \wedge \beta \rightarrow \gamma$ ergibt sich ${}\vdash \beta \rightarrow \gamma$.

Damit lässt sich doch nun ganz einfach Lemma 10.7 (1) beweisen:

$\vdash s=s$

$\vdash (s=t)\wedge (s=s)\rightarrow t=s$

$\vdash s=t\rightarrow t=s$

Das ist doch der Inhalt von Lemma 10.2,dass die Schlussregeln auch für Ausdrücke in der Prädikatenlogik gelten

alle aussagenlogischen Tautologien und Schlussregeln gelten in der Prädikatenlogik, ja. Daraus allein lässt sich aber nicht die Symmetrie der Gleichheit ableiten, dazu brauchen wir die beiden Gleichheitsaxiome (Ihre zweite Ableitungszeile beruht auf dem Substitutionsaxiom)

Das ist mir schon bewusst. Ich habe jetzt nur Lemma 3.18(2) auf die erste und zweite Zeile angewendet. Der obige Beweis ist somit auch richtig oder?

ja, nur die zweite Zeile kommt vom Substitutionsaxiom her.

Dann stellt sich mir nur noch eine Frage. Und zwar wurde bei Lemma 10.7(1) von folgender Äquivalenz Gebrauch gemacht:

$\vdash ((s=t)\wedge (s=s)\rightarrow t=s)\leftrightarrow ((s=s)\wedge (s=t)\rightarrow t=s)$

Warum gilt das?

Testklausur Nr. 9.(3)

Warum muss man bei der Testklausur in Aufgabe Nr 9.(3) noch zeigen was für die eine Anzahl von n≥3 Individuen geschieht ? Die Frage lautet doch dort : "Zeige das die Tierart genau dann aussterben muss, wenn es in einer Generation nur zwei oder weniger Individuen gibt." Unter "genau dann, wenn zwei oder weniger" verstehe ich das man nur den Fall 2 Tiere 1 Tier und 0 Tiere betrachten muss. Bei null Tieren ist die Generation bereits ausgestorben; bei einem Tier kann dieses alleine keine Nachfahren zeugen und stirbt mit der Zeit; bei zwei Tieren folgt maximal ein Nachkomme und dieser kann wieder alleine keine Nachkommen zeugen und stirbt ebenfalls mit der Zeit. Meines Erachtens ist somit nach einer Generation mit 3 Tieren gar nicht gefragt. Gab -1 Punkt Abzug, wären dann ja 3 Punkte.

Sie müssen genau dann zeigen, also auch, dass wenn die Tiere aussterben müssen, es dann maximal 2 in einer Generation gibt. Durch Kontraposition müssen Sie also zeigen, dass bei mindestens drei Tieren das Aussterben verhindert werden kann.

Lemma 10.7(4)

Hallo, ich weiß nicht, wo genau die Transitivität der Implikation zum Beweis von Lemma 10.7(4) verwendet wird. Ich komme bloß zu folgendem Beweis:

$\vdash s_{i}=t_{i}\rightarrow {\left(Rt_{1}\ldots t_{i-1}us_{i+1}\ldots s_{n}{\frac {s_{i}}{u}}\rightarrow Rt_{1}\ldots t_{i-1}us_{i+1}\ldots s_{n}{\frac {t_{i}}{u}}\right)},$

$\vdash s_{i}=t_{i}\rightarrow {\left(Rt_{1}\ldots t_{i-1}s_{i}s_{i+1}\ldots s_{n}\rightarrow Rt_{1}\ldots t_{i-1}t_{i}s_{i+1}\ldots s_{n}\right)}.$

$\vdash (s_{1}=t_{1})\wedge \ldots \wedge (s_{n}=t_{n})\rightarrow {\left(Rt_{1}\ldots t_{i-1}s_{i}s_{i+1}\ldots s_{n}\rightarrow Rt_{1}\ldots t_{i-1}t_{i}s_{i+1}\ldots s_{n}\right)}.$

Wobei der dritte Schritt gemäß der Schlussregel zu Lemma 3.16(1) gilt. Weiter komme ich aber nicht. Um Hilfe wäre ich dankbar

Sie haben hinten die Implikationen

$\Psi _{i}=\alpha _{i}\rightarrow \alpha _{i+1}$

mit ${}\alpha _{i}=Rt_{1}\ldots t_{i-1}s_{i}s_{i+1}\ldots s_{n}$ für die verschiedenen ${}i$. Dabei ist der Vordersatz gleich dem Nachsatz zu ${}\Psi _{i-1}$, sie haben also eine Kette von Implikationen, die insgesamt ${}\alpha _{1}\rightarrow \alpha _{n}$ ergeben.

Tut mir leid, aber mir will immer noch nicht klar werden, warum dann dadurch

$\vdash (s_{1}=t_{1})\wedge \ldots \wedge (s_{n}=t_{n})\rightarrow {\left(Rs_{1}\ldots s_{n}\rightarrow Rt_{1}\ldots t_{n}\right)}.$

gilt. Kann jemand bitte wie oben einen formalen Beweis erstellen?

Ein formaler Beweis ist von n abhängig.

Der Vordersatz (die Konjunktion) ist immer gleich. Das sei ${}\gamma$. Bei bspw n=3 haben wir

$\vdash \gamma \rightarrow {\left(Rs_{1}s_{2}s_{3}\rightarrow Rt_{1}s_{2}s_{3}\right)}$

und

$\vdash \gamma \rightarrow {\left(Rt_{1}s_{2}s_{3}\rightarrow Rt_{1}t_{2}s_{3}\right)}$

und

$\vdash \gamma \rightarrow {\left(Rt_{1}t_{2}s_{3}\rightarrow Rt_{1}t_{2}t_{3}\right)}.$

Aus aussagenlogischen Gründen (Transitivität der Implikation) ist

${\left({\left(Rs_{1}s_{2}s_{3}\rightarrow Rt_{1}s_{2}s_{3}\right)}\wedge {\left(Rt_{1}s_{2}s_{3}\rightarrow Rt_{1}t_{2}s_{3}\right)}\right)}\rightarrow {\left(Rs_{1}s_{2}s_{3}\rightarrow Rt_{1}t_{2}s_{3}\right)}$

und somit ist

$\vdash \gamma \rightarrow {\left(Rs_{1}s_{2}s_{3}\rightarrow Rt_{1}t_{2}s_{3}\right)}$

Mit der dritten Zeile kriegt man dann ebenso auch noch das letzte ${}s_{3}$ in ein ${}t_{3}$ verwandelt.

Danke...jetzt habe ich es verstanden!

Proposition 17.7.4

Fehlt hier nicht für s die Eigenschaft selbst eine obere Schranke zu sein?

stimmt, Danke +1KP

EM

Ich hätte eine grandiose Idee die anstehende EM für alle Kursteilnehmer noch interessanter zu gestalten: Es könnte doch einen Kollektivpunkt für jedes für Deutschland gewertete Tor geben, so dass man von nun an nicht mehr nur auf das Tor anstößt, sondern auch auf einen gewonnenen Kollektivpunkt.

Wären Sie damit einverstanden?

das hab ich schon in der Vorlesung gesagt, dass das nur bei einer WM in Frage kommt. Mein Bedauern.

Beweis Lemma 19.9

Im Beweis heißt es: "Zu jeder natürlichen Zahl $n$ berechnet man sämtliche Programme $P$ mit $c(P)\neq n$." Das sind doch unendlich viele. Müssen es nicht alle Programme $P$ mit $c(P)\leq n$ sein, damit irgendwann n inkrementiert werden kann?

richtig, 1KP.

Lemma 11.7

Hallo, kann man Lemma 11.7 auch wie folgt interpretieren, dass

$\vdash \forall x\alpha \rightarrow \alpha$

und

$\vdash \alpha \rightarrow \forall x\alpha$

syntaktische Tautologien sind?

nein, das wäre deutlich stärker! Das erste stimmt, das zweite nicht.

Dann verstehe ich nicht ganz genau, was Lemma 11.7 aussagt. Ich habe es so verstanden, dass aus der Ableitbarkeit von

$\vdash \alpha$

die Ableitbarkeit

$\vdash \forall x\alpha$

folgt und umgekehrt

11.7 besagt nur die Regel, dass aus einer Ableitbarkeit eine andere Ableitbarkeit folgt. Sie müssen zwischen systeminternen Ableitungen (was kann das System beweisen; diese sind stärker) und Regeln unterscheiden.

Auch semantisch besteht dieser Unterschied deutlich.

$\vdash \alpha \rightarrow \beta$

bedeutet, dass in allen Modellen, in denen ${}\alpha$ gilt, jeweils auch ${}\beta$ gilt. Dagegen bedeutet

${\text{ Wenn }}\vdash \alpha ,{\text{ dann auch }}\vdash \beta ,$

dass falls in allen (!) Modellen ${}\alpha$ gilt, dann auch in allen Modellen ${}\beta$ gilt (wenn ${}\alpha$ nicht in allen Modellen gilt, ist die Gesamtaussage automatisch wahr).

Definition 24.3

Eine Kleinigkeit: Bei $\Diamond \gamma \rightarrow (\Diamond \neg \alpha \vee \Diamond (\alpha \wedge \gamma )$ fehlt eine Klammer zu.

Danke 1KP

Vorlesung 26 - gerichtete Graphen und Semantik

Bei dem dritten Beispiel von Kripkes Semantik ist geschrieben, dass $M,w_{5}\vDash \Box \phi$ und gleich darunter, dass $M,w_{5}\vDash \Box \lnot \phi$. Wie kommt das zustande? Schließlich gibt es keine Folgeknoten nach $w_{5}$ mehr.

Eben, wenn es keinen Nachfolger gibt, ist die Allaussage fuer alle Nachfolger erfuellt und daher ist ${}\Box \alpha$ fuer jede Aussage.

PDF Vorlesung 24/27

Hallo. Können noch die PDFs der Vorlesung 24 und 27 hochgeladen werden? Vielen Dank!

Beispiel 13.9

In der Zeile $(u|x)\land (u|y)\land ((v|x)\land (v|y)\rightarrow u|v)$ muss es am Ende $v|u$ heißen.

Danke

Lemma 14.9

Etwas Rosinenpickerei: Da wir den Belegungsbegriff nur für Variablen definiert haben, müsste man nicht streng formal fordern dass die Interpretation I gleich (M mit den Interpretationen c^M=[c], \beta) ist, mit \beta nur auf Variablen definiert?

stimmt, sehr aufmerksam.

Beweis Fixpunktsatz 22.8

Im ersten Textabschnitt steht F(m,n) = s(n). Das müsste aber GN(s(n)) sein oder?

richtig.

Peano-Arithmetik umfassen

Eine Verständnisfrage: Was bedeutet es genau die Peano Arithmetik zu umfassen?

Dass in der Theorie zumindest

Zahlentheorie/Peano-Axiome/Operation/Erste Stufe/Axiom gilt (eventuell aber auch mehr).

Okay: Folgender Gedankengang. Die Menge der arithmetischen Ausdrücke ist nicht entscheidbar, also die Menge der natürlichen Zahlen mit den erststufigen Peano-Axiomen. Nun wird im 2. Unvollständigkeitssatz gefordert, dass Gamma sowohl entscheidbar und wsf sei als auch die natürliche Arithmetik umfasse. D.h. insbesondere Gamma ist ein erstufiges modell der natürlichen Zahlen. Heißt das also es gibt Nicht-Standardmodelle der natürlichen Zahlen die entscheidbar sind? oder gibt es einen Denkfehler?

nicht Theorien (wie ${}\Gamma$ bzw. ${}\Gamma ^{\vdash }$) und Modelle zusammenschmeißen. ${}\Gamma$ ist kein Modell, sondern eine Ausdrucksmenge, und auch nicht die Gültigkeitsmenge eines Modells, da eine solche vollständig ist. Ein solches Nicht-Standard-Modell, das die erststufige Peano-Arithmetik umfasst, kann es aufgrund des ersten GUV nicht geben.

Kontraposition des Löb-Axioms

Wieso ist die Kontraposition des Löb-Axioms ( ${\displaystyle \Box (\Box \alpha \rightarrow \alpha )\rightarrow \Box \alpha }$ ) denn ${\displaystyle \Diamond \alpha \rightarrow \Diamond (\alpha \wedge \neg \Diamond \alpha )}$ und nicht ${\displaystyle \Diamond \alpha \rightarrow \Diamond (\neg \alpha \wedge \neg \Diamond \neg \alpha )}$?

Sie meinen ${\displaystyle \Diamond \neg \alpha \rightarrow \Diamond (\neg \alpha \wedge \neg \Diamond \neg \alpha )}$ Ja, das ist die direkte Kontraposition. Nur kann man dann die Negation wegkriegen, indem man überall statt ${}\neg \alpha$ einfach ${}\beta$ und dafuer dann wieder ${}\alpha$ schreibt (das gilt ja stets fuer beliebige Aussage).

Klausureinsicht

Wann ist die Einsicht für die Nachschreibeklausur? Danke.

Sprechstunde, oder sonst mal versuchen. Beispielsweise morgen (Do 6.Oktober) nachmittag 13-15 Uhr.

Lösungen zu den Arbeitsblättern?

Gibt es irgendwo die Lösungen zu den Arbeitsblättern?

nein, nuur für die Aufgaben mit einem Stern.