**Propositional Logic**

**Negation**

~F

~P

~S

She's not French.

It's not the case that

Pluto is a planet.

It's false that tomorrow

is Sunday.

**Conjunction**

Gene made a machine and

Joe made it go.

Gene made a machine but

Frances did some dances.

Gene made a machine, however

Heather found a feather.

G & J

G & F

G & H

**Disjunction**

H

v

G

H

v

T

H

v

L

You can have homefries or you

can have grits.

You can have either homefries

or tater-tots.

Unless you're going to have some

homefries, you should just leave.

**Conditional**

If it fits, then I sits.

I sits if it fits.

It fits only if I sits.

I sits, provided that

it fits.

It don't always fits, but

when it does, I sits.

F S

F S

F S

F S

F S

**Truth Tables for Propositions**

**Truth Table - A representation of every possible**

combination of truth values for the simplest

components of a complex statement.

combination of truth values for the simplest

components of a complex statement.

T

F

F

F

T T T

T F F

F T T

F F F

F

T

F

T

T

T

T

F

F

F

T

T

T T T

T T F

T F T

T F F

F T T

F T F

F F T

F F F

T

F

F

F T

F

T F

T

T F

F

F T

F

F T

F

F T

F

F T

F

2

Rule

n

&

&

**Truth Tables for Arguments**

We can use truth tables to determine whether or not an argument is valid.

Valid - if the premises

are true the con-

clusion MUST be

true.

OR

Valid - there's no way

for the conclusion to

be false if the pre-

mises are true.

If they serve pork at the dinner, then I won't eat.

If I don't eat, then we'll need to stop for food on the way home.

Therefore, if they serve pork at the dinner, then we'll need to stop for food on the way home.

If Darren knowingly plagiarizes an assignment, then he deserves a grade of zero for that assignment.

Darren did not knowingly plagiarize this assignment.

Therefore, Darren does not deserve a grade of zero for that assignment.

T

F

T

T

F

F

T

T

F

T

F

T

INVALID!

F

F

T

T

F

F

T

T

F

F

T

T

T

T

T

T

F

F

T

T

F

F

T

T

T

T

T

F

T

T

T

F

T

F

T

F

T

T

T

T

VALID!

Which means...

If we can find a line on the truth table where the premises are TRUE and the conclusion is FALSE, then we know the argument is INVALID!!!

**Proofs by "Natural Deduction"**

Say we want to prove a certain conclusion from a collection of premises, but it's not immediately clear how, and a truth table would be inconvenient...

We can prove that our conclusion follows validly from its premises by taking a series of smaller steps that we know are valid.

Some Basic Rules of Inference

Modus Ponens

P Q

P

Q

P Q / P // Q

T

T

T

T T

T

F

F

T F

F

T

T

F T

F

T

F

F F

Valid!!!

Modus Tolens

P Q

~Q

~P

P Q / ~Q // ~P

T

T

T

F

T

F

T

T

F

F

T

F

F

T

F

T

T

F

T

T

F

F

T

F

T

F

T

F

Valid!!!

Disjunctive Syllogism

P v Q

~P

Q

P v Q / ~P // Q

T

T

T

F

T

T

T

T

F

F

T

F

F

T

T

T

F

T

F

F

F

T

F

F

Valid!!!

(MP)

(MT)

(DS)

Hypothetical Syllogism

P Q

Q R

P R

P Q / Q R // P R

T

T

T T

T

T T

T

T

T

T

T T

F

F T

F

F

T

F

F F

T

T T

T

T

T

F

F F

T

F T

F

F

F

T

T T

T

T F

T

T

F

T

T T

F

F F

T

F

F

T

F F

T

T F

T

T

F

T

F F

T

F F

T

F

Valid!!!

(HS)

If Aaron gets the job, then Ben won't get the job.

If Carol gives him a good recommendation, then Ben will get the job. Aaron does get the job. Therefore, Carol did not give Ben a good recommendation.

Is this valid?

1) A ~B

2) C B

3) A // ~C

4) ~B 1,3 MP

5) ~C 2,4 MT

VALID!!!

Prove conclusion:

T

from premises:

F v (D T)

,

~F

,

D

1) F v (D T)

2) ~F

3) D // T

4) D T 1,2 DS

5) T 4,3 MP

1) (C M) (R P)

2) (C R) (R M)

3) (C P) ~M

4) C R // ~C

5) R M 2,4 MP

6) C M 4,5 HS

7) R P 1,6 MP

8) C P 4,7 HS

9) ~M 3,8 MP

10) ~C 6,9 MT

More Rules of Inference

Conjunction

(Conj)

P

Q

P & Q

~A

B v C

~A & (BvC)

T U

R S

(T U) & (R S)

Simplification

(Simp)

P & Q

P

(P Q) & (R S)

P Q

~B & (C v D)

C v D

Addition

(Add)

P

P v Q

P & Q

(P & Q) v (R S)

~B

~B v ~(C v D)

Constructive Dilemma

(CD)

(P Q) & (R S)

P v R

Q v S

[H (K v L)] & [(EvF) G]

H v (E v F)

(K v L) v G

~M v N

(~M S)&(N ~T)

S v ~T

1) (N B) & (O C)

2) Q (N v O)

3) Q // B v C

4) N v O 2,3 MP

5) B v C 1,4 CD

1) N (D & W)

2) D K

3) N // N & K

4) D & W 1,3 MP

5) D 4 Simp

6) K 2,5 MP

7) N & K 3,6 Conj

1) (C N) & E

2) D v (N D)

3) ~D // ~C v P

4) N D 2,3 DS

5) ~N 4,3 MT

6) C N 1 Simp

7) ~C 6,5 MT

8) ~C v P 7 Add

Using Assumptions in Formal Proofs

The basic principle behind any natural deduction is to show that the conclusion must be true without making any other assumptions besides the truth of the premises.

However...

There are some very useful natural deduction strategies that make use of

additional

assumptions.

We just have to make sure we're very careful about how we use these additional assumptions.

Conditional Proof

If high-tech products are exported to Russia, then domestic industries will benefit. If the Russians can effectively utilize high-tech products, then their standard of living will improve. Therefore, if high-tech products are exported to Russia and the Russians can effectively utilize them, then their standard of living will improve and domestic industries will benefit.

1) H D

2) U S // (H & U) (S & D)

3) H & U ASSUMP

4) H 3 Simp

5) D 1,4 MP

6) U 3, Simp

7) S 2,6 MP

8) S & D 7,5 Conj

9) (H&U) (S&D) 3-8 CP

If I can prove that something (S) follows from an assumption (A), then I can prove the conditional statement, "If A, then S."

Proof by Cases

If I have a disjunction, and I can show that the same statement follows if I assume

either

disjunct, then I can prove the statement must follow.

1) P v ~Q

2) P R

3) ~R Q // R

4) P ASSUMP

5) R 2,4 MP

6) ~Q ASSUMP

7) R 3,6 MT

8) R 1,4-7 PBC

Reductio Ad Absurdum

If I can show that assuming the negation of my conclusion leads to a naked contradiction, then I can prove my conclusion.

1) (A v B) (C & D)

2) C ~D // ~A

3) A ASSUMP

5) C & D 1,4 MP

6) C 5 Simp

7) ~D 2,6 MP

8) D 5 Simp

4) A v B 3 Add

9) D & ~D 7,8 Conj

10) ~A 3-9 RAA

n=1

T

F

T

F

T

F

n=2

T

F

T

F

T

F

T

F

n=3

T

F

T

F

T

F

T

F

T

F

T

F

T

F

T

F

n=4

Every time we add a new variable,

we double the number of lines in our truth table

Conditional Proof

If I can prove that something (S) follows from an assumption (A), then I can prove the conditional statement, "If A, then S."

Proof by Cases

If I have a disjunction, and I can show that the same statement follows if I assume

either

disjunct, then I can prove the statement must follow.

Reductio Ad Absurdum

If I can show that assuming the negation of my conclusion leads to a naked contradiction, then I can prove my conclusion.