Boolesche Formel, Belegungen bestimmen

[C.B.]

Hallo,

ich möchte eine Prüfungsvorbereitungsaufgabe lösen und hab eine boolesche Formel gegeben. Ich möchte herausfinden für wie viele verschiedene Belegungen der Variablen (6 verschiedene Variablen) diese Formel true ergibt. Habt ihr eine Idee wie ich hier vorgehen könnte? Es ist nicht angegeben von welchem Typ die Variablen sind. Aber wie geht man generell bei so einer Aufgabe in Java vor?

Vielen Dank.

 

[httpdigest]

Boolean satisfiability problem - Wikipedia

en.wikipedia.org

Es ist nicht angegeben von welchem Typ die Variablen sind.

Wenn es eine boolesche Formel ist, dann sind die Variablen ebenfalls boole'sch, können also die Werte "wahr"/true oder "falsch"/false annehmen.

 

[kneitzel]

Also wenn Du es in eine Normalform bekommst in der Form, dass Du mehrere Ausdrücke, die per und verknüpft sind, alle per oder verknüpft sind, dann hast die Anzahl der Möglichkeiten.

Da musst Du dann nur noch schauen:
a) unmögliche Kombinationen (also sowas wie "a und !a" oder etwas komplexer etwas wie "a<b und b<c und c<a", das nie wahr werden kann.) herausfiltern
b) doppelte Kombinationen herausfiltern.

Das wäre so mein Ansatz ...

 

[C.B.]

Boolean satisfiability problem - Wikipedia

en.wikipedia.org

Wenn es eine boolesche Formel ist, dann sind die Variablen ebenfalls boole'sch, können also die Werte "wahr"/true oder "falsch"/false annehmen.

Vielen Dank, dann weiß ich jetzt schon mal den Typen der Variablen.

 

[Jw456]

Wenn du uns auch die Formel sagst von der du spricht könnten wir vielleicht weiter helfen.

 

[C.B.]

Vielen Dank für die Hilfe. Die Formel lautet:

!(u && v || w && !x || y && z && !u || z && v && !y || (x && (y || !(x && z && w) && !(y || z)))&&!(!z && !y || y&& x && !z)

Setzte ich zu Beginn die Variablen u, v, w, x, y und z erstmal alle auf false oder durcheinander false und true?

Vielen Dank.

 

[httpdigest]

Du probierst einfach alle moeglichen Belegungen aus. Gibt ja nur 2^6 = 64.
Stichwort: verschachtelte for-Schleifen oder Rekursion
Ich gehe mal davon aus, dass es bei der Aufgabe darum geht, ein Programm zu schreiben, was genau das tut.

 

[C.B.]

Du probierst einfach alle moeglichen Belegungen aus. Gibt ja nur 2^6 = 64.
Stichwort: verschachtelte for-Schleifen oder Rekursion
Ich gehe mal davon aus, dass es bei der Aufgabe darum geht, ein Programm zu schreiben, was genau das tut.

Vielen Dank. Ich probiere mal bisschen rum 🙂 Genau es geht darum ein Programm zu schreiben.

 

[Neumi5694]

Ja, recht viel mehr als Brute-Force bleibt dir nicht.