1
$\begingroup$

Is it valid to say that: $$\begin{array}{l}\neg p\vee\neg q\\p\\\hline\therefore\neg q\end{array}$$ knowing that?: $$\begin{array}{l}p\vee q\\\neg p\\\hline\therefore q\end{array}$$ (the last reasoning is called "Disjunctive syllogism").


I think yes, because:

$$\begin{array}{lll} (1)&\neg p\vee\neg q&\text{Premise}\\ (2)&p&\text{Premise}\\ (3)&p\to\neg q&\text{Conditional equivalence in (1)}\\ (4)&\neg q&\text{Modus Ponens (2)-(3)}\\ \end{array}$$

Therefore the first reasoning is valid.

Is my deduction correct?

$\endgroup$
  • 1
    $\begingroup$ Everything is correct! $\endgroup$ – azif00 Jul 1 '19 at 3:27
  • 1
    $\begingroup$ The "disjunctive syllogism" is a special case of Resolution, as used (at least theoretically, implementations may differ) in Prolog $\endgroup$ – David Tonhofer Jul 1 '19 at 16:34
3
$\begingroup$

Yes, this is valid. As you mention, it's called the Disjunctive Syllogism (or Modus Tollendo Ponens) and is one of the fundamental building blocks (inference rules) of propositional calculus.

The "standard" proof goes something like this, using conjunction introduction and De Morgan:

  • Given $\neg p \vee \neg q$
  • Given $p$
  • Hypothetically suppose $q$:
    • Conjunction introduction gives $p \wedge q$
    • De Morgan gives $\neg (\neg p \vee \neg q)$
    • Let $X$ stand for $\neg p \vee \neg q$
    • We now have $X \wedge \neg X$: a contradiction
  • Therefore $q \rightarrow \bot$
  • Therefore, by reductio ad absurdum, $\neg q$

You can also get this without De Morgan if you have to:

  • Given $\neg p \vee \neg q$
  • Given $p$
  • Hypothetically suppose $\neg p$:
    • Now we have $p \wedge \neg p$, which is a contradiction
  • So $\neg p \rightarrow \bot$, and $\bot \rightarrow \neg q$ (principle of explosion)
  • Therefore $\neg p \rightarrow \neg q$
  • $\neg q \rightarrow \neg q$, by conditional introduction
  • So $\neg q$ by disjunction elimination
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you!! Another question could be "But we did not use the disjunctive syllogism to prove the validity of this reasoning", and we could answer "But that reasoning was not necessary to prove this one", right? $\endgroup$ – manooooh Jul 1 '19 at 3:31
  • 1
    $\begingroup$ @manooooh Correct! I added a short proof. $\endgroup$ – Draconis Jul 1 '19 at 3:34
  • 2
    $\begingroup$ @manooooh There's a rule called "ex falso sequitur quodlibet" or the "principle of explosion", which says basically that $\bot \rightarrow X$ for any $X$. I'll clarify. $\endgroup$ – Draconis Jul 1 '19 at 3:48
  • 1
    $\begingroup$ Alternatively, use disjunction elimination, negation elimination, and negation introduction.$$\def\fitch#1#2{\quad\begin{array}{|l} #1\\\hline #2\end{array}}\small\fitch{1.~\lnot p\lor\lnot q\hspace{5ex}\text{Premise}\\2.~p\hspace{11.5ex}\text{Premise}}{\fitch{3.~q\hspace{8ex}\text{Assume}}{\fitch{4.~\lnot p\hspace{3ex}\text{Assume}}{5.~\bot\hspace{4ex}\text{Negation Elim.},2,4}\\\fitch{6.~\lnot q\hspace{3ex}\text{Assume}}{7.~\bot\hspace{4ex}\text{Negation Elim.},3,6}\\8.~\bot\hspace{7.5ex}\text{Disjunction Elim.},1,4{-}5,6{-}7}\\9.~\lnot q\hspace{10ex}\text{Negation Intro.},3{-}8}$$ $\endgroup$ – Graham Kemp Jul 1 '19 at 6:46
  • 2
    $\begingroup$ @GrahamKemp I didn't know one could write comments like that. How? $\endgroup$ – David Tonhofer Jul 1 '19 at 16:29

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.