I'm struggling to apply the theorems of natural deduction to these two examples.

$$((p \to q) \land (p \to \neg q)) \to \neg p$$

$$((p \to q) \land (p \to r)) \to (p \to (q \land r))$$

Can anyone help? That is, soundness and/or completeness.

  • 6
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help with conceptual questions but just answering homework-style exercises for you is unlikely to really help you. $\endgroup$ – David Richerby Sep 23 '16 at 16:52
  • $\begingroup$ I tried to follow the formula and I think I understand the rules that are necessary to complete the theorem, but I am finding hard to apply them to real case examples. Especially I am having trouble knowing what to assume, reiterate, derive etc. $\endgroup$ – sebastian Sep 23 '16 at 22:18

I won't write natural deduction tree, but make a sketch of the proof.

  • ((๐‘ โŸถ ๐‘ž)โ‹€(๐‘ โŸถ ยฌ๐‘ž)) โŸถ ยฌ๐‘
    To prove the implication, you fist assume (๐‘ โŸถ ๐‘ž)โ‹€(๐‘ โŸถ ยฌ๐‘ž). To get ยฌ๐‘, you assume ๐‘ and get a contradiction by getting both ยฌ๐‘ž and ๐‘ž.
  • ((๐‘ โŸถ ๐‘ž)โ‹€(๐‘ โŸถ ๐‘Ÿ)) โŸถ (๐‘ โŸถ (๐‘žโ‹€๐‘Ÿ))
    Again, to prove an implication, you assume the antecedent (๐‘ โŸถ ๐‘ž)โ‹€(๐‘ โŸถ ๐‘Ÿ). From this asummption you can get (๐‘ โŸถ ๐‘ž) (*) and (๐‘ โŸถ ๐‘Ÿ)(**) separately. Now you need again to prove another implication ๐‘ โŸถ (๐‘žโ‹€๐‘Ÿ), so you assume ๐‘ and get both ๐‘ž and ๐‘Ÿ by using (*) and (**) with ๐‘

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.