# Thread: Beginning Student in Propositional Logic: Problems Working Through Three Proofs

1. ## Beginning Student in Propositional Logic: Problems Working Through Three Proofs

I'm new to propositional logic and I've been struggling to find justifications for these three proofs. Can anyone help?

_____________________________

1. A

Therefore, B ⊃ (~ A ⊃ C)

Prove valid using only the rule of inference and the rules of replacement (cannot use Conditional or Indirect Proofs)

Here’s how I have it done right now:

1. A
2. A v (C v ~B) 1 Add
3. (C v ~B) v A 2 Comm
4. C v ( ~B v A) 3 Assoc
5. ( ~B v A) v C 4. Comm
6. (~B v ~ ~A) v C 5. DN
7. ~ (B • ~A) v C 6. DeM
8. (B • ~A) ⊃ C 7. Cont
9. B ⊃ (~A ⊃ C) 8. Exp

I ended up working backwards on this proof which explains why each justification derives from the preceding line. I don't see anything wrong with my justifications (though if there is please correct me), but I'm wondering if there is a more eloquent way to do this proof. Also, say I didn't want to work backwards. Obviously I would have to start with an Addition, but how would I go about choosing what to add to A?
______________________________

1. A v B
2. C ⊃ ~ A
3. D ⊃ E
4. ~ D ⊃ C
5. E ⊃ ~ A

Therefore, B

Prove valid using any of the rules of deductive logic
_____________________________________

~(~ T ⊃ ~ R) , ~ S v T , R ≡ S

Using Natural Deduction demonstrate that the following set of statements are inconsistent.

2. What does

stand for? Material implication?

/

What rules of replacement? Different textbook authors have different rules.

/

What "any" rules of deductive logic? Here's a rule of deductive logic:

If a formula B is a tautological consequence of a finite set of formulas G, then from G we may infer B.

So, since B is a tautological consequence of G = {AvB, C->~A, D->E, ~D->C, E->~A} we have that G proves B.

If you wish to see some easy reasoning though:

Since AvB, we only need to show ~A.
E implies ~A, so we only need to show also ~E implies ~A.
But D implies E, so ~E implies ~D, so, since ~D implies C, and C implies ~A, we have ~E implies ~A

/

What specific system of natural deduction?

Anyway, here's some basic reasoning:

Suppose ~(~T -> ~R).
So ~T & R.
Suppose R <-> S.
So S.
Suppose ~S v T
So T, which provides a contradiction.

3. ⊃ is the material implication. I'll start using -> in its place to avoid confusion.

Rules of Replacement are as follows:
Double Negation
DeMorgan's Theorem (two variations)
Commutation (two variations)
Association (two variations)
Distribution (two variations)
Contraposition
Implication
Exportation
Tautology
Equivalence

Valid Argument Forms of Inference:
Modus Ponens
Modus Tollens
Disjunctive Syllogism (two variations)
Simplification
Conjunction
Hypothetical Syllogism
Constructive Dilemma
About the specific system of Natural Deduction, I'm not sure. I typed exactly what it said on the sheet, though I assume it means use any of the ways of natural deduction emphasized in this section (the rules of replacement, valid argument forms of inference, and of conditional and implied proofs)

4. For your own sake, you need to write out, for yourself, each rule specifically, and understand why each one is valid.

And what is the difference in this system between conditional proof and implied proof? And does this system have any rules for indirect proof (sometimes called 'proof by contradiction'), and are there variations?

What is the rule in this system for putting a premise on a line?

DeMorgan's has two allowed variations?

Equivalence has two allowed variations?

And there is no rule of simplification for conjunctions?

And there is no rule of addition for disjunctions? And no other rules for disjunctions?

You need to be crystal clear about these things.

5. Originally Posted by coach2uf
1. A
Therefore, B ⊃ (~ A ⊃ C)
Prove valid using only the rule of inference and the rules of replacement (cannot use Conditional or Indirect Proofs)

Here’s how I have it done right now:

1. A
2. A v (C v ~B) 1 Add
3. (C v ~B) v A 2 Comm
4. C v ( ~B v A) 3 Assoc
5. ( ~B v A) v C 4. Comm
6. (~B v ~ ~A) v C 5. DN
7. ~ (B • ~A) v C 6. DeM
8. (B • ~A) ⊃ C 7. Cont
9. B ⊃ (~A ⊃ C) 8. Exp

I ended up working backwards on this proof which explains why each justification derives from the preceding line. I don't see anything wrong with my justifications (though if there is please correct me), but I'm wondering if there is a more eloquent way to do this proof. Also, say I didn't want to work backwards. Obviously I would have to start with an Addition, but how would I go about choosing what to add to A?
______________________________

1. A v B
2. C ⊃ ~ A
3. D ⊃ E
4. ~ D ⊃ C
5. E ⊃ ~ A

Therefore, B

Prove valid using any of the rules of deductive logic
_____________________________________

~(~ T ⊃ ~ R) , ~ S v T , R ≡ S

Using Natural Deduction demonstrate that the following set of statements are inconsistent.
This is Copi's notation he learned from Russel.
You fine in below.
1. A
2. A v (C v ~B) 1 Add
3. (C v ~B) v A 2 Comm
4. C v ( ~B v A) 3 Assoc
5. ( ~B v A) v C 4. Comm
6. ~B v (A v C) 5. Assoc
7, B ⊃ (~A ⊃ C) 6. Impl (twice)

6. ~(~ T ⊃ ~ R) , ~ S v T , R ≡ S

Using Natural Deduction demonstrate that the following set of statements are inconsistent.
You mean the preceding set of statements?

The derivation depends on whether ~ is taken as a primitive connective or if ~A is a contraction for A -> _|_, where _|_ denotes contradiction. I'll assume the latter, but it should not be too hard to change the derivation to the former style.

It is sufficient to show ~ S v T , R ≡ S |- ~ T ⊃ ~ R. So, assume ~T and R; one has to show _|_. Do reasoning by cases on ~ S v T. If T, then T and ~T give _|_. If ~S, then the assumption R together with R ≡ S give S, so again one has _|_.

7. Originally Posted by Plato
Copi's
Oh, okay, then cancel my admonishment to the poster.

But it would be helpful for posters to specify, such as saying "System found in Copi's 'Symbolic Logic' 4th edition" or whatever, so that it is clear exactly the rules and their exact formulation.

8. Originally Posted by emakarov
The derivation depends on whether ~ is taken as a primitive connective or if ~A is a contraction for A -> _|_, where _|_ denotes contradiction. I'll assume the latter
In Copi, '~' is primitive.