BoolFormel in KNF & DNF?

[_bool]

Hallo,

könnte mir jemand Folgende Formel in schrittweiße in KNF und DNF ohne Wahrheitstafel also nur umwandeln in die jeweilige Form bringen?

Formel:

A <-> (B<->C)

Danke in vorraus!

[knivil]

Man benutzt fuer gewoehnlich eine Wahrheitstafel fuer die KNF bzw. DNF. Warum willst du ohne arbeiten.

[_bool]

Weil es mit Umformen kürzer wird, als mit der Wahrheitstafel!

mfg

[volkard]

vermutung:
A <-> (B<->C)
//x<->y = (x & y) | (!x & !y)
A <-> ((B&C)|(!B&!C))
//x<->y = (x & y) | (!x & !y)
(A&((B&C)|(!B&!C))) | (!A&!((B&C)|(!B&!C)))
und dann deMorgan und ausklammern, bis fertig.

[knivil]

Ob das jetzt einfacher als 8 Zeilen Wahrheitstafel + Ablesen ist, wage ich zu bezweifeln.

[mazal]

Man benutzt fuer gewoehnlich eine Wahrheitstafel fuer die KNF bzw. DNF. Warum willst du ohne arbeiten.

Man will in der Praxis oft die (Un-)Erfüllbarkeit von Formeln mit weit mehr als 1000 Variablen feststellen. Und die meisten Algorithmen arbeiten auf KNF-Formeln. Die Wahrheitstafelmethode zur Erstellung von KNF-Formeln ist hoffnungslos ineffizient (exponentiell in Anzahl der Variablen). Deswegen formt man Formeln mithelfe der boolschen Algebra um.

[+fricky]

a<->b ist ja ein umgedrehtes xor (immer true, wenn beide inputs gleich sind), also das gleiche wie not(a xor b). das entspricht: (not a and b) or (a and not b) das müsste ja schon mal die DNf a<->b sein, oder? das 'or' in der mitte kriegt man aber auch weg, mit: x or y = not(not x and not y).

[knivil]

in der Praxis oft die (Un-)Erfüllbarkeit von Formeln mit

Ich glaube kaum, dass das ein Praxisbeispiel war, auch stellst du das Problem in einen Kontext, der so ueberhaupt nicht gegeben war.

[mazal]

Sorry, ich vergaß: Was für den Computer gilt, gilt auch für den Menschen. Ich bezweifle, dass du bei einer Formel mit 8 Variablen, schneller mit der Wahrheitstafelmethode, als ich durch algebraische Umformungen auf eine Formel in KNF kommst.

[u_ser-l]

das hängt ein bisschen von der Fkt ab. Wenn die DNF 254 Terme hat, könnte die Wahrheitstafel-Methode schon konkurrenzfähig sein (^v)

[mazal]

das hängt ein bisschen von der Fkt ab. Wenn die DNF 254 Terme hat, könnte die Wahrheitstafel-Methode schon konkurrenzfähig sein (^v)

Das sind dann meistens sehr konstruierte Beispiele, wenn man bedenkt, dass im Nenner 2⁽²n) steht. Bin schon zu besoffen um nachzudenken, was im Zähler steht Werd morgen vielleicht nochmal revidieren. Aber ich wage zu behaupten, dass man in den allermeisten Fällen besser liegt.

[u_ser-l]

in den allermeisten Fällen sicherlich, sofern nicht die KDNF verlangt ist - die dürfte im Mittel ~2^{n-1} Terme haben.