Neue Frage

Propositional Logic CNF

gefragt 2017-08-06 13:25:56 +0200

blackmamba Gravatar-Bild

aktualisiert 2017-08-06 13:26:10 +0200

How can I compute this in a faster way?


I want to know if I can directly apply any formulas here to reduce it to CNF. Right now it takes me much time to compute it.

bearbeiten retag Als beleidigend melden schließen löschen


3 Antworten


geantwortet 2017-08-07 09:55:39 +0200

aktualisiert 2017-08-07 11:08:37 +0200

The first answer of contradictioned is great. Thanks for answering that! However, there was a small typo. The first two connectives in the the right most formula should be switched. So it should be $(\neg x \wedge \neg y) \vee (x \wedge y)$. (which has been fixed now)

For the given example $d \leftrightarrow a \leftrightarrow b$ , I want to point out that connectives are left associative (slide 6 in the VRS-Chapter on propositional logic).

Your formula is hence equivalent to $(d \leftrightarrow a) \leftrightarrow b$. If you look at the inner subformula, it can be written as $(\neg d \vee a) \wedge(d \vee \neg a) $ or $(d \wedge a) \vee (\neg d \wedge \neg a)$. Thus, you could transform the formula like this:

  • $d \leftrightarrow a \leftrightarrow b =$
  • $(d \leftrightarrow a) \leftrightarrow b =$
  • $(\neg (d \leftrightarrow a) \vee b) \wedge ((d \leftrightarrow a) \vee \neg b) =$
  • $(\neg (d \leftrightarrow a) \vee b) \wedge (((\neg d \vee a) \wedge (d \vee \neg a)) \vee \neg b) =$
  • $(\neg (d \leftrightarrow a) \vee b) \wedge (\neg d \vee a \vee \neg b) \wedge (d \vee \neg a \vee \neg b) =$
  • $(\neg ((d \wedge a) \vee (\neg d \wedge \neg a)) \vee b) \wedge (\neg d \vee a \vee \neg b) \wedge (d \vee \neg a \vee \neg b) =$
  • $(((\neg d \vee \neg a) \wedge (d \vee a)) \vee b) \wedge (\neg d \vee a \vee \neg b) \wedge (d \vee \neg a \vee \neg b) =$
  • $(\neg d \vee \neg a \vee b) \wedge (d \vee a \vee b) \wedge (\neg d \vee a \vee \neg b) \wedge (d \vee \neg a \vee \neg b)$
bearbeiten Als beleidigend melden löschen publish Link mehr



Thanks for spotting :)

contradictioned ( 2017-08-07 10:42:52 +0200 )bearbeiten

Thanks for the explanation!

blackmamba ( 2017-08-07 11:44:28 +0200 )bearbeiten

if you think, the answer is right, you can click the checkmark below the voting tool next to the answer. This marks the answer as correct for the other users.

Martin ( 2017-08-07 11:46:21 +0200 )bearbeiten

geantwortet 2017-08-09 10:49:10 +0200

PS Gravatar-Bild

The answers so far are great and explain to really compute the CNF. As you were asking actually for a faster way to do that, here are two:

Fast Way #1:

If you just need the result, then you may remember the parity function: Given n variables x1,...,xn the parity function is the boolean function associated with the formula x1⊕...⊕xn and it is true if and only if an odd number of the variables is true. Next, observe that (a⊕b) is equivalent to ¬(a↔︎b), so that (d↔︎a)↔︎b is equivalent to (d⊕a)⊕b. Hence, the formula is true if and only if an odd number of variables is true, i.e., either exactly one or all three.

Hence, its DNF is obtained by listing these assignments:

a∧b∧d ∨ a∧¬b∧¬d ∨ ¬a∧b∧¬d ∨ ¬a∧¬b∧d,

and the DNF of its negation is obtained by listing the other assignments (where none or exactly two variables are true):

a∧b∧¬d ∨ a∧¬b∧d ∨ ¬a∧b∧d ∨ ¬a∧¬b∧¬d

The CNF of (d↔︎a)↔︎b can now be obtained by negating the latter, which clearly yields

(¬a∨¬b∨d)  ∧ (¬a∨b∨¬d) ∧ (a∨¬b∨¬d) ∧ (a∨b∨d)

Fast Way #2:

BDDs can also compute CNFs and DNFs by simply enumerating all paths from the root node to the 1 or 0 leaves, respectively. Hence, you may first transform the formula into a BDD, i.e., if-then-else form which is then a=>(d↔︎b)|¬(d↔︎b) by making case distinctions on a, and then a=>(b=>d|¬d)|(b=>¬d|d) by a further case distinction on b. From here you can read the DNF a∧b∧d ∨ a∧¬b∧¬d ∨ ¬a∧b∧¬d ∨ ¬a∧¬b∧d and proceed as above.

bearbeiten Als beleidigend melden löschen publish Link mehr

geantwortet 2017-08-07 09:44:16 +0200

contradictioned Gravatar-Bild

aktualisiert 2017-08-07 10:39:27 +0200

If you are free to choose a procedure to do that, I would probably (up to four variables) just write down a truth-table of the formula and read the CNF from that. That is in my opinion the least error prone way.

If you are asked to transform it by applying formulas, then why not use iteratively

$$x \leftrightarrow y \equiv (\neg x \lor y) \land (x \lor \neg y) \equiv (\neg x \land \neg y) \lor (x \land y) $$

until you have all other operators eliminated and then bring it into CNF? Again, using many simple steps--in my opinion--reduces the amount of mistakes. However, you have to practice these small steps ;)

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]


1 Follower


Gefragt: 2017-08-06 13:25:56 +0200

Gesehen: 70 mal

Letztes Update: Aug 09