Erfüllbark. log Ausdrücke < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
Liebe KollegInnen!
Ich habe folgendes Problem: Es geht um den Algorithmus der Bestimmung der Erfüllbarkeit v. log. Ausdrücken.
Beispiel:
((P [mm] \to [/mm] Q) [mm] \wedge [/mm] Q) [mm] \to [/mm] P
nun erzeuge ich 2 Äste, wobei für den linken gilt [P/L].. also P wird durch den Wert L (wahr) ersetzt und beim rechten gilt [P/O]... P wird durch O ersetzt (falsch) daraus folgt also im ersten Schritt:
linker Ast:
(((L [mm] \to [/mm] Q) [mm] \wedge [/mm] Q) [mm] \to [/mm] L und daraus folgt dann:
(Q [mm] \wedge [/mm] Q) [mm] \to [/mm] L
und das verstehe ich schon mal nicht: wieso wird aus
((L [mm] \to [/mm] Q) [mm] \wedge [/mm] Q) plötzlich (Q [mm] \wedge [/mm] Q) ?
Dann geht es weiter: Es wird nun [Q/L] im linken Ast und [Q/O] im rechten Ast ersetzt.
Im linken Ast wird dann aus (siehe auch oben):
Q [mm] \wedge [/mm] Q) [mm] \to [/mm] L
(L [mm] \wedge [/mm] L) [mm] \to [/mm] L.
Das ergibt am Ende auch L. (naja, aus L wird vielleicht nur L?)
Im rechten Ast wird aus (siehe auch oben):
(Q [mm] \wedge [/mm] Q) [mm] \to [/mm] L
(O [mm] \wedge [/mm] O) [mm] \to [/mm] L .
Das ergibt am Ende auch wieder L ???
Danke für Eure Unterstützung!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
LG, RoterBlitz
|
|
| |
|
Hallo RoterBlitz!
> Ich habe folgendes Problem: Es geht um den Algorithmus der
> Bestimmung der Erfüllbarkeit v. log. Ausdrücken.
Ich kenne zwar diesen Algorithmus nicht, aber vielleicht kann ich dir trotzdem helfen. 
> Beispiel:
> ((P [mm]\to[/mm] Q) [mm]\wedge[/mm] Q) [mm]\to[/mm] P
>
> nun erzeuge ich 2 Äste, wobei für den linken gilt [P/L]..
> also P wird durch den Wert L (wahr) ersetzt und beim
> rechten gilt [P/O]... P wird durch O ersetzt (falsch)
> daraus folgt also im ersten Schritt:
>
> linker Ast:
>
> (((L [mm]\to[/mm] Q) [mm]\wedge[/mm] Q) [mm]\to[/mm] L und daraus folgt dann:
> (Q [mm]\wedge[/mm] Q) [mm]\to[/mm] L
> und das verstehe ich schon mal nicht: wieso wird aus
> ((L [mm]\to[/mm] Q) [mm]\wedge[/mm] Q) plötzlich (Q [mm]\wedge[/mm] Q) ?
müsste das nicht heißen:
(Q [mm]\wedge[/mm] Q) [mm]\to[/mm] O - du sagst doch, P wird durch O ersetzt?
Jedenfalls müsste dein Problem so zu lösen sein:
es gilt:
[mm] L\Rightarrow [/mm] Q [mm] \equiv \neg [/mm] L [mm] \vee [/mm] Q
und damit steht dann da:
[mm] (\neg [/mm] L [mm] \vee Q)\wedge [/mm] Q
und das ist nach den Gesetzen der Aussagenlogik (in diesem Fall das Absorptionsgesetz) eben =Q.
> Dann geht es weiter: Es wird nun [Q/L] im linken Ast und
> [Q/O] im rechten Ast ersetzt.
>
> Im linken Ast wird dann aus (siehe auch oben):
> Q [mm]\wedge[/mm] Q) [mm]\to[/mm] L
> (L [mm]\wedge[/mm] L) [mm]\to[/mm] L.
Mmh, ich verstehe nicht so ganz, ist das so richtig? Du schreibst doch, im rechten Ast soll Q durch O ersetzt werden, aber es ist doch rechts gar kein Q da? Oder verstehe ich diese Ersetzungsweise nur nicht?
> Das ergibt am Ende auch L. (naja, aus L wird vielleicht
> nur L?)
Natürlich ergibt das L, denn [mm] L\wedge [/mm] L=L und [mm] L\Rightarrow [/mm] L ist eine wahre Aussage, und L steht doch für wahr!?
> Im rechten Ast wird aus (siehe auch oben):
> (Q [mm]\wedge[/mm] Q) [mm]\to[/mm] L
> (O [mm]\wedge[/mm] O) [mm]\to[/mm] L .
> Das ergibt am Ende auch wieder L ???
Ja, das gilt aufgrund der Regel, dass eine Implikation wahr ist, wenn auf der rechten Seite eine wahre Aussage steht (also hier das L). Ich weiß leider nicht, wie diese Regel heißt, aber vielleicht hast du schonmal was mit Wahrheitstabellen und der Implikation dabei gemacht. Wenn du da dann z. B. 0 und 1 einsetzt, erhältst du:
[mm] 0\Rightarrow [/mm] 0=1
[mm] 0\Rightarrow [/mm] 1=1
[mm] 1\Rightarrow [/mm] 0=0
[mm] 1\Rightarrow [/mm] 1=1
hier siehst du, dass [mm] \Rightarrow [/mm] wahr (1) ist, wenn rechts eine 1 steht, egal, was links steht. Natürlich ist das nicht die einzige Möglichkeit, wie [mm] \Rightarrow [/mm] wahr werden kann, aber darum ging es ja jetzt nicht.
Ich hoffe, ich konnte dir schonmal helfen, aber wenn nochwas unklar ist, kannst du gerne nochmal nachfragen.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Hallo,
ich versuche mal den gesamten Baum in einem Word-File anzuhängen.. so sollte die Lösung aussehen:
Dateianhänge:
Anhang Nr. 1 (Typ: doc) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:58 Do 06.01.2005 | | Autor: | wluut |
Ha, da haben wir wohl beinahe gleichzeitig getippt, und ich war schon wieder zu langsam.
Ich hoffe mit meiner Antwort wird einigermaßen klar, warum der Baum so aussieht.
Wobei mir persönlich allerdings nicht klar ist, wann und wie welche Vereinfachungsregeln benutzt werden, denn wie in der anderen Antwort schon gesagt, kann man den linken Teilbaum ja schon nach dem ersten Schritt zu L vereinfachen und muss gar nicht erst Q durch O und L ersetzen.
Vielleicht haben das diejenigen übersehen, die den Baum gemacht haben. Im rechten Teil haben sie ja auch mehrere Schritte auf einmal gemacht.
Liebe Grüße nochmal.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:50 Do 06.01.2005 | | Autor: | wluut |
Hallo,
Bastiane hat zwar schon geantwortet, ich versuch's trotzdem nochmal etwas ausführlicher zu erklären. Insbesondere der Teil mit den Wertetabellen hat mir damals mit diesem Logikkram sehr geholfen.
Wichtig sind in diesem Beispiel die Wertetabellen für die logische Implikation (Aus A folgt B, als Formel: A [mm] \Rightarrow [/mm] B) und die sogenannte Konjunktion ( UND-Verknüpfung, A [mm] \wedge [/mm] B ).
Also mit L [mm] \hat= [/mm] wahr und O [mm] \hat= [/mm] falsch ergeben sich:
(hat Bastiane ja auch schon aufgeschrieben:)
O [mm] \Rightarrow [/mm] O ist eine wahre Aussage, also L.
O [mm] \Rightarrow [/mm] L ist eine wahre Aussage, also L.
(da musste ich mich auch erst dran gewöhnen, aber aus etwas falschem kann halt auch mal was richtiges folgen, das ist halt so definiert.)
L [mm] \Rightarrow [/mm] O ist eine falsche Aussage, also O.
L [mm] \Rightarrow [/mm] L ist eine wahre Aussage, also L.
Mit Hilfe dieser Tabelle kann man jeden der Ausdrücke vereinfachen.
Man kann aber auch mit Hilfe der Tabelle auch Regeln dafür ableiten, dass man nicht alle Werte kennt. Zum Beispiel sieht man, dass immer, wenn vorne ein O steht, insgesamt L herauskommt, also:
O [mm] \Rightarrow [/mm] x ist IMMER wahr (also L), egal, ob x nun O ist oder L.
So ergeben sich auch noch andere Regeln, die man leicht mit der Wertetabelle überprüfen kann:
1) L [mm] \Rightarrow [/mm] x = x
2) O [mm] \Rightarrow [/mm] x = L
3) x [mm] \Rightarrow [/mm] L = L
4) x [mm] \Rightarrow [/mm] O = [mm] \neg [/mm] x (also NICHT x, sondern das Gegenteil)
Mit Hilfe der 3. der obigen Regeln, hättest Du eigentlich schon nach dem ersten Schritt aufhören können:
> linker Ast:
>
> (((L [mm]\to[/mm] Q) [mm]\wedge[/mm] Q) [mm]\to[/mm] L
Aus Regel 3 folgt nämlich gleich, dass der ganze Ausdruck immer L wird, egal was man noch für Q einsetzt.
Hier gibt's nochmal die Wertetabellen für UND (Konjunktion) und ODER (Disjunktion) mit ein paar Regeln dazu, die kann man nämlich immer mal wieder gebrauchen, und vielleicht hast du ja noch mehr Aufgaben dieser Art.
UND:
O [mm] \wedge [/mm] O = O
O [mm] \wedge [/mm] L = O
L [mm] \wedge [/mm] O = O
L [mm] \wedge [/mm] L = L
Regeln:
O [mm] \wedge [/mm] x = O
x [mm] \wedge [/mm] O = O
L [mm] \wedge [/mm] x = x
x [mm] \wedge [/mm] L = x
ODER:
O [mm] \vee [/mm] O = O
O [mm] \vee [/mm] L = L
L [mm] \vee [/mm] O = L
L [mm] \vee [/mm] L = L
Regeln:
O [mm] \vee [/mm] x = x
x [mm] \vee [/mm] O = x
L [mm] \vee [/mm] x = L
x [mm] \vee [/mm] L = L
für alle anderen logischen Operationen gibt es natürlich auch solche Wertetabellen und Regeln, die kann man sich im Zweifel aber selbst schnell mal hinschreiben.
Falls der Algorithmus naiv ist, und den ganzen Baum bis zum Schluss aufmalt, muss man halt am Ende jedes Zweiges den entstandenen Ausdruck mit Hilfe der Wertetabellen auswerten. Falls es irgendweinen Zweig gibt, wo am Ende L rauskommt, hat man eine erfüllende Belegung für den Ausdruck gefunden. Falls immer O rauskommt, ist der Ausdruck nicht erfüllbar.
Liebe Grüße, auch an Bastiane, die wieder mal schneller war 
|
|
|
| |
|
> Hallo,
> Bastiane hat zwar schon geantwortet, ich versuch's
> trotzdem nochmal etwas ausführlicher zu erklären.
> Insbesondere der Teil mit den Wertetabellen hat mir damals
> mit diesem Logikkram sehr geholfen.
>
> Wichtig sind in diesem Beispiel die Wertetabellen für die
> logische Implikation (Aus A folgt B, als Formel: A
> [mm]\Rightarrow[/mm] B) und die sogenannte Konjunktion (
> UND-Verknüpfung, A [mm]\wedge[/mm] B ).
>
> Also mit L [mm]\hat=[/mm] wahr und O [mm]\hat=[/mm] falsch ergeben sich:
> (hat Bastiane ja auch schon aufgeschrieben:)
>
> O [mm]\Rightarrow[/mm] O ist eine wahre Aussage, also L.
> O [mm]\Rightarrow[/mm] L ist eine wahre Aussage, also L.
> (da musste ich mich auch erst dran gewöhnen, aber aus
> etwas falschem kann halt auch mal was richtiges folgen, das
> ist halt so definiert.)
> L [mm]\Rightarrow[/mm] O ist eine falsche Aussage, also O.
> L [mm]\Rightarrow[/mm] L ist eine wahre Aussage, also L.
>
> Mit Hilfe dieser Tabelle kann man jeden der Ausdrücke
> vereinfachen.
> Man kann aber auch mit Hilfe der Tabelle auch Regeln dafür
> ableiten, dass man nicht alle Werte kennt. Zum Beispiel
> sieht man, dass immer, wenn vorne ein O steht, insgesamt L
> herauskommt, also:
> O [mm]\Rightarrow[/mm] x ist IMMER wahr (also L), egal, ob x nun O
> ist oder L.
>
> So ergeben sich auch noch andere Regeln, die man leicht mit
> der Wertetabelle überprüfen kann:
>
> 1) L [mm]\Rightarrow[/mm] x = x
> 2) O [mm]\Rightarrow[/mm] x = L
> 3) x [mm]\Rightarrow[/mm] L = L
> 4) x [mm]\Rightarrow[/mm] O = [mm]\neg[/mm] x (also NICHT x, sondern das
> Gegenteil)
>
> Mit Hilfe der 3. der obigen Regeln, hättest Du eigentlich
> schon nach dem ersten Schritt aufhören können:
>
> > linker Ast:
> >
> > (((L [mm]\to[/mm] Q) [mm]\wedge[/mm] Q) [mm]\to[/mm] L
>
> Aus Regel 3 folgt nämlich gleich, dass der ganze Ausdruck
> immer L wird, egal was man noch für Q einsetzt.
>
> Hier gibt's nochmal die Wertetabellen für UND (Konjunktion)
> und ODER (Disjunktion) mit ein paar Regeln dazu, die kann
> man nämlich immer mal wieder gebrauchen, und vielleicht
> hast du ja noch mehr Aufgaben dieser Art.
>
> UND:
> O [mm]\wedge[/mm] O = O
> O [mm]\wedge[/mm] L = O
> L [mm]\wedge[/mm] O = O
> L [mm]\wedge[/mm] L = L
>
> Regeln:
> O [mm]\wedge[/mm] x = O
> x [mm]\wedge[/mm] O = O
> L [mm]\wedge[/mm] x = x
> x [mm]\wedge[/mm] L = x
>
> ODER:
> O [mm]\vee[/mm] O = O
> O [mm]\vee[/mm] L = L
> L [mm]\vee[/mm] O = L
> L [mm]\vee[/mm] L = L
>
> Regeln:
> O [mm]\vee[/mm] x = x
> x [mm]\vee[/mm] O = x
> L [mm]\vee[/mm] x = L
> x [mm]\vee[/mm] L = L
>
> für alle anderen logischen Operationen gibt es natürlich
> auch solche Wertetabellen und Regeln, die kann man sich im
> Zweifel aber selbst schnell mal hinschreiben.
>
> Falls der Algorithmus naiv ist, und den ganzen Baum bis zum
> Schluss aufmalt, muss man halt am Ende jedes Zweiges den
> entstandenen Ausdruck mit Hilfe der Wertetabellen
> auswerten. Falls es irgendweinen Zweig gibt, wo am Ende L
> rauskommt, hat man eine erfüllende Belegung für den
> Ausdruck gefunden. Falls immer O rauskommt, ist der
> Ausdruck nicht erfüllbar.
>
> Liebe Grüße, auch an Bastiane, die wieder mal schneller war
>
>
>
Hallo nochmals!
Erstmals: Danke für Eure tolle Mithilfe
Ich habe dazu also noch eine folgende Aufgabenstellung, dabei geht es um die Kombinationen mit: [mm] \gdw
[/mm]
Bin ich nun mit den folgenden Angaben richtig?
L [mm] \gdw [/mm] x ergibt x
O [mm] \gdw [/mm] x ergibt [mm] \neg [/mm] x
x [mm] \gdw [/mm] L ergibt x
x [mm] \gdw [/mm] O ergibt [mm] \neg [/mm] x
Weiters verstehe ich nicht ganz die Erläuterung mit dem .. daß der Gesamtausdruck wahr ist, wenn auf der rechten Seite der Ausdruck wahr ist (ich meine, damit ist der Ausdruck rechts vom [mm] \to [/mm] gemeint? Weil wenn A falsch ist, dann ist doch auch der Gesamtausdruck wahr, egal ob B nun wahr oder falsch ist
A B A [mm] \to [/mm] B
w w w
w f w
Und dann hätte ich noch eine Frage zu meiner angefügten Datei..
Danke!!!
LG, RoterBlitz
Dateianhänge:
Anhang Nr. 1 (Typ: doc) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:23 Fr 07.01.2005 | | Autor: | wluut |
> Bin ich nun mit den folgenden Angaben richtig?
>
> L [mm]\gdw[/mm] x ergibt x
> O [mm]\gdw[/mm] x ergibt [mm]\neg[/mm] x
> x [mm]\gdw[/mm] L ergibt x
> x [mm]\gdw[/mm] O ergibt [mm]\neg[/mm] x
Ja, so wie ich das sehe, stimmt das.
> Weiters verstehe ich nicht ganz die Erläuterung mit dem ..
> daß der Gesamtausdruck wahr ist, wenn auf der rechten Seite
> der Ausdruck wahr ist (ich meine, damit ist der Ausdruck
> rechts vom [mm]\to[/mm] gemeint? Weil wenn A falsch ist, dann ist
> doch auch der Gesamtausdruck wahr, egal ob B nun wahr oder
> falsch ist
äh...den Satz muss ich nochmal lesen...
Ja, es war der Ausdruck rechts von dem [mm] \Rightarrow [/mm] gemeint.
Falls also B wahr ist, ist es egal, wie A aussieht, A [mm] \Rightarrow [/mm] B ist dann immer wahr.
> A B A [mm]\to[/mm] B
> w w w
> w f w
Da ist wohl ein Fehler drin. w [mm] \Rightarrow [/mm] f = f !
Hier nochmal die Wertetabelle für die Implikation:
> > O [mm]\Rightarrow[/mm] O = L.
> > O [mm]\Rightarrow[/mm] L = L.
> > L [mm]\Rightarrow[/mm] O = O.
> > L [mm]\Rightarrow[/mm] L = L.
> >
> > 1) L [mm]\Rightarrow[/mm] x = x
> > 2) O [mm]\Rightarrow[/mm] x = L
> > 3) x [mm]\Rightarrow[/mm] L = L
> > 4) x [mm]\Rightarrow[/mm] O = [mm]\neg[/mm] x (also NICHT x)
> Und dann hätte ich noch eine Frage zu meiner angefügten
> Datei..
L [mm] \Rightarrow [/mm] Q = Q ist mit Regel 1 schon beantwortet, gell?
Bleibt, wenn ich richtig sehe, die Frage:
Wieso ist [mm] ((O\Rightarrow Q)\wedge [/mm] Q)=Q ?
Ganz einfach: Da hat jemand zwei Schritte auf einmal gemacht:
[mm] (O\Rightarrow [/mm] x) = L, erster Schritt.
Dann steht da:
[mm] (L\wedge [/mm] Q)
Zweiter Schritt: [mm] (L\wedge [/mm] x)=x
Also Q in diesem Fall.
LG
wluut
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:28 Fr 07.01.2005 | | Autor: | RoterBlitz |
Hi, Cool... ja ist nicht so einfach. Aber danke nochmal, ich werd' mir alles noch mal genau durchdenken.
Vielleicht ja bis bald ***ggg***.
RoterBlitz
|
|
|
|
