Verify that $(\neg P\land N)\lor(\neg D \land P)\rightarrow \neg D\lor N$

logicpropositional-calculus

The answer seems to be $\neg D \lor N$, but below is what I got,no idea where it goes wrong

$$\begin{aligned} (\neg P\land N)\lor(\neg D \land P) &\equiv \neg(\neg N\lor P)\lor \neg(\neg P\lor D)\\ &\equiv\neg[(N\implies P)\land(P\implies D)]\\&\rightarrow \neg(N\implies D)\\ &\equiv\neg(\neg N\lor D) \\ &\equiv\neg D\land N \end{aligned}
$$

Appreciate for any help.

Best Answer

\begin{aligned} (\neg P\land N)\lor(\neg D \land P) &\equiv \neg(\neg N\lor P)\lor \neg(\neg P\lor D)\\ &\equiv\neg((N\implies P)\land(P\implies D))\\&\rightarrow \neg(N\implies D)\\ &\equiv\neg(\neg N\lor D) \\ &\equiv\neg D\land N \end{aligned}

That logical entailment in Line 3 is incorrect, as evidenced by the assignment $(P,N,D)=(0,1,1).$

Here's a correct attempt, if you don't mind applying the distributive laws: \begin{aligned} (\neg P\land N)\lor(\neg D \land P) &\equiv (¬P∨¬D)∧(¬P∨P)∧(N∨¬D)∧(N∨P)\\ &\models (N∨¬D)\\ &\equiv \neg D ∨ N. \end{aligned} Thus, $$(\neg P\land N)\lor(\neg D \land P) \to \neg D ∨ N$$ is a validity, as required.

P.S. I use $≡$ and $⊨$ to mean logically equivalent and logically implies, respectively (i.e., as metalogical symbols), while I use $\to$ merely as the material conditional (i.e., as a logical operator). As for $\implies,$ I use it just to mean implies (e.g., $x=2\implies x^2=4$) rather than as the material conditional.

Related Question