Abfrage, ob f erfüllbar ist

Question

"Implementieren Sie eine Funktion, welche für die gegebene 3-SAT Instanz

\( f(x_0,x_1,x_2,x_3) = (x_1 ~ ∨ ~ \bar x_2 ~ ∨  x_3) ∧ (x_0 ~ ∨ x_2  ~ ∨  \bar x_3) ∧ (\bar x_1 ~ ∨ ~ x_2 ~ ∨ x_3) \) und für eine gegebene Belegung der Variablen \( x_0,..., x_3 \) überprüft, ob die Belegung die Funktion f erfüllt.

Die Funktion Test(...) soll ein int-Array übergeben bekommen, in welchem an i-ter Stelle die Belegung der Variablen \(x_i\) steht, dargestellt durch eine 1 oder 0. Ihre Funktion Test(...) soll öffentlich aufrufbar sein und den Wert true zurückgeben, falls die gegebene Belegung die Funktion f erfüllt, andernfalls false."

Ich hab die Aufgabe gemacht, allerdings habe ich die Fälle, in denen f nicht erfüllbar ist, explizit mit if-else-Abfragen hingeschrieben. Es ist zwar eine Lösung, die man so bestimmt für 3 oder wie in diesem Fall 4-bit machen kann, aber für größere Eingaben eher nicht mehr geeignet ist.

Es gibt noch eine Möglichkeit es anders und eleganter zu lösen, aber ich komm nicht drauf.

Meine Idee war, das Array mit der Belegung für jede Stelle zu durchlaufen, aber das klappt irgendwie nicht bzw nicht so wie ich es mir vorgestellt habe.

Hat jemand eine Idee oder Vorschlag, wie man es lösen könnte.

Answer 1

Die Funktion soll für eine gegebene Belegung (kodiert durch ein Integer-Array der Länge \(4\)) ermitteln, ob der gegebene Ausdruck \( f(x_0,x_1,x_2,x_3) = (x_1\ ∨ \ \bar x_2 \ ∨  x_3) ∧ (x_0 \ ∨ x_2  \ ∨  \bar x_3) ∧ (\bar x_1 \ ∨ \ x_2 \ ∨ x_3) \) erfüllt ist oder nicht. Hierfür reicht bereits ein Einzeiler:

 public static boolean Test(final int[] x){
    return (b(x[1]) || !b(x[2]) || b(x[3])) && (b(x[0]) || b(x[2]) || !b(x[3])) && (!b(x[1]) || b(x[2]) || b(x[3]));
 }

Du übergibst (wie gefordert) das Integer-Array und innerhalb der Funktion wird der Ausdruck entsprechend der gegebenen Formel ausgewertet. Ich habe zusätzlich eine Hilfsfunktion geschrieben, mit der die Integer-Werte \(0\) und \(1\) in die entsprechenden Boolean-Werte übersetzt werden. Dies kannst Du theoretisch auch direkt in der Funktion Test(...) vornehmen:

 private static boolean b(int integer){
    return integer == 0? false : true;
 }

Der Aufruf für die Belegung \(f(1,0,1,0)\) sieht folgendermaßen aus:

 public static void main(final String... args) {
    System.out.println(Test(new int[]{1,0,1,0}));
 }

Das Ergebnis ist false. Alle Belegungskombinationen erhältst Du durch "binäres Hochzählen".

Comments

Hab einige Fragen:

1. warum kommt da ein "final" hin bei meinem Array ?

2. so wie dein Einzeiler aussieht, hatte ich es zuerst auch, aber Java hat gemeckert, dass ich "||" , "&&" und "!" nicht benutzen kann. Was hat es mit "b(x[1])" auf sich ? so was hatten wir, soweit ich mich erinnern kann, nicht.

---

warum kommt da ein "final" hin bei meinem Array ?

Das final ist optional. Damit wird nur ausgedrückt, dass es sich bei dem Übergabeparameter um ein unveränderliches Array handelt (guter Programmierstil).

aber Java hat gemeckert, dass ich "||" , "&&" und "!" nicht benutzen kann.

? Welchen Java-Compiler nutzt Du? Wer genau hat gemeckert? Deine IDE? Kannst Du einen Screenshot von der Fehlermeldung einstellen?

Was hat es mit "b(x[1])" auf sich ?

Ich habe unten (wie in meiner Antwort bereits erwähnt) eine zweite Funktion geschrieben, nämlich

 private static boolean b(int integer){
    return integer == 0? false : true;
 }

Die ist einfach dazu da, um die Integer- in Boolean-Werte zu transformieren. Sonst müsstest Du erst alle Werte aus dem Array auslesen und dann fragen

"Bist Du eine \(1\)? Wenn ja, dann setze werde zu true. Anonsten zu false."

---

Ich programmiere mit Eclipse.

Meine Methode sieht momentan mit entsprechendem Gemecker von Java wie folgt aus:

*...* ist der Teil, der von Java rot unterstrichen wird.

public static boolean Test(int A[]){

if ((A[1] || *!A[2]* || A[3]) && (*A[0] || A[2]* || A[3]) && 
(*!A[1]* || A[2] || A[3]) == 0){
 return false;
}

return true;

}

Und wenn ich mein Programm laufen lasse, kriege ich folgende Fehlermeldung:

Exception in thread "main" java.lang.Error: Unresolved compilation problems:
The operator ! is undefined for the argument type(s) int
The operator || is undefined for the argument type(s) int, int
The operator ! is undefined for the argument type(s) int

---

Diese Fehlermeldung musst Du an dieser Stelle auch bekommen, weil A[1] usw. keine Boolean-, sondern Integer-Werte sind. Für Integer-Werte sind in Java keine logischen Operatoren definiert. !0 ist in Java nicht gleich \(1\). Deshalb musst Du die Integer-Werte erst in Boolean-Werte umrechnen und dann mit den logischen Operatoren vergleichen. Z. B. mit meiner oberen Methode oder direkt in Test(...) via

boolean a1 = false;

if(A[1] == 1){
   a1 = true;
}

Fun Fact: In C++ geht das. Da ist \(!0=1\) :-)

---

Funktioniert es jetzt?

---

Deine zwei Methoden funktionieren. Hätte mich jetzt auf gewundert, wenn nicht :D

Wenn ich jetzt wie bei meiner angepassten Ursprungsabfrage "==0" und der if-Bedingung testen will, geht das (natürlich) wieder nicht.

Und auch wenn ich direkt in meiner Test-Methode abfrage, müsste ich das dann nicht für jedes A[] einzeln machen ?

---

Wenn ich jetzt wie bei meiner angepassten Ursprungsabfrage "==0" und der if-Bedingung testen will, geht das (natürlich) wieder nicht.

Ich habe Dir gerade eine Alternativ-Lösung erstellt, welch die Umwandlung der Integer- in Boolean-Werte direkt innerhalb der Funktion Test(...) vornimmt.

 public static boolean Test(final int[] x) {
    // Umgewandeltes Array.
    boolean[] b = new boolean[x.length];
    // Transformiere jeden Integer-Wert in einen Boolean-Wert.
    for(int i = 0; i < b.length; i++) {
       if(x[i] == 1) {
          b[i] = true;
       } else {
          b[i] = false;
       }
    }
       return (b[1] || !b[2] || b[3]) && (b[0] || b[2] || !b[3]) && (!b[1] || b[2] || b[3]);
 }

Hilft Dir das weiter? Stelle gerne Rückfragen, wenn etwas unklar ist.

---

Infofrage:

wie machst du das mit der Unterlegung bei " Test(...)"  usw. ?

---

wie machst du das mit der Unterlegung bei " Test(...)"  usw. ?

Das geht über SHIFT+2 mal `

Die Funktoin Test(...) wird dann zwischen die beiden Apostrophe geschrieben.

---

Danke, muss ich gleich probieren :-)

---

Klasse! Du warst erfolgreich :-)

@studi01 - Ich hoffe, dass Du mit dem Code zurechtkommst. Wie gesagt: Notfalls noch einmal nachhaken.

---

Ja, der Code macht natürlich total Sinn. Maaaaaaaan :D

Programmieren ist echt nicht meins. Ich denke auch oft zu kompliziert und wenn ich mal den richtigen Gedanken habe, dann klappt es nie, das ganze in einen funktionierenden Code zu schreiben.

Danke!

Letzte Frage: Könnte ich theoretisch bei der if-Abfrage auch "==0" fragen und dementsprechend die "false" und "true" Zuweisung umdrehen ? Bzw macht es einen Unterschied wie rum ich das Abfrage ?

---

Könnte ich theoretisch bei der if-Abfrage auch "==0" fragen und dementsprechend die "false" und "true" Zuweisung umdrehen ?

Ja, das ist völlig legitim.

Bzw macht es einen Unterschied wie rum ich das Abfrage ?

Nein. Nur wenn Du vergisst auch true und false zu tauschen.

---

Ok, super.

Danke!