a) $(\lnot(P \land Q)) \lor (Q \land R)$
b) $(P \lor Q) \land \lnot(Q)$
How do I simplify these 2 expression?
$\begingroup$
$\endgroup$
3
asked May 6 '11 at 13:05
-
$\begingroup$ Can you do something about the TeX? $\endgroup$ – Asaf Karagila♦ May 6 '11 at 13:08
-
2$\begingroup$ An equation is something with an equals sign. You have written two formulas, not two equations. $\endgroup$ – Gerry Myerson May 6 '11 at 13:11
-
$\begingroup$ You can use DeMorgan's so that all the connections are "AND"s or "OR"s... $\endgroup$ – J. M. isn't a mathematician May 6 '11 at 13:17
Add a comment
|
$\begingroup$
$\endgroup$
6
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.
-
$\begingroup$ You're right, I did have a mistake - have deleted it now! $\endgroup$ – Chris Taylor May 6 '11 at 14:34
-
$\begingroup$ The expression $\lnot P\lor\lnot Q\lor(Q\land R)$ is already in disjunctive normal form. $\endgroup$ – Asaf Karagila♦ May 6 '11 at 14:50
-
$\begingroup$ @Asaf, yup, hence "As it happens, we've already reached disjunctive normal form in the above formula.". $\endgroup$ – okintheory May 6 '11 at 15:00
-
-
1$\begingroup$ @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.$ $\endgroup$ – okintheory May 6 '11 at 15:27
$\begingroup$
$\endgroup$
0
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.
$\begingroup$
$\endgroup$
2
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?
-
$\begingroup$ for the second one $ (x')' = x $ therefore $ (P \lor Q) $ $\endgroup$ – ilovetolearn May 6 '11 at 13:24
-
$\begingroup$ why $(\lnot(P \land Q)) \lor (Q \land R)$ becomes $(\lnot(P \land Q)) \lor R$ $\endgroup$ – ilovetolearn May 6 '11 at 14:01
