Hallo
Ich hab mal eine Frage zu F1 Aufgabenblatt 3 Präsensaufgabe 2.
Wie kann ich diese am besten beweisen und lässt sich die Aufgabe auch mittels Wahrheitstabelle lösen? Und falls ja, wie?
Danke im voraus!
http://www.informatik.uni-hamburg.de/WSV/f1/2002/Aufgaben/Blatt3.pdf
Editier den Link doch bei Gelegenheit mal auf Blatt 3 [img]
http://www.fb18.de/gfx/28.gif[/img]
Edit(Bjorn42): DoneUnd wenn das Acroread 3(!) auf dem Rechner mir die Logiksymbole anzeigen würde, könnte ich wahrscheinlich auch helfen [img]
http://www.fb18.de/gfx/22.gif[/img]
Aber Prinzipiell würde ich sagen eine Wahrheitstabelle sollte das machen können. Halt bei der Tautologie nur den Fall 1, bei der Kontradiktion nur 0 und bei den kontingenten Formeln 1 und 0.
Wenn ich nun H->G habe, wovon H und G Kontradiktionen ergeben, dann habe ich eine Wahrheitstabelle der Form:
HG H->G
00 1
00 1
00 1
00 1
somit würde dies eine Tautologie ergeben. Nach der Musterlösung ist es aber kontingent(genauso ergeben sich bei den weiteren Aufgaben bei mir auch andere Ergebnisse als vorgesehen)
Wo ist mein Denkfehler?
nee, für die anderen Aufgaben ergeben sich bei mir richtige Werte nach der Art w. u. gezeigt. Also geht es nur um Aufgabe a) und e). Bei e) bekomme ich nur eine KOntingenz heraus. Die Erklärung in der Musterlösung ist mir nicht ganz klar. Woher weiss ich, dass ich z.Bsp. H= -K setzen kann usw.? Dann könnte ich doch praktisch alle kontingenten Formeln auf diese Art prüfen um zu gucken, das keine direkte Aussage möglich ist.
Also deine Wahrheitstabelle ist etwas sparsam.. du überprüfst da nur die Werte H=0 und G=0. Interessanter ist das für:
H G H=>G
0 0 1
0 1 1
1 0 0
1 1 1
ok,ok *patsch* hab verstanden. Hatte wohl ein Brett vor dem Kopf. danke für die Antworten!
Also deine Wahrheitstabelle ist etwas sparsam.. du überprüfst da nur die Werte H=0 und G=0. Interessanter ist das für:
H G H=>G
0 0 1
0 1 1
1 0 0
1 1 1
Nach Aufgabenstellung ist G eine Kontradiktion (immer 0) und H kontingent, mal 1 mal 0. Die Implikation H->G kann nur an den Stellen wahr sein, an denen H = 0 ist.
Die obige Formel nach Aufgabenstellung wäre dann kontingent.
nee, für die anderen Aufgaben ergeben sich bei mir richtige Werte nach der Art w. u. gezeigt. Also geht es nur um Aufgabe a) und e). Bei e) bekomme ich nur eine KOntingenz heraus. Die Erklärung in der Musterlösung ist mir nicht ganz klar. Woher weiss ich, dass ich z.Bsp. H= -K setzen kann usw.? Dann könnte ich doch praktisch alle kontingenten Formeln auf diese Art prüfen um zu gucken, das keine direkte Aussage möglich ist.
Ich kann leider die Musterlösung nicht einsehen, aber ich gehe davon aus, daß es darum geht, daß H (weil kontingent) auch gleich -K (kontingent, da K kontingent) sein kann! Die Biimplikation ist eben wahr, genau dann wenn (und zwar ausschließlich) H und K unter den gleichen Voraussetzungen wahr sind. Da ich aber H = -K oder K setzen kann ist die Formel kontingent.
Nach Aufgabenstellung ist G eine Kontradiktion (immer 0) und H kontingent, mal 1 mal 0. Die Implikation H->G kann nur an den Stellen wahr sein, an denen H = 0 ist.
[img]
http://www.fb18.de/gfx/22.gif[/img] die hab ich mir gar nicht angesehen [img]
http://www.fb18.de/gfx/7.gif[/img]
Und dann geht es gleich auch schon weiter mit Aufgabenzettel 5.
Übungsaufgabe 1 kann ich lösen nur blöderweise Präsensaufgabe 1 nicht, obwohl es nach dem gleichen Prinzip läuft. Eigentlich hätte ich es mir einfach gemacht, indem ich aus einer Wahrheitstabelle die DNF und KNF gebildet hätte. Allerdings steht in der Aufgabenstellung, das man unter Verwendung der Äquivalenzen von Folie 4-[img]
http://www.fb18.de/gfx/7.gif[/img] umformen soll. Ich bleibe stecken nach der Auflösung der Biimplikation bei der Umformung der Junktoren unter zu hilfenahme der de morganschen Regel.
HÜÜLFE!!!
willst du, dass jemand den aufgabenzettel sucht,
das nachrechnet und irgendwie deinen fehler nachvollzieht? [img]
http://www.fb18.de/gfx/22.gif[/img]
schreib doch einfach deine formel hier rein
wenn ein einzelner schritt nicht funktioniert
willst du, dass jemand den aufgabenzettel sucht,
das nachrechnet und irgendwie deinen fehler nachvollzieht? [img]http://www.fb18.de/gfx/22.gif[/img]
schreib doch einfach deine formel hier rein
wenn ein einzelner schritt nicht funktioniert
jo, dann klappt das auch mit den Nachbarn
Sorry, hab wohl im Übereifer einfach alles vergessen, was wichtig ist;-)
Hier erst einmal der link:
http://www.informatik.uni-hamburg.de/WSV/f1/2002/Aufgaben/Blatt5.pdfdann habe ich für (a<->((BvC)->C))
1.(A<->(-(BvC)vC)) elimieren der Implikation
2.(A&(-(BvC)vC)v(A&-(-(BvC)vC) eliminieren d. Biimplikation
3.(A&(-B&-C)vC)v(A&(–B&–C)v-C) de morgan
4.(A&(-B&-C)vC)v(A&(B&C)v-C) elimieren d. doppelten Negation
5.???ab da bleibe ich hängen
Bei der Auflösung der Biimplikation fehlt schon ein "Nicht"…
2.(A & (-(BvC)vC) v (-A & -(-(BvC)vC)
^
2.( A & ( -( B v C ) v C ) ) v ( -A & -( -( B v C ) v C ) ) zudem noch klammern vergessen
3.( A & ( -B & -C ) v C ) ) v ( A & (–( B & C) & -C ) ) de morgan, aber nicht richtig angewandt
zu 5. A v ( B & C ) ~= ( A v B ) & ( A v C ) hier A= C, B= -B C=-C …
2.( A & ( -( B v C ) v C ) ) v ( -A & -( -( B v C ) v C ) ) zudem noch klammern vergessen
3.( A & ( -B & -C ) v C ) ) v ( A & (–( B & C) & -C ) ) de morgan, aber nicht richtig angewandt
zu 5. A v ( B & C ) ~= ( A v B ) & ( A v C ) hier A= C, B= -B C=-C …
Wieso wird aus 2. zu 3. aus dem -A ein A?
weil ich ein - vergessen habe :)
schlau wäre es auch noch,
am anfang erst mal nur ((BvC)->C) zu vereinfachen,
das klappt hier, und dann gibts gleich
weniger variablen in der formel,
2.( A & ( -( B v C ) v C ) ) v ( -A & -( -( B v C ) v C ) ) zudem noch klammern vergessen
3.( A & ( -B & -C ) v C ) ) v ( A & (–( B & C) & -C ) ) de morgan, aber nicht richtig angewandt
eher
3.( A & ( -B & -C ) v C ) ) v ( -A & (( B v C) & -C ) )
weil ich ein - vergessen habe :)
2.( A & ( -( B v C ) v C ) ) v ( -A & -( -( B v C ) v C ) ) zudem noch klammern vergessen
genau wie ich die Klammer :)
Hallo!
Bei Aufgabenzettel 9http://
www.informatik.uni-hamburg.de/WSV/f1/2002/Aufgaben/Blatt9.pdf Aufgabe 1 b) bleibt aus dem Resolutionsverfahren {-A,G} übrig.Nun könnte ich doch {-A,G} noch mit {-A,F,C,D} vereinen, so dass letztendlich nur G übrigbleibt.Wäre das dann auch richtig oder falsch? Und wenn nur G übrigbleibt , dann ist die Formel unerfüllbar oder gibt es dann noch eine andere Aussage für das/die übriggebliebenen Klauseln?
du könntest zu der klausel G kommen, richtig,
edit
nicht direkt aus diesen beiden klauseln, aber mit hilfe der anderen
/edit
da G nicht die leere klausel ist,
ist die unerfüllbarkeit der formel auf diesen weg nicht zu zeigen,
es besagt lediglich, das in jeder belegung der formel,
die für diese auch ein modell sein soll,
das literal G wahr sein muss, also den wahrheitswert 1 haben muss,
denn die formel ist ja nur dann wahr, wenn alle konjunktiv
verbundenen klauseln wahr sind, also auch {G}
über die anderen klauseln sagt das nichts besonderes aus,
hätte man 2 klauseln, eine {G} und eine {-G},
würde das bedeuten, dass in einem modell der formel
G mit 1 belegt sein muss (da klausel {G} wahr sein muss), und
G mit 0 belegt sein muss (da klausel {-G} wahr sein muss),
das ist ein widerspruch -> es gibt kein modell, die formel ist unerfüllbar,
eben weil man ja aus G und -G die leere klausel resolvieren kann,
G alleine bringt nicht viel
Danke für die sehr ausführliche Antwort!
Nun könnte ich doch {-A,G} noch mit {-A,F,C,D} vereinen, so dass letztendlich nur G übrigbleibt.
Wo sind denn da die komplementaeren Literale? Damit man hier resolvieren koennte, muesste beispielsweise A statt -A in einer der beiden Mengen stehen. Und auch dann waere das Ergebnis nicht {G} sondern {G, F, C, D}, oder?
naja man hat da noch ein paar andere klauseln in der aufgabe,
mit denen klappts dann in mehreren schritten,
das war wohl nicht der kern der frage,
{G, F, C, D} würde bei deiner A-vorraussetzung rauskommen, ja
es besagt lediglich, das in jeder belegung der formel,
die für diese auch ein modell sein soll,
das literal G wahr sein muss, also den wahrheitswert 1 haben muss,
Genau dies ist übrigens die Definition der Folgerbarkeit. Alle Resolventen sind deshalb folgerbare Formeln aus der Formelmenge.
Wenn ich mich recht erinner, hab ich damals beim Lernen weniger auf Quantität als auf Qualität geachtet… sprich: Lernt lieber den "Standardkram", aber den dafür umso mehr. Während der Klausur ist es extrem wichtig, dass man Standardalgorithmen quasi im Schlaf kann, sonst werdet ihr arg in Zeitnot geraten.
