Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

a) $(\lnot(P \land Q)) \lor (Q \land R)$

b) $(P \lor Q) \land \lnot(Q)$

How do I simplify these 2 expression?

share|improve this question
    
Can you do something about the TeX? –  Asaf Karagila May 6 '11 at 13:08
2  
An equation is something with an equals sign. You have written two formulas, not two equations. –  Gerry Myerson May 6 '11 at 13:11
    
You can use DeMorgan's so that all the connections are "AND"s or "OR"s... –  J. M. May 6 '11 at 13:17
add comment

3 Answers

up vote 5 down vote accepted

You can often simplify boolean propositions by fiddling around with the algebra.

Sometimes it helps to push in all negations to bring the formula to negation normal form. This means using de Morgan's law repeatedly until all negation signs are directly in front of literals:

$\neg (P\wedge Q) \vee (Q\wedge R) = \neg P\vee \neg Q \vee (Q\wedge R)$ [de Morgan's]

The next step you should do is either to bring the formula to conjunctive normal form or disjunctive normal form. Both of these forms only have to "layers" of nesting in terms of bracketing, provided you write $A \wedge (B \wedge C)$ as $A \wedge B \wedge C$, and similarly also don't write brackets in chains of disjunctions (i.e. "$\vee$"s) . To bring a formula to disjunctive normal form, you have to push in $\wedge$ using the law $A \wedge ( B \vee C) = (A \wedge B) \vee (A \wedge C)$. As it happens, we've already reached disjunctive normal form in the above formula.

From here, there are many ways to continue. In the above example, the formula is clearly true if $\neg P$ or $\neg Q$ are true. Then what happens if $P$ and $Q$ are true? Well, in that case, you must have $Q \wedge R$ true, and we're already assuming $Q$ is true, it's enough that $R$ is true. So, a simplified version of your formula is

$\neg P\vee \neg Q \vee R$.

In your second formula, considering the different possible values of $Q$ will also help you out.

If you want to be more systematic in your simplifications, then a good approach is to use Karnaugh maps. These are a very human-friendly way of simplifying formulas with up to four variables, but after that the maps get very unwieldy.

If you need to cope with more variables in a systematic way, you can use the Quine-McCluskey algorithm.

You don't have to put your formula in disjunctive normal form to use Karnaugh maps or the Quine-McCluskey algorithm, you just have to compute the truth table for your formula.

share|improve this answer
    
You're right, I did have a mistake - have deleted it now! –  Chris Taylor May 6 '11 at 14:34
    
The expression $\lnot P\lor\lnot Q\lor(Q\land R)$ is already in disjunctive normal form. –  Asaf Karagila May 6 '11 at 14:50
    
@Asaf, yup, hence "As it happens, we've already reached disjunctive normal form in the above formula.". –  itsokintheory May 6 '11 at 15:00
    
D'oh, I did not see that :-) –  Asaf Karagila May 6 '11 at 15:01
1  
@liangteh, that's not quite what happens. One way to understand it is to do the following manipulation: $\neg Q \vee (Q\wedge R) = (\neg Q \vee Q)\wedge(\neg Q \vee R) = T \wedge (\neg Q \vee R) = \neg Q \vee R.$ –  itsokintheory May 6 '11 at 15:27
show 1 more comment

a)
1. $(\lnot(P \land Q)) \lor (Q \land R)$
2. $(\lnot P \lor \lnot Q) \lor (Q\land R)$
3. $((\lnot P \lor \lnot Q) \lor Q) \land ((\lnot P \lor \lnot Q) \lor R)$
4. $(\lnot P \lor (\lnot Q \lor Q)) \land (\lnot P \lor \lnot Q \lor R)$
5. $(\lnot P \lor True) \land (\lnot P \lor \lnot Q \lor R)$
6. $(True ) \land (\lnot P \lor \lnot Q \lor R)$
7. $\lnot P \lor \lnot Q \lor R\qquad$ (Simplified normal disjunctive form)

Note: By DeMorgan's, (7) is equivalent to $\lnot(P \land Q) \lor R$

b)
1. $(P \lor Q) \land \lnot(Q)$
2. $(P \land \lnot Q) \lor (Q \land \lnot Q)$
3. $(P \land \lnot Q) \lor (False)$
4. $(P \land \lnot Q)\qquad$ (simplified in normal disjunctive form)

Can you understand how to move from one step to the next? Essentially, I am simply applying "distribution":
e.g. $(a \lor b) \land c \equiv (a \land c) \lor (b \land c)$
also $a \lor (b \land c) \equiv (a \lor b) \land (a \lor c)$
and I've used DeMorgan's in the first simplifications.

share|improve this answer
add comment

For the first, try writing $\lnot (P \land Q)$ using an "or" instead of an "and" - you should know a rule to convert between the two.

For the second, what can you say about P, given you know that Q is false?

share|improve this answer
    
for the second one $ (x')' = x $ therefore $ (P \lor Q) $ –  optimus May 6 '11 at 13:24
    
why $(\lnot(P \land Q)) \lor (Q \land R)$ becomes $(\lnot(P \land Q)) \lor R$ –  optimus May 6 '11 at 14:01
add comment

Your Answer

 
discard

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.