Ausagenlogik Umformen(Glöst) < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 14:36 Sa 02.02.2008 | | Autor: | XOR |
| Aufgabe | Gegeben Sei die Formel (r [mm] \vee [/mm] p) [mm] \to [/mm] (q [mm] \vee [/mm] z)
Bringen Sie die Formel in eine äquivalente Darstellung, sodass ein Algorithmus für
die Untersuchung der Erfüllbarkeit von Formeln in KNF, deren Klauseln genau 3
Literale haben (3SAT-Problem), diese als Eingabe akzeptieren kann.
|
bei mir happert es schon , dass ich nicht weiss wie ich nach dem Auflösen der Implikation,also von:
(r [mm] \vee; [/mm] p) [mm] \to [/mm] (q [mm] \vee [/mm] z) [mm] <=>(~r\wedge~r) \vee [/mm] q [mm] \vee [/mm] z weiter machen soll :( ist bestimmt sehr einfach nur bin ich mir meiner lösung nicht sicher
EDIT:
okay ich hab's selber gelöst,
mir war der schritt mit dem Distributiv nicht klar gewesen:
Lösung:
(r [mm] \vee; [/mm] p) [mm] \to [/mm] (q [mm] \vee [/mm] z) [mm] <=>(~r\wedge~p) \vee [/mm] q [mm] \vee [/mm] z <=> (~r [mm] \wedge [/mm] ~p [mm] \wedge [/mm] q) [mm] \vee [/mm] z
<=> (~r [mm] \wedge [/mm] q [mm] \wedge [/mm] z) [mm] \vee [/mm] (~p [mm] \wedge [/mm] q [mm] \wedge [/mm] z)
Somit ist auch die 3-SAT Aufgabe gelöst da alle Klauseln genau 3 Literale Haben
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:26 Sa 02.02.2008 | | Autor: | Bastiane |
Hallo XOR!
> Gegeben Sei die Formel (r [mm]\vee[/mm] p) [mm]\to[/mm] (q [mm]\vee[/mm] z)
>
> Bringen Sie die Formel in eine äquivalente Darstellung,
> sodass ein Algorithmus für
> die Untersuchung der Erfüllbarkeit von Formeln in KNF,
> deren Klauseln genau 3
> Literale haben (3SAT-Problem), diese als Eingabe
> akzeptieren kann.
>
> bei mir happert es schon , dass ich nicht weiss wie ich
> nach dem Auflösen der Implikation,also von:
> (r [mm]\vee;[/mm] p) [mm]\to[/mm] (q [mm]\vee[/mm] z) [mm]<=>(~r\wedge~r) \vee[/mm] q [mm]\vee[/mm] z
> weiter machen soll :( ist bestimmt sehr einfach nur bin ich
> mir meiner lösung nicht sicher
>
> EDIT:
> okay ich hab's selber gelöst,
> mir war der schritt mit dem Distributiv nicht klar
> gewesen:
>
> Lösung:
>
> (r [mm]\vee;[/mm] p) [mm]\to[/mm] (q [mm]\vee[/mm] z) [mm]<=>(~r\wedge~p) \vee[/mm] q [mm]\vee[/mm] z
> <=> (~r [mm]\wedge[/mm] ~p [mm]\wedge[/mm] q) [mm]\vee[/mm] z
> <=> (~r [mm]\wedge[/mm] q [mm]\wedge[/mm] z) [mm]\vee[/mm] (~p [mm]\wedge[/mm] q [mm]\wedge[/mm] z)
Bist du sicher, dass das richtig ist? Ich verstehe schon die erste Umformung nicht - es gilt doch: [mm] $A\Rightarrow B\equiv \neg A\vee [/mm] B$. Und die anderen Umformungen verstehe ich auch nicht...
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Mi 06.02.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
