Hallo,
ich bin gerade dabei ein Programm zu schreiben, welches das Erfüllbarkeitsproblem löst (bzw. SAT = satisfiability problem). Hierzu darf die aussagenlogische Formal aus dem Alphabet: X,1,0,(,),V,&,- bestehen. Dabei steht das „V“ für Oder, das „&“ für UND und das „–„ für die Negation. Mit X,1,0 lassen sich somit auch alle Zahlen kodieren (z.B. die Zahl 1 = X01, 2= X02 usw.). Damit nur dieses Alphabet vorkommt, verwende ich das Pattern machting. Dies wird wie folgt geprüft:
Nun habe ich einige Schwierigkeiten:
1)
Damit syntaktische Korrektheit garantiert wird, sollten die Konstellationen wie „ X1 V& X2“, „X1 VV X2“, „X1 && X2“ nicht zugelassen werden.
Frage: Gibt es eine Möglichkeit mit dem Pattern-Matching diese Konstellationen auszuschließen, sodass z.B. diese als „false“ angesehen werden und die Nachricht „Eingabestring ist unzulässig“ ausgegeben wird? Ich habe schon sehr viel im Internet dazu gesucht aber leider nichts gefunden.
2)
Nachdem ich die syntaktische Korrektheit erlangt habe, geht’s zum Auswerten. Kann mir da jemand vielleicht einen Tipp geben, wie ich am besten diese aussagenlogischen Ausdrücke auswerten kann? Auf dem Blattpapier würde ich hierzu eine Baumstruktur erstellen und mit der innersten Klammer anfangen. Wenn die Formel wie folgt aussieht :
(X10 V X01)-((X11 & X01) V X10))
3. 1. 2.
-- Dann würde ich zuerst 1. Auswerten, dann mit 2. Auswerten und anschließend das ganze mit 3. Auswerten.
Frage: Wie könnte ich das in Java umsetzen ? Hat da jemand ein Vorschlag für mich?
3)
Es gibt noch einen speziellen Fall, der ebenfalls direkt ausgeschlossen werden soll.
Wenn dieselbe Variable mit einem UND verknüpft wird, und eine davon negiert ist, dann soll ist dieser Bereich schon mal nicht erfüllbar. Dies sieht dann wie folgt aus:
(X1 & -X1) --> nicht erfüllbar.
Frage: Wie könnte ich dies mein Programm erkennen lassen? Es sollte hier also erkannt wird, dass dieselbe Variable (einmal z.B. X1 und einmal negiert X1) mit der Operation & verknüpft wurde?
Ich bedanke mich schon mal für die Tipps und Denkanstöße.
ich bin gerade dabei ein Programm zu schreiben, welches das Erfüllbarkeitsproblem löst (bzw. SAT = satisfiability problem). Hierzu darf die aussagenlogische Formal aus dem Alphabet: X,1,0,(,),V,&,- bestehen. Dabei steht das „V“ für Oder, das „&“ für UND und das „–„ für die Negation. Mit X,1,0 lassen sich somit auch alle Zahlen kodieren (z.B. die Zahl 1 = X01, 2= X02 usw.). Damit nur dieses Alphabet vorkommt, verwende ich das Pattern machting. Dies wird wie folgt geprüft:
Java:
public void suche(String eingabe) {
if(Pattern.matches("[X10()V&-]+", eingabe) == true)
{
System.out.println("Eingabestring ist zulässig");
}
else
{
System.out.println("Eingabestring ist unzulässig");
}Nun habe ich einige Schwierigkeiten:
1)
Damit syntaktische Korrektheit garantiert wird, sollten die Konstellationen wie „ X1 V& X2“, „X1 VV X2“, „X1 && X2“ nicht zugelassen werden.
Frage: Gibt es eine Möglichkeit mit dem Pattern-Matching diese Konstellationen auszuschließen, sodass z.B. diese als „false“ angesehen werden und die Nachricht „Eingabestring ist unzulässig“ ausgegeben wird? Ich habe schon sehr viel im Internet dazu gesucht aber leider nichts gefunden.
2)
Nachdem ich die syntaktische Korrektheit erlangt habe, geht’s zum Auswerten. Kann mir da jemand vielleicht einen Tipp geben, wie ich am besten diese aussagenlogischen Ausdrücke auswerten kann? Auf dem Blattpapier würde ich hierzu eine Baumstruktur erstellen und mit der innersten Klammer anfangen. Wenn die Formel wie folgt aussieht :
(X10 V X01)-((X11 & X01) V X10))
3. 1. 2.
-- Dann würde ich zuerst 1. Auswerten, dann mit 2. Auswerten und anschließend das ganze mit 3. Auswerten.
Frage: Wie könnte ich das in Java umsetzen ? Hat da jemand ein Vorschlag für mich?
3)
Es gibt noch einen speziellen Fall, der ebenfalls direkt ausgeschlossen werden soll.
Wenn dieselbe Variable mit einem UND verknüpft wird, und eine davon negiert ist, dann soll ist dieser Bereich schon mal nicht erfüllbar. Dies sieht dann wie folgt aus:
(X1 & -X1) --> nicht erfüllbar.
Frage: Wie könnte ich dies mein Programm erkennen lassen? Es sollte hier also erkannt wird, dass dieselbe Variable (einmal z.B. X1 und einmal negiert X1) mit der Operation & verknüpft wurde?
Ich bedanke mich schon mal für die Tipps und Denkanstöße.
