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.