Sentential logic derivations?

  • #1
how do i prove the following is a theorem in SD
[(A -> B)->A]->A
... i started off by assuming [(A -> B)->A] then assume ~A to try to derive A in the end... but now i'm stuck :(

and also:

Suppose we dropped from SD the rule for vE, and adopted in its place the rule of Disjunctive Syllogism (DS), thus giving a modified system SD. Show that
you can derive the SD rule for vE in SD.

I have no idea how to even approach the second question.. any help would be greatly appreciated.. thanks! :D
 

Answers and Replies

  • #2
sylas
Science Advisor
1,646
7
how do i prove the following is a theorem in SD
[(A -> B)->A]->A
... i started off by assuming [(A -> B)->A] then assume ~A to try to derive A in the end... but now i'm stuck :(

and also:

Suppose we dropped from SD the rule for vE, and adopted in its place the rule of Disjunctive Syllogism (DS), thus giving a modified system SD. Show that
you can derive the SD rule for vE in SD.

I have no idea how to even approach the second question.. any help would be greatly appreciated.. thanks! :D

I am pretty sure this should be in the homework section, and have requested it to be moved. But in any case, it would be a good idea to use the homework template to show your work so far. The template requests you to provide the following sections:

Homework Statement



Homework Equations



The Attempt at a Solution


You should also describe your terms. I am pretty sure you must be using the text book The Logic Book by Bergmann, Moor and Nelson, or something like it. Sentential logic is often also called propositional logic. There are a number of different equivalent proof systems for SL, or PL. Your reference to SD is probably the "Derivation System" described in chapter 5. This proof system has rules for "introduction" and "exit" of the various connectives. Is that correct?

"Disjunctive syllogism" (DS) is an additional rule that you can add to the system SD, which still proves all the same theorems, but lets you do so faster and more easily. The second question asks if you can derive the rule for "or Exist" (vE) by using SD+DS-vE.

If I have understood the context of your question, and if you can show a bit more about what you have done so far, we may be able to help.

Cheers -- sylas
 
  • #3
12
0
I get the feeling that I am in this person's class. If so here is the question:

Suppose we dropped from SD the rule for vE (Disjunction Elimination), and adopted in its place the rule of Disjunctive Syllogism, thus giving a modified systemd of SD*. Show that you can derive the SD rule for vE in SD*.

All terms come from the Bergmann Logic Book. All the basic Derivation rules can be used except vE (duh). Furthermore, Modus Tollens, Hypothetical Syllogism and Disjunctive Syllogism can be used as well as what the book describes as Rules of Replacement. The rules of Replacement concern how certain things such as P -> Q can be replaced by ~P v Q. Essentially, they are all the logical equivalences that exist in SD.

There is nothing more to the question but I'm not going to add a solution because I feel obliged not to give away answers to people I'm actually in a class with. I'm sure you guys can do it and save me my conscience.
 
  • #4
12
0
Since he already made an attempt to find the solution to the first question I'm going to help out and post my answer for you guys to help me out and him at the same time.

Question: Show that [(A -> B) -> A] -> A is a theorem of SD.

Relevant Equations: All rules of SD found in the Logic Book. This includes all the ones in the above post BUT vE is not excluded.

The Attempt at a Solution:

1. [(A -> B) -> A] Assume
2. ~A Assume
3. ~(A->B) Modus Tollens from 1,2
4. ~(~AvB) Implication from 3
5. ~~A & ~B De Morgan from 4
6. ~~A & Elimination from 5
7. A Double Negation from 6
8. ~A Reiteration from 2
9. A ~ Elimination from 2-8
10. [(A -> B) -> A] -> A -> Introduction from 1, 9

Since this began with an empty set the final result must be a theorem of SD.
 
  • #5
12
0
Since he already made an attempt to find the solution to the first question I'm going to help out and post my answer for you guys to help me out and him at the same time.

Question: Show that [(A -> B) -> A] -> A is a theorem of SD.

Relevant Equations: All rules of SD found in the Logic Book. This includes all the ones in the above post BUT vE is not excluded.

The Attempt at a Solution:

1. [(A -> B) -> A] Assume
2. ~A Assume
3. ~(A->B) Modus Tollens from 1,2
4. ~(~AvB) Implication from 3
5. ~~A & ~B De Morgan from 4
6. ~~A & Elimination from 5
7. A Double Negation from 6
8. ~A Reiteration from 2
9. A ~ Elimination from 2-8
10. [(A -> B) -> A] -> A -> Introduction from 1, 9

Since this began with an empty set the final result must be a theorem of SD.
 
  • #6
9
0
Knark's solution makes use of SD+ concepts (e.g. Modus Tollens.)

Since the answer asks for the use of SD, are we to assume that such a concepts of SD+ may be cited, without requiring the appropriate subderivation?
 
  • #7
12
0
Well every thing that can be done using SD+ can also be done using SD, it would simply take a little more time. But I believe you are right and that it should be done in only SD so I will rework it. Thanks for catching that.
 

Related Threads on Sentential logic derivations?

  • Last Post
Replies
0
Views
2K
Replies
4
Views
2K
Replies
0
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
1K
Replies
5
Views
2K
Replies
4
Views
993
  • Last Post
Replies
1
Views
929
  • Last Post
Replies
1
Views
1K
Top