# How to prove this propositional logic equation?

How do I prove the following equation?

$$\neg[(p\vee\neg q) \vee (r\wedge(p\vee\neg q))]\equiv\neg p \wedge q$$

I've been using all the laws for algebra of propositions to prove this for 3 hours but to no avail. I always ended up going back to where I started.

• The identity is not tue in general.
– user228113
Commented Apr 22, 2017 at 11:14
• I noticed a few seconds ago that there was a mistake in the equation and I've since corrected it. Please look into it again! Thanks!
– kh95
Commented Apr 22, 2017 at 11:16
• Still, when $p=1$, RHS is $0$ and LHS is $\neg r$.
– user228113
Commented Apr 22, 2017 at 11:37

let $t$ denote $(p \lor \lnot q)$ then we have $$(\lnot t) \lor (t \land r)$$

This is true whenever $t$ is false regardless of whether $r$ is true or false. When is $t$ false? Only when $p \land \lnot q$ is false. (This last statement can be verified very easily with a truth table)

However, if we assume that $r$ is true and $t$ is true we get that your whole statement is false as we can choose a $p$ and $q$ (True and False) which results in a true $t$ and a true $\lnot p \land q$ which if $r$ is true contradicts your statement.

Therefore your statement is incorrect and only works for $r$ false which is just De morgan's law.

Use

Absorption

$p \land (p \lor q) \equiv p$

$p \lor (p \land q) \equiv p$

In your case, if you treat $p \lor \neg q$ as a statement, then by Aborption:

$(p \lor \neg q) \lor (r \land (p \lor \neg q)) \equiv p \lor \neg q$

Your statement is the negation of this, so by DeMorgan:

$\neg (p \lor \neg q) \equiv \neg p \land q$

• Are you sure you didn't make a mistake when you're writing the second equation? I think the last p should be q instead, in the second equation. Thanks for answering btw.
– kh95
Commented Apr 22, 2017 at 12:57
• @kh95 Yes, typo. good catch! Commented Apr 22, 2017 at 13:17