1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ From 2nd to 3rd line you need De Morgan : $\lnot (\lnot p \lor \lnot q) \equiv (p \land q)$ $\endgroup$ – Mauro ALLEGRANZA Mar 17 '17 at 9:24
  • $\begingroup$ You can do this using the method of analytic tableaux. $\endgroup$ – Shaun Mar 17 '17 at 9:49
  • 1
    $\begingroup$ 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. $\endgroup$ – CiaPan Mar 17 '17 at 9:54
0
$\begingroup$

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

enter image description here

is indeed closed. (Each path contains a contradiction.) Hence $$(\lnot p \lor \lnot q)\implies \lnot q \equiv p \lor\lnot q.$$

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

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

$\endgroup$
0
$\begingroup$

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

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