Discrete-Mathematics-Chapter-1-Sets-and-logic-Chapter-2-Proofs第一二單元課件

????

DiscreteMathematics

8/30Ch19/1Ch1Hw1Ch1,26Ch28Ch215Ch320Ch3Hw2Ch3,422Ch4Quiz1Ch1,227Ch429Ch510/4Ch5Hw3Ch5,66Ch611Ch6Quiz2Ch3,413Ch718Ch7Hw4Ch7,820WedExam1Ch1~625Ch827Ch811/1Ch93Ch9Hw5Ch9,108Ch10Quiz3Ch7,810Ch1015Ch1117Ch11Hw6Ch11,1222WedExam2Ch7~1024Ch1229Ch1212/16-Quiz4Ch11,128-FinalAllchaptersDiscreteMathematics

7thedition,2009Chapter1SetsandlogicChapter2Proofs51.1SetsSet=acollectionofdistinctunorderedobjectsMembersofasetarecalledelementsHowtodetermineasetListing:Example:A={1,3,5,7}DescriptionExample:B={x|x=2k+1,0<

k

<3}6FiniteandinfinitesetsFinitesetsExamples:A={1,2,3,4}B={x|xisaninteger,1<

x

<4}InfinitesetsExamples:Z={integers}={…,-3,-2,-1,0,1,2,3,…}S={x|xisarealnumberand1<

x<4}=[1,4]7SomeimportantsetsTheemptysethasnoelements.Alsocallednullsetorvoidset.Universalset:thesetofallelementsaboutwhichwemakeassertions.Examples:U={allnaturalnumbers}U={allrealnumbers}U={x|xisanaturalnumberand1<

x<10}8CardinalityCardinalityofasetA(insymbols|A|)isthenumberofelementsinAExamples:IfA={1,2,3}then|A|=3IfB={x|xisanaturalnumberand1<

x<9}then|B|=9InfinitecardinalityCountable(e.g.,naturalnumbers,integers)Uncountable(e.g.,realnumbers)9Subsets,PowersetXisasubset

ofYifeveryelementofXisalsocontainedinY

(insymbolsX

Y)Equality:X=YifX

YandY

XXisapropersubsetofYifX

YbutY

XObservation:isasubsetofeverysetThepowersetofXisthesetofallsubsetsofX,insymbols

P(X),i.e.

P(X)={A|A

X}Example:ifX={1,2,3}, then

P(X)={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}Theorem2.1.4:If|X|=n,then|P(X)|=2n.10Setoperations

GiventwosetsXandYTheunionofXandYisdefinedastheset

X

Y={x|x

Xorx

Y}TheintersectionofXandYisdefinedastheset

X

Y={x|x

Xandx

Y}

TwosetsXandYaredisjointifXY=Thedifferenceoftwosets

X–Y={x|x

Xandx

Y}

ThedifferenceisalsocalledtherelativecomplementofYinXSymmetricdifference

X

Δ

Y=(X–Y)(Y–X)Thecomplement

ofasetAcontainedinauniversalsetUisthesetAc=U–A

11VenndiagramsAVenndiagramprovidesagraphicviewofsetsSetunion,intersection,difference,symmetricdifferenceandcomplementscanbeidentifiedUAB12PropertiesofsetoperationsTheorem2.1.10: LetUbeauniversalset,andA,BandCsubsetsofU. Thefollowingpropertieshold:a)Associativity: (A

B)C=A(B

C) (A

B)C=A(B

C)b)Commutativity: A

B=B

A

A

B=B

Ac)Distributivelaws: A(B

C)=(A

B)(A

C)

A(B

C)=(A

B)(A

C)d)

Identitylaws: A

U=A

A=Ae)Complementlaws: A

Ac=U

A

Ac=13Propertiesofsetoperationsf)Idempotentlaws:A

A=A

A

A=Ag)Boundlaws: A

U=U

A=h)Absorptionlaws: A(A

B)=A

A(A

B)=Ai)Involutionlaw: (Ac)c=Aj)0/1laws: c=U

Uc=k)DeMorgan’slawsforsets: (A

B)c=Ac

Bc (A

B)c=Ac

Bc141.2PropositionsLogic=thestudyofcorrectreasoningStatementsasasingledatumhaving(binary)truthvalueRepresenting“facts”digitallyQ:whataboutstatementsthathavedegreeoftruthvalue?Howcanwemanipulatethemtoderivenewthings?UseoflogicInmathematics:toprovetheoremsIncomputerscience:toprovethatprogramsdowhattheyaresupposedtodoAI/DB:TheoremproverSoftwareengineering:Programcorrectness15PropositionsApropositionisastatementorsentencethatcanbedeterminedtobeeithertrueorfalse.

Examples:“Johnisaprogrammer"isaproposition“IwishIwerewise”isnotaproposition(?)Well,youcanstillassignsomevalue…Computersdon’treallycare…16ConnectivesIfpandqarepropositions,newcompoundpropositionscanbeformedbyusingconnectives

Mostcommonconnectives:ConjunctionAND. Symbol^

InclusivedisjunctionOR SymbolvExclusivedisjunctionOR SymbolvNegation Symbol~Implication Symbol

Doubleimplication Symbol

17TruthtableTruthtableofconjunction^,and,???pqp^qTTTTFFFTFFFFpqpvqTTTTFTFTTFFFTruthtableof(inclusive)disjunctionv,or,???Truthtableofexclusivedisjunction“Eitherporq”(butnotboth),

,exclusiveorpqp

v

qTTFTFTFTTFFFTruthtableofNegation

~,not,??p~pTFFT18MorecompoundstatementsLetp,q,rbesimplestatements

Wecanformothercompoundstatements,suchas(p

q)^rp(q^r)(~p)(~q)(p

q)^(~r)andmanyothers…

Exampletruthtableof(p

q)^rpqr(p

q)^

rTTTTTTFFTFTTTFFFFTTTFTFFFFTFFFFF191.3Conditionalpropositions(????)and

logicalequivalence(??)Aconditionalproposition“Ifpthenq”,"ponlyifq"Insymbols:p

qTruthtablep:antecedentorhypothesis(??)sufficientcondition(????)forq

q:consequentorconclusion(??)necessarycondition(????)forppqp

qTTTTFFFTTFFT20Logicalequivalencelogicallyequivalent

??two

truthtablesareidentical.converse?converseofpqisqpp

q~p

q

p

qTTTTTFFFFTTTFFTTp

qp

qq

pTTTTTFFTFTTFFFTTcontrapositive

??contrapositiveofthepqis~q~p.logicallyequivalentpqp

q~q~pTTTTTFFFFTTTFFTT21Logicalequivalencedoubleimplication

???pifandonlyifqp

qlogicallyequivalentto(p

q)^(q

p)tautology

????truthtablecontainsonlytruevaluesforeverycasecontradiction

????truthtablecontainsonlyfalsevaluesforeverycasepqp

q(p

q)^(q

p)TTTTTFFFFTFFFFTTpqp

pvq

TTTTFTFTTFFTpp^(~p)TFFF22DeMorgan’slawsforlogicThefollowingpairsofpropositionsarelogicallyequivalent:~(p

q)and(~p)^(~q)~(p

^q)and(~p)(~q)231.4ArgumentsandrulesofinferenceDeductivereasoning:theprocessofreachingaconclusionqfromasequenceofpropositionsp1,p2,…,pn.Thepropositionsp1,p2,…,pn

arecalled

premises(??)orhypothesis

(??).Thepropositionqthatislogicallyobtainedthroughtheprocessiscalledtheconclusion.24Rulesofinference1.Lawof

detachmentormodus

ponens(modethataffirms)p

qpTherefore,q2.Modus

tollens

(modethatdenies)p

q~qTherefore,~p3.Ruleof

AdditionpTherefore,p

q4.Ruleof

simplificationp^qTherefore,p5.RuleofconjunctionpqTherefore,p^q6.Ruleofhypotheticalsyllogismp

qq

rTherefore,p

r

7.Ruleofdisjunctivesyllogismp

q~pTherefore,q25Rulesofinferenceforquantifiedstatements1.Universalinstantiation

x

D,P(x)d

DThereforeP(d)2.UniversalgeneralizationP(d)foranyd

DThereforex,P(x)3.Existentialinstantiation

x

D,P(x)ThereforeP(d)forsomed

D4.ExistentialgeneralizationP(d)forsomed

DThereforex,P(x)261.5Quantifiers(????)Apropositionalfunction

P(x)isastatementinvolvingavariablexForexample:P(x):2xisaneveninteger

DomainofapropositionalfunctionifxisanelementofasetD,DiscalledthedomainofP(x)Forexample,xisanelementofthesetofintegersthedomainDofP(x)mustbedefined(cf.)P(x):xisanevenintegerifDisasetofevenintegersifDisasetofoddintegers27Universalquantifieruniversalquantifierforevery…

x

P(x):P(x)forevery

xinadomainDTrueifP(x)istrueforevery

x

DFalseifP(x)isnottrueforsome

x

DExample:LetP(n)bethepropositionalfunctionn2+2nisanoddinteger

n

D={allintegers}P(n)istrueonlywhennisanoddinteger,falseifnisaneveninteger.28Existentialquantifier,Counterexampleexistentialquantifierforsome…

x

P(x):P(x)forsomexinadomainDtrueifthereexistsanelementxinthedomainDforwhichP(x)istrue.counterexample

x

P(x)isfalseifx

DsuchthatP(x)isfalse.ThevaluexthatmakesP(x)falseiscalledacounterexampletothestatement

x

P(x).ExampleP(x)="everyxisaprimenumber",foreveryintegerx.

Butifx=4(aninteger)thisxisnotaprimernumber.Then4isacounterexampletoP(x)beingtrue.29GeneralizedDeMorgan’slawsforLogic

IfP(x)isapropositionalfunction,theneachpairofpropositionsina)andb)belowhavethesametruthvalues:

a)~(

x

P(x))andx:~P(x)

"Itisnottruethatforeveryx,P(x)holds"isequivalentto"ThereexistsanxforwhichP(x)isnottrue“

b)~(x

P(x))andx:~P(x)

"ItisnottruethatthereexistsanxforwhichP(x)istrue"isequivalentto"Forallx,P(x)isnottrue"301.6NestedQuantifiersNestedquantifier:multiplequantifierExample

x

y

P(x,y)ForeveryxinD,thereisyinDsuchthatP(x,y)istrue

x

y(x<y)Foreveryx,thereexistysuchthatx<y.D:integer

x

y

L(x,y)L(x,y):xlovesyEverybody(x)lovessomebody(y)E.g.False:thereissomeonewholovesnobody

x

y

P(x,y)ForeveryxinDandforeveryyinD,P(x,y)istrue.

x

y((x>0)^(y>0))(x+y>0)),D:realnumberIfthereisatleastonexandatleastysuchthatP(x,y)isfalseLikeinx

y((x>0)^(y<0))(x+y0)),D:realnumberCounterexample:x=1,y=-131NestedQuantifierExample

x

y

P(x,y)ThereisatleastonxsuchthatP(x,y)istrueforeveryyinD

x

y(x

y),D:positiveintegerx=1

x

y(x

y),D:positiveintegerFalse:foreveryx,thereisatleastonepositiveintegery(ex.y=x+1)

x

y

P(x,y)ThereisatleastonexinDandatleastoneyinDsuchthatP(x,y)istrue.

x

y((x>1)^(y>1)^(xy=6))

x

y((x>1)^(y>1)^(xy=7))32

x

y

P(x,y)

x

y

P(x,y)

x

y

P(x,y)

x

y

P(x,y)NestedQuantifierX={a,b,c},Y={1,2,3,4}abc1234P(x,y)XYabc1234P(x,y)XYabc1234P(`,y)XYabc1234P(x,y)XYabc1234P(x,y)XYabc1234P(x,y)XYabc1234P(x,y)XY332.1Mathematicalsystems,directproofsandcounterexamplesAmathematicalsystemconsistsofUndefinedtermsDefinitionsAxioms34Undefinedterms,DefinitionsUndefinedtermsarethebasicbuildingblocksofamathematicalsystem.Thesearewordsthatareacceptedasstartingconceptsofamathematicalsystem.Example:inEuclideangeometrywehaveundefinedtermssuchasPointLine

Adefinition(??)isapropositionconstructedfromundefinedtermsandpreviouslyacceptedconceptsinordertocreateanewconcept.Example:InEuclideangeometrythefollowingaredefinitions:Twotrianglesarecongruentiftheirverticescanbepairedsothatthecorrespondingsidesareequalandsoarethecorrespondingangles.Twoanglesaresupplementaryifthesumoftheirmeasuresis180degrees.35Axioms,TheoremsAnaxiom(??)isapropositionacceptedastruewithoutproofwithinthemathematicalsystem.Therearemanyexamplesofaxiomsinmathematics:Example:InEuclideangeometrythefollowingareaxiomsGiventwodistinctpoints,thereisexactlyonelinethatcontainsthem.Givenalineandapointnotontheline,thereisexactlyonelinethroughthepointwhichisparalleltotheline.Atheorem(??)

isapropositionoftheformp

qwhichmustbeshowntobetruebyasequenceoflogicalstepsthatassumethatpistrue,andusedefinitions,axiomsandpreviouslyproventheorems.36LemmasandcorollariesAlemma(????)isasmalltheoremwhichisusedtoproveabiggertheorem.Acorollary(????)isatheoremthatcanbeproventobealogicalconsequenceofanothertheorem.ExamplefromEuclideangeometry:"Ifthethreesidesofatrianglehaveequallength,thenitsanglesalsohaveequalmeasure."37TypesofproofAproofisalogicalargumentthatconsistsofaseriesofstepsusingpropositionsinsuchawaythatthetruthofthetheoremisestablished.Directproof:p

qAdirectmethodofattackthatassumesthetruthofpropositionp,axiomsandproventheoremssothatthetruthofpropositionqisobtained.38Directproof:exampleIfniseven,thenn2

iseven.Supposeniseven.

Thenbydefinitionof“even”thereisanintegermforwhichn=2m.

Ifwesquarebothsides,wegetn2=4m2=2*2m2.2m2

isanintegerbecausemisaninteger,sobydefinitionof“even”,niseven.392.2MoremethodsofproofProofbycontradictionProofbycontrapositiveProofbycasesProofsofequivalenceExistenceproofs

40IndirectproofThemethodofproofbycontradiction(a.k.a.indirectproof)ofatheoremp

qconsistsofthefollowingsteps:Assumepistruebutqisfalse~(p

q)

p

~q2.Usingp,~q,axioms,previouslyderivedtheoremsandrulesofinference,deriver^(~r),acontradictionInparticular,rcouldbep3.Concludeqcannotbefalse,hencep

q

TheonlydifferenceisthenegatedconclusioninourassumptionsUsewhendirectproofisdifficult

41Specialcase:proofbycontrapositiveIfr=pintheproofbycontradiction,itiscalledtheproofbycontrapositiveSinceineffectwehaveshown(~q)(~p),whichislogicallyequivalenttop

qExample:ShowforeverynZ,ifn2iseven,thenniseven.Supposen2iseven,butnisodd.Thenthereexistsanintegerks.t.n=2k+1.Ifwesquarebothsidesweobtainn2=4k2+4k+1=2(2k2+2k)+1.Buttheequationtellsusn2isodd,acontradiction.WehaveprovedthatforeverynZ,ifn2iseven,thenniseven.Proofbycontradiction:exampleProve2isirrational.Suppose2isrational.Thenthereexistintegerspandqsuchthat2=p/q.Assumethefractionp/qisinlowesttermssothatpandqarenotbotheven.Squaringbothsidesgives2=p2/q2

Multiplyingbyq2gives2q2=p2.Itmeansp2

iseven,thenpiseven(!).Therefore,thereexistsanintegerks.t.p=2k.Substitutinginto2q2=p2givesq2=2k2.Therefore,qiseven.Thusbothpandqarebotheven,contradictingourassumption.Therefore,2isirrational.42OthersProofbycasesProve(p1

p2

p3

…

pn)

qInsteadprove(p1

q)…(pn

q)AlsocalledexhaustiveproofUsewhenthenumberofcasestoproveissmallProofofequivalenceProvep

qProvep

qandq

pExistenceproofProve

xP(x)Justfindonexthatsatisfiesaboveandthatisit…Sometimesitisnotsoeasytofindthatx…442.3ResolutionproofsDuetoJ.A.Robinson(1965)Aclauseisacompoundstatementwithtermsseparatedby“or”,andeachtermisasinglevariableorthenegationofasinglevariableExample:p

q(~r)isaclause(p

q)

r(~s)isnotaclause

HypothesesandconclusionarewrittenasclausesIfahypothesisisnotaclause,itmustbereplacedbyanequivalentexpressionthatiseitheraclauseortheandofclausesOnlyonerule:If(p

q)and(~p

r)arebothtrue