DMA-1.5-7離散數(shù)學(xué)課件

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.)常見(jiàn)推理定律附加律 A(A∨B)化簡(jiǎn)律 (A∧B)A假言推理

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

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

A假言三段論

(A→B)∧(B→C)(A→C)等價(jià)三段論 (A?B)∧(B?C)(A?C)構(gòu)造性兩難 (A→B)∧(C→D)∧(A∨C)(B∨D)構(gòu)造性兩難(特殊形式) (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.推理的形式結(jié)構(gòu)前提：A1,A2,A3,…,Ak

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

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

?p

結(jié)論：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.

推理的形式結(jié)構(gòu)前提：A1,A2,A3,…,Ak

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

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

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

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

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

A假言三段論

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

前提：p∨q，

?p

結(jié)論：q

證明：(1)p∨q

前提引入

(2)?p前提引入

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

前提：(p∧q)

→r，

?s∨p，q

結(jié)論：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)假言三段論證明(舉例、續(xù))證明：(p∧q)

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

→r

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

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

?q∨(?p∨r)

(交換律、結(jié)合律)

q→(?p∨r)

(蘊(yùn)涵等值式)

q→(p→r)

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

A：甲作的案

B：乙作的案

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

E：午夜燈光滅

則以上五句話成為五個(gè)命題（1）

A∨B（2）

A→C（3）

D→?E（4）

?

D→?C（5）

E

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

如果，AB，則A→B反證推理規(guī)則

如果，?

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

A2

A3),A4

A1,

A2

A4

A3例給出的證明A1?

A2,A2?

A3,

A3

?

A4

?

A1習(xí)題證明下面的等值式：

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

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

，

p，q

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

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

讀作：A推出B含義：A為真時(shí),B也為真AB

當(dāng)且僅當(dāng)AB是永真式例如：xF(x)xF(x)F一階邏輯推理定律(來(lái)源)命題邏輯推理定律的代換實(shí)例基本等值式生成的推理定律其他的一階邏輯推理定律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)

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

代入A=F(a),B=G(a),得到(F(a)→G(a))∧F(a)G(a)一階邏輯推理定律(舉例、續(xù))基本等值式生成的推理定律即由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))推理定律與推理規(guī)則推理定律AB表示A→B是永真式推理規(guī)則是在證明過(guò)程中使用的規(guī)則每一條推理定律都可以作為推理規(guī)則有些推理規(guī)則不是推理定律一階邏輯的常用推理規(guī)則前提引入、結(jié)論引入、置換規(guī)則假言推理、附加、化簡(jiǎn)、拒取式、假言三段論、析取三段論、構(gòu)造性兩難、合取引入U(xiǎn)I、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規(guī)則(universalinstantiation)全稱量詞消去規(guī)則

表示為xA(x)xA(x)

————或————

A(y)

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

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

(2)

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

表示為

A(y)

————

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

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

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

表示為xA(x)

————

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

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

(2)

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

表示為

A(c)

————

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

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

(2)

x(F(x)∧G(x))(1)EG構(gòu)造推理的證明(舉例)前提:x(F(x)G(x))，F(xiàn)(a)

結(jié)論:G(a)

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

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

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

結(jié)論: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構(gòu)造推理的證明(舉例、續(xù))“先EI，后UI”證明:(1)x(F(x)G(x))前提引入

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

(3)xF(x)前提引入

(4)F(c)(3)EI

說(shuō)明：這個(gè)證明是錯(cuò)的.(3)(4)應(yīng)當(dāng)在(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構(gòu)造推理的證明(舉例、續(xù))前提:?x(F(x)∧H(x)),

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

結(jié)論: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習(xí)題-構(gòu)造下面推理的證明(1)前提：xF(x)y((F(y)∨G(y))R(y)),xF(x)

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

結(jié)論：xF(x)(3)有些病人相信所有的醫(yī)生，但病人都不相信一個(gè)騙子。證明：醫(yī)生都不是騙子。§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術(shù)語(yǔ)Theorem定理Astatementthathasbeenproventobetrue.Axioms,postulates,hypotheses,premises公理假定假設(shè)前提Assumptions(oftenunproven)definingthestructuresaboutwhichwearereasoning.Rulesofinference推理規(guī)則Patternsoflogicallyvaliddeductionsfromhypothesestoconclusions.MoreProofTerminologyLemma

引理-Aminortheoremusedasastepping-stonetoprovingamajortheorem.Corollary

推論-Aminortheoremprovedasaneasyconsequenceofamajortheorem.Conjecture

猜想-Astatementwhosetruthvaluehasnotbeenproven.

(Aconjecturemaybewidelybelievedtobetrue,regardless.)Theory

理論–

Thesetofalltheoremsthatcanbeprovenfromagivensetofaxioms.推理（deduction）推理：從前提出發(fā)推出結(jié)論的思維過(guò)程前提：已知命題公式的集合結(jié)論：從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式

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