I`m having some difficulties solving a boolean expression (I am converting it to CNF form).

The expression is:

$$F = (Q_1 \to P1 \land \lnot P_2) \lor Q_1 \land P_2 \lor P_1$$

So i do not know, how to put the brackets properly. I know the conjunction signs have precedence over the other signs. So, the 1st step would be:

$$F = (Q_1 \to (P_1 \land \lnot P_2)) \lor (Q_1 \land P_2) \lor P_1$$

And in the second step the 1st OR sign would have precedence over the second sign (left associative?):

$$F = \Big(\big(Q_1 \to (P1 \land\lnot P_2)\big) \lor (Q_1 \land P_2)\Big) \lor P_1$$

Am I doing this right, or am I totally off here?

Thank you in advance for your replies.

  • 2
    $\begingroup$ I think you're right. And btw, $( A \vee B ) \vee C = A \vee ( B \vee C )$ so your second step is useless. $\endgroup$ – xavierm02 Oct 6 '12 at 15:30

Definitely AND gets preference over OR, while parentheses get higher preference than either. Also each of AND and OR is associative.

So you're correct so far, and next you have

( Q -> (P1 or -P2)) OR (Q1 and P2) OR P1.

Now you can apply that x -> y is the same as (-x) OR y to the inside...

-Q1 OR P1 OR -P2 OR (Q1 and Q2) OR P1.

The last thing to do is to expand out the (Q1 and Q2) term. So you get

[ -Q1 OR P1 OR -P2 OR Q1 OR P1 ] AND [ -Q1 OR P1 OR -P2 OR P2 OR P1 ]

But both things in these brackets contain " x OR -x " for a certain x. So the things in both brackets are 1, or "true", and it seems this means the simplest CNF form is the word "true" or the symbol 1, or whatever stands for a tautology in the system.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.