Folgerungen < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | 1)
Ist die folgende Behauptung richtig oder falsch?
Für drei Formeln Ψ,φ und η, mit Ψ |= η (das |= ist dieses umgekippte pi, was glaube ich folgerung bedeutet) und Ψ ist eine Teilformel von φ, gilt:
φ |= φ´, wobei φ´aus φ entsteht, indem ein Vorkommen von Ψ durch η ersetzt wird.
Begründen Sie ihre Antwort (Beweis oder Gegenbeispiel).
2)
Gegeben ist die Formelmenge F={ [mm] \neg [/mm] (a [mm] \wedge \neg [/mm] b), [mm] \neg [/mm] b [mm] \vee [/mm] c}.
a) Ist die Formel [mm] \neg [/mm] a aus F folgerbar? Begr.
b) Ist die Formel [mm] \neg [/mm] a [mm] \vee [/mm] c aus F folgerbar? begr.
c) Geben Sie eine Formel φ an, so dass b aus der Formelmenge F [mm] \cup {\emptyset} [/mm] erfolgert werden kann. Begr.
d) Geben Sie ine Formel Ψ an, so dass die Formelmenge F [mm] \cup [/mm] {Ψ} kein Modell hat! Begr. |
Hallo liebe Leute.
Also ich muss sagen, meine dozentin ist unfähig, fragen werden ignoriert und erklärt wird gleich mal gar nix. jetzt haben wir aber in den übungsaufgaben diese lustigen aufgaben bekommen. Mein Problem ist nur, dass ich keine ahnung habe, was dieses umgekippte pi bedeutet (gut, "Folgerung", aber das sagt mir auch nix)...
Kann mir das jemand bitte in Bezug auf die obigen Aufgaben erklären?
|
|
| |
|
Hallo,
anscheinend beschäftigt sich die Vorlesung mit Grundlagen der Logik und Modelltheorie.
Wenn dir die Vorlesung nichts bringt, empfehle ich dir, ein Buch über Logik oder Modelltheorie zu lesen. Jede Unibibliothek sollte sowas haben, du findest sicher auch Skripte im Netz. Vielleicht habt ihr auch Übungen, in denen Fragen zur Vorlesung gestellt werden können?
Dieses [mm] "$\Phi \models \eta$" [/mm] heißt wörtlich "aus [mm] $\Phi$ [/mm] folgt [mm] $\eta$", [/mm] und bedeutet, dass jedes Modell von [mm] $\Phi$ [/mm] auch ein Modell von [mm] $\eta$ [/mm] ist. Das heißt, immer dann, wenn [mm] $\Phi$ [/mm] erfüllt ist, ist auch [mm] $\eta$ [/mm] erfüllt. Das ist erstmal etwas anderes als die Aussage [mm] "$\Phi \vdash \eta$", [/mm] "aus [mm] $\Phi$ [/mm] ist [mm] $\eta$ [/mm] herleitbar", denn dies ist eine Aussage über Beweisbarkeit in einem zugrundeliegenden logischen Kalkül. Diese beiden Beziehungen stimmen aber meistens überein.
Du hast drei Formeln [mm] $\Psi, \varphi, \eta$ [/mm] mit [mm] $\Psi \models \eta$ [/mm] und [mm] $\Phi$ [/mm] Teilformel von [mm] $\varphi$.
[/mm]
Es gibt durchaus Beispiele, wo das Ersetzen von [mm] $\Phi$ [/mm] durch [mm] $\eta$ [/mm] zu einer Formel [mm] $\varphi'$ [/mm] führt mit [mm] $\varphi \models \varphi'$, [/mm] aber das ist nicht notwendig, d.h. es gibt ebenfalls Beispiele, wo [mm] $\varphi \not\models \varphi'$.
[/mm]
Bei der zweiten Aufgabe hast du dich bei c) bestimmt verschrieben, wenn $F [mm] \cup \{\varphi\}$ [/mm] gemeint ist, dann kannst du [mm] $\varphi [/mm] = b$ wählen. Bei d) gibt einfach eine Formel an, die bereits selbst kein Modell hat.
Gruß,
SirJective
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:10 Sa 28.10.2006 | | Autor: | sorry_lb |
Naja, die Übung nimmt sich nicht viel von der Vorlesung, da wir hier nur die Aufgaben besprechen, die bereits abgegeben werden mussten.Gut, im nachhinein versteh ich das dann auch, allerdings bringt mir das keine punkte und auf meine frage, ob es vielleicht möglich wäre, beispiele vorzurechnen (was ich auch in bezug auf die mathematische form als sinnvoll erachten würde), erhielt ich nur ein klares "nein". so weit so gut, also haben meine kommelitonen uns damit abgefunden die aufgaben zu machen und danach zu erfahren, wie man sie rechnet und in welcher mathematischen form sie aufzustellten sind. werd aber gleich montag zur bibliothek gehen, vielleicht bringt mir das wirklich mehr als die vorlesung.
nun nochmal zur aufgabe: also entspricht |= einfach dem Implikationpfeil [mm] \Rightarrow [/mm] ?
|
|
|
| |
|
Das Folgerungssymbol [mm] $\models$ [/mm] und das Herleitungssymbol [mm] $\vdash$ [/mm] entsprechen beide in etwa dem, was du in der Schule und in mathematischen Beweisen durch den Implikationspfeil [mm] $\Rightarrow$ [/mm] ausdrückst: Dass man irgendwie logisch richtig von der einen Formel zur nächsten kommt.
Man darf es nur nicht mit der objektsprachlichen Implikation [mm] $\rightarrow$ [/mm] verwechseln:
[mm] "$\Phi \models \eta$" [/mm] ist eine Aussage über zwei Formeln (also eine Aussage der Metasprache), während
[mm] "$\Phi \rightarrow \eta$" [/mm] eine Formel ist (also eine Aussage der Objektsprache).
Gruß,
SirJective
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:53 So 29.10.2006 | | Autor: | sorry_lb |
nun gut, was der spass jetzt bedeutet weiß ich so ungefähr, aber ich weiß immer noch nicht, wie ich das jetzt beweise bzw wie ich begründe, dass bei 2a) [mm] \neg [/mm] a nicht folgerbar ist?!
Bei 2a) hab ich mir jetzt überlegt, dass wenn ich w2(a)=1 und w2(b)=1 setze, der Wahreitswert von F 1 ist und von [mm] \neg [/mm] a gleich 0, also ist [mm] \neg [/mm] a nicht aus F folgerbar oder hab ich´s immer noch nich?
|
|
|
| |
|
Das hast du gut erkannt.
Wenn du a, b und c mit 1 belegst, ist F erfüllt, aber [mm] $\neg [/mm] a$ ist nicht erfüllt. Damit gilt $F [mm] \not\models \neg [/mm] a$.
Wenn du die nötigen theoretischen Mittel hast, kannst du 2b) so angehen:
Genau dann, wenn aus F folgt [mm] $\neg [/mm] a [mm] \vee [/mm] b$, ist die Formel
[mm] $\neg [/mm] ( [mm] (\neg (a\wedge \neg [/mm] b)) [mm] \wedge (\neg [/mm] b [mm] \vee [/mm] c)) [mm] \vee (\neg [/mm] a [mm] \vee [/mm] b)$
allgemeingültig.
Diese Formel kannst du nun mit logischen Schlussregeln umformen (vor allem de Morgans Gesetz), um ihre Allgemeingültigkeit zu zeigen. Das benutzt aber die Äquivalenz von Folgerung mit Herleitbarkeit.
Alternativ kannst du auch die Wertetabellen ausrechnen - damit hättest du direkt die Folgerung bewiesen.
Gruß,
SirJective
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:20 Di 31.10.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
