0

In this Wikipedia page https://en.wikipedia.org/wiki/Propositional_calculus, specifically in the section "Example 2. Natural deduction system", it mentions 11 inference rules and no axioms for a natural deduction system. I wanted to know how we can prove the following formulas using only the 11 rules mentioned in that page:

  1. ¬A∨A
  2. ¬(¬A∧A)
  3. (A→¬A)→¬A
  4. A→(B→C) → (A∧B)→C

And most importantly, please show all of that using a sequence of numbered lines, instead of any tree-proofs or diagrams.

CC BY-SA 4.0
3
  • 4
    This site is not intended for you to just ask people to solve problems for you. You should explain what progress you have made on the problem, and what exactly you are having difficulty with.
    – David M
    Jan 4 at 1:41
  • I know exactly what this site is for, I just had no idea how to begin the proofs since many crucial inference rules (like RAA) aren't allowed.
    – Ahmed
    Jan 4 at 2:17
  • With all due respect, just try something out. I understand it can be hard to come up with ideas and to get lost in all the formulas and symbols, but that is what math is about. If you hit a roadblock, it's easier to point out exactly where in your work you're confused about and why so that someone can explain that particular part. Otherwise, you're expecting a detailed explanation of things that you might just gloss over.
    – Accelerator
    Jan 6 at 7:54

1 Answer 1

Reset to default
1

The first three all have a similar technique to use, so I’ll just prove A∨¬A. The last one should be fairly easy.

  1. ¬(A∨¬A) [H]

  1. A [H]

  2. A∧¬(A∨¬A) [1,2 ∧ I]

  3. ¬(A∨¬A) [3 ∧ E]

  1. A→¬(A∨¬A) [2-4 → I]

  1. A [H]

  2. A∨¬A [6 ∨ I]

  1. A→(A∨¬A) [6-7 → I]

  2. ¬A [5,8 ¬ I]

  3. A∨¬A [9 ∨ I]

  4. ¬(A∨¬A)→(A∨¬A) [1-10 → I]

  1. ¬(A∨¬A) [H]
  1. ¬(A∨¬A)→¬(A∨¬A) [12-12 → I]

  1. ¬¬(A∨¬A) [11,13 ¬ I]

  2. (A∨¬A) [14 DNE]

Note that this system requires you to use rules for other operators to prove things for negation, reiteration, etc. The general strategy is the same as for a simpler ND system, but you just have to translate those rules to these ones.

CC BY-SA 4.0

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