Neue Frage
1

How to convert from RMNF to DNF/CNF?

gefragt 2017-08-09 17:39:56 +0200

blackmamba Gravatar-Bild

aktualisiert 2017-08-09 17:40:16 +0200

I have an RMNF, for example - (a ⊕ b ⊕ a & b)

How can I convert it to CNF/DNF?

bearbeiten retag Als beleidigend melden schließen löschen

2 Antworten

1

geantwortet 2017-08-10 17:50:24 +0200

PS Gravatar-Bild

I am afraid that there is no simple way to do this, since there are formulas having a short RMNF like the parity function x[1]⊕x[2]⊕...⊕x[n] (which is already in RMNF) whose DNF and CNF have however both exponential size. Hence, any algorithm for translating RMNF to DNF or CNF must also have an exponential runtime. Therefore, almost the best you can do is generate a truth table, and read the DNF from the truth table.

bearbeiten Als beleidigend melden löschen publish Link mehr

Kommentare

As @SR pointed out, ROBDD is an alternative to the truth table. Another possibility is removing syntactic sugar and multiplying it out.

Martin ( 2017-08-14 11:50:34 +0200 )bearbeiten

Yes, the way via ROBDDs is good, and also for the example I mentioned (parity function) it is better than the truth table (even though the end result has unavoidably an exponential size). I would also recommend the BDDs here, that is a good idea.

PS ( 2017-08-14 12:07:06 +0200 )bearbeiten

Maybe we should tell the solution for the above case: (a ⊕ b ⊕ a & b) has CNF (a|b|c)&(a|b|!c) and DNF !a&b&c | !a&b&!c | a&b&c | a&b&!c | a&!b&c | a&!b&!c as computed with http://es.cs.uni-kl.de/tools/teaching/PropLogic.html

PS ( 2017-08-19 23:25:33 +0200 )bearbeiten
0

geantwortet 2017-08-10 18:54:14 +0200

SR Gravatar-Bild

The simplest way is to convert the result to SNF and draw the ROBDD of the RMNF. From ROBDD you can convert it to CNF/DNF easily. RMNF is another representation of the CNF/DNF formula.

bearbeiten Als beleidigend melden löschen publish Link mehr

Ihre Antwort

Du kannst deinen Eintrag bereits als Gast verfassen. Deine Antwort wird zwischengespeichert, bis du dich eingeloggt oder registriert hast.
Bitte nur konstruktive Antworten auf diese konkrete Frage posten.
Falls du eine Frage stellen willst, dann stelle eine neue Frage.
Für kurze Diskussionen und Nachfragen benutze bitte die Kommentar-Funktion.
Deine Fragen und Antworten kannst du jederzeit nachbearbeiten und verbessern.
Gute Fragen und Antworten kannst du mit einem Upvote oder Downvote bewerten.

Schreibe deine Antwort auf diese Frage

[Vorschau ausblenden]

Fragen-Tools

Beobachten
1 Follower

Statistik

Gefragt: 2017-08-09 17:39:56 +0200

Gesehen: 55 mal

Letztes Update: Aug 10