# Boolean simplification expression

In words my problem is

NOT(p AND q) AND (NOT p OR q) AND (p OR p).

I have rewritten it in symbols

¬(p ∧ q) ∧ (¬p ∨ q) ∧ (p ∨ p)

I got this far:

(¬p ∨ ¬q) ∧(¬p ∨ q) ∧ p

-
You should get the null set. – Chris K Feb 15 '14 at 0:20

You can use De Morgan's law to start off with

$$\neg( (p \wedge q) \vee (p \wedge \neg q) \vee \neg p)$$

Then you can combine the first and second terms as $(p \wedge q) \vee (p \wedge \neg q) = p$. See below for the intuition beind this: $(p \wedge q)$ in red, and $(p \wedge \neg q) = p$ in green.

You should be good to go from there on in.

Alternatively, without the need for any intutition, it's possible to simply follow the rules of Boolean algebra. First of all you multiply out the brackets using the distributive law.

\begin{align} (\neg p \vee \neg q) \wedge (\neg p \vee q) \wedge p &= (\neg p \vee \neg q) \wedge (\neg p \wedge p \;\vee\; q \wedge p) \\ &= (\neg p \vee \neg q) \wedge (q \wedge p) \\ &= \neg p \wedge q \wedge p \;\;\vee\;\; \neg q \wedge q \wedge p \end{align}

Second you use the associative law to rearrange the logical AND on the left to $\neg p \wedge p \wedge q$.

-
Ahh! Got it! it becomes p ∧ (q ∨ ¬q)! – user128891 Feb 15 '14 at 2:14
@user128891 yes, exactly. I'd started a drawing when I saw your comment and I've added that to my answer. – TooTone Feb 15 '14 at 2:19
@user128891 what you wrote prompted me to do some leg work and look up the formal rules of Boolean algebra. I've added a second approach and some links which you might find useful (I did). – TooTone Feb 15 '14 at 2:34

Hint: Using De Morgan's law, your last step is: [(~p v (~q and q) ) and p].

-