2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.