1

I can't wrap my head around the hometask, where you're not supposed to use Boole to show validity: A→ B


¬B → ¬A

  • Er, what rules of inference / tools are you allowed to use? – virmaior Apr 4 '17 at 2:25
  • I'm in the middle of an introductory class, so mostly basic stuff (con-/disjunction/negation/contradiction/conditional/biconditional negation/introduction, conditional proof As for the tools, It think it's Fitch/ F – Alex Apr 4 '17 at 2:34
1

I don't know if this works for fitch, but the key is conditional proof:

  1. A → B Assumption

Here's the conditional proof:

2. | ¬B Assumption

Then, if you can use modus tollens:

3. | ¬A MT 1,2
4. ¬B → ¬A CP 2-3

If you cannot use modus tollens:

3. || A Assumption
4. || B MP 1,3
5. || B & ¬B &I2,4
6. | ¬A RAA 3-5 7. ¬B → ¬A CP 2-6

The names of your tools might be different. Here's what I'm calling things:

  • Assumption = to start the proof or a sub proof
  • | the vertical bar to indicate when we are in subproofs
  • MP which might be called conditional elimination
  • MT which might also be called conditional elimination or be absent from your system
  • &I for conjunction
  • RAA for "reductio ad absurdum" -- meaning you hit a contradiction in a subproof and can reject the assumption that took you there.
  • Some proof systems require you to use R (repetition) when using something from outside the subproof. (The most pedantic versions even require you always have two things that take two lines immediately be repeated before you take the step (i.e., 4. Q MP 1,3 is not acceptable). I haven't done so here.

Some general thoughts. If you see a conditional as your goal, then usually you will want a conditional proof. Otherwise it's a pain to get a conditional back in there.

Also, what you're proving is called "contraposition" so there should be lots of proofs for it.

If you're coming from truth tables, you can somewhat translate what you learned there into proofs especially if you learned how to short-circuit the table (in that case, each step can generally become a step in a proof).

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.