fb18.de
/ Bachelorstudieng
/ PM Formale Informatik
FGI-1 Klausur am 12.10.2007
Ich mache schon mal eine Thread auf, wo man bezüglich dieser Klausur posten kann.
Glaubt ihr, dass Prof Habel aus dem Schlamassel der letzten Klausur welche Schlüsse gezogen kann, und diesmal eine humane Klausur erstellt???
Denke ich auch nicht. Bzw. lerne ich mich lieber dumm und dämlich und lasse mich dann ggf. positiv überraschen, alsdass ich mir jetzt unterbewusst den Stress nehme und an die spontane Wohlgesinnung des Habels glaube.
Die Message an die Studentennation ist also eindeutig….Don't trust the enemy!!!
Bei der letzten Klausur gab es eine Frage zu den verschiedenen Bedeutungen von dem Zeichen "I=" , die genannt und erklärt werden sollten.Steht es irgendwo im Skript? Oder kann das jemand hier posten.
Ich unterstelle ihm doch keine Feindschaft. Sehe es auch nicht als solche. Aber leider ist in mancher Professoren Köpfe noch die Vorstellung vom Studenten, der eine 80Std.-Woche schuftet und dessen Lernziel es ist, das Skript streng auswendig zu lernen bzw. eine Aufgabe im Bruchteil einer Sekunde lösen zu können. Mein Vater ist auch von diesem Schlag. "Ihr habt doch nix And'res am Kopp als studier'n, also mach dat auch ordentlich!" [25] Ich kann mir auch gut vorstellen, dass man einfach nicht mehr den Blick für den Schwierigkeitsgrad hat, wenn man Jahr für Jahr den gleichen Senf runtersabbeln muss… [7]
Ich kann mir auch gut vorstellen, dass man einfach nicht mehr den Blick für den Schwierigkeitsgrad hat, wenn man Jahr für Jahr den gleichen Senf runtersabbeln muss…
Ich glaube, da hast du ins schwarze getroffen.
Bei der letzten Klausur gab es eine Frage zu den verschiedenen Bedeutungen von dem Zeichen "I=" , die genannt und erklärt werden sollten.Steht es irgendwo im Skript? Oder kann das jemand hier posten.
Skript: Kap 5 Aussagenlogik - Folgerung[ 5 ]
Dort ist ne Tabelle mit allen möglichen Verwendungen.
Kann sich jemand noch an die 2. Aufgabe der letzten Klausur erinnern, da ging es um: erfüllbar(anders gesagt gültig), unerfüllbar, kontingent.Das ganze war in Form einer Tabelle aufgebaut, wo man an entsprechenden Stellen Kreuzchen setzen musste.
Die Aussage dazu war:
Was kann F sein, wenn folgendes gilt: <Eigenschaften von G oder G => F oder was auch immer>
Ich habe an dieser Aufgabe ziemlich viel Zeit vergeudet, weil ich viele Schritte zu Fuß(mit Wahrheitstabellen) gemacht habe.Diese Aufgabe bezieht sich(genau wie die erste) auf Kapitel 5.Hat jemand eine Idee/einen Kniff , wie man das elegant und effizient bewerkstelligen kann????Ich kann mir nämlich sehr gut vorstellen, dass so eine Aufgabe noch mal drankommen kann.
Ich denke es ist einfacher die Aufgabe zu lösen, wenn man im Kopf hat, was für kombinationen was ergeben. z. B. wenn man weiß, dass Top => F immer eine Tautologie ist
(stimmt nicht, nicht falsch merken!) oder ähnliches.
Und ich glaube dafür ist es sinnvoll sich folgende Aufgabe nochmal anzugucken
Aufgabenblatt 3 Präsenzaufgabe 3 (
http://www.fb18.de/mybb/showthread.php?tid=8707)
Andere Tipps kann ich leider nicht geben. Mir ist dies Aufabe total leicht gefallen. Vielleicht hängt das auch einfach davon ab, ob einem Logik liegt oder nicht.
[edit]
sehr sinnvoll ist es natürlich, wenn man die Umformungsregeln beherrscht. Die sind eigentlich Grundlage für die ganze Aufgabe
[/edit]
z. B. wenn man weiß, dass Top => F immer eine Tautologie ist
Kann man das wirklich wissen?
Was ist zum Henker "Top"????
Ich kann mir auch gut vorstellen, dass man einfach nicht mehr den Blick für den Schwierigkeitsgrad hat, wenn man Jahr für Jahr den gleichen Senf runtersabbeln muss…
Ich glaube, da hast du ins schwarze getroffen.
Gerade Prof Habel ist doch für ein gewisses elitäres Denken bekannt. Der stellt seine Klausuren mit voller Absicht so, wie er sie stellt. Dies hat er doch auch schon mehrfach in Gesprächen mit Studenten angedeutet (ich war einer dieser Studenten, dem er das an den Kopf geschmettert hat).
Das ändert nicht die Tatsache, dass man die Klausur bestehen muss."Elitär" hört sich gut an.Stell dir vor, ab dem nächsten Semester würden alle Profs ihre Klausuren elitär konzipieren….Wenn man elitäre Aufgaben stellt, dann muss man auch elitäre Vorlesungen und Übungen anbieten, und AUCH den Ruf des Studiengangs in der Außenwelt elitär gestalten.
z. B. wenn man weiß, dass Top => F immer eine Tautologie ist
Kann man das wirklich wissen?
Oh nein, kann man nicht… ich meinte Bottom => F.
Wenn man Tipps gibt sollte man das richtig machen. Naja, mir ist es auch alles nicht mehr 100% klar.
Top und Bottom sind die Zeichen für Tautologie und Kontradiktion. Das T und das umgedrehte T.
Noch zurück zu der Aufgabe: In der 3. Aufgabe war vorgegeben, dass F und G kontingent sind.In der Klausuraufgabe hieß es: G oder G=>F .Waren hier F und G einfach beliebige aussagenlogische Formeln und waren sie näher spezifiziert, z.B. mit Kontingenz????
Top=>F ist eine Tautologie, weil ich auf der linken Seite nur 1 haben kann (wegen Tautologie), und aus 1 kann ausschließlich 1 folgen
Bottom=>F ist eine Kontingenz, weil ich links immer 0 habe, und aus 0 kann entweder 0 oder 1 folgen.
Top=>F ist eine Tautologie, weil ich auf der linken Seite nur 1 haben kann (wegen Tautologie), und aus 1 kann ausschließlich 1 folgen
Nein, das ist äquivalent zu F, also: für tautologisches F ist das eine
Tautologie, für kontradiktorisches F ist es eine Kontradiktion und
für kontingentes F ist es kontingent.
Bottom=>F ist eine Kontingenz, weil ich links immer 0 habe, und aus 0 kann entweder 0 oder 1 folgen.
Nein, das ist für alle F eine Tautologie.
Nochmal zur Erinnerung die Definition der Implikation:
A impliziert B, wenn jedes Modell für A auch ein Modell für B ist
Nun betrachte ich
Top => F und Bottom => F
Top => F
Top ist eine Tautologie. Das bedeutet jede beliebige Belegung A ist ein Modell für Top.
Das würde bedeuten, wenn Top => F eine Tautologie wäre müsste jede beliebige Belegung A ein Modell für F sein (was nicht der Fall ist, da F nicht explizit eine Tautologie ist).
Bottom => F
Bottom ist eine Kontradiktion. Das bedeutet, dass es keine Belegung A gibt, das ein Modell für Bottom ist. Da es also kein Modell für Bottom gibt ist jedes Modell für Bottom auch ein Modell für F. Deshalb ist Bottom => F eine Tautologie.
Tut mir leid, wenn ich mit meinem Fehler von vorhin für Verwirrung gesorgt habe.
Ja,klar: Man muss nur das Implikationszeichen auflösen, dann sieht man's deutlich:
Top=>F heißt: -Top oder F heißt: K oder F also F
Bottom=>F heißt: -Bottom oder F heißt: T oder F also Tautologie
Wie verhält sich das ganze bei:
Top |= F
Bottom |= F
???????
Man kann keine Wahrheitswertanalyse für "|=" machen. |= ist kein Junktor, sondern eine Beziehung zwischen Formeln.
Es gilt
Bottom |=
und
|= Top
weil man aus Bottom alles Folgern kann und man aus jeder beliebigen Formel Top folgern kann.
Satz 5.8 |= ist kein Junktor, dennoch eng mit der Implikation verwandt:
a)F=>G ist allgemeingültig , gdw G aus F folgt
b)|= F=>G gdw
c)F |= G
was sagst du zu a und c?
wie? was soll ich denn dazu sagen? ja, das stimmt… aber ich versteh deine Frage/dein Problem nicht.
Außerdem behandeln die Sätze 5.2 bis 5.8 die Folgerbarkeit in allen möglich Konstellationen:
Somit kann man für die Folgerbarkeit die gleichen Fragen stellen wie für die Implikation, oder?
Meine Frage war einfach:
Wie verhält sich das ganze bei:
Top |= F
Bottom |= F
????
Und du meinst, wenn ich das richtig verstehe, dass das nicht geht.
Ich habe bei => die Implikationszeichen aufgelöst und die Lösungen klar und deutlich gezeigt.
Kann ich denn das gleiche bei Folgerbarkeiten anwenden???
Wir haben in der Klausur: G oder G=>F auf erfüllb, unerfüllb., usw zu untersuchen bekommen.Nun bekommst du in der Klasur:
G oder G|=F und wat nu?????
Verstehst du meine Frage nicht oder weißt du die antwort nicht???
Top |= F gilt nur, wenn F eine Tautologie ist
Bottom |= F gilt immer
Wir haben in der Klausur: G oder G=>F auf erfüllb, unerfüllb., usw zu untersuchen bekommen.Nun bekommst du in der Klasur: G oder G|=F und wat nu?????
Das wird nicht passieren. Mann kann nämlich nicht sagen G |= F ist erfüllbar/unerfüllbar. Man kann nur sagen, ob es gilt oder nicht. G |= F könnte höchstens eine Bedingung sein, unter der man eine bestimmte Formel betrachtet oder sowas. z. B. G ist eine Tautologie, es gilt G |= F, was ist mit F.
Nun bekommst du in der Klasur:
G oder G|=F und wat nu?????
Dann hast Du keine Formel, kannst also nichts auf Erfuellbarkeit etc. untersuchen.
Hm….
Alle Belegungen, die Modell von Top sind-das sind offensichlich allle belegungen- sind Modell von F.
Alle Belegungen, die Modell von Bottom sind -das sind offensichlich gar keine Belegungen, sind Modell von F.
Deine erste Anwort mit gilt nur…….. ist falsch formuliert.Da geht es nicht um Bedingungen sondern um Aussagen.Du schreibst aber, gilt nur, wenn………..
Wenn F aus einer Tautolgie folgt, dann ist F eine Tautologie.Punkt. Satz 5.3
Zu: Bottom |= F
Satz 5.5 Aus jeder unerfüllbaren Formelmenge(oder einer einfachen Formel) ist jede beliebige Formel F folgerbar.
Das heißt: F kann erfüllbar, unerfüllbar oder kontingent sein.
Ich habe erst jetzt deine Nachtrag gelesen, wo ich das mit den Bedingungen gelesen habe.
Also bei Implikationen können wir alle möglichen Vermutungen über Erfüllb., Unerfüllbar., usw aufstellen bei
Folgerbarkeiten nur Bedingungen, unter denen etwas folgerbar ist, richtig?
Top |= F
Bottom |= F
Man kann das so oder so sehen. Entweder diese Beiden Beziehungen stehen fest und unter diesen Bedingungen soll man eine Formel untersuchen oder diese beiden Beziehungen sind zu untersuchen, unter welchen Bedingungen sie gültig sind. Das kommt dann aber auf die Aufgabenstellung drauf an.
Also bei Implikationen können wir alle möglichen Vermutungen über Erfüllb., Unerfüllbar., usw aufstellen bei Folgerbarkeiten nur Bedingungen, unter denen etwas folgerbar ist, richtig?
Ja, das ist richtig.
Ich kann mich erinnern, dass die aufgabe zur Unifikation 3 Prädikate enthielt und das hat mich aus dem Konzept gebracht. In der Vorlesung 2, in der Übung 2 und in der Klausur natürlich 3 -hat man ja eine Menge Zeit um neues ungeübtes auszuprobieren.Ich frage mich, ob Feuerwehrleute auch dann extra üben, wenn es gerade ein ernster Fall ist.
Kann mir jemand den ansatz für die Unifikation von 3 Prädikaten sagen???
Unifikation von 3 Prädikaten funktioniert genauso, wie Unifikation von 2 Prädikaten. Was genau ist denn dein Problem?
Man hangelt sich auch von term zu term und wenn man dann z. B.
t1 = x
t2 = g(y)
t3 = g(h(t))
x, y: Variablen; t: Konstante
hat, dann nimmt man als Subsitution einfach [x / g(y)][y / h(t)] oder [x / g(h(t))][y / h(t)]
Kannst du mir welche Beispiele von aufgaben geben, wo man 3 Prädikate unifizieren soll.Ich finde im Skript kein einziges Beispiel.Ich will es selber in aller Ruhe durchrechnen.
Ich habe selber ein Beispiel ausgedacht:
K={P(f(x,b),a,z),P(z,x,f(y)),P(x,f(z),f(x))}
Ist der 1. Unifikationsschritt etwa: sigma1=[z/f(x,b)] oder etwa sigma1=[z/x] oder etwa sigma1=[x/z] oder etwa sigma1=[x/f(x,b)]
????????????
@doodles
Keine Ahnung, wie das gehen soll?????
In deinem Beispiel ist keine Unifikation moeglich, weil x ein Teilterm von f(x,b) ist.
Dann modifiziere ich eben:
K={P(f(x,b),a,z),P(z,x,f(y)),P(x,f(z),f(b))}
Unifikation von 3 Prädikaten funktioniert genauso, wie Unifikation von 2 Prädikaten. Was genau ist denn dein Problem?
Warum bist du nun so ruhig, Doodles???
Ich meinte natürlich:
K={P(f(x,b),a,z),P(z,x,f(y)),P(x,f(z),f©)}
Wie wollt ihr denn die Klausur bestehen, wenn keiner mir eine der einfachsten Aufgaben in der Klausur überhaupt erklären kann?????
Ich kann Unifikationen mit 2 Prädikaten im Schlaf durchführen, mit 3 kann ich nichts anfangen.
Ich meinte natürlich:
K={P(f(x,b),a,z),P(z,x,f(y)),P(x,f(z),f©)}
Wiese geht das denn, dass f einmal zweistellig
und andererseits auch einstellige Funktion ist??
Das sollte ebenfalls so nicht sein.
Du hast recht, dann ein weiterer Versuch:
K={P(f(x,b),a,z),P(z,x,f(y)),P(x,f(z),g(d)}
hmm… irgendwie konnte ich die ganze Zeit nicht antworten… "Bad Request"..
Dein Beispiel ist immernoch nicht unifizierbar, da x immernoch echter Teilterm von f(x, b) ist.
Aber allgemein würde ich sagen, dass es egal ist, welche Substution man als erstes macht.
Bei meinem Beispiel:
t1 = x
t2 = g(y)
t3 = g(h(t))
x, y: Variablen; t: Konstante
hat, dann nimmt man als Subsitution einfach [x / g(y)][y / h(t)] oder [x / g(h(t))][y / h(t)]
[x / g(y)][y / h(t)] hat genau den gleichen Effekt, wie [x / g(h(t))][y / h(t)]
Insofern müsste das egal sein.
Allerdings bin ich mir nicht komplett sicher.
Ich möchte es trotzdem am Beispiel sehen.Du hast dir was einfaches ausgedacht, was dir gerade ins Konzept passt.Ich habe selbst mit google keine Beispiele finden können.Vielleicht sollten wir von Habel ein paar Beispiele abkaufen.Er denkt ja elitär, da wird er bestimmt welche Beispiele auf Lager haben.
K={P(f(x,b),a,z),P(z,x,g(y)),P(y,g(z),g(d)}
1. [z/f(x,b)][y/f(x,b)]
K={P(f(x,b),a,f(x,b)), P(f(x,b), x, g(f(x,b))), P(f(x,b), g(f(x,b)), g(d))}
2. x ist echter Teilterm von g(f(x,b))
3. nicht unifizierbar
und wenn ichs irgendwie andersrum versuche:
K={P(f(x,b),a,z),P(z,x,g(y)),P(y,g(z),g(d)}
1. [z/y][y/f(x,b)]
K={P(f(x,b),a,f(x,b)),P((f(x,b),x,g(f(x,b))),P(f(x,b),g(f(x,b)),g(d)}
2. x ist echter Teilterm von g(f(x,b))
3. nicht unifizierbar
kommt aufs selbe hinaus, aber so geht das im Prinzip.
Wie ist das eigentlich mit den Inferenzregeln, würden die vorgegeben werden, falls man die benötigt, oder lernt ihr die alle auswendig?!
Erstens: Unifikation für 3 Prädikate soll angeblich genauso gehen wie für 2. Wieso machst du denn in einem Unifikationsschritt 2 Substitutionen??????
Zweitens: Zitat: und wenn ichs irgendwie andersrum versuche:
[z/y][y/f(x,b)] ist das nicht das gleiche wie: [z/f(x,b)][y/f(x,b)]. Das wiederum würde bedeuten, dass du 2 Variablen (in einem Schritt) durch den gleichen Term substituierst.
war ein netter Versuch, aber ich bin nicht davon überzeugt.
Inferenzregeln: Ich lerne sie auswendig.Ich könnte mir sehr schwer vorstellen, dass du sie angegeben bekommst.
Eine andere Frage: Das war auch eine Klausuraufgabe, und zwar die dritte: Zeigen Sie mittels Resolution, dass M|=G NICHT gilt. Erklären Sie, wie man dafür überhaupt Resoltion anwenden kann.
Für mein Verständnis der dinge kann man zeigen, dass eine Formel GILT, indem man die ursprüngliche Formel negiert und mittels Resolution zum Widerspruch führt.Habe ich den Widerspruch der negierten Formel hergeleitet, habe ich gezeigt, dass die ursprügliche Formel gültig ist.
Wie soll man jetzt mittels Resolution zeigen, dass eine Formel NICHT gilt??????????????????
Vielleicht ohne Negation?
Erstens: Unifikation für 3 Prädikate soll angeblich genauso gehen wie für 2. Wieso machst du denn in einem Unifikationsschritt 2 Substitutionen??????
Weil man anders wohl kaum 3 Prädikate unifizieren kann.
Zweitens: Zitat: und wenn ichs irgendwie andersrum versuche:
[z/y][y/f(x,b)] ist das nicht das gleiche wie: [z/f(x,b)][y/f(x,b)].
Doch, das ist das gleiche. Rechne es nach, wenn Du es nicht glaubst.
Das wiederum würde bedeuten, dass du 2 Variablen (in einem Schritt) durch den gleichen Term substituierst.
Ja, und?
Erstens: Unifikation für 3 Prädikate soll angeblich genauso gehen wie für 2. Wieso machst du denn in einem Unifikationsschritt 2 Substitutionen??????
Zweitens: Zitat: und wenn ichs irgendwie andersrum versuche:
[z/y][y/f(x,b)] ist das nicht das gleiche wie: [z/f(x,b)][y/f(x,b)]. Das wiederum würde bedeuten, dass du 2 Variablen (in einem Schritt) durch den gleichen Term substituierst.
war ein netter Versuch, aber ich bin nicht davon überzeugt.
Inferenzregeln: Ich lerne sie auswendig.Ich könnte mir sehr schwer vorstellen, dass du sie angegeben bekommst.
zu erstens:
dann mach eben nur eine Substitution pro Schritt, es kommt auf gleiche hinaus.
zu zweitens:
dann teil es eben wieder in zwei Schritte(wie schon bei 1.)
Ich versteh dein Problem nicht, natürlich ist es das gleiche.
wenn man a = 12 setzt und b = 12
dann ist das doch das gleiche wie
a = b; b = 12;
oder etwa nicht?
zu M |= G.
gehe davon aus, dass es gilt, dann resolvieren um zu zeigen, dass die leere Menge keine Resolvente ist.
Gabs doch mal als Übungsaufgabe, dort wurde dann mit der p-Resolution gearbteitet, damit nicht zuviele Resolventen gebildet werden müssen.
hm, muss mich mal anmelden, kann den Posts garnicht mehr editieren :(
also mit a = b; b = 12 war eigentlich gemeint: a = b = 12 ;)
zu M|=G
Kannst du vlt. noch sagen, welche aufgabe das gewesen sein soll.
eine Frage zu BPF und Skolemisieren: Skript: PL_Resolution.pdf ,Seite 7
1)Im 3. Schritt findet eine Umbenennung statt: Warum wird da nur das eine X (rechts) umbenannt.Das X in der Mitte ist ursprünglich doch das gleiche X.
2)Bei der Skolemisierung wird ein Existenzquantor durch eine Konstante[x/a] ersetzt, der andere Existenq. jedoch durch eine Funktion [w/f(z)]. Woher der Unterschied???
1)Im 3. Schritt findet eine Umbenennung statt: Warum wird da nur das eine X (rechts) umbenannt.Das X in der Mitte ist ursprünglich doch das gleiche X.
Wo das X herkommt ist total egal. Interessant ist nur durch welchen Quantor das x gebunden ist, bevor es umbenannt wird.
2)Bei der Skolemisierung wird ein Existenzquantor durch eine Konstante[x/a] ersetzt, der andere Existenq. jedoch durch eine Funktion [w/f(z)]. Woher der Unterschied???
Für jeden Allquantor vor dem Existenzquantor, der gerade entfernt bekommt die Skolemfunktion ein Argument mehr.
Also z. B. bei (A=Allquantor, E=Existensquantor)
AxAyEw wird w durch f(x, y) ersetzt
bei
AxEwAy wird w durch f(x) ersetzt
bei
EwAxAy wird w durch e ersetzt
und so weiter…
Das ist im Skript nicht gerade so super erklärt. Guck dir am besten mal
http://de.wikipedia.org/wiki/Skolemisierung an
Hier sind doch bestimmt Einige, die bereits ein bis dreimal :) die Klausur mitgeschrieben haben, mich würde interessieren, ob die Prädikatenlogische Formel, die zur Resolution vorbereitet werden soll, sehr lang war bisher. Denn diese ganze Umformung bis zur Skolemisierung kann ja bei längeren Formeln schonmal eine halbe Ewigkeit dauern und je länger desto mehr häufen sich Vorzeichenfehler und desto unübersichtlicher wird das ganze.
@doodles
sehr interessant, da habe ich was neues erfahren.Auf der Wikipedia-Seite ist es tatsächlich einfach erklärt.Da habe ich aber trotzdem eine Frage:
Wenn ich bei dem Schritt Skopuserweiterung bin, dann können dabei verschiedene Konstellationen von Existenz- und Allquantoren entstehen.Am Beispiel von Seite 7:
EyAz[(/P(z,y)oderAx(/p(z,x)oder/P(x,z))) und (P(z,y) oder Ew(P(z,w) und P(w,z)))]
Skopuserweiterung:
EyAzEwAx[……..]
Warum nicht:
EyAzAxEw
oder
EwAxEyAz
???
Wo das X herkommt ist total egal. Interessant ist nur durch welchen Quantor das x gebunden ist, bevor es umbenannt wird.
Du meinst, die Umbenennung findet nur bei Existenquantoren statt???
Hier sind doch bestimmt Einige, die bereits ein bis dreimal :) die Klausur mitgeschrieben haben, mich würde interessieren, ob die Prädikatenlogische Formel, die zur Resolution vorbereitet werden soll, sehr lang war bisher. Denn diese ganze Umformung bis zur Skolemisierung kann ja bei längeren Formeln schonmal eine halbe Ewigkeit dauern und je länger desto mehr häufen sich Vorzeichenfehler und desto unübersichtlicher wird das ganze.
Eine Ewigkeit nicht, ca. 6-10 Zeilen.Fehler passieren dabei sehr wohl.Deswegen sollte man einen Schritt pro Zeile machen, damit man schnell den fehler orten kann und am besten erst gar keine begeht.
@doodles
sehr interessant, da habe ich was neues erfahren.Auf der Wikipedia-Seite ist es tatsächlich einfach erklärt.Da habe ich aber trotzdem eine Frage:
Wenn ich bei dem Schritt Skopuserweiterung bin, dann können dabei verschiedene Konstellationen von Existenz- und Allquantoren entstehen.Am Beispiel von Seite 7:
EyAz[(/P(z,y)oderAx(/p(z,x)oder/P(x,z))) und (P(z,y) oder Ew(P(z,w) und P(w,z)))]
Skopuserweiterung:
EyAzEwAx[……..]
Warum nicht:
EyAzAxEw
oder
EwAxEyAz
???
Gute Frage. Kann ich dir leider nicht beantworten
Wo das X herkommt ist total egal. Interessant ist nur durch welchen Quantor das x gebunden ist, bevor es umbenannt wird.
Du meinst, die Umbenennung findet nur bei Existenquantoren statt???
Nein, so ist das nicht. Ich meine damit, dass, wenn eine Variable, die ursprünglich mal durch einen Quantor gebunden war und durch umformungen (welcher Art auch immer) nun durch zwei Quantoren gebunden ist (an zwei verschiedenen Stellen), bei der Umbenennung nur ein Quantor (Existens- oder Allquantor) betrachtet wird und dass alle Variablen, die genau von diesem Quantor gebunden werden umbenannt werden.
Nein, so ist das nicht. Ich meine damit, dass, wenn eine Variable, die ursprünglich mal durch einen Quantor gebunden war und durch umformungen (welcher Art auch immer) nun durch zwei Quantoren gebunden ist (an zwei verschiedenen Stellen), bei der Umbenennung nur ein Quantor (Existens- oder Allquantor) betrachtet wird und dass alle Variablen, die genau von diesem Quantor gebunden werden umbenannt werden.
Verstehe.Das heißt, sie hätten genauso den Allquantor Ax umbenennen können, statt dem Existenz. Ex. Das Wichtigste, es gibt keine Doppeldeutigkeiten wegen 2 mal X
Und zu Skopuserweiterung:
Ich kann mich erinnern, der Tutor meinte, mehrere Möglichkeiten wären ok, wobei nicht alle.
Man kann sich als Faustregel merken:
Die schon da stehenden Quantoren so belassen und die am weitesten rechts stehenden zuerst einreihen.
wie sieht es aus mit dem Unterschied von den beiden Symbolen:
|=
|-
beide sind ja irgendwie folgerbarkeitsrelationen, ich kann den unterschied nur noch nicht so richtig erkennen.
Woher hast du das "Folgerbarkeitszeichen" mit einem Querstrich?????
Ist es wahrscheinlich, dass wir in der Klausur den alten guten Hilbert bemühen müssen.Der Prof kann natürlich nicht voraussetzen, dass wir alle 8 Regeln des Hilbert-Kalküls drauf haben.Ich habe mir gerade aufgabenblatt 6 angeschaut und dieses ist so ziemlich dem Hilbert gewidmet.
..und wenn, dann stehen die Regel im Anhang. Wichtig ist nur, dass du weißt wie man die Regel anwendet. Ich würde hingegen aber alle Inferenzregel auswendig lernen und Chomsky-Normal-Formen! (Wie letztes Jahr kam es dran, nach nur einer Vorlesung)
|= (Folgerbarkeit)
|- (Ableitbarkeit (mit einem Kalkül oder so))
wenn |- gilt und das benutze Kalkül aus korrekten Inferenzregeln und Axiomen, die Tautologien sind besteht gilt auch |=
Was meinst du mit Chomsky-Normal-Formen lernen???
Meinst du:
Eine formale Grammatik ist in Chomsky-Normalform, wenn jede Produktion eine der folgenden Formen hat:
A => BC
A=>a
S=>epsilon
Die Inferenzregeln habe ich schon drauf:)Man muss sich eine Eselsbrücke bauen, dann geht es.
Und das mit Hilbert und Anhang, glaube ich nur schwer.
Ich beschäftige mich jetzt mit "reductio ad absurdum" , womit die allgemeingültigkeit einer Formel gezeigt werden kann.Es gibt ein Beispiel in aufgabe 4.3 .Die Schritte 7a und 7b sind mir unklar.Im 6. Schritt wurde festgelegt, dass A = 1 und B=0 sein müssen, damit die rechte Hälfte der Formel "1" ergibt.Das bedeutet für die linke Seite der Formel: A=>B (1=>0) =0 und nicht 1 wie am Anfang angenommen.Was passiert eigentlich in Schritt 7a und 7b ??????
Man junge geh`doch endlich pennen es ist mitten in der Nacht…. hast du nichts besseres zu tun?
Ich beschäftige mich jetzt mit "reductio ad absurdum" , womit die allgemeingültigkeit einer Formel gezeigt werden kann.Es gibt ein Beispiel in aufgabe 4.3 .Die Schritte 7a und 7b sind mir unklar.Im 6. Schritt wurde festgelegt, dass A = 1 und B=0 sein müssen, damit die rechte Hälfte der Formel "1" ergibt.Das bedeutet für die linke Seite der Formel: A=>B (1=>0) =0 und nicht 1 wie am Anfang angenommen.Was passiert eigentlich in Schritt 7a und 7b ??????
In Schritt 7a und 7b wird einfach die Tabelle vervollständigt, damit du am Schluss den Widerspruch auch ablesen kannst. Du hast schon richtig "erkannt" dass Â(A=> B) = 0 gilt
wenn Â( A ) = 1 und Â( B ) = 0.
Somit zeigst du ja dass die Annahme nicht erfüllt sein kann und dann
 ( not(( A => B ) and ( not B and ( A and not B ) ) ) = 0 niemals gilt.
also ist not(( A => B ) and ( not B and ( A and not B ) ) eine Tautologie
und ( A => B ) and ( not B and ( A and not B ) eine Kontradiktion.
Insbesondere wird in der Musterlösung der Widerspruch in Zeile 7a durch die Fettgedruckte 1 unterm A verdeutlicht.
Anmerkung Zeile 7a und b hätte man auch anders ausfüllen können, da
Â(A => B) = 1 gilt wenn 1. Â ( A ) = 1 Â ( B ) = 1
2. = 0 = 0
3. = 0 = 1
Strukturelle Induktion wird sicherlich auch drankommen, aber ich habe keine Übungsaufgaben mehr um das zu üben. Im Web habe ich auch keine gefunden :(
hat noch jemand paar Übungen zur strukturellen Induktion?
@Goldl
Du hast vollkommen recht.So wie du 7a 7b 7c gemacht, so hätte ich es auch gemacht. Wie suchen schließlich auch Belegungen, wo a=>b "1" ergibt.Andererseits hätte ich nach der 6. Zeile abgebrochen, weil ein Widerspruch gefunden wurde.Wozu denn die anderen Fallunterscheidungen.Und das, was die gemacht haben, kann man gar nicht verstehen, weil:
7a)A=1 B=0 ergibt 0(steht unterstrichen unter A)
7b) A=1 B=0(also das gleiche) ergibt 1(steht unterstrichen unter B)
Und noch das fettgedruckte: in 7a die 1, in 7b die 0 ?????????
Was soll der Blödsinn????
Andererseits hätte ich nach der 6. Zeile abgebrochen, weil ein Widerspruch gefunden wurde.
Hätte ich auch gemacht und nen Satz dazu.
7a)A=1 B=0 ergibt 0(steht unterstrichen unter A)
7b) A=1 B=0(also das gleiche) ergibt 1(steht unterstrichen unter B)
Das steht da nicht.
Zeile 6: A B not ((A => B ) and ( not B and ( A and not B ) ) )
1 0 0 1 1 1 0 1 1 1 1 0
Diese Zeile ist ja klar.
Zur Zeile 7a: In 6 steht unter den Junktor von A => B eine 1 d.h  ( A => B ) = 1 soll gelten. Damit das gilt "muss" A = 0 sein also trage unter dem A eine 0 ein.
Zeile 7b wenn nun das A = 0 ist dann "muss" das B = 1 sein.
Könnte natürlicha uch so aussehen:
A = 1 B = 1
A = 0 B = 0
Ich denke sie haben die Variante mit dem A = 0 und B = 1 genommen damit es deutlich in der Tabelle erkennbar ist
A B not A => B….
7a 1 0 0 0 1 … // A =1 und A = 0 widerspruch
7b 1 0 0 0 1 1 // B = 0 und B = 1 widerspruch
Aufgabe 3.3 Beweis der Allgemeingültigkeit durch Widerspruch:
Man untersucht, wann die rechte Seite Null sein kann und schließt damit auf die linke Seite der Implikation.Man hat für den einen Fall gezeigt, dass es widersprüchlich ist, und es heißt dann:Genauso zeigt man's für den 2. Fall.Wozu brauche ich überhaupt den 2. Fall zu betrachten.Ist der Widerspruch im 1. Fall nicht ausreichend????
@Goldl
sehr gute Erklärung.Danke!
Wozu brauche ich überhaupt den 2. Fall zu betrachten.Ist der Widerspruch im 1. Fall nicht ausreichend????
Ich bin eh gerade komplett kaputt von FGI, also entschuldigt, wenn ich nun Stuss rede: Wäre es nicht theoretisch noch möglich, dass Fall 2 eine gültige Belegung ergibt? Das Beispiel ist hier sicherlich besonders eindeutig gewählt und mir fällt auch kein anderes ein, aber wenn es zwei Varianten für die Falsifizierung einer Formel gibt und eine davon funktioniert nicht, könnte die andere aber dennoch funktionieren… oder? Ich weiß nicht… [28]
aber wenn es zwei Varianten für die Falsifizierung einer Formel gibt und eine davon funktioniert nicht, könnte die andere aber dennoch funktionieren… oder?
Das ist klar, sonst bräuchte man den 2. Fall definitiv nicht zu untersuchen.
Die Frage ist nur, was es heißt, wenn der 1. Fall widersprüchlich ist und der andere OK????
Ich vermute mal,um die tautologie der ursprünglichen Formel aufzuzeigen, müssen tatsächlich beide Fälle widersprüchlich sein, sonst würde es nur heißen, dass die ursp. Formel kontingent oder Tautologie ist(auf jeden Fall gültig).Das wäre aber kein Beweis der Allgemeingültigkeit.
Die Frage ist nur, was es heißt, wenn der 1. Fall widersprüchlich ist und der andere OK????
Aber wir sprechen doch noch vom reductio ad absurdum-Gedöns, oder? Wenn eine Variante dann widersprüchlich ist und die zweite Variante liefert eine gültige Belegung, hat man die vermeintliche Allgemeingültigkeit der Formel widerlegt, weil es ja tatsächlich eine Belegung gibt, unter der die Formel nicht wahr ist.
Vielleicht reden wir auch aneinander vorbei? [25]
Dieses Verfahren (aus Aufgabe 3.3) hat keinen formalen Namen, aber es verläuft ähnlich wie reductio ad absurdum- nur halt ohne strukturierte Tabelle.Somit müsstest du recht haben.Sie haben vlt. nur erwähnt, dass der 2. fall ähnlich gemacht wird - wenngleich nicht mehr nötig.Vlt. ist das des Rätsels Lösung.
Vlt. ist das des Rätsels Lösung.
Es ist doch eigentlich auch schon wieder super, wie wir uns jetzt über die nichtigsten Sachen den Kopf zerbrechen. Und morgen ist der Schwierigkeitsgrad der Klausur exponentiell gestiegen und ein pillepalle-Allgemeingültigkeitsnachweis interessiert keinen mehr und alles zugemüllt mit Kellerautomaten und bösen Verständnisfragen… quasi ein FGI-Endzeit-Szenario![img]
http://img530.imageshack.us/img530/2668/w00tal3.gif[/img]
Mögest du unrecht haben.Außerdem kann er in der Klausur des ganzen Semesters nicht nur Fragen zu Kellerautomaten stellen, weil es davor 9 Kapitel gegeben hat.Das wäre dreist und aus dem 11. September würde der 12. Oktober:)
joar, vielleicht wird ja bedacht, dass einige den letzten Versuch morgen haben…
Ich glaube, erstaunlich viele schreiben die Klausur zum letzten Mal.
Eine andere Frage: Das war auch eine Klausuraufgabe, und zwar die dritte: Zeigen Sie mittels Resolution, dass M|=G NICHT gilt. Erklären Sie, wie man dafür überhaupt Resoltion anwenden kann.
Für mein Verständnis der dinge kann man zeigen, dass eine Formel GILT, indem man die ursprüngliche Formel negiert und mittels Resolution zum Widerspruch führt.Habe ich den Widerspruch der negierten Formel hergeleitet, habe ich gezeigt, dass die ursprügliche Formel gültig ist.
Wie soll man jetzt mittels Resolution zeigen, dass eine Formel NICHT gilt??????????????????
zu M |= G.
gehe davon aus, dass es gilt, dann resolvieren um zu zeigen, dass die leere Menge keine Resolvente ist.
Gabs doch mal als Übungsaufgabe, dort wurde dann mit der p-Resolution gearbteitet, damit nicht zuviele Resolventen gebildet werden müssen.
Gehe davon aus, dass es gilt, heißt für mich:
1. M und G
2. /M und G
3. /M und /G
Die 3 Fälle resolvieren????Die leere Menge keine Resolvente???
Ich verstehe das nicht.Weiß jemand , wie das geht oder welche Aufgabe damit gemeint war???
Ich nehme mal an M soll eine endliche Menge sein und G eine Formel. Ich bin mir zwar nicht ganz sicher aber man könnte dies vielleicht so lösen:
Zu zeigen M |= G gilt nicht:
{F1,F2,…,Fn} |= G gdw . ((…(F1 and F2 ) and F3) and… )and Fn) |= G
nach Skript Satz 5.13
gdw ((…(F1 and F2 ) and F3) and… )and Fn) and not G unerfüllbar ist
nach Skript Satz 5.9
Zeige nun mit Resolution dass die Formel:
((…(F1 and F2 ) and F3) and… )and Fn) and not G erfüllbar ist, denn dann gilt nicht
M |= G
(Natürlich muss die Formel erst in KNF sein um Resolution anwenden zu können)
nein, es gilt: M und -G |=
falls M |= G gelten würde
und dann M mit -G resolvieren. Bsp.:
A=>B, B |= A
{-A, B}{B} |= A
{-A, B}{B}{-A} Resolvieren!
egal wie du's anstellst, es kommt immer die Resolvente {-A,B} heraus. also erfüllbar, also nicht gültig
hm, da war einer schneller ^^
Ja genau M: = {A => B , B} G : = A
((A => B ) and B ) and not A
<=> (not A or B) and B and not A (ist in KNF)
Resolution {not A ,B} {B} {not A} so wie bei dir dann ….
So wollte ich das spontan lösen.Jedoch war ich mir total unsicher.Generell könnte man sagen, dass es egal ist, ob ich mittels Resolution auf Gültigkeit oder Nicht-Gültigkeit prüfe, das Verfahren ist immer das gleiche M und /G.Habe ich die leere-Menge-Resolvente herleiten können, dann ist die urspr. Formel gültig, ist es nicht möglich(was man sauber mit w-vollständigen Resolutionen wie P-Resolution oder N-Resolution zeigen kann) die leere-Menge-Resolvente herzuleiten, dann ist die urspr. Formel nicht gültig.Mit anderen Worten: Es gibt kein Extra-Verfahren um die Nicht-Gültigkeit einer Formel zu zeigen.
egal wie du's anstellst, es kommt immer die Resolvente {-A,B} heraus. also erfüllbar, also nicht gültig
Ich bin der Meinung, dass man KEIN einziges Mal resolvieren kann.Sprich die "Resolvente"(die gar keine ist) ist die ganze Formel {/A,B}{B}{/A} und nicht etwa {/A,B} .Solange das keine leere-Menge ist, ist es völlig egal, was dabei rauskommt.
F,G-kontingent
G oder G=>F
ist: [..]kontingent, [..]Kontradiktion, [..]gültig, [..]Tautologie
G oder G=>F ist äquivalent zu: G oder /G oder F, das heißt: T oder F, also eine Tautologie
also gültig und Tautologie, oder????Gültig hieß doch allgemeingültig oder kontingent, oder?
gültig == allgemeingültig == Tautologie
erfüllbar == allgemeingültig oder kontigent
Ach, so war das.Dass aber gültig und allgemeingültig das gleiche ist, ist irgendwie bescheuert.Was wiederum das gleiche ist, wie Tautologie.
Dann hieße die Antwort auf die vorige Frage:
[x]gültig(Tautologie)
Die 4 Kästchen hat es gegeben, wenn ich mich nicht irre. "Erfüllbar" wäre doppelt gemoppelt.
kontingent, erfüllbar, unerfüllbar, gültig
Sind die Strukturen A=(U,I) schwierig oder machen sie nur so einen Eindruck???
Es gab nämlich die eine Aufgabe, wo es hieß:
F= Ax(P(x)=>Q(x))
G= Q(x) and AxP(x)
Zeigen Sie dass F|=G nicht gilt (haben wir schon heute gehabt:)) und konstruieren Sie dazu eine Struktur (A=(U,I)) und werten Sie die Formeln nach der Struktur aus.
In welchem Skript steht denn überhaupt was zu den Strukturen???
mal ne andere Frage.
Wann geht es morgen los? Um 11:45 oder um 11?
Die Klausur startet um 11:45.
Ab 11Uhr Einlass ins Audimax I.
Haeh? 18:00 und noch kein Geheule wie gemein Herr Habel ist? Ich bin verwirrt.
Warum bist du denn verwirrt??????
Das Geheule kommt erst mit der Zeit, wenn die ersten realisiert haben, was sie da gemacht haben, haben mussten;-)
Bin trotzdem mal neugierig was jetzt so dran kam…
Vielleicht mag ja einer mal berichten.
ich fand die Kausur relativ fair, die Aufgaben waren klar gestellt und ich wusste eigentlich immer, was zu tun war (nur nicht wie [28]). Insgesamt auf jeden Fall schaffbar, das haben auch die meisten Anderen gesagt mit denen ich gesprochen habe.
Thematisch ging das ganze nicht allzu tief. Bedeutung von [latex]\models, \Rightarrow, \vdash_{MP}[/latex], ein bisschen Resolution, der Markierungsalgorithmus, kaum Prädikatenlogik, keine Pränexform/Skolemisierung. Im Automatenteil ein bisschen Reguläre Ausdrücke, kontextfreie Grammatiken, Pumping-Lemma, Potenzmengenkonstruktion, am Schluss musste man einen Kellerautomaten zu einer Grammatik bauen. (Kein Anspruch auf Vollständigkeit)
das hört sich ja einfach an im vergleich zur ersten klausur. ich wünschte ich hätte diese schreiben können…
Ich bin zwar besser zurechtgekommen als beim ersten Mal, aber trotzdem nicht sicher, daß ich bestanden habe..wie soll das erst mit FGI 2 werden? :-(
lulz bestanden :O
ähm 34 bestanden, 8 durchgefallen…schnitt wohl gut korrigiert, obwohl ich die klausur eigentlich fair fand…hoffe die stine ergebnisse sind fest und werden nicht nachträglich noch geändert…
greetz akephalos/ christian
Man muss schon sagen, dass die Klausur ganz normal ausgefallen ist-weder gut noch schlecht. FGI1 ist halt kein einfacher Stoff.Und das wichtigste: Die Klausur entsprach dem, was wie in den Übungen geübt haben.Somit hat sich Prof. Habel diesmal ganz fair verhalten.
Zu FGI2: Wenn ich mich nicht irre, hat's fast gar nix mit FGI1 gemeinsam.Da geht es um Petri-Netze.Die Tatsache ist, dass es schwieriger ist als FGI1:)
Die Klausur war absolut fair.
Zumindest was ich davor über die Klausuren gelesen habe kann ich nicht bestätigen.
Vielen Dank an Habel