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

Vorlesung 3

Bearbeiten

In der dritten Vorlesung sollte unter "Ein Ableitungskalkül für die aussagenlogischen Tautologien" in dem Satz "Man könnte auch de Implikation   durch   definieren,"   (und die statt de) stehen.

richtig, Danke

Was bedeutet  ?

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

Bearbeiten

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

ja

Lemma 3.11

Bearbeiten

Hallo, ist folgende Ableitung richtig?

Wegen Axiom (1) gilt:

 

Wegen Axiom (4) gilt:

 

Nun gilt

 

Mit Modus Ponens erhalten wir somit

 

Beste Grüße

Vorsicht, die Gleichheit
 

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

 

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)

Bearbeiten

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:

 
 
 

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

 

zu

 


es ist nach 3.8(2)
 

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

Lemma 4.6

Bearbeiten

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

Bearbeiten

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

 

dass   widerspruchsfrei ist

nehmen wir   widersprüchlich an. Dann ist  . Nach einer Aufgabe (4.4) ist dann  . Wegen   folgt nach Fallunterscheidungsregel  .

Vorlesung 7

Bearbeiten

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

 

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

 

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)

Bearbeiten

Bei der Implikation, Sei   heißt es:  . Müsste es nicht ein   sein?

Vorlesung 2 Alphabet

Bearbeiten

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

ja

Vorlesung 10

Bearbeiten

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   und   ergibt sich  .

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

 
 
 

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:


 

Warum gilt das?

Testklausur Nr. 9.(3)

Bearbeiten

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)

Bearbeiten

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:

 
 
 

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
 

mit   für die verschiedenen  . Dabei ist der Vordersatz gleich dem Nachsatz zu  , sie haben also eine Kette von Implikationen, die insgesamt   ergeben.

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

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  . Bei bspw n=3 haben wir

 

und

 

und

 

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

 

und somit ist

 

Mit der dritten Zeile kriegt man dann ebenso auch noch das letzte   in ein   verwandelt.

Danke...jetzt habe ich es verstanden!

Proposition 17.7.4

Bearbeiten

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

stimmt, Danke +1KP

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

Bearbeiten

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

richtig, 1KP.

Lemma 11.7

Bearbeiten

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

 

und

 

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
 

die Ableitbarkeit

 

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.

 

bedeutet, dass in allen Modellen, in denen   gilt, jeweils auch   gilt. Dagegen bedeutet

 

dass falls in allen (!) Modellen   gilt, dann auch in allen Modellen   gilt (wenn   nicht in allen Modellen gilt, ist die Gesamtaussage automatisch wahr).

Definition 24.3

Bearbeiten

Eine Kleinigkeit: Bei   fehlt eine Klammer zu.

Danke 1KP

Vorlesung 26 - gerichtete Graphen und Semantik

Bearbeiten

Bei dem dritten Beispiel von Kripkes Semantik ist geschrieben, dass   und gleich darunter, dass  . Wie kommt das zustande? Schließlich gibt es keine Folgeknoten nach   mehr.

Eben, wenn es keinen Nachfolger gibt, ist die Allaussage fuer alle Nachfolger erfuellt und daher ist   fuer jede Aussage.

PDF Vorlesung 24/27

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

Beispiel 13.9

Bearbeiten

In der Zeile   muss es am Ende   heißen.

Danke

Lemma 14.9

Bearbeiten

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

Bearbeiten

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

richtig.

Peano-Arithmetik umfassen

Bearbeiten

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   bzw.  ) und Modelle zusammenschmeißen.   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

Bearbeiten

Wieso ist die Kontraposition des Löb-Axioms (   ) denn   und nicht  ?

Sie meinen   Ja, das ist die direkte Kontraposition. Nur kann man dann die Negation wegkriegen, indem man überall statt   einfach   und dafuer dann wieder   schreibt (das gilt ja stets fuer beliebige Aussage).

Klausureinsicht

Bearbeiten

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?

Bearbeiten

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

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