PHIL 012 – Symbolic Logic

March 30, 2001

Announcements

Exam 1 – hand back Monday

Homework 7 – I’ll hand back at the end of class

Homework 9

  • Due Monday 1-22 except #15, 17, 21. Note that #2 is an exercise.
  • Also, note that the proofs required in this homework set are informal.

Sara Leland will be out of town next week. Her office hours will be cancelled. However, she’ll have extra hours on Saturday 4/7 at 3:00.

Translation Exercises

1. If a is a tetrahedron then it is in front of d.

5. c is to the right of d only if b is to the right of c and left of e.

Other translation exercises

4.4 Methods of Proof involving  and 

Modus Ponens:

PQ

P

 Q

Later, we will call this Conditional Elimination ( Elim).

Biconditional Elimination:

PP

PQorQP

 Q Q

This follows from the fact that PQ (and QP) state(s) that P and Q have the same truth conditions. So, if we know one of them (i.e., P), then we know the other (i.e., Q), and vice versa.

Other Valid Steps

1.P  QQ P(Contraposition)

This follows from the fact that P  Q states that if you have P, you must also have Q (see Modus Ponens, above). Therefore, it also follows that if you don’t have Q, you can’t have P either.

2.P  QP  QAlready discussed

3.(P  Q)P Q

This follows from the fact that,

(P  Q)(P  Q)See rule 2, above

and,

(P  Q)(P Q)DeMorgan’s Theorems

4.P  Q(P  Q)  (Q  P)Already discussed

5.P  Q(P  Q)  (P Q)

This follows from the truth table for P  Q

PQP  Q

TT T(P  Q)

TF F

FT F

FF F(P Q)

Method of Conditional Proof

  • The method of conditional proof is one more method of proof that involves an assumption (in addition to  Elim and  Intro).
  • Basically it is an expression of Modus Ponens and is simply the observation that if you can get Q by assuming P, you know that P  Q.
  • When we get to formal proofs, we will refer to this proof as Conditional Introduction ( Intro)

Example:

  • Suppose we are given as premises A  B and B  C.
  • Just by thinking about it, we can see that if these premises are true, A  C must also be the case. But how can we prove it?
  • In addition to our premises, let’s also assume A and try to show that C follows. If we can show that by assuming A we can conclude C, we will have proven A  C by the method of conditional proof.
  • Assume A.
  • Now we know,

A  B(premise)

A(assumption

We can therefore conclude

B(modus ponens)

  • Now we also know

B  C(premise)

B(previous step)

So, we can conclude

C(modus ponens)

  • Since we have been able to prove, given our premises, that by assuming A, we can validly conclude C, we have shown that C follows from A. In other words, A is a condition of C or, A implies C.
  • Symbolically, A  C.
  • Note that this method of proof also works for contraposition.

Homework Examples

Problem 16, #1

Prove Modus Tollens: From A  B and B infer A.

We are given A  B and B. We could prove this a number of ways, but here is one. We know that A  B is equivalent to A  B. Now, considering the truth table for A  B, in order to make this statement true (which it is), one side or the other must be true. However, we know that B is true, therefore B is false. Therefore, in order to make the disjunction true, A must be true. Therefore A.

Problem 20, #1

Prove that A  (B  A) is a logical truth.

Recall that we prove that a statement is a logical truth by proving it by starting with no premises.

The only way to prove something by starting with no premises is to prove it by starting out with an assumption.

We know of three methods of proof involving assumptions,  Intro,  Elim, and now Conditional Proof ( Intro). Let’s use the last method.

In order to use the method of conditional proof, we assume the antecedent and then prove that the consequent follows from it. The antecedent of the conditional we’re trying to prove is A, so we’ll start by assuming A.

Now, all we know is A. How are we going show that B  A from A?

Note that what we have here is another conditional, B  A.

There’s no reason why we can’t go down another level in our method of conditional proof.

So, we’ll assume B.

Now, we already know A. Thus, we have shown that given B, we can prove A (because we already know A, having assumed it). Therefore, we have shown that B  A, by the method of conditional proof.

Now that we have proven B  A, given the fact that we have proven this by assuming A, we have also shown that B  A follows from the assumption of A. Therefore, we have proven A  (B  A) by the method of conditional proof.

Because we have been able to prove A  (B  A) from no premises, we have shown that it is a logical truth.

This might be a little clearer if stated formally. So (anticipating 4.5),

1. A

2. B

3. AReit. 1

4. B  A Intro [PAM1]2-3

5. A  (B  A) Intro 1-4

Note that you don’t have to do the formal version for Problem 20. I’m only showing in case it helps make the proof clearer for some.

[PAM1]1Conditional Proof