How to prove this propositional logic equation?

Question

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.

Answer 1

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.

Answer 2

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$