《离散数学》总复习

1、总 复 习,复习重点 命题逻辑 1.联结词的定义(含义及真值表定义). 2.会命题符号化. 3.永真式的证明. 4.永真蕴涵式的证明,记住并能熟练应用常用公式. 5.等价公式的证明,记住并能熟练应用常用公式. 6.会写命题公式的范式, 能应用范式解决问题. 7.熟练掌握命题逻辑三种推理方法.,谓词逻辑 1.准确掌握有关概念. 2.会命题符号化. 3.掌握常用的等价公式和永真蕴涵式.包括: 带量词的公式在论域内展开式,量词否定,量词辖域扩充, 量词分配公式. 4.会用等价公式求谓词公式的真值. 5.会写前束范式 6.熟练掌握谓词逻辑推理.,二元关系 1.关系的概念,表示方法. 2.二元关系的 性

2、质的定义, 熟练掌握性质的判断及证明. 3.掌握关系的复合,求逆及闭包运算(计算方法及有关性质) 4.掌握等价关系的判断,证明,求等价类和商集. 5.偏序关系的判断,会画Hasse图,会求一个子集的极小(大) 元,最小(大)元,上界与下界,最小上界及最大下界.,第八章 图论 1.掌握图的基本概念.(特别注意相似的概念) 2.熟练掌握图中关于结点度数的定理. (会应用) 3.无向图的连通性的判定,连通分支及连通分支数的概念. 4.有向图的可达性,强连通,单侧连通和弱连通的判定.求强 分图,单侧分图和弱分图. 5.会求图的矩阵. 6.会判定欧拉图和汉密尔顿图. 7.会判定平面图, 掌握欧拉公式.

3、8.掌握树的基本定义,v和e间的关系式.会画生成树,会求最 小生成树.根树的概念,完全m叉树的公式,会画最优树,会 设计前缀码.,离散数学总复习,离散数学总复习,离散数学总复习,离散数学总复习,离散数学总复习,离散数学总复习,离散数学总复习,会用三种推理方法,进行逻辑推理. 例如:证明 (AB)C)D(CD) AB 1.直接推理: D P CD P C T I10 Q, (PQ) P (AB)C P (AB) T I12 Q, PQ P AB T E8 (PQ)PQ,(AB)C)D(CD) AB 2.条件论证:适用于结论是蕴涵式. AB AB A P(附加前提) (AB)C P A(BC) T

4、 E19 BC T I11 D P CD P C T I10 B T I12 AB CP,(AB)C)D(CD) AB 3.反证法: (AB) P(假设前提) AB T E9 (AB)C P C T I11 D P CD P C T I10 CC T I9,用公式的等价变换. 主析取范式;A(P,Q,R) (PQ)R (PQ)R (PQ)R (PQ(RR)(PP)(QQ)R) (PQR) (PQR)(PQR) (PQR)(PQR)(PQR) (PQR )(PQR )(PQR) (PQR )(PQR ) 主合取范式:A(P,Q,R) (PQ)R (PQ)R (PQ)R ( PR )(QR) (

5、P(QQ)R )(PP)QR) (PQR )(PQR)(PQR ),离散数学总复习,离散数学总复习,例如金子闪光,但闪光的不一定都是金子. 设: G(x):x是金子. F(x):x闪光. x(G(x)F(x)x(F(x)G(x) x(G(x)F(x)x(F(x)G(x) 没有大学生不懂外语. S(x):x是大学生. F(x):x外语. K(x,y):x懂得y. x(S(x)y(F(y)K(x,y) x(S(x)y(F(y)K(x,y) 有些液体可以溶解所有固体. F(x):x是液体.S(x):x是固体.D(x,y):x可溶解y. x(F(x)y(S(y)D(x,y) 每个大学生都爱好一些文体活

6、动。 S(x):x是大学生,L(x,y):x爱好y, C(x):x是文娱活动， P(x):x是体育活动.) x(S(x)y(C(y)P(y)L(x,y),掌握常用的等价公式和永真蕴涵式.包括: 带量词的公式在论域内展开式,量词否定,量词辖域扩充, 量词分配公式. 设论域为a1,a2,.,an，则 1). xA(x)A(a1)A(a2).A(an) 2). xB(x)B(a1)B(a2).B(an) 1). xA(x)xA(x) 2). xA(x)xA(x) 1). xA(x)Bx(A(x)B) 2). xA(x)Bx(A(x)B) 3). xA(x)Bx(A(x)B) 4). xA(x)Bx(

7、x)B) 5). BxA(x)x(BA(x),6). BxA(x)x(BA(x) 7). xA(x)Bx(A(x)B) 8). xA(x)Bx(A(x)B) 1). x(A(x)B(x)xA(x)xB(x) 2). x(A(x)B(x)xA(x)xB(x) 3). x(A(x)B(x)xA(x)xB(x) 4). xA(x)xB(x)x(A(x)B(x) 会用等价公式求谓词公式的真值. 例设论域为1,2,A(x,y):x+y=xy, 求xyA(x,y)的真值. xyA(x,y) xyA(x,y) yA(1,y)yA(2,y) (A(1,1)A(1,2)(A(2,1)A(2,2) (TT)(TF

8、) T,将下面谓词公式写成前束范式 (xF(x,y)yG(y)xH(x,y) (xF(x,y)yG(y)xH(x,y) (去) xF(x,y) yG(y) xH(x,y) (摩根) xF(x,y) yG(y) xH(x,y) (量词否定) xF(x,z) yG(y) tH(t,z) (变元换名) xyt(F(x,z) G(y) H(t,z) (辖域扩充),离散数学总复习,证明,(x)(P(x)(W(x)T(x),(x)(P(x)(T(x)R(x), (x) (P(x)R(x) (x) (P(x)W(x) (x) (P(x)R(x)P规则 P(a)R(a)ES规则 P(a)T规则(2) R(a)

9、T规则(2) (x)(P(x)(T(x)R(x)P规则 P(a)(T(a)R(a)US规则(5) T(a)R(a)T规则(3)(6) T(a)T规则(4)(7) (x)(P(x)(W(x)T(x)P规则 P(a)(W(a)T(a)US规则(9) W(a)T(a)T规则(3)(10) W(a)T规则(8)(11) P(a) W(a)T规则(3)(12) (x) (P(x)W(x)EG规则(13),首先使用含有存在量词的前提,例如.证明下面推理的有效性. 证明: x(A(x)D(x) P A(a)D(a) ES A(a) T I D(a) T I x(A(x)(B(x)C(x) P A(a)(B(

10、a)C(a) US B(a)C(a) T I x(A(x)(C(x)D(x) P A(a)(C(a)D(a) US C(a)D(a) T I C(a) T I B(a) T I A(a)B(a) T I x(A(x)B(x) EG ,证明,(x)(M(x)(P(x)Q(x) (x)Q(x)(x)(M(x)P(x) (x)Q(x)P规则（附加前提） (x)Q(x)T规则(1) Q(a)US规则(2) (x)(M(x)(P(x)Q(x)P规则 M(a)(P(a)Q(a)US规则(4) M(a)P(a)Q(a)T规则(5) M(a)P(a)T规则(3)(6) (M(a)P(a)T规则(7) (x)

11、(M(a)P(a)UG规则(8) (x)(M(x)P(x)T规则(9) (x)Q(x)(x)(M(x)P(x)CP规则(1)(10),关系性质当证明方法归纳: 设R是A上关系， 1.证明R的自反性： 方法1 用自反定义证：任取 xA,证出R. 方法2 用恒等关系IA证：证出IA R. 方法3 用自反闭包证：证出r(R)=R, 即RIA=R. 2.证明R的反自反性： 方法1 用反自反定义证：任取 xA,证出R. 3.证明R的对称性： 方法1 用对称定义证： 任取 x,yA,设R, 证出 R. 方法2 用求逆关系证：证出 Rc=R. 方法3 用对称闭包证：证出 s(R)=R, 即RRc =R.,4

12、.证明R的反对称性： 方法1 用定义1证： 任取 x,yA,设R, R.证出 x=y。 方法2用定义2证： 任取 x,yA,xy, 设R,证出R. 方法3 用定理证：证出 RRc IA . 5.证明R的传递性： 方法1 用传递定义证： 任取 x,y,zA,设R,R, 证出 R. 方法2 用传递闭包证：证出 t(R)=R, 即 RR2R3. =R. 方法3用定理证：证出 同学们可以根据具体情况,选用相应方法证明.其中必须掌 握的是用基本定义证明.,证明： 一.证明RS的自反性 方法1 用自反定义证： 任取 xA, (证出RS) 因R和S都自反， 所以有R，S， 于是有RS， 所以RS也自反。,R

13、和S都A上是自反、对称、传递的，求证RS也 是自反、对称和传递的。,方法2 用恒等关系IA证：(证出IA RS) 因R和S都自反， 所以 IA R ，IA S， 所以 IA RS 所以RS也自反。,R和S都A上是自反、对称、传递的，求证RS也 是自反、对称和传递的。,方法3 用对称闭包证： (证出 s(RS)=RS, 即(RS)(RS)c=RS.) 因为R和S对称， 所以s(R)=R,s(S)=S s(RS)= (RS)(RS)c =(RS)(RcSc) =(RRc)(RSc)(SSc)(SRc) =(s(R)(RSc)(s(S)(SRc) =(R(RSc)(S(SRc)=RS (吸收律) R

14、S对称。,证明： 二.证明RS的对称性： 方法1 用对称定义证： 任取 x,yA,设RS, (证出 RS.) 则R，S， 因为R和S对称， 所以有R，S， 于是RS。 RS对称。,R和S都A上是自反、对称、传递的，求证RS也 是自反、对称和传递的。,方法2 用求逆关系证： (证出 (RS)c=RS.) 因为R和S对称， 所以有Rc=R， Sc=S， 而(RS)c=RcSc=RS RS对称。,证明： 二.证明RS的对称性： 方法1 用对称定义证： 任取 x,yA,设RS, (证出 RS.) 则R，S， 因为R和S对称， 所以有R，S， 于是RS。 RS对称。,R和S都A上是自反、对称、传递的，求

15、证RS也 是自反、对称和传递的。,方法3 用自反闭包证： (证出r(RS)=RS, 即 (RS)IA= RS) 因R和S都自反， 所以r(R)=R, r(S)=S, r(RS)=(RS)IA = (RIA)(SIA) = r(R)r(S)=RS 所以RS也自反。,三.证明R的传递性： 方法1 用传递定义证：任取 x,y,zA, 设RS,RS, (证出RS) RSRS RSRS (RR)(S S) RS （因为R、S传递） RS 所以RS传递。,R和S都A上是自反、对称、传递的，求证RS也 是自反、对称和传递的。,三.证明R的传递性： 方法2 用传递闭包证：证出 t(RS)=RS, 即 (RS)

16、(RS)2(RS)3. =RS. 方法3用定理证：证出(RS) (RS)RS,R和S都A上是自反、对称、传递的，求证RS也 是自反、对称和传递的。,用方法2、方法3证明此题的传递性有很大难度。 R(ST)(RS)(RT),希望同学们灵活掌握证明关系性质的方法。,证明：“ ” 设R是集合X上的一个自反关系， 如果R是X上对称和传递的， 则当任意a，b，cX， 若有a，bRa，cR 则b，aRa，cR（ R是对称的） 故得b，cR（ R是传递的）,设R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当若a，b和a，c在R之中，则有b，c在R之中。,证明：“”反之， 若a，bR和a，cR，

17、则b，cR成立， 对任意x，yX， 若x，yR， R自反，x，xR， 得到y，xR， 故R是对称的。,设R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当若a，b和a，c在R之中，则有b，c在R之中。,对任意x，y，zX， 若x，yR且 y，zR， R对称， y，xR 且y，zR， 得到x，zR， 故R是可传递的。,设R是集合A上的一个传递关系和自反关系，S是A上的一个关系，使得对任意a,bA，S当且仅当R且R，试证明S是A上的一个等价关系。,证明： 1）对任意aA，因R是自反的，所以R。由R并且R，有S，即S是自反的。 2）对任意a,bA，若S，则由已知条件有R并且R，即有R并且R

18、， 所以，S，即S是对称的。,3）对任意a,b,cA，若S，S，则由已知条件有：R并且R和R并且R。所以，由R并且R，有R；由R并且R，有R；由：R并且R，有S，即S是传递的。 由1),2),3)知，S是A上的一个等价关系。,离散数学总复习,离散数学总复习,离散数学总复习,解先求A的划分：只有1个划分块的划分为1，具有2个,设A=a,b,c，求A上所有的等价关系。,划分块的划分为2、3和4，具有3个划分块的划分为 5，如下图所示。,设i导出的等价关系为i，i=1,2,3,4,5。则有 R1=, ,=AA； R2=,； R3=,； R4=,； R5=,=IA。,离散数学总复习,离散数学总复习,今有a,b,c,d,e,f,g七个人,已知下列事