Prove: $(p \lor q) \land (\lnot p \lor \lnot q) \Rightarrow (p \land \lnot q) \lor (\lnot p \land q)$ using natural deduction.

308 Views Asked by At

I am trying to prove

$$ (p \lor q) \land (\lnot p \lor \lnot q) \Rightarrow (p \land \lnot q) \lor (\lnot p \land q) $$ using Natural deduction.

But I am unable to get beyond the implication reduction and the conjuction elimination on the left.

Can someone please suggest something to finish the proof.

1

There are 1 best solutions below

7
On BEST ANSWER

You'd need a rule for a proof step based on an or, something like "if we can get from $x$ to $z$, and we can get from $y$ to $z$, then we can conclude $z$ is a consequence of $x \lor y$. Also needed are rules such as: from $u$ we can derive $u \lor v$ for whatever $v$ we want.

case 1) assume $p$. Bring down next $ \lnot p \lor \lnot q$, and use some rule to arrive at $\lnot q$. Now combine the case assumption $p$ with this and get to $p \land \lnot q$, and finally use the rule about placing any other statement with this in an or to arrive at the conclusion for case 1 of $(p \land \lnot q) \lor (\lnot p \land q)$

case 2) assume $q$. This time bring down $\lnot p \lor \lnot q$ and after a few steps get again the same conclusion $(p \land \lnot q) \lor (\lnot p \land q)$ as case 1 produced.

Now looking at the two deductions of the same final $(p \land \lnot q) \lor (\lnot p \land q)$, one ("case 1") from $p$ and the other ("case 2") from $q$, you can put these two together and say you have shown that $(p \lor q) \land (\lnot p \land \lnot q)$ implies $(p \land \lnot q) \lor (\lnot p \land q).$

There are some details left out, which need to be filled in by using whatever deduction rules your version of "natural deduction" might be. But I believe the above is a general framework for the proof. Some versions use numbered lines in the proof, and refer to previous line numbers and rules used to fully justify the overall proof.