Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Fragen + Lsg. Ansatz zur Altklausur Aufgabe 2 von WS1415
Die Aufgabenstellung zu finden hier: https://www8.cs.fau.de/_media/ws14:gloin:probeklausurWS1415.pdf
Die geTeXte Version meines Ansatzes zur besseren Lesbarkeit, siehe Anhang.
Zu Teilaufgabe 5. verstehe ich nicht ganz, wie man die Vereinigung alle einelementigen Mengen von X darstellen soll. Daher: konstruktive Vorschläge und Kommentare etc. werden gerne angenommen.
Attachment:
Aufgabe 2 Formalisierung in Prädikatenlogik.pdf: https://fsi.cs.fau.de/unb-attachments/post_150549/Aufgabe 2 Formalisierung in Prädikatenlogik.pdf
In deinem Lösungsversuch sind ein paar notationelle Schwächen. Beachte, dass die Formalisierungsaufgabe genau definiert, was du verwenden darfst. Hier ist es FOL mit binärem ∈ und unärem p. In deiner Lösung schreibsT du allerdings Pot statt p.
Auch wenn man in Mathematischen Argumentationen ∀x∈X. … verwenden sollte, ist das hier erstmal nicht definiert. Du hast nur Logik erster Stufe (∀x.…) sowie binäres ∈ (z.B. x∈y), aber erstmal nicht ∀x∈X.… (analog für ∃).
Wenn du eine Eigenschaft formalisierst, dann sollten die freien Variablen der Formel genau die Objekte sein, die explizit verwähnt werden. Z.b. die Formel zu “X ist Teilmenge von Y” sollte genau zwei freie Variablen haben: X und Y. Überdenke diesbezgl. deine Antwort zu 1, 2 und 3.
Bei der 5. wird nach “höchstens einelementig” gefragt, d.h. hier ist auch “leer” erlaubt.
Bzgl. der vereinigung kannst du dir überlegen: Nehmen wir an, eine Menge Y würde all diese höchstens einelementigen Teilmengen von X enthalten, wie würde sich Y dann zu X verhalten? 
Die 4 die dir fehlt ist meiner Meinung nach die einfachste, weil man direkt beschreibt, was grammatikalisch da steht.
1 „Gefällt mir“
errnosys, erst einmal vielen Dank! Deine Antwort war höchst nützlich und ich habe auch meinen Aufschrieb abgeändert. Ich habe die mathematische Argumentation in FOL umgemodelt, wie ich denke, dass es geht. Zum Beispiel: Aus “\forall x \in X” schrieb ich “\forall x.(x \in X)” - zugeben der Unterschied wirkt auf mich äußerst mickrig… und bin mir daher auch nicht sicher, ob es passt.
Habe auch eine Version zu Teil 4. hinzugefügt.
Zu deinem Wink Bzgl. “bzgl. der Vereinigung” - habe ich nicht verstanden, worauf du hinaus möchtest, kann nur raten.
- Jede Teilmenge von Y ist eine Teilmenge von X.
- X = Y
Attachment:
Aufgabe 2 Formalisierung in Prädikatenlogik2.pdf: https://fsi.cs.fau.de/unb-attachments/post_150557/Aufgabe 2 Formalisierung in Prädikatenlogik2.pdf
Es geht hier ja nicht darum ob irgendeine Formel so ähnlich aussieht wie eine andere, sondern was definiert ist und was nicht. und „∀x∈X“ wurde schlichtweg nie in der vorlesung in FOL definiert. (Und wird auch in tatsächlicher Mengentheorie nie als eigenständige Formel definiert).
Teil 1. passt aber immer noch nicht. Du schreibst „S(X, Y ) ⇔ ((x ∈ X) ⇒ (x ∈ Y ))“ für „X ist Teilmenge von Y“. Erstens sieht es so aus, als würdest du in deiner Formel ein S verwenden, und nirgendwo steht was dieses S sein soll oder woher es kommt. Allgemein ein Tipp: du sollst eine formel hinschreiben für „X ist Teilmenge von Y“, also schreib bei Teilaufgabe 1 einfach eine Formel hin die genau dies tut. Zweitens hat deine Formel drei freie Variablen (x, X, Y), die Aussage „X ist Teilmenge von Y“ hat jedoch nur X und Y als freie variablen.
Bei Teil 2 ist genau umgekehrt: „Jede Menge ist durch ihre Elemente eindeutig bestimmt.“ hat keine freie variable, d.h. die Formel die du bei Teilaufgabe 2 hinschreibst sollte ebenfalls keine freien Variablen haben. Gleiches gilt für Teil 3 und Teil 4.
Teil 3: „Die Potenzmenge einer Menge X enthält gerade die Teilmengen dieser Menge X“ heißt: „jedes z ist genau dann eine Teilmenge von X wenn z ein element aus p(X) ist“.
Nehmen wir mal an bei Teil 1 würdest du mit „S(X,Y) <=> …“ meinen „Ich definiere das prädikat S(X,Y) als …“. Dann wäre dein „p(x) <=> …“ inkonsistent dazu, denn p(x) ist kein prädikat sondern ein funktionssymbol aus deiner signatur, und das kannst du folglich auch nicht via „<=>“ definieren.
Deshalb wieder mein Tipp: schreib wie in der Angabe verlangt einfach eine Formel hin die das gewünschte formalisiert.
Teil 4: „Jede nichtleere Menge …“ bedeutet, dass jede Menge, die nicht leer ist, die angegebene Eigenschaft „…“ hat. Du allerdings sagst mit „ne(X) ∧ …“ dass jede Menge nicht leer ist, und obendrein die Eigenschaft „…“ hat. Das was dann kommt sieht ganz gut aus, also das „∃x.((x ∈ X)“, jedoch danach passt es nicht mehr.
Also allgemein empfiehlt sich folgende Tabelle von Vokabeln:
Jedes x …: ∀x.…
wenn … dann …: … → …
es gibt ein x: ∃x
es gibt kein x: ¬∃x
Und man muss den Satz grammatikalisch nur auf diese Phrasen massieren und dann stupide ersetzen, z.B. für Teil 4:
Jede nichtleere Menge enthält ein Element, mit dem sie keine Elemente gemeinsam hat
≡ Jede nichtleere Menge x enthält ein Element z und es gibt keine gemeinsamen Elemente von x und z
≡ Jede Menge x, wenn x nicht leer ist, enthält ein Element z, und es gibt keine gemeinsamen Elemente von x und z
≡ Jede Menge x, wenn x nicht leer ist, enthält ein Element z, und es gibt kein Element y das in x und z gleichzeitig sind
≡ ∀ x. ne(x) → ∃z. z∈x ∧ ¬∃y. (y∈x ∧ y∈z)
(dein ne(x) stimmt zwar, aber es ginge noch einfacher. Dass eine Menge x nichtleer ist bedeutet nämlich, dass es eben ein Element gibt).
Hast du schonmal deine zwei Verzuche überprüft? 
1 „Gefällt mir“
errnosys, erst einmal wirklich großen Dank dafür wie viel Mühe du dir gibst und mir hilfst…
Ich tue mir nur immer noch etwas schwer konkret Aussage und Formel Relation zu setzen. Z.b. A1 ist eine Aussage und F1 seine Formel dazu.
A2 ist auch eine Aussage mit den freien Variabeln x, y und F2 seine Formel dazu.
Man kann dann schreiben: A1 = F1 und A2 = F2 (x,y) ?
Ansonsten: Ich habe versucht deine Ratschläge sogut es geht umzusetzen, hoffe jetzt, dass es in die richtige Richtung geht…
Attachment:
Aufgabe 2 Formalisierung in Prädikatenlogik3.pdf: https://fsi.cs.fau.de/unb-attachments/post_150690/Aufgabe 2 Formalisierung in Prädikatenlogik3.pdf
Das Wort „Aussage“ ist komplett informel und kein Mathematisch definierter Begriff. Eine Formel jedoch schon (Definition 35 im Skript). Deshalb muss man auch nicht Dinge wie „A1 = F1“ schreiben, denn „Aussagen“ sind hier keine Mathematischen Objekte. Was man manchmal macht sind Hilfsdefinitionen, wie z.B. dein ss(X,Y). Das ist aber nur, um sich Schreibarbeit in den folgenden Formeln zu ersparen.
Wenn du nämlich bei Teil 1 sagst:
ss(X, Y ) := (∀x.((x ∈ X) ⇒ (x ∈ Y )))
meinst du damit eigentlich nur die Formel
(∀x.((x ∈ X) ⇒ (x ∈ Y )))
aber du merkst an „in späteren Teilaufgaben werde ich ss wieder verwenden um mir Schreibarbeit zu sparen, aber ersetze bitte Gedanklich die rechte Seite des := ein“. Das ist auch nichts anderes als eine Makrodefinition im Präprozessor von C. (Denn z.B. #define ist kein Schlüsselwort der Programmiersprache C)
Deshalb ist auch deine erste Definition von ss korrekt, und deine alternative Definition leicht Problematisch. An sich ist
ss(X, Y ) := X ∈ p(Y )
vollkommen korrekt für die Teilaufgabe 1. Wenn du jedoch dann in Teilaufgabe 3 schreibst
∀x, y.(x ∈ p(y) ⇔ ss(x, y))
dann bedeutet das, dass du die Formel
∀x, y.(x ∈ p(y) ⇔ x ∈ p(y))
meinst. Aber diese Formel ist natürlich in jedem Model („jeder erdenklichen Situation“) wahr, und formalisiert nicht die Aussage nach der in Teil 3 gefragt wird.
Teil 1 bis 4 sieht richtig aus, nur bei der 4 ist ein Tippfehler: es fehlt eine Negation vor ∃. (in der Klausur empfiehlt es sich übrigens die Buchstaben mehr abzuwechseln, da X und x handschriftlich nur schwer zu unterscheiden sind).
Teil 5 passt noch nicht, aber ich denke das ist auch nicht so schlimm, weil Teil 5 die einser Frage ist, evtl. sogar schwieriger. (Hätte ich evtl. auch mal früher sagen sollen…). Bei dir ist u(x) eine formel, dein Makro ss erwartet jedoch einen Term, oder mit anderen Worten: wenn du u und ss einsetzt, dann stünde da an einer Stelle …((x ∈ ∃z.…, und das erlaubt die Grammatik aus Definition 35 nicht, da Prädikate Terme als Parameter bekommen und ∃x.… eine Formel ist.
Ich glaub ich verstehe aber was du meinst. Du versuchtest das u(x) die Menge bezeichnet, die aus nur einem Element, nämlich x, besteht. Und wenn das gehen würde wäre die eigentliche Formel von dir auch richtig so weit ich das sehe :-). Deshalb würde ich an deiner Stelle wenn dann noch andere Sachen (Übungsblätter, Braindumps,…) formalisieren, statt die 5.
1 „Gefällt mir“
Ein Vorschlag zur 5:
Idee auf Metaebene: (A = \bigcup B_i) ⇔ Jedes Element in A findet sich in einem B_i wieder und jedes Element jeder B_i-Menge findet sich in A wieder. Also beide Teilmengen-Richtungen.
In Prädikatenlogik: siehe Anhang.
Zur Notation nochmal: Im Skript wird klar zwischen ⇔ (Metaebene) und ↔ (Aussagen-/Prädikatenlogik) unterschieden, deswegen würde ich ⇔ nicht in Formeln verwenden.
Attachment:
Phi_5.png: https://fsi.cs.fau.de/unb-attachments/post_150714/Phi_5.png
2 „Gefällt mir“