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

Question

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.

Answer 1

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) $$

Answer 2

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.

Answer 3

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)$.

Answer 4

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

Adjacency

$(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)$$