a) $(\lnot(P \land Q)) \lor (Q \land R)$
b) $(P \lor Q) \land \lnot(Q)$
How do I simplify these 2 expression?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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.
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$
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.
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?