0
$\begingroup$

I need some assistance solving what seems to be a very intuitive problem, but becomes tough when only using strict natural deduction and not assuming De Morgan laws.

Laws allowed: Implication, And, Or, MT, PBC, Copy Rule, Negation, Double Negation, Contradictions, law of excluded middle

I'm thinking it uses the law of excluded middle but I can't quite figure it out.

$$ \lnot(P \land \lnot Q), \; (\lnot P \to S) \land \lnot Q \;\;\; \text{premises} \tag{1} $$

$$ T \lor S \;\;\; \text{conclusion} \tag{2} $$

$\endgroup$
2
  • $\begingroup$ Please copy-paste the formulas into the text... they are only two. $\endgroup$ – Mauro ALLEGRANZA Jan 18 at 15:12
  • $\begingroup$ I added the formulas as mathjax. There's a tutorial and reference here $\endgroup$ – Gregory Nisbet Jan 18 at 16:12
2
$\begingroup$

Hint

  1. $\lnot (P \land \lnot Q)$ --- premise

  2. $(\lnot P \to S) \land \lnot Q$ --- premise

  3. $\lnot Q$ --- from 2) by $(\land \text E)$

  4. $P$ --- assumed [a]

  5. $(P \land \lnot Q)$ --- from 4) and 3) by $(\land \text I)$

  1. Contradiction !

and so on, deriving the sought conclusion: $T \lor S$.

The Natural Deduction rules needed, in addition to the $\land$-rules above, are $(\lnot \text I), (\to \text E)$ and $(\lor \text I)$.

$\endgroup$
1
  • $\begingroup$ Thanks boss, ended up getting it because of you. u the man $\endgroup$ – algebruh Jan 18 at 17:30
0
$\begingroup$

My proof here. Let me know if you see anything wrong with it, or if there's a more efficient way

$\endgroup$
2
  • $\begingroup$ On line 4, just assert ¬P∨P and so on line 8 you need only assume P. There is no need for the double negation elimination. $\endgroup$ – Graham Kemp Jan 19 at 0:40
  • $\begingroup$ Indeed you do not need LEM at all. Since you can derive a contradiction when you assume P, you have an Indirect Proof of ¬P and so may infer S from ¬P →S. $\endgroup$ – Graham Kemp Jan 19 at 0:50

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.