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
    Commented Mar 17, 2017 at 9:24
  • $\begingroup$ You can do this using the method of analytic tableaux. $\endgroup$
    – Shaun ♦
    Commented Mar 17, 2017 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
    Commented Mar 17, 2017 at 9:54

3 Answers 3

Reset to default
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$

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
    Commented Mar 17, 2017 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 ♦
    Commented Mar 17, 2017 at 10:35
  • $\begingroup$ @skyking See this meta post of mine. $\endgroup$
    – Shaun ♦
    Commented Mar 17, 2017 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
    Commented Mar 17, 2017 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 ♦
    Commented Mar 17, 2017 at 10:52
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .