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

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Vista-kmixdocked.png

Neuer Beitrag

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

EM[Bearbeiten]

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.