> ac`g jbjbjVV >r<r<'CTTTTThhh8dDh0,HH4WWW$\ xTWWWWWTTWTTW`M 00 T TWWWWWWWWWW0WWWW WWWWWWWWW :
Propositional Logic Proof Theory: Rules with Discharge, Part 1 (! introduction)
As you ve probably discerned from doing the homework assignments, using truth tables to determine the validity of arguments can be very tedious. In L and many languages formed by extending L (adding to the syntax and semantics of L) logicians typically use the semantics of L to show that purported deductive arguments are not valid. However, to show that deductive arguments are valid, they usually utilize a system of deductive proof. We can define deductive entailment the following way:
Deductive entailment A set of sentences D, deductively entails a sentence G if and only if, there exists a proof of G resting upon a subset of the sentences in D in our proof system for L.(If this is the case we say D  G,  , is called single turnstile . We can also say that an argument with the sentences in D as premisses and G as a conclusion is deductively valid.)
Though we won t prove this result in this class, a two wonderful properties of L, and the proof system of L, are the soundness and completeness results. The obtaining of these results tell us that our proof system is good enough.
Soundness If D  G, then D = G.
Completeness If D = G, then D  G.
These two results tell us that the relations of deductive validity and semantic validity coincide. Soundness is good because it tells us that if we can use the truthtable method to determine that D does not semantically entail G then we know that there does not exist a proof in our system of G from D. Since semantic validity is taken as primary by most logicians (most logicians take the semantics to really specify the meanings of the logical constants), the soundness result is usually taken to be an assurance that every deduction in proofsystem in question is really an instance of validity. Likewise the completeness result is taken to show that the proof system in question is capable of illustrating all instances of validity.
Before we can appreciate the force of the soundness and completeness results we need to learn how to construct proofs in our system. First Ill give the formal definition of proof in our system and then I will explain how to use it in constructing proofs. Proof construction is very much a practical ability, so if you find the formal definition a bit Byzantine, dont worry too much. Most of us couldnt explain the physics involved in riding a bicycle, yet we can still ride them. However, as you start to work through the proofs it might be helpful to look back at the definition to gain a better understanding of what youre doing.
X is a proof of G from D if and only if
X is a numbered sequence of sentences such that:
(1) All of the premises in X are members of D, and the premises, if any, occur in the first lines of the proof.
(2) All arbitrary assumptions introduced for the rules elimination , ! introduction , or introduction are discharged at a succeeding line,
(3) All sentences in the proof which are neither premises at the beginning of the proof, nor arbitrary assumptions, are inferred by either derived or underived rules from a previous line not in the scope of assumptions already discharged by a derived or underived rule.
(4) The last line of the proof has G on it.
There are several terms of art in this definition. Rather than defining each one, I will proceed to give examples and explanations of proofs using following rules of inference.
Rules of Inference
In the statement of the rules below, the Greek letters are variables which stand for any wff of L. The lowercase English letters represent numerals. Note it is usually not the case that n = m + 1, and only necessarily the case that n > m in the rules elimination ! introduction , and introduction .
Reflexivity:
n. G
G n reflexivity
Elimination rules: Introduction rules:
m. G
n. (G F) n. F
G n elimination (G F) n, m introduction
n. (G F)
F n elimination
m.  G Assumption for elimination n. G
 (G F) n introduction

n.  Y n. F
o.  F Assumption for elimination (G F) n introduction


p.  Y
q. (G F)
Y nm,op, q elimination
m. (G ! F) m.  G Assumption for ! introduction
n. G 
F n,m ! elimination 
n. F
(G ! F) mn ! introduction
m. G m.  G Assumption for ( introduction
n. G 
( m,n elimination 
n.  (
(G mn ( introduction
________________________________________
Intuitionist Absurdity Rule: 
m. ( 
G m ( 
_______________________________________
Classical Double Negation Elimination Rule: 
n. G 
G n DNE 
______________________________________
The rules other than elimination , ! introduction , and ( introduction are exactly the same as those for L . elimination , ! introduction , and ( introduction are a little more difficult to than those of L, as they involve hypothetically assuming the truth of some sentence in the proof, and then drawing a line from the assumption to the subconclusion sanctioned by the rule of inference.
For example the following proof uses ! introduction.
Claim;  ((((P R) ! (P Q))
Proof:
1.  (((P R) assumption for ! introduction
2.  (P R) 1 DNE
3.  P 2 elimination
4.  (P Q) 3 introduction
5. ((((P R) ! (P Q)) 14 ! introduction
In the above proof we assume (((P R) in line one, and then prove from this (P Q). Then since we know that (P Q) is provable from (((P R), we discharge the initialFEYDF`
b
j
l
(*NPrVXdfi0ʸh6h
iOJQJh
iOJQJ h
i>*"hU&
h
i5CJOJQJ\aJ1hU&
hU&
5B*CJaJfHphq
1hU&
h6 5B*CJaJfHphq
h
i>CEprij02x@@]@^@gd6gd6$a$x
48JL>P " L N !!"!&!,!0!2!4!6!8!:!!T!`!j!l!v!!!!!ΰιιhGrOJQJhGr>*OJQJ^JhGr>*OJQJh
i>*OJQJhcN=OJQJhGrh
i>*OJQJ h
i5hcN=h
ih6h
iOJQJh6OJQJh
iOJQJ:<=>Qn p !&!! """D""""#d###B$^$z$$$``!!!!!!!!!""" """&"*","."0"2"4"6"8"D"T"V"^"`"b""""""""""""""#4#6#8#:#<#>#F#H#J#d############ȿȫȫޣޫȫhGrOJQJh
i>*OJQJhGr>*OJQJ^JhGr>*OJQJh
i>*OJQJ h
i>*hcN=h
ih
iOJQJh
iOJQJhGrOJQJhGrOJQJ^J?#######$$$$$$$$&$($B$z$~$$$$$$$$$$$$$$$$$$
%%%%"%(%*%,%.%0%2%B%J%L%x%z%%%%%%%%%%%%żűżҼ詞h^Sh
iOJQJh^SOJQJhGr>*OJQJ^Jh
i>*OJQJh
i>*OJQJhcN=h
ihGrOJQJ^JhGrOJQJh
iOJQJh
iOJQJhcN=OJQJ>$%%%%%&@&&~&&'d'''"((<))*j**+j+l+..gd[gdcN=gdI``%%%%&&&&&$&&&>&@&B&D&F&H&J&L&^&`&b&&~&&&&&&&&&&&&&&&&&&'
'ȿֳַ֯}tkhI>*OJQJhI>*OJQJ hI>*hIh
i jhGrOJQJhIOJQJhcN=OJQJhihIOJQJhIhcN=h
iOJQJh
i>*OJQJh
i>*OJQJ h
i>*h
ihGrh^SOJQJh
iOJQJhGrOJQJ^JhGrOJQJ*
'''' '"'*'D'R'V'd'l'p't'x''~'''''''''''''((䋃xpph\hhcN=>*OJQJhcN=OJQJhGrOJQJ jhGrOJQJh
iOJQJ jhGrOJQJ^J j^hIhI>*OJQJhIhI>* h
i>*hGrh
ihcN=hIhIOJQJ^JhihIOJQJ j^hIOJQJhIOJQJhIh
i>*OJQJh
iOJQJ(((2)4)8):)<)@)B)L)P)R)))r*v*x****+j+l++++L,N,,,,....////$/&/ԽԧԠԵԵzvqvjv jh[ h
i>*h[ h
iH* jh^Sh^Sh
ihcN=>*OJQJ hcN=>*hcN=hhcN= j^hhcN=OJQJhcN=OJQJhihcN=OJQJhhcN=>*OJQJhcN=OJQJhhcN=OJQJhcN=>*OJQJ j^hhcN=>*OJQJ).//D/R///0N000MMMMFNrNNNOO:OHOdOrOOOp`p``gd[&/./0/8/:/D/N/R/V/\/`/f/h///////////000 00040N0R0V0Z0`0b0j0l0t0v000000D1R1111112JJVJJJJJJK"K$K(K6K8KHKPKXKZKKKLLLNLLLZMMMMMMMMMMFNJNrNvN h
i5U jh[ h
i>*h[h
iZ assumption by drawing the line from 1 to 4. Thus, the conclusion does not rest upon (((P R) as a premise, as the conclusion just says that if (((P R) is true then (P Q) must be true. The truth of the conclusion however does not depend on (((P R) being true though. With the rule of ! introduction we can see the importance of the rule of reflexivity. Since (P ! P) is clearly a logical truth, we should be able to prove it not resting on any premises, in this manner:
Claim;  (P ! P)
Proof:
1.  P assumption for > introduction
2.  P 1 reflexivity
3. (P ! P) 12 > introduction
The following proof uses ( introduction.
Claim; (P ! Q), (Q  (P
Proof:
1. (P ! Q)
2. (Q
3.  P assumption for ( introduction
4.  Q 1,3 ! elimination
5.  ( 2, 4 ( elimination
6. (P 35 ( introduction
This rule of inference is very intuitive if you think about it. If we were to reason through the above proof the mental process would go like this. O.K. We know that if P then Q is true, and we also know that it is not the case that Q is true. Well let s suppose that P were true. But then if P were true, then Q would also have to be true (since we know that if P then Q is true). But then Q and it is not the case that Q would be true. Well since Q and it is not the case that Q can never be true then the original supposition that P is true must have been completely wrong. Therefore if it s true that if P then Q and it s true that it is not the case that Q , then it must be true that it is not the case that P .
Our last rule of inference, elimination is also very intuitive if you think about it. It says that if a disjunction is true, and you can prove some sentence from each disjunct, then that sentence is itself true. For example:
Claim: (P Q), (P ! R), (Q ! R)  R
Proof:
1) (P Q)
2) (P ! R)
3) (Q ! R)
4)  P assumption for elimination
5)  R 2,4 ! elimination
6)  Q assumption for elimination
7)  R 3,6 ! elimination
8) R 1, 45, 67 elimination
Reasoning through this proof in natural language would look like this. Suppose that P or Q , if P then R , and if Q then R are all true. Now suppose that P is true, then it follows (since if P then R is true) that R is true. Now suppose that Q is true, then it follows (since if Q then R is true) that R is true. Well since we know that either P or Q is true, then in either case R must be true.
Things to watch out for. (1) Our definition of proof says that any assumption introduced for later discharge must be discharged at a succeeding line. For example, the following proof is incorrect.
1. (P ! Q)
2.  P assumption for ! introduciton
3. Q 1, 2 ! elimination
If this were a correct proof it would mean that the truth of if P the Q ensured the truth of Q , which is crazy.
(2) Clause 3 of the initial definition of proof is hard for some people to wrap their mind around. However, given our conventions for reading the schematic rules of inference it can easily be seen what clause 3 prohibits. Basically, you should never have rows of discharge lines overlapping like this:



 
 


Assumptions introduced for later discharge in the scope of another assumption introduced for discharge should always be discharged prior to the assumption introduced earlier. An instance of this correct pattern will look like this:

 
 
 

Here s an example of a correct proof that does this.
Claim: (R ! (P ! (Q (Q)))  (R ! (P)
Proof: 1. (R ! (P ! (Q (Q)))
2.  R assumption for ! introduction
3.  (P ! (Q (Q)) 1,2 ! elimination
4.   P assumption for ( introduction
5.   (Q (Q) 3,4 ! elimination
6.   Q 5 elimination
7.   (Q 5 elimination
8.   ( 6,7 ( elimination
9.  (P 48 ( introduction
10. (R ! (P) 29 ! introduction

Homework 9
1. (P ! Q), (Q ! R)  (P ! Q)
2.  ((P (P) ! R)
3. (P ! Q), (R ! (Q)  (P ! (R)
4. (P ! Q)  ((Q ! R) ! (P ! R))
PAGE \* MERGEFORMAT 6
PAGE
PAGE 6
vN~NNNNNNNOOOO(O*O4O6O:ODOHOLOTOVOdOhOjOlOrOOOOOOOOOOPPP
PPPP0P2P8P:PJPLPNPPPRQQQQQQRXRjRRSSTUpVtVXXXXX,X.X>X@XRX\XlXnXhS jhT j^h% jh%h% h
i>* jh[hTh[h
iPO2PhPjP4V6VXXRX`XXXXX*YxYYYY$]&]^^^_@@]@^@gdSgdS``gdTp`pnXXXXXXXYY*Y`YYYYYDZZZ[[[@\~\^^^^^_4_6_(b2bVeXelenevexeeeeeeeeeeeeeeeeeff:f>fJfLfTfVfXfZfnfpffffffffffg
gggg2g~ggg jhshs jh6gh6g h
i>* h
i5hSh
iT_P_R_:`<`bbbbbbbbbbddddddddVeXeee`gdS@@]@^@gdSe:fff2gnggg(hnhph\iritiii jdjfjjjljpjrjvjxjj~jgdPogdV`ggggggggh
hh(h,h.h0h:h6666666666666666666666666666666666666666666666666hH66666666666666666666666666666666666666666666666666666666666666666p62&6FVfv2(&6FVfv&6FVfv&6FVfv&6FVfv&6FVfv&6FVfv8XV~_HmH nH sH tH D`DNormal1$CJ_HhmH sH tH DA`DDefault Paragraph FontViV
0Table Normal :V44
la(k (
0No List<& <Footnote Reference.O. WP_Normal4 @4Footer
!.)@!.Page Number222WP_Footnote4@B460Header
H$6oQ660Header CharCJhPK![Content_Types].xmlN0EHJ@%ǎǢș$زULTB l,3;rØJB+$G]7O٭V$!)O^rC$y@/yH*)UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSebORD۫qu gZo~ٺlAplxpT0+[}`jzAV2Fi@qv֬5\ʜ̭NleXdsjcs7f
W+Ն7`gȘJjh(KD
dXiJ؇(x$(:;˹!I_TS1?E??ZBΪmU/?~xY'y5g&/ɋ>GMGeD3Vq%'#q$8K)fw9:ĵ
x}rxwr:\TZaG*y8IjbRcXŻǿI
u3KGnD1NIBs
RuK>V.EL+M2#'fi~Vvl{u8zH
*:(W☕
~JTe\O*tHGHY}KNP*ݾ˦TѼ9/#A7qZ$*c?qUnwN%Oi4=3N)cbJ
uV4(Tn
7_?mٛ{UBwznʜ"ZxJZp;{/<P;,)''KQk5qpN8KGbe
Sd̛\17 pa>SR!
3K4'+rzQ
TTIIvt]Kc⫲K#v5+D~O@%\w_nN[L9KqgVhn
R!y+Un;*&/HrT >>\
t=.Tġ
S; Z~!P9giCڧ!# B,;X=ۻ,I2UWV9$lk=Aj;{AP79s*Y;̠[MCۿhf]o{oY=1kyVV5E8Vk+֜\80X4D)!!?*fv
u"xA@T_q64)kڬuV7t'%;i9s9x,ڎ45xd8?ǘd/Yt&LILJ`& Gt/PK!
ѐ'theme/theme/_rels/themeManager.xml.relsM
0wooӺ&݈Э5
6?$Q
,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}$b{P8g/]QAsم(#L[PK![Content_Types].xmlPK!֧60_rels/.relsPK!kytheme/theme/themeManager.xmlPK!0C)theme/theme/theme1.xmlPK!
ѐ' theme/theme/_rels/themeManager.xml.relsPK]
1( *5BBBE!#%
'(&/vNnXgjj !"$68;=$.O_e~jj#79:<$&*16<>E!!!t8@0(
B
S ?(+KN;"G"&&'''''''''/(2(y}Rd{)+IN38KMf=?M!e!%%&&/&3&V&Z&t&x&&&&&'''''''''/(2(3333333333333333333333333333334&4&<&<&?&@&S&&&&&&&&s''''''''''''''''''''''''''''''''''''(((#(,(2(U&
6 %WIcd7cN=jFxQ^SGY
i9oEp9`pGrsPo[VS6giT16''@&&&&oooooi
iii
1(pp@ppppp(@pppp<@p p"p$p&p(p*p,p.p0pJUnknownG*Ax Times New Roman5Symbol3.*Cx Arial3*Ax TimesA$BCambria Math" h*H4
a!H!H! ''J HP
$P2!xxHandout 1 Syntax of LPHILOSJon CogburnOh+'0
<H
T`hpxHandout 1 Syntax of LPHILOSNormalJon Cogburn13Microsoft Office Word@CP1@#O@ M!՜.+,0hp
The Ohio State UniversityH'Handout 1 Syntax of LTitle
!"#$%&'()*+,./0123456789:;<=>@ABCDEFGHIJKLMNOQRSTUVWYZ[\]^_bRoot Entry F Md1Table? WordDocument>SummaryInformation(PDocumentSummaryInformation8XCompObjr
F Microsoft Word 972003 Document
MSWordDocWord.Document.89q