# Proof of laws of logic.

I'm really confused with laws of logic unlike truth tables. Here, i'm trying to prove:

$$(\lnot p \lor \lnot q)\implies \lnot q \equiv p \lor\lnot q$$

LHS:

\begin{align}&&(\lnot p \lor \lnot q)⇒ \lnot q\\ \equiv&& \lnot(\lnot p \lor \lnot q) \lor \lnot q \tag{by Implication law}\\ \equiv&&p \lor q \lor \lnot q \tag{by Double Negation law}\end{align}

I'm stuck till there where I have no idea on how to get rid of $q$ as it seemed like I'm already close to the answer.

• From 2nd to 3rd line you need De Morgan : $\lnot (\lnot p \lor \lnot q) \equiv (p \land q)$ – Mauro ALLEGRANZA Mar 17 '17 at 9:24
• You can do this using the method of analytic tableaux. – Shaun Mar 17 '17 at 9:49
• You made a mistake in the last step: $¬(¬p∨¬q)∨¬q$ is equivalent to $(p{\color{red}∧}q)∨¬q$ – a negation of an alternative is a conjunction of negations. – CiaPan Mar 17 '17 at 9:54

## 3 Answers

It is enough to prove that $$(\lnot p\lor\lnot q)\to(\lnot q\leftrightarrow(p\lor\lnot q))$$ is a tautology; that is, that the tableau of its negation is closed; but is indeed closed. (Each path contains a contradiction.) Hence $$(\lnot p \lor \lnot q)\implies \lnot q \equiv p \lor\lnot q.$$

• Please don't just insert a picture. Use MathJax instead... – skyking Mar 17 '17 at 10:29
• @skyking I would usually but I'm using my phone at the moment; if you can put this picture into MathJax, though, please do. – Shaun Mar 17 '17 at 10:35
• @skyking See this meta post of mine. – Shaun Mar 17 '17 at 10:47
• @Shaun thanks a lot. i wouldn't mind the picture as it would help me understand better. much thanks! – Maxxx Mar 17 '17 at 10:50
• @Maxxx You're welcome. Please upvote my answer if you like it or even accept it if it answers your question & helps you learn. – Shaun Mar 17 '17 at 10:52

$\neg (\neg p \vee \neg q) \vee \neg q \equiv\\ (p\color{red}{\wedge} q) \vee \neg q \equiv\\ (p\vee\neg q)\wedge (q \vee \neg q) \equiv\\ (p\vee\neg q) \wedge \text{True} \equiv (p\vee\neg q)$

$$\begin{array} {c|c} \lnot p \lor \lnot q)\implies \lnot q&Premise\\ \hline \lnot(\lnot p \lor \lnot q)\lor \lnot q&Implication\\ \hline (p\land q)\lor \lnot q&De Morgan\\ \hline (p\lor \lnot q)\land(q\lor \lnot q)&Distribution\\ \hline (p\lor \lnot q)\land1&Excluded\;Middle\\ \hline p\lor \lnot q&Redundant\;Truth \end{array}$$

using Propositional Calculus.