Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
I think you're right. And btw, $( A \vee B ) \vee C = A \vee ( B \vee C )$ so your second step is useless. – 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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