离散复习分析

1、1证明下列等价式： (pr)(q r) (pq) r证明：左边(pr)(qr)(pq)r(p q)r(p q)r (p q)(p q)p证明：(p q)(pq)p(qq)pFp2. 求下面命题公式的主析取范式，再用主析取范式求出主合取范式。(pq)(q r)证明： (pq) (qr)(p q)(qr)(pq)q) (p q)r)(pq)(pr) (qr)(pq r) (pqr)(pqr) ( pqr)( pqr) (pqr) ( p q r) ( p q r)( p qr) (pqr)(主析取范式 ) 0,1,3,7 2,4,5,6(pq r)(pqr)(p qr)(pqr)(主合取范式 )3

2、用CP 规则推证下题的有效结论。pqr s， stupu证明 : p pqP( 附加前提 )T附加律 pqr s rs s stPT假言推理T化简律T附加律 stu u puPT假言推理CP 规则4 证明下面命题推得的结论是有效的： 如果今天是星期三， 那么我有一次离散数学或数字逻辑测验。 如果离散数学课老师有事， 那么没有离散数学测验。 今天是星期三且离散数学老师有事。所以，我有一次数字逻辑测验。注：设p：今天是星期三。q：我有一次离散数学测验。r：我有一次数字逻辑测验。s：离散数学课老师有事。证明：该推理就是要证明：p (qr)， sq，psr psP pT化简律 sT化简律 sqPqT假

3、言推理 p(qr)P qrT假言推理 rT析取三段论5证明下式。( x)(F(x)(G(y)R(x)， (x)F(x)( x)(F(x)R(x)证明： ( x)F(x) P F(c) ES (x)(F(x) (G(y) R(x) P F(c) (G(y)R(c)US G(y)R(c)T假言推理 R(c)T化简律 F(c) R(c)T合取引入 ( x)(F(x) R(x)EG6. 设 A= a,b ，B= 1,2,3 ，求： A B，BA，AA，BB 和 (AB)( B A)。解： A B=a,1,a,2,a,3,b,1,b,2,b,3BA=1,a,1,b,2,a,2,b,3,a,3,bAA=a

4、,a,a,b,b,a,b,bBB=1,1,1,2,1,3,2,1,2,2,2,3, 3,1 , 3,2 , 3,3(AB) (BA)=7. 设G,是一个简单有向图Vv1,v2,v3,v4，邻接矩阵如下：V E=， =0100A(G)=001111011100求 v1的出度 deg ( v1) 。求 v4 的入度 deg ( v4) 。 由 v1 到 v4 长度为 2 的路有几条？解： deg ( v1)=1 deg ( v4)=2010001000011A2=AA=0 0 11 0011=220 1110111011211110011000111由于2=1，所以由 v1 到 v4 长为 2 的

5、路有 1 条。a14证明：(p(p q) q(p (pq) q(p (pq) q(pp)(pq) q(pq)qT9. 求命题公式 ( p q) r 的主析取范式，再用主析取范式求出主合取范式。解：(pq) r(p q)r(p q r)(pqr)(p r)(pr)(p q r)(pqr) (pqr) (pq r) (p qr) (pq r)(p q r) (pqr) (pqr) (p q r) (pqr)( 主析取范式 ) 1,3,5,6,7 0,2,4(p q r)(p qr)( p q r)(主合取范式 )10用反证法推证下题的有效结论。r q， rs，s q，p qp证明 :pP( 附加前

6、提 ) pT双重否定律 pqP qT假言推理 r qPrT拒取式 r sP sT析取三段论 s qPqT假言推理 q q（矛盾）T合取引入11证明下面推理：每个有理数都是实数。有的有理数是整数。因此，有的实数是整数。解：首先将命题符号化：Q(x)： x 是有理数。R(x)： x 是实数。Z(x) ：x 是整数。本题要证明： ( x)(Q(x) R(x), ( x)(Q(x) Z(x)( x)(R(x) Z(x)证明： ( x)(Q(x) Z(x)P Q(c)Z(c)ESQ(c)T化简律Z(c)T化简律( x)(Q(x) R(x)PQ(c)R(c)USR(c)T假言推理R(c)Z(c)T合取引入

7、( x)(R(x) Z(x)EG12证明下式。( x)(F(x) (G(y) R(x) ，( x)F(x)( x)(F(x) R(x)证明： ( x)F(x)PF(c)ES( x)(F(x) (G(y) R(x)PF(c)(G(y) R(c)USG(y) R(c)T假言推理R(c)T化简律F(c)R(c)T合取引入( x)(F(x) R(x)EG13.设A1,2,3,4,6,8,12,24上的整除关系Ra1 ,a2a1, a2A, a1整除 a2R 是否为 A 上的偏序关系？若是，则：(1)、画出的哈斯图；(2)、求它的极小元，极大元，极大元，最大元。解答：（1）R 是 A 上的偏序关系。（

8、2）极小元、最小元是1,极大元、最大元是 24。14. 有向图 G 如图所示。 写出 G的邻接矩阵。 根据邻接矩阵求各结点的出度和入度。 求 G 中长度为 3 的路的总数，其中有多少条回路。01101000解： MR=10100000441，1，deg)=2deg (v(v)=1deg (v2)=1，deg (v2 )=2，3)=1，deg (v3)=2，deg (vdeg (v4)=0，deg (v4)=1。11011110 A2=01 1 0，A3=11 01100001100000 440000 44长度为 3 的路有 8 条，其中回路 3 条。15证明： PQ, R S, PR 蕴涵

9、Q S。证明： (1) PRP(2) RPT(1)(3) PQP(4) R QT(2)(3)(5) Q RT(4)(6) RSP(7) QST(5)(6)(8) QST(7)16. 设命题公式 G = (PQ)(Q ( PR), 求 G 的主析取范式。证明： G = (PQ)(Q( PR)= ( PQ)(Q(PR)= (P Q) (Q(PR)= (P Q)(QP)(QR)= (P Q R) (P Q R)(P QR) (PQ R)(PQR)(PQR)= (PQR)(PQR)(PQR)(PQR)(PQR)= m3m4m5m6 m7 =(3, 4, 5, 6, 7).17.设 R 和 S 是集合

10、A a, b, c, d 上的关系，其中R(a, a),(a, c),(b, c),(c, d),S(a, b),(b, c),(b, d),(d, d).(1) 试写出 R 和 S 的关系矩阵；(2) 计算 R?S, R S, R 1, S 1?R1.10100100解：(1)MR0010M S00110001000000000001(2)R?S(a, b),(c, d),R S (a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d),R 1(a, a),(c, a),(c, b),(d, c),S 1?R1 (b, a),(d, c).18用推理规

11、则证明P(a)G (a) 是x( P( x)(Q(x)R( x) ,(Q (a)R(a) ,S(a) ,x( S( x)G ( x) 的有效结论。证明：（1）xP( x)(Q (x)P(x)P（2） P(a)(Q( a)P(a)US(1)(3)(Q (a) R(a)P(4)P(a)T(2)(3)I(5)x( S( x)G (x)P(6)S( a)G ( a)US(5)(7)S( a)G (a)T(6)E,I(8)S(a)P(9)G (a)T(7)(8)I(10)P(a)G ( a)T(4)(9)I19构造下面命题推理的证明如果今天是星期三， 那么我有一次英语或数学测验； 如果数学老师有事， 那

12、么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。解： p：今天是星期三。q ：我有一次英语测验。r ：我有一次数学测验。s ：数学老师有事。前提： p (q r) , sr , p s结论： q证明： p s前提引入 p化简 p(q r)前提引入 q r假言推理 s化简 sr前提引入 r假言推理 q析取三段论推理正确。20. 设集合 A1, 2, 4, 6, 8, 12 ， R 为 A 上整除关系。(1) 画出偏序集 (A,R) 的哈斯图；(2) 写出 A 的最大元，最小元，极大元，极小元；(3) 写出 A 的子集 B = 4, 6, 8, 12 的上界，下界，最小上界，最大

13、下界.解： (1)8124621(2) 无最大元，最小元 1，极大元 8, 12; 极小元是 1.(3) B 无上界，无最小上界。下界1, 2; 最大下界 2.21.某次会议有 20 人参加，其中每人至少有10 个朋友，这 20 人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？并说明理由。解：可能。将人用结点表示，当两人是朋友时相应结点间连一条边，则得一个无向图G V , E ，20 人围一桌，使每人邻做都是朋友，即要找一个过每个点一次且仅一次得回路。由题已知，u , vV , deg(u)10 ,deg(v) 10 ，deg(u)deg(v) 20 ，由判定定理， G 中存在一条汉

14、密尔顿回路。即所谈情况可能。e122. 有向图 G 如图所示。v 1v 4（ 1）求 G 的邻接矩阵 A ；e 3e4e6e 7e 2（ 2） G 中 v1 到 v4长度为 4 的路径有几条？v 2e5v 3（ 3） G 中 v1 到自身长度为 3 的回路有几条？（ 4） G 是哪类连通图？解：12101231（1） A0010A20001000100100010000112431264A30010A40 00 10001001000100001（ 2）由A4 中 a1444 可知， v1 到 v4长度为 4 的路径有条（ e1 e1 e4 e6 ， e4 e6 e7 e6 ，e1 e2 e5

15、e6 ， e1 e3 e5 e6 ）。（ 3）由 A3 中 a1131可知， v1 到自身长度为 3 的回路有 1 条（ e1e1e1 ）。（ 4） G 是单向连通图。23用逻辑推演下式(AB) C，D，CDAB解： CD前提引入DC置换D前提引入C假言推理 ( AB) C前提引入( AB)拒取式AB置换24. 求 (QP)(PQ ) 的主合取范式。解：(QP)(PQ)(QP)(PQ)(QPQ )(PPQ)F(P Q) (PQ) (PQ)(PQ)25. 设 f,g,hRR，且 f(x) =x 2- 2， g(x) =x4，h(x) =x 3- 1 试求 g f 和 fg g f 和 fg 是单

16、射？满射？双射？ f,g,h 中哪些有反函数？若有，求出反函数。2f g(x)=x 2+8x+14 g f 不是单射，不是满射，不是双射。f g 不是单射，不是满射，不是双射。 f 不是单射，不是满射，不是双射。无反函数。g 是单射，是满射，是双射。有反函数。g-1(x)= x- 4h 是单射，是满射，是双射。有反函数。h-1(x)= 3x126用 CP 规则证明下式。( x)(F(x) R(x)(x)F(x) (x)R(x)证明： (x)F(x) P(附加前提 ) F(c) US (x)(F(x) R(x) P F(c) R(c)US R(c)T假言推理 (x)R(x) UG (x)F(x)

17、 (x)R(x)CP27符号化语句： “有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证其结论。解： M ( x) : x是人;F ( x) : x是花;G(x) : x是杂草 ;H (x, y) : x喜欢 yx(M (x)y( F ( y) H ( x, y)x( M (x)y(G ( y)H ( x, y)x(F ( x)G ( x)证明如下： x( M (x)y( F ( y)H ( x, y)P M ( a)y( F ( y)H (a, y)ES M (a)TIy( F ( y)H (a, y)x(M ( x)y(G ( y)H ( x, y) M ( a)y(G (

18、 y)H ( a, y)y(G ( y)H ( a, y)y( H (a, y)G ( y) F (z)H ( a, z) H (a, z)G ( z) F (z)G ( z)x( F (x)G ( x)TIPUSTITEUSUSTIUG28. 集合 A2 , 3 , 6 , 12 , 24 , 36 上的偏序关系为整除关系。设B 6 ,12 ，C 2 , 3 , 6 ，试画出其哈斯图，并求 A，B，C 的最大元素、极大元素、下界、上确界。解：哈斯图为集合最大元极大元下界上确界A无24，36无无B12126，2，312C66无629. 旋转鼓的表面分成 8 块扇形 ,如图所示。图中阴影区表示用

19、导电材料制成 ,空白区用绝缘材料制成 ,终端 a、b 和 c 是接地或不是接地分别用二进制信号0或 1 表示。因此 ,鼓的位置可用二进制信号表示。试问应如何选取这 8 个扇形的材料使每转过一个扇形都得到一个不同的二进制信号 ,即每转一周 ,能得到 000 到 111 的 8 个数。解：这个问题可以这样来考虑 :如图用 4 个结点分别表示 0011的 4 个二进码 ,若结点 u 的二进码的第二位和结点 v 的第一位相同，则 (u,v)是有向图的一条边 ,这条边对应于 3 位的二进码，通过这种办法可以构造出一个有 4 个结点 8 条边的有向图 ,问题中找 000 到 111 的 8 个数就是在图中

20、找一条有向欧拉回路 ,由回路中每条边对应码构成的循环序列就是所求结果 .,由此得到对应的8 个 0 或 1 的排列方式 0001110130. 无向图 G 如图所示。 写出 G 的邻接矩阵。 根据邻接矩阵求各结点的度数。 求 G 中长度为 3 的路的总数，其中有多少条回路。0111解：邻接矩阵101111001100 deg(v1)=3，deg(v2 )=3，deg(v3)=2， deg(v4)=2。0111011101113211A=1011，A2= 10111011= 231111001100110011221100110011001122011132114555A3= 10112311= 5455110011225522110011225522长度为 3 的路的总条数 66 条，其中回路 12 条。31假定 A和 ABAC，说明这不能得出 BC ，假设中增加ABAC ，能得出 BC 吗？试证明。证明：反例A1,2 ,B2,C1则ABAC但BCBAB(A