1TheFoundations:LogicandProofs

1.1PropositionalLogic

1.2PropositionalEquivalences

1.3PredicatesandQuantifiers

1.4NestedQuantifiers

1.5RulesofInference

1.6IntroductiontoProofs

1.7ProofMethodsandStrategyRulesofInference

Rosen6thed.,§1.5Argument(論證)Asequenceofstatementsthatendwithaconclusion.“Ifyouhaveacurrentpassword,thenyoucanlogontothenetwork.”“Youhaveacurrentpassword.”Therefore“Youcanlogontothenetwork.”ArgumentformAnargumentforminpropositionallogicisasequenceofcompoundpropositionsinvolvingpropositionalvariables.Anargumentformisvalidifnomatterwhichparticularpropositionsaresubstitutedforthepropositionalvariablesinitspremises,theconclusionistrueifthepremisesarealltrue.Correspondingtautology:((p1)(p2)…(pn))qNature&ImportanceofProofsInmathematics,aproofis:acorrect(well-reasoned,logicallyvalid)andcomplete(clear,detailed)argumentthatrigorously&undeniablyestablishesthetruthofamathematicalstatement.Whymusttheargumentbecorrect&complete?Correctnesspreventsusfromfoolingourselves.Completenessallowsanyonetoverifytheresult.Inthiscourse(&throughoutmathematics),averyhighstandardforcorrectnessandcompletenessofproofsisdemanded!!Overviewof§1.5Methodsofmathematicalargument(i.e.,proofmethods)canbeformalizedintermsofrulesoflogicalinference.Mathematicalproofscanthemselvesberepresentedformallyasdiscretestructures.Wewillreviewbothcorrect&fallaciousinferencerules,&severalproofmethods.InferenceRules-GeneralFormAnInferenceRuleisApatternestablishingthatifweknowthatasetofantecedentstatementsofcertainformsarealltrue,thenwecanvalidlydeducethatacertainrelatedconsequentstatementistrue.antecedent1

antecedent2…

consequent“”means“therefore”SomeInferenceRules

p RuleofAddition

pqpq RuleofSimplification

pp RuleofConjunction

q

pqSyllogismInferenceRulespq Ruleofhypothetical

qr syllogism假言三段論

prpq Ruleofdisjunctive

p syllogism析取三段論

qAristotle

(ca.384-322B.C.)常見推理定律附加律 A(A∨B)化簡律 (A∧B)A假言推理

(A→B)∧AB拒取式 (A→B)∧?B

?A析取三段論 (A∨B)∧?B

A假言三段論

(A→B)∧(B→C)(A→C)等價三段論 (A?B)∧(B?C)(A?C)構造性兩難 (A→B)∧(C→D)∧(A∨C)(B∨D)構造性兩難(特殊形式) (A→B)∧(?A→B)∧(A∨?A)B破壞性兩難 (A→B)∧(C→D)∧(?B∨?D)(?A∨?C)FormalProofsAformalproofofaconclusionC,givenpremisesp1,p2,…,pn

consistsofasequenceofsteps,eachofwhichappliessomeinferenceruletopremisesorpreviously-provenstatements(antecedents)toyieldanewtruestatement(theconsequent).Aproofdemonstratesthatifthepremisesaretrue,thentheconclusionistrue.推理的形式結構前提：A1,A2,A3,…,Ak

結論：B推理的形式結構：(A1∧A2∧A3∧…∧Ak)→B一個推理是正確的，當且僅當推理的形式結構是永真式UsingRulesofinferencetoBuildArgumentsThestepsofargumentsaredisplayedonseparatelines,withthereasonforeachstepexplicitlystated.推理（舉例）例：下午小王或去看電影或去游泳。他沒去看電影。所以，他去游泳了。設：p：小王下午去看電影

q：小王下午去游泳前提：p∨q，

?p

結論：qProofExamplecont.Letusadoptthefollowingabbreviations:sunny=“Itissunny”;cold=“Itiscold”;

swim=“Wewillswim”;canoe=“Wewillcanoe”;early=“Wewillbehomeearly”.Then,thepremisescanbewrittenas:

(1)sunnycold(2)swimsunny

(3)swimcanoe(4)canoeearlyProofExamplecont.Step

Reason

1.sunnycold

Premise#1.

2.sunny

Simplificationof1.

3.swimsunny

Premise#2.

4.swim

Modustollenson2,3.

5.swimcanoe

Premise#3.

6.canoe

Modusponenson4,5.

7.canoeearly

Premise#4.

8.early

Modusponenson6,7.ProofExampleStep

Reason

1.pq

Premise#1.

2.

q

p

Contrapositiveof1.

3.pr

Premise#2.

4.qr

Hypotheticalsyllogismusing2,3.

5.rs

Premise#3.

6.qs

Hypotheticalsyllogismusing4,5.

推理的形式結構前提：A1,A2,A3,…,Ak

結論：B推理的形式結構：(A1∧A2∧A3∧…∧Ak)→B一個推理是正確的，當且僅當推理的形式結構是永真式推理定律（舉例）(p∨q)∧?pq(p∨q)∧?p→q

是永真式pqp∨q?p(p∨q)∧?p(p∨q)∧?p→q

001101010111110001001111常見推理定律附加律 A(A∨B)化簡律 (A∧B)A假言推理

(A→B)∧AB拒取式 (A→B)∧?B

?A析取三段論 (A∨B)∧?B

A假言三段論

(A→B)∧(B→C)(A→C)等價三段論 (A?B)∧(B?C)(A?C)構造性兩難 (A→B)∧(C→D)∧(A∨C)(B∨D)構造性兩難(特殊形式) (A→B)∧(?A→B)∧(A∨?A)B破壞性兩難 (A→B)∧(C→D)∧(?B∨?D)(?A∨?C)推理規則前提引入規則：在證明的任何步驟上都可以引入前提結論引入規則：在證明的任何步驟上所得到的結論都可以做為后繼證明的前提置換規則：在證明的任何步驟上，命題公式中的子公式都可以用與之等值的公式置換，得到公式序列中又一個公式分離規則(假言推理)已知(A→B)，A，則有B。證明(舉例)

前提：p∨q，

?p

結論：q

證明：(1)p∨q

前提引入

(2)?p前提引入

(3)q(1)(2)析取三段論證明(舉例、續)

前提：(p∧q)

→r，

?s∨p，q

結論：s→r

證明：(1)?s∨p

前提引入

(2)s→p(1)置換

(3)(p∧q)

→r

前提引入

(4)q→(p→r)

(3)置換

(5)q

前提引入

(6)p→r(4)(5)假言推理

(7)s→r(2)(6)假言三段論證明(舉例、續)證明：(p∧q)

→rq→(p→r)(p∧q)

→r

?(p∧q)∨r(蘊涵等值式)

(?p∨?q)∨r(德●摩根律)

?q∨(?p∨r)

(交換律、結合律)

q→(?p∨r)

(蘊涵等值式)

q→(p→r)

(蘊涵等值式)總結等值式（16組、24條）冪等律、交換律、結合律、分配律、吸收律；雙重否定律、德●摩根律；零律、同一律、排中律、矛盾律；蘊涵等值式、等價等值式、假言易位、等價否定等值式歸謬論推理定律（9條）附加、化簡假言推理、拒取式、析取三段論、假言三段論、等價三段論、構造性兩難（特殊形式）、破壞性兩難例以下命題已經成立，求誰是作案兇手：(1）甲或乙作的案(2）如甲作的案，作案時間應在午夜后(3）若乙證詞正確，則午夜燈光未滅(4）若乙證詞不正確，作案時間不在午夜之后(5）午夜燈光滅了例（續）命題符號：

A：甲作的案

B：乙作的案

C：作案時間在午夜后D：乙的證詞正確

E：午夜燈光滅

則以上五句話成為五個命題（1）

A∨B（2）

A→C（3）

D→?E（4）

?

D→?C（5）

E

從而可以演繹出B，即是B作的案。推理規則附加前提推理規則(簡稱CP規則)

如果，AB，則A→B反證推理規則

如果，?

AF，則A例給出?(A?B),?BC,?C?A的證明例給出的證明A1(

A2

A3),A4

A1,

A2

A4

A3例給出的證明A1?

A2,A2?

A3,

A3

?

A4

?

A1習題證明下面的等值式：

(1)(p→q)∧(p→r)p→(q∧r)(2)(p∧?q)∨(?p∧q)(p∨q)∧?(p∧q)構造下面推理的證明：

(1)前提：p→(q→r)

，

p，q

結論：r∨s(2)前提：p→q，?(q∧r)，r

結論：?p例：有一個邏輯學家誤入某部落，被拘于勞獄，酋長意欲放行，他對邏輯學家說：“有兩門，一為自由，一為死亡，你可任意開啟一門。為協助你脫逃，今加派兩名戰士負責解答你所提的一個問題。惟可慮者，此兩戰士中一名天性誠實，一名說謊成性，今后生死由你自己選擇。”邏輯學家沉思片刻，即向一戰士發問，然后開門從容離去。該邏輯學家應如何發問？解：邏輯學家手指一門問身旁的一名戰士說：“這扇門是死亡門，他（指另一名戰士）將答‘是’，對嗎？”當被問戰士回答“對”，則邏輯學家開啟所指的門從容離去。當回答“否”，則開啟另一扇門從容離去。分析P：被問戰士是誠實人Q：被問戰士的回答是“是”R：另一名戰士的回答是“是”S：這扇門是死亡之門PQRS0011010010011110一階謂詞推理證明一階邏輯推理定律(定義)推出：AB

讀作：A推出B含義：A為真時,B也為真AB

當且僅當AB是永真式例如：xF(x)xF(x)F一階邏輯推理定律(來源)命題邏輯推理定律的代換實例基本等值式生成的推理定律其他的一階邏輯推理定律xA(x)∨xB(x)x(A(x)∨B(x))x(A(x)∧B(x))xA(x)∧xB(x)x(A(x)→B(x))xA(x)→xB(x)x(A(x)→B(x))xA(x)→xB(x)

一階邏輯推理定律(舉例)命題邏輯推理定律的代換實例例如:假言推理規則:(A→B)∧AB

代入A=F(a),B=G(a),得到(F(a)→G(a))∧F(a)G(a)一階邏輯推理定律(舉例、續)基本等值式生成的推理定律即由AB可得AB和BA

例如:量詞分配等值式:x(A(x)∧B(x))xA(x)∧xB(x)

可得x(A(x)∧B(x))xA(x)∧xB(x)xA(x)∧xB(x)x(A(x)∧B(x))推理定律與推理規則推理定律AB表示A→B是永真式推理規則是在證明過程中使用的規則每一條推理定律都可以作為推理規則有些推理規則不是推理定律一階邏輯的常用推理規則前提引入、結論引入、置換規則假言推理、附加、化簡、拒取式、假言三段論、析取三段論、構造性兩難、合取引入UI、UG、EI、EGInferenceRulesforQuantifiersx

P(x)

P(o) (substituteanyspecificobjecto)P(g) (forgageneralelementofu.d.)

x

P(x)x

P(x)

P(c) (substituteanew

constant

c)P(o) (substituteanyextantobjecto)

x

P(x)UniversalinstantiationUniversalgeneralizationExistentialinstantiationExistentialgeneralizationUI規則(universalinstantiation)全稱量詞消去規則

表示為xA(x)xA(x)

————或————

A(y)

A(c)注意1:y是自由變項；c是個體常項注意2:被消去量詞的轄域是整個公式例如

(1)x(F(x)→G(x))前提引入

(2)

F(a)→G(a)(1)UIUG規則(universalgeneralization)全稱量詞引入規則

表示為

A(y)

————

xA(x)注意1:y是自由變項注意2:量詞加在整個公式前面例如

(1)F(y)→G(y)前提引入

(2)x(F(x)→G(x))(1)UGEI規則(existentialinstantiation)存在量詞消去規則

表示為xA(x)

————

A(c)注意1:c是特定的滿足A的個體常項注意2:被消去量詞的轄域是整個公式例如

(1)x(F(x)∧G(x))前提引入

(2)

F(a)∧G(a)(1)EIEG規則(existentialgeneralization)存在量詞引入規則

表示為

A(c)

————

xA(x)注意1:c是個體常項注意2:量詞加在整個公式前面例如

(1)F(c)∧G(c)前提引入

(2)

x(F(x)∧G(x))(1)EG構造推理的證明(舉例)前提:x(F(x)G(x))，F(a)

結論:G(a)

證明:(1)F(a)前提引入

(2)x(F(x)G(x))前提引入

(3)F(a)G(a)(2)UI(4)G(a)(1)(3)假言推理構造推理的證明(舉例、續)前提:x(F(x)G(x))，xF(x)

結論:xG(x)

證明:(1)xF(x)前提引入

(2)F(c)(1)EI(3)x(F(x)G(x))前提引入

(4)F(c)G(c)(3)UI(5)G(c)(2)(4)假言推理

(6)xG(x)(5)EG構造推理的證明(舉例、續)“先EI，后UI”證明:(1)x(F(x)G(x))前提引入

(2)F(c)G(c)(2)UI

(3)xF(x)前提引入

(4)F(c)(3)EI

說明：這個證明是錯的.(3)(4)應當在(1)(2)前，(4)中的c是特定的，(2)中的c是任意的Example13PremisesAstudentinthisclasshasnotreadthebookx(C(x)∧?B(x))Everyoneinthisclasspassedtheexamx(C(x)P(x))ConclusionSomeonewhopassedtheexamhasnotreadthebook.x(P(x)∧?B(x))C(x):xinthisclassB(x):xreadthebookP(x):xpasstheexamExample13stepReason1x(C(x)∧?B(x))Premise2C(a)∧?B(a)EI3C(a)Simplificationfrom(2)4x(C(x)P(x))Premise5C(a)P(a)UI6P(a)Modusponensfrom(3)and(5)7?B(a)Simplificationfrom(2)8P(a)∧?B(a)Conjunctionfrom(6)and(7)9x(P(x)∧?B(x))EU構造推理的證明(舉例、續)前提:?x(F(x)∧H(x)),

x(G(x)H(x)),

結論:x(G(x)?F(x))

證明:(1)?x(F(x)∧H(x))

前提引入

(2)x(?F(x)∨?H(x))(1)置換

(3)x(H(x)?F(x))(2)置換

(4)H(y)?F(y)(3)UI(5)x(G(x)H(x))前提引入

(6)G(y)H(y)(5)UI(7)G(y)?F(y)(4)(6)假言三段論

(8)x(G(x)?F(x))(7)UG習題-構造下面推理的證明(1)前提：xF(x)y((F(y)∨G(y))R(y)),xF(x)

結論：xR(x)(2)前提：x(F(x)∨G(x)),x(?G(x)∨?R(x)),xR(x)

結論：xF(x)(3)有些病人相信所有的醫生，但病人都不相信一個騙子。證明：醫生都不是騙子。§1.5–4,6,12,16,20,241、直接證明/directproof:p→Q

2、間接證明/indirectproof:p→Q??Q→?P3、空證明/vacuousproof:p→Q其中P為F4、平凡證明/trivialproof：p→Q其中Q為T1.6IntroductiontoProofs

定理證明方法：ApplicationsofProofsAnexerciseinclearcommunicationoflogicalargumentsinanyareaofstudy.Thefundamentalactivityofmathematicsisthediscoveryandelucidation,throughproofs,ofinterestingnewtheorems.Theorem-provinghasapplicationsinprogramverification,computersecurity,automatedreasoningsystems,etc.Provingatheoremallowsustorelyupononitscorrectnesseveninthemostcriticalscenarios.ProofTerminology術語Theorem定理Astatementthathasbeenproventobetrue.Axioms,postulates,hypotheses,premises公理假定假設前提Assumptions(oftenunproven)definingthestructuresaboutwhichwearereasoning.Rulesofinference推理規則Patternsoflogicallyvaliddeductionsfromhypothesestoconclusions.MoreProofTerminologyLemma

引理-Aminortheoremusedasastepping-stonetoprovingamajortheorem.Corollary

推論-Aminortheoremprovedasaneasyconsequenceofamajortheorem.Conjecture

猜想-Astatementwhosetruthvaluehasnotbeenproven.

(Aconjecturemaybewidelybelievedtobetrue,regardless.)Theory

理論–

Thesetofalltheoremsthatcanbeprovenfromagivensetofaxioms.推理（deduction）推理：從前提出發推出結論的思維過程前提：已知命題公式的集合結論：從前提出發應用推理規則推出的命題公式

GraphicalVisualization…VariousTheoremsTheAxioms

oftheTheoryAParticularTheoryAproofAxiomsTheoremsThoughtDoctrineIdeology5、反證明/proofofcontradiction：

P?

PS∧?S6、分例證明/proofofcases：

P1∨P2…

∨Pn→Q

（P1→Q）

∧（P2→Q）…∧（Pn→Q）定理證明方法：7、存在證明/existenceproof：

xP(x)8、歸納證明/inductionproof：

xP(x)定理證明方法：（含有量詞）ProofMethodsforImplicationsForprovingimplicationspq,wehave:Directproof:

Assumepistrue,andproveq.Indirectproof:

Assumeq,andprovep.Vacuousproof:

Provepbyitself.Trivialproof:

Proveqbyitself.Proofbycases:

Showp(ab),and(aq)and(bq).DirectProofExampleDefinition:Anintegerniscalledoddiffn=2k+1forsomeintegerk;niseveniffn=2kforsomek.

Theorem:Everyintegeriseitheroddoreven.Thiscanbeprovenfromevensimpleraxioms.Theorem:(Forallnumbersn)Ifnisanoddinteger,thenn2isanoddinteger.Proof:Ifnisodd,thenn=2k+1forsomeintegerk.Thus,n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1.Thereforen2isoftheform2j+1(withjtheinteger2k2+2k),thusn2isodd.□IndirectProofExampleTheorem:(Forallintegersn)

If3n+2isodd,thennisodd.Proof:Supposethattheconclusionisfalse,i.e.,thatniseven.Thenn=2kforsomeintegerk.Then3n+2=3(2k)+2=6k+2=2(3k+1).Thus3n+2iseven,becauseitequals2jforintegerj=3k+1.So3n+2isnotodd.Wehaveshownthat?(nisodd)→?(3n+2isodd),thusitscontra-positive(3n+2isodd)→(nisodd)isalsotrue.□VacuousProofExampleTheorem:(Foralln)Ifnisbothoddandeven,thenn2=n+n.Proof:Thestatement“nisbothoddandeven”isnecessarilyfalse,sincenonumbercanbebothoddandeven.So,thetheoremisvacuouslytrue.□TrivialProofExampleTheorem:(Forintegersn)Ifnisthesumoftwoprimenumbers,theneithernisoddorniseven.Proof:

Anyintegerniseitheroddoreven.Sotheconclusionoftheimplicationistrueregardlessofthetruthoftheantecedent.Thustheimplicationistruetrivially.□ProofbyContradictionAmethodforprovingp.Assumep,andprovebothqandqforsomepropositionq.(Canbeanything!)Thusp(qq)(qq)isatrivialcontradiction,equaltoFThuspF,whichisonlytrueifp=FThuspistrue.ProofbyContradictionExampleTheorem:isirrational.Proof:Assume21/2wererational.Thismeansthereareintegersi,jwithnocommondivisorssuchthat21/2=i/j.Squaringbothsides,2=i2/j2,so2j2=i2.Soi2iseven;thusiiseven.Leti=2k.So2j2=(2k)2=4k2.Dividingbothsidesby2,j2=2k2.Thusj2iseven,sojiseven.Buttheniandjhaveacommondivisor,namely2,sowehaveacontradiction.□Review:ProofMethodsSoFarDirect,indirect,vacuous,andtrivialproofsofstatementsoftheformpq.Proofbycontradictionofanystatements.Next:Constructiveandnonconstructive

existenceproofs.ProvingExistentialsAproofofastatementoftheformx

P(x)iscalledanexistenceproof.IftheproofdemonstrateshowtoactuallyfindorconstructaspecificelementasuchthatP(a)istrue,thenitisaconstructiveproof.Otherwise,itisnonconstructive.ConstructiveExistenceProofTheorem:Thereexistsapositiveintegernthatisthesumoftwoperfectcubesintwodifferentways:equaltoj3+k3andl3+m3wherej,k,l,marepositiveintegers,and{j,k}≠{l,m}Proof:Considern=1729,j=9,k=10,

l=1,m=12.Nowjustcheckthattheequalitieshold.AnotherConstructive

ExistenceProofTheorem:Foranyintegern>0,thereexistsasequenceofnconsecutivecompositeintegers.Samestatementinpredicatelogic:

n>0xi(1in)(x+iiscomposite)Prooffollowsonnextslide…Theproof...Givenn>0,letx=(n+1)!+1.Leti1andin,andconsiderx+i.Notex+i=(n+1)!+(i+1).Note(i+1)|(n+1)!,since2i+1n+1.Also(i+1)|(i+1).So,(i+1)|(x+i).x+iiscomposite.nx1in:x+iiscomposite.Q.E.D.NonconstructiveExistenceProofTheorem:

“Thereareinfinitelymanyprimenumbers.”Anyfinitesetofnumbersmustcontainamaximalelement,sowecanprovethetheoremifwecanjustshowthatthereisnolargestprimenumber.I.e.,showthatforanyprimenumber,thereisalargernumberthatisalsoprime.Moregenerally:Foranynumber,alargerprime.Formally:Shownp>n:pisprime.

Theproof,usingproofbycases...Givenn>0,provethereisaprimep>n.Considerx=n!+1.Sincex>1,weknow

(xisprime)(xiscomposite).Case1:

xisprime.Obviouslyx>n,soletp=xandwe’redone.Case2:

xhasaprimefactorp.Butifpn,thenpmodx=1.Sop>n,andwe’redone.TheHaltingProblem(Turing‘36)Thehaltingproblemwasthefirst

mathematicalfunctionprovento

havenoalgorithmthatcomputesit!Wesay,itisuncomputable.ThedesiredfunctionisHalts(P,I):≡

thetruthvalueofthisstatement:“ProgramP,giveninputI,eventuallyterminates.”Theorem:

Haltsisuncomputable!I.e.,TheredoesnotexistanyalgorithmAthat

computesHaltscorrectlyforallpossibleinputs.Itsproofisthusanon-existenceproof.Corollary:Generalimpossibilityofpredictiveanalysisofarbitrarycomputerprograms.AlanTuring

1912-1954TheProofGivenanyarbitraryprogramH(P,I),ConsideralgorithmBreaker,definedas:

procedure

Breaker(P:aprogram)

halts:=

H(P,P)

if

halts

thenwhile

TbeginendNotethatBreaker(Breaker)haltsiffH(Breaker,Breaker)=F.SoHdoesnotcomputethefunctionHalts!Breakermakesa

liaroutofH,by

doingtheopposite

ofwhateverH

predicts.LimitsonProofsSomeverysimplestatementsofnumbertheoryhaven’tbeenprovedordisproved!E.g.Goldbach’sconjecture:Everyintegern≥2isexactlytheaverageofsometwoprimes.n≥2primesp,q:n=(p+q)/2.Therearetruestatementsofnumbertheory(oranysufficientlypowerfulsystem)thatcanneverbeproved(ordisproved)(G?del).CommonFallaciesAfallacyisaninferenceruleorotherproofmethodthatisnotlogicallyvalid.Afallacymayyieldafalseconclusion!Fallacyofaffirmingtheconclusion:“pqistrue,andqistrue,sopmustbetrue.”(No,becauseFTistrue.)Fallacyofdenyingthehypothesis:“pqistrue,andpisfalse,soqmustbefalse.”(No,againbecauseFTistrue.)CircularReasoningThefallacyof(explicitlyorimplicitly)assumingtheverystatementyouaretryingtoproveinthecourseofitsproof.Example:Provethatanintegerniseven,ifn2iseven.Attemptedproof:

“Assumen2iseven.Thenn2=2kforsomeintegerk.Dividingbothsidesbyngivesn=(2k)/n=2(k/n).Sothereisanintegerj(namelyk/n)suchthatn=2j.Thereforeniseven.”Circularreasoningisusedinthisproof.Where?Begsthequestion:Howdo

youshowthatj=k/n=n/2isaninteger,withoutfirstassumingthatniseven?ACorrectProofWeknowthatnmustbeeitheroddoreven.Ifnwereodd,thenn2wouldbeodd,sinceanoddnumbertimesanoddnumberisalwaysanoddnumber.Sincen2iseven,itisnotodd,sincenoevennumberisalsoanoddnumber.Thus,bymodustollens,nisnotoddeither.Thus,bydisjunctivesyllogism,nmustbeeven.■Thisproofiscorrect,butnotquitecomplete,

sinceweusedseverallemmaswithoutproving

them.Canyouidentifywhattheyare?AMoreVerboseVersionSupposen2iseven2|n2

n2mod2=0.Ofcoursenmod2iseither0or1.Ifit’s1,thenn1(mod2),son21(mod2),usingthetheoremthatifab(modm)andcd(modm)thenacbd(modm),witha=c=nandb=d=1.Nown21(mod2)impliesthatn2mod2=1.Sobythehypotheticalsyllogismrule,(nmod2=1)implies(n2mod2=1).Sinceweknown2mod2=01,bymodustollensweknowthatnmod21.Sobydisjunctivesyllogismwehavethatnmod2=02|nniseven.Usessomenumbertheorywehaven’tdefinedyet.MoreProofExamplesQuizquestion1a:Isthisargumentcorrectorincorrect?“AllTAscomposeeasyquizzes.RameshisaTA.Therefore,Rameshcomposeseasyquizzes.”First,separatethepremisesfromconclusions:Premise#1:AllTAscomposeeasyquizzes.Premise#2:RameshisaTA.Conclusion:Rameshcomposeseasyquizzes.AnswerNext,re-rendertheexampleinlogicnotation.Premise#1:AllTAscomposeeasyquizzes.LetU.D.=allpeopleLetT(x):≡“xisaTA”LetE(x):≡“xcomposeseasyquizzes”ThenPremise#1says:x,T(x)→E(x)Answercont…Premise#2:RameshisaTA.LetR:≡RameshThenPremise#2says:T(R)AndtheConclusionsays:E(R)Theargumentiscorrect,becauseitcanbereducedtoasequenceofapplicationsofvalidinferencerules,asfollows:TheProofinGoryDetailStatement

Howobtainedx,T(x)→E(x) (Premise#1)T(Ramesh)→E(Ramesh)(Universal instantiation)T(Ramesh) (Premise#2)E(Ramesh) (ModusPonensfrom

statements#2and#3)AnotherexampleQuizquestion2b:Correctorincorrect:Atleastoneofthe280studentsintheclassisintelligent.Yisastudentofthisclass.Therefore,Yisintelligent.First:Separatepremises/conclusion,

&translatetologic:Premises:(1)xInClass(x)Intelligent(x)

(2)InClass(Y)Conclusion:Intelligent(Y)AnswerNo,theargumentisinvalid;wecandisproveitwithacounter-example,asfollows:ConsideracasewherethereisonlyoneintelligentstudentXintheclass,andX≠Y.ThenthepremisexInClass(x)Intelligent(x)istrue,byexistentialgeneralizationof

InClass(X)Intelligent(X)ButtheconclusionIntelligent(Y)isfalse,sinceXistheonlyintelligentstudentintheclass,andY≠X.Therefore,thepremisesdonotimplytheconclusion.AnotherExampleQuizquestion#2:Provethatthesumofarationalnumberandanirrationalnumberisalwaysirrational.First,youhavetounderstandexactlywhatthequestionisaskingyoutoprove:“Forallrealnumbersx,y,ifxisrationalandyisirrational,thenx+yisirrational.”x,y:Rational(x)Irrational(y)→Irrational(x+y)AnswerNext,thinkbacktothedefinitionsofthetermsusedinthestatementofthetheorem:realsr:Rational(r)?

Integer(i)Integer(j):r=i/j.realsr:Irrational(r)??Rational(r)Youalmostalwaysneedthedefinitionsofthetermsinordertoprovethetheorem!Next,let’sgothroughonevalidproof:WhatyoumightwriteTheorem:

x,y:Rational(x)Irrational(y)→Irrational(x+y)Proof:Letx,ybeanyrationalandirrationalnumbers,respectively.…(universalgeneralization)Now,justfromthis,whatdoweknowaboutxandy?Youshouldthinkbacktothedefinitionofrational:…

Sincexisrational,weknow(fromtheverydefinitionofrational)thattheremustbesomeintegersiandjsuchthatx=i/j.

So,letix,jxbesuchintegers…Wegivethemuniquenamessowecanrefertothemlater.Whatnext?Whatdoweknowabouty?Onlythatyisirrational:?integersi,j:y=i/j.But,it’sdifficulttoseehowtouseadirectproofinthiscase.Wecouldtryindirectproofalso,butinthiscase,itisalittlesimplertojustuseproofbycontradiction(verysimilartoindirect).So,whatarewetryingtoshow?Justthatx+yisirrational.Thatis,?i,j:(x+y)=i/j.Whathappensifwehypothesizethenegationofthisstatement?Morewriting…Supposethatx+ywerenotirrational.Thenx+ywouldberational,sointegersi,j:x+y=i/j.So,letisandjsbeanysuchintegerswherex+y=is/js.

Now,withallthesethingsnamed,wecanstartseeingwhathappenswhenweputthemtogether.So,wehavethat(ix/jx)+y=(is/js).Observe!Wehaveenoughinformationnowthatwecanconcludesomethingusefulabouty,bysolvingthisequationforit.Finishingtheproof.Solvingthatequationfory,wehave:

y=(is/js)–(ix/jx)

=(isjx–ixjs)/(jsjx)

Now,sincethenumeratoranddenominatorofthisexpressionarebothintegers,yis(bydefinition)rational.Thiscontradictstheassumptiont