# Prove that $(\neg P \lor Q)\wedge (P \lor \neg R)\wedge (\neg P \lor \neg Q)$ and $\neg (P \lor R)$ logically equivalent.

Prove that $$(\neg P \lor Q)\wedge (P \lor \neg R)\wedge (\neg P \lor \neg Q)$$ and $$\neg (P \lor R)$$ logically equivalent.

I can get a feel for why this will be true.

My argument goes as follows:

Let's take the term $$(\neg P \lor Q)$$ to be $$(1)$$, $$(P \lor \neg R)$$ to be $$(2)$$ and $$(\neg P \lor \neg Q)$$ to be $$(3)$$, each seperated by $$\wedge$$.

Our goal is to identify when all the $$3$$ terms are True.

When $$P$$ is True, $$(2)$$ is necessarily True. Now, $$(1)$$ is True if $$Q$$ is True. $$(3)$$ is True if $$Q$$ is False. Hence, there is no way for the expression to return True if $$P$$ is True as all $$3$$ terms can never be True at the same time.

When $$P$$ is False, $$(1)$$ and $$(3)$$ are necessarily True. Now, $$(2)$$ is True only if $$R$$ is False.

Hence, the condition for the entire expression to be True is $$\neg P \wedge \neg Q$$ which is the same as $$\neg (P \lor Q)$$ by De Morgan's Law.

I know this is not the proof that my teacher was looking for. I feel like in the arguments that I made above, I am sort of constructing the Truth Table of the given expression.

Can anyone give me a method to prove this using only Logical Equivalences and by working from the given expression towards the final expression.

This is what you are looking for. A construction from the left expression to the right using logical properties (very simples as distributive, conmutative)

$$(\sim P \vee Q)\wedge(P\vee\sim R)\wedge(\sim P \vee \sim Q)$$

$$(\sim P \vee Q)\wedge(\sim P \vee \sim Q)\wedge(P\vee\sim R)~~\mbox{ (conmutative property) }$$

$$[(\sim P) \vee (Q \wedge \sim Q)]\wedge(P\vee\sim R) ~~\mbox{ (distributive property) }$$

$$[(\sim P) \vee ( F)]\wedge(P\vee\sim R)~~ \mbox{ (property of } \wedge )$$

$$(\sim P) \wedge(P\vee\sim R)~~ \mbox{(absorption)}$$

$$\sim P \wedge \sim R ~~\mbox{ (Morgan)}$$ $$\sim (P \vee R)$$

Well, $$(\neg P\vee Q)\wedge (\neg P\vee \neg Q)$$ is equivalent to $$\neg P\wedge (Q\vee \neg Q)$$ by distributivity and the latter is clearly equivalent to $$\neg P$$.

Then $$\neg P\wedge (P\vee \neg R)$$ is equivalent by distributivity to $$(\neg P\wedge P)\vee (\neg P\wedge \neg R)$$ which in turn is equivalent to $$\neg P\wedge \neg R$$ and by de Morgan $$\neg(P\vee R)$$.

One easier argument is as follows. We want to show that $$(1) \land (2) \land (3)$$ is true if and only if $$\neg (P \lor R)$$ is true. If we have $$(1) \land (2) \land (3)$$ is true, then if $$P$$ is true, then either $$(1)$$ or $$(3)$$ is false (check!). Hence $$P$$ is false, thus by $$(2)$$, $$R$$ is false, thus $$\neg (P \lor R)$$ is true. Conversely, if $$\neg (P \lor R)$$ is true, then $$P$$ and $$R$$ must be false, then we can easily check $$(1) \land (2) \land (3)$$ is true.

There are two very useful logical equivalences that can show this equivalence very quickly:

$$(P \lor Q) \land (P \lor \neg Q) \Leftrightarrow P$$

Reduction

$$P \land (\neg P \lor Q) \Leftrightarrow P \land Q$$ (think of this as: given the truth of $$P$$, the term $$\neg P \lor Q$$ 'reduces' to just $$Q$$)

With these two principles applied to your statement, you get:

$$(\neg P \lor Q)\land (P \lor \neg R)\land(\neg P \lor \neg Q) \overset{\text{Adjacency}}{\Leftrightarrow}$$

$$\neg P\land (P \lor \neg R)\overset{\text{Reduction}}{\Leftrightarrow}$$

$$\neg P\land \neg R\overset{\text{DeMorgan}}{\Leftrightarrow}$$

$$\neg (P\lor R)$$