计算理论导论(英文版)数学基础.ppt

《计算理论导论(英文版)数学基础.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、Chapter0:Introduction,mathematicalnotation,prooftechniques10.2.1StandardSetTheoryreviewAsetisanunorderedcollectionofobjects.Elements(members)DonotdistinguishrepetitionsoftheelementsMultiset-Dodistinguishrepetitionsoftheelements{7,7}and{7}Singleton-mayhave

2、onlyoneelementTheemptyset–withnoelementatall:ΦNonemptyNaturalnumbersN(0inclusive)IntegersZ2writtenListingRefertoothersetsandproperties345SetoperationsUnion:ABIntersection:ABComplement:ADifference:A-BDisjointSets:AB=Null6LawsandPropertiesCommutativelawA

3、ssociativelawDistributivelawAbsorptionlawDemogan’slawIdempotentlaw7SuperSetAcollectionofanysets89CoverageDifferencebetweencoverageandpartition100.2.2sequencesandtuplesHowtoexpressrelationsbetweenobjectsThelanguageofsetsFortheobjectsbelongtotherelationNoth

4、eobjectsnotdistinguished11OrderedPairs12Cartesianproduct13Binaryrelation14OrderedtupleOrdered2-tupleorderedpairsOrdered3-tupleorderedtriplesOrdered4-tuplequadruplesOrdered5-tuplequintuplesOrdered6-tuplesextuplesSequenceisanorderedn-tupleforsomeunspecified

5、n,wherenisthelengthofthesequence.N-foldCartesianproduct15N-aryrelation1-aryrelationunaryrelations2-aryrelationbinaryrelations3-aryrelationternaryrelations16175compositionQR={(a,b):forsomec,(a,c)Qand(c,b)R}Compositionoff:ABandg:BCisafunctionhfromAtoCsu

6、chthath(a)=g(f(a)).186specialtypesofbinaryrelationsdirectedgraphNodeEdgesNotes:donotallow“parallelarrows”.Adjacentmatrix19PropertiesofrelationsReflexiveSymmetricAsymmetricAnti-symmetricTransitive20ReflexiveArelationRA×Aisreflexiveif(a,a)RforeachaA.Thed

7、irectedgraphrepresentingareflexiverelationhasaloopfromeachnodetoitself.Whatisthecharacteristicsofitsmatrix?Alloftheelementsonthediagonallineofitsmatrixare1.21SymmetricArelationRA×Aissymmetricif(b,a)Rwhenever(a,b)R.Inthedirectedgraphrepresentingasymmetr

8、icrelation,wheneverthereisanarrowbetweentwonodes,therearearrowsbetweenthosenodesinbothdirections.Characteristicsofmatrix?Example:{(a,b):aandbarepersonswiththesamefather}22undirectedgraphAsymmetricrelationwithoutpair