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