Lecture Notes PHIL 243 - Natural Deduction I Gregory ch 4 PDF

Preview

Summary

Dr. Sarah Hoffman lecture notes for Logic II...

Description

Classical Propositional Logic – Natural Deduction - TThe he Derivation System SD

In SD we develop techniques that look more like the kind of reasoning we do everyday, instead of truth-table and other semantic tools. IN the next module on metatheory we will be investigating the relationship between our system of derivation rulesSD and the semantic properties of the language S. SD is a system of derivation rules that tell us when we can derive one sentence from otherson the basis of their syntax.

The simplest rule is REITERATION: Reiteration (R) i

ℙ

Ø ℙ

iR

The Ø indicates the sentence that the rule says we are allowed to derive from the one(s) above. It is only when you already have the sentence(s) above that the rule justifies the sentence that the Ø points at This vertical line of scope indicates a relationship of dependence , everything to the right of it is in its scope. This horizontal line indicates the end of the primary assumptions Example: 1 2

A Ù (B ® C) FÚG

Primary Assumption

3

A Ù (B ® C)

1 Reiteration

Primary Assumption

Number each line so you can refer back to them This is where you JUSTIFY each line in your derivation Normally we will shorten our justifications like this: 1 2

A Ù (B ® C) FÚG

P

3

FÚG

2R

P

We also have in SD derivation rules that allow us to introduce and eliminate each of the connectives of SL.

Introduction and elimination rules for ‘Ù’ Conjunction Introduction (ÙI)

Conjunction Elimination (ÙE) OR

i

ℙ

i

ℙÙℚ

j

ℚ

Ø

ℙ

Ø

ℙÙℚ

i, j ÙI

Example:

1 (A Ú B) Ù ¬A

P

2 (A Ú B)

1 ÙE

3 ¬A

1 ÙE

4 ¬ A Ù (A ÚB)

3, 2 Ù I

i i ÙE

ℙÙℚ

Ø ℚ

i ÙE

Introduction and Elimination rules for ‘®’ Conditional Elimination (®E)

Conditional Introduction (®I)

i

ℙ®ℚ

i

ℙ

j

ℙ

j

ℚ

Ø

ℚ

I, j ®E

Ø ℙ®ℚ

Examples:

1 2

1 (A ® (B Ù C)) 2 A

P P

3

1, 2 ®E

(B Ù C)

4 B

3 ÙE

5 C

3 ÙE

6 (C Ù B)

4, 5 ÙI

B® ¬A ¬A®C

P P

3

B

A

4

¬A

1,3®E

5

C.

2,4®E

6

B®C

3-5 ®I

i—j ®I

Introduction and Elimination rules for ‘¬’ Negation Introduction (¬I)

Negation Elimination (¬E)

ℙ

i

ℙ

i

ℚ ¬#ℚ

j Ø

ℚ

¬#ℙ

¬#ℚ

j Ø

i—j ¬ I

¬#ℙ

i—j ¬E

Introduction and Elimination Rules for ‘Ú’ Disjunction Introduction (ÚI)

i

ℙ

Ø

ℙ Ú ℚ

iÚI

Disjunction Elimination (ÚE)

i

ℙ

Ø

ℚ Ú #ℙ

i iÚI

ℙ Ú #ℚ

j

ℙ

k

ℝ

l

ℚ

m

ℝ

Ø

#ℝ

I, j-k, l-m Ú E

Watch the recorded mini lecture to see me work through examples of these rules and the last two for the material biconditional!

Introduction and Elimination Rules for ‘«’ Biconditional Introduction («I)

i

ℙ

j

ℚ

k

ℚ

l

ℙ

Ø ℙ « #ℚ

i—j, k—l «I

Biconditional Elimination («E)

OR i

ℙ«ℚ

i

ℙ«ℚ

j

ℙ

j

ℚ

Ø

ℚ

Ø

ℙ########

i, j «E

i, j « E...