1

I have to prove that [¬ A → ¬ (A → B)] → A is a theorem using the rules of SD.

Any hints or advice?

  • sentential derivation – Bartleby Feb 3 '15 at 17:22
3

Mauro has already provided one correct derivation, but since you asked for help and advice, here's an expansion on the technique:

When doing a derivation like this, you want to look at the overall structure of the final result. If proving something of the form A -> B, assume A and derive B. If proving something of the form A & B, you usually want to prove A first, then B, then put them together. If all else fails, assume the opposite of what you want to prove, and derive a contradiction.

In this case, the larger form of this is [complex expression] -> A, so you'll first want to assume the complex expression (Mauro's step 1). From here you'll want to derive A, so assume the opposite and look for contradictions (Mauro's step 2). The next steps require a little creativity --basically you want to look for anything you can create that contradicts something you already have. You have NOT A so you can get NOT ( A -> B), which is an obvious statement to try to contradict. This means that you want to create A -> B, which is a problem like the one you started with, except easier and simpler.

In general, that's the whole technique of natural deduction --try to break a longer, harder problem into a series of shorter, simpler problems.

There are purely mechanical ways to get the same results, but in my opinion, natural deduction leads to greater understanding.

1

Because this looks like homework, I won't give you a full answer, but just a hint. I also don't know what SD is (unless you mean Service-dominant logic, which is off topic here and doesn't seem applicable), but here's a method for propositional logic.

You could make a truth table of parts of your expression. Like this:

A | B | expr 1 | expr 2 | ...
--+---+--------+--------+-----
0 | 0 | ?      | ?      | ...
0 | 1 | ?      | ?      | ...
1 | 0 | ?      | ?      | ...
1 | 1 | ?      | ?      | ...

Now as expressions you can take first (A → B), which is a part of your theorem. Then you take ¬ (A → B), which you can, because you know the truth table for (A → B) - you just wrote it down. Like this, you proceed, until you have the full expression in the rightmost column.

If this column contains only 1, that means that the theorem is true for any values of A and B. Thus, the theorem would be proven.

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.