大学离散数学期末重点知识点总结(考试专用).pptx

大学离散数学期末重点知识点总结(考试专用).pptx学海无涯1p∧(P→Q)=>Q┐Q∧(P→Q)=>┐┐p∧(P∨Q)=>Q(P→Q)∧(Q→R)=>P→R析取三段式条件三段式(PQ)∧(QR)=>PR双条件三段式(P→Q)∧(R→S)∧(P∧R)=>Q→S 合取构造二难(P→Q)∧(R→S)∧(P∨R)=>Q∨S 析取构造二难(x)((Ax)∨(Bx))<=>(x)(Ax)∨(x)(Bx)(x)((Ax)∧(Bx))<=>(x)(Ax)∧(x)(Bx)—┐(x)(Ax)<=>(x)┐(Ax)—┐(x)(Ax)<=>(x)┐(Ax)(x)(A∨(Bx))<=>A∨(x)(Bx)(x)(A∧(Bx))<=>A∧(x)(Bx)(x)((Ax)→(Bx))<=>(x)(Ax)→(x)(Bx)(x)(Ax)→B<=>(x)((Ax)→B)(x)(Ax)→B<=>(x)((Ax)→B)A→(x)(Bx)<=>(x)(A→(Bx))A→(x)(Bx)<=>(x)(A→(Bx)) (x)(Ax)∨(x)(Bx)=>(x)((Ax)∨(Bx))(x)((Ax)∧(Bx))=>(x)(Ax)∧(x)(Bx)(x)(Ax)→(x)(Bx) =>(x)((Ax)→(Bx)).→,前键为真,后键为假才为假;<—>,相同为真,,这2n为(0~2n-1)刚出后键为真,假定前键为假推出后键也为假):P规则,T规则①真值表法;②直接证法;③归谬法;④附加前提法;:谓词有n个个体,多元谓词描述个体之间的关系;,表示自然数集,1,2,3……,不包括0;n|P(A)|=2|A|=2n;集合的分划:(等价关系)①每一个分划都是由集合A的几个子集构成的集合;②这几个子集相交为空,相并为全(A);集合的分划与覆盖的比较:分划:每个元素均应出现且仅出现一次在子集中;覆盖:只要求每个元素都出现,没有要求只出现一次;,集合B有n个元素,则笛卡尔A×Bmnn的基数为mn,A到B上可以定义2种2不同的关系2;2n若集合A有n个元素,则|A×A|=,A上有个不同的关系;全关系的性质:自反性,对称性,传递性;空关系的性质:反自反性,反对称性,传递性;全封闭环的性质:自反性,对称性,反对称性,传递性;前域(domR):所有元素x组成的集合;后域(ranR):所有元素y组成的集合;自反闭包:r(R)=RUIx;对称闭包:s(R)=RUR-1;传递闭包:t(R)=RUR2UR3U……递性,则R称为等价关系;:集合A上的关系R满足自反性,反对称性和传递性,则称R是A上的一个偏序关系;={<x,y>|x,y属于A,y盖住x};极大元:集合A中没有比它更大的元素(若存在可能不唯一);最小元:比集合A中任何其他元素都小(若存在就一定唯一);:B是A的子集是B的上界(若存在,可能不唯一);是B的下界(若存在,可能不唯一);上确界:最小的上界(若存在就一定唯一);下确界:最大的下界(若存在就一定唯一);|X|=m,|Y|=n,则从X到Y有2mn种不同的关系,有nm种不同的函数;在一个有n个元