> AC@[ 3bjbjYY <;p\;p\[$666P$,6v,R((($X n((0999B((9999(@qE9uF0v9 ' 9 9<99v >: Homework 1 Propositional Logic The Language and Syntactic Proofs
In order to come up with a precise notion of proof, we shall have to construct a simple language, one which wears its logical properties on its sleeves, so to speak. For such a language to be successful it is absolutely essential that certain forms of ambiguity are prohibited. For example, consider the following English language sentence.
Im going to the store, and shes buying smokes, or Im watching T.V.
This sentence is ambiguous. If we use parentheses to disambiguate, on the one hand it could mean (Im going to the store) and (shes buying smokes, or Im watching T.V). From this reading of the sentence we would know that Im going to the store. If we parsed the sentence as (Im going to the store and shes buying smokes) or (Im watching T.V), we wouldnt know that Im going to the store.
By formalizing our language, we prohibit all such ambiguities.
Vocabulary: All capital english letters (A, B, C, . . . ,Z) are propositional variables, as well as all numerically subscripted Z s (Z1,Z2, Z3. . .).
A set of logical connectives: , , , !.
Formation rules:
(1) All propositional variables are wffs (well formed formulas) of L.
(2) If G is a wff, then G is a wff.
(3) If G and F are wffs, then (G F) is a wff.
(4) If G and F are wffs, then (G F) is a wff.
(5) If G and F are wffs, then (G ! F) is a wff.
(6) All and only the wffs of L are generated by the above 6 rules.
Intuitively, the logical connectives mean (respectively) not, and, or, and if... then. Thus, where P = Im going to the store, Q = shes buying smokes, and R = Im watching T.V. We can formalize both interpretations of the above sentence in this language. The first interpretation is equal to (P (Q R)) , while the second interpretation is equal to ((P Q) R) .
In the next two lectures will start to worry about the interpretation of the language L. Here we are just concerned with the syntax of L, given by the above six formation rules. We can think of the rules as giving us a procedure by which we construct, from the bottomup, sentences of our language. This procedure can be rigorously formalized as a natural deduction proof system. Each of the following rules corresponds to one of the clauses of our definition of wffhood.
Natural deduction formulation of the first 6 rules
Where G is a propositional variable,
________ n) G
n) G rule 1 G n, rule 2
m) G m) G
n) F n) F
(G F) m,n rule 3 (G F) m,n rule 4
m) G
n) F
(G ! F) m,n rule 5
A proof of well formedness is then defined as a numbered sequence of sentences such that each sentence follows by previously numbered sentences by the above rules.
For example, if I want to show that (P Q) is a sentence I have to construct the following proof.
1. P by rule 1
2. Q by rule 1
3. (P Q) 1,2 by rule 4
The m s and n s don t need to be distinct. To construct (P P) , we need only provide the following proof of wellformedness.
1. P by rule 1
2. (P P) 1, 1 by rule 4
Consider tBCD vwz
&*,.2HJVZbd'ۺǺۺӺӺӺۺӺӺǲۺӺӺӺh_COJQJh+OJQJ h+H*h_Ch_COJQJh+OJQJh+h+CJOJQJh+5CJOJQJhh5CJOJQJFCD vw
H+@@]@^@`gd_C@@]@^@gd_C`gd_C$a$'p
~0b>Zfnp~ (.48:<>hlnpt
hr
&''J'L''Uh+>*OJQJh_COJQJ^Jh+>*OJQJ h+>*h+OJQJh+OJQJ h+5h_Ch+L+,./0de>p.
T<\`&&&&'>'t''
(((((00
11111111gd_C`he more complicated wff, ~((P & Q) > (Q v R)). The proof looks like this.
1. P by rule 1
2. Q by rule 1
3. R by rule 1
4. (P Q) 1,2 by rule 3
5. (Q R) 2,3 by rule 4
6. ((P Q) ! (Q R)) 4,5 by rule 5
7. ((P Q) ! (Q R)) 6 by rule 2
Notice that parentheses must be added for applications of all rules except for rules 1 and 2.
Once you get the hang of doing such wellformedness proofs, you will see that they are very easy. It is very important to be able to do them though, for what follows. We can not know what a sentence means, unless we know how a sentence is constructed. What holds for our formal language holds for English as well. The meaning of a sentence is a function of the meanings of the words in the sentence and the way those words are put together. If we didn t have a tacit, or unconscious, knowledge of English syntax, we would not understand any sentences. Part of the goal of formal languages is to make explicit the procedures we follow subconsciously when we recognize that sentences are wellformed. While natural languages are incredibly more difficult than the formal language given here, it is likely that we follow a similar (albeit much more complicated) procedure every time we speak or understand a sentence.

Homework 1
Construct proofs of wellformedness for the following wffs.
1. (P Q)
2. (P ! Q)
3. (P Q)
4. ((P Q) R)
5. (P ! (P R))
6. P
7. (P P)
8. (Q (P ! (Q R)))
9. (R ! ((P Q) ! R))
10. (P ! (P P))
PAGE \* MERGEFORMAT 1
PAGE
PAGE 1
PAGE
PAGE 3
''''''''''''''''((000
111111111111111111122
222$2&2(20282>2@2B2D2V2X2Z2^2d2f2n2p2r2t222222222222222222222222222jh+Uh+5OJQJ\hhh+h_CY12*2J2~22222222222383:3<3N3P3R3h3j3l3~3&`#$$a$ ]^` gdh2223303234363:3<3>3J3L3N3R3T3`3b3d3f3h3l3n3z33~333333333ľľľıľľh_CmHnHujh+0JU*h:>0JmHnHu*
h+0Jjh+0JUjh2UmHnHu*h:>mHnHu*h2jh2Ujh+Uh+"~333333333$&`#$a$d< 00PBP/ =!"#$%Dp< 00PBP/ =!"#$%Dps666666666vvvvvvvvv666666>6666666666666666666666666666666666666666666666666hH66666666666666666666666666666666666666666666666666666666666666666p62&6FVfv2(&6FVfv&6FVfv&6FVfv&6FVfv&6FVfv&6FVfv8XV~ 0@ 0@ 0@ 0@ 0@ 0@ 0@ 0@ 0@ 0@ 0@ 0@ 0@ 0@_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@B420Header
H$6/Q620Header CharCJhPK![Content_Types].xmlN0EHJ@%ǎǢș$زULTB l,3;rØJB+$G]7O٭VvnB`2ǃ,!"E3p#9GQd; H
xuv 0F[,F᚜KsO'3w#vfSVbsؠyX p5veuw 1z@ l,i!b
IjZ29L$Z15xl.(zm${d:\@'23ln$^@^i?D&#td!6lġB"&63yy@t!HjpU*yeXry3~{s:FXI
O5Y[Y!}S˪.7bdn]671.
tn/w/+[t6}PsںsL.J;̊iN $AI)t2Lmx:(}\i*xQCJuWl'QyI@ھ
m2DBAR4 w¢naQ`ԲɁ
W=0#xBdT/.3F>bYL%˓KK6HhfPQ=h)GBms]_Ԡ'CZѨys
v@c])h7Jهic?FS.NP$
e&\Ӏ+I "'%QÕ@c![paAV.9Hd<ӮHVX*%A{YrAբpxSL9":3U5U
NC(p%u@;[d`4)]t#9M4W=P5*f̰lk<_XCwT%Ժ}B% Y,]
A̠&oʰŨ;\lc`,bUvPK!
ѐ'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!R%theme/theme/theme1.xmlPK!
ѐ' theme/theme/_rels/themeManager.xml.relsPK]
B)<)>< *5BBBBBMZZZ]''23+1~33$&*15<>BINTV]!!!!!t8@0(
B
S ?"7;ORgk( +

0
g
j
/9
.2@C
h
j
!
E
G
U
W
@C3333333333333wx
%(04=C :>
Tu
h_C+2IS@r r
rrBH@HHH @HH(@HHHH&UnknownG*Ax Times New Roman5Symbol3.*Cx Arial3*Ax TimesA$BCambria Math" h " "! J HP $P
2!xxHandout 1 Syntax of LPHILOSThomasOh+'0h
$0
<HPX`Handout 1 Syntax of LPHILOSNormalThomas2Microsoft Office Word@@0k@0k՜.+,0hp
The Ohio State University" Handout 1 Syntax of LTitle
!"#$%&'()*+,./12345679:;<=>?BRoot Entry F㖛D1Table WordDocument<SummaryInformation(0DocumentSummaryInformation88CompObjr
F Microsoft Word 972003 Document
MSWordDocWord.Document.89q