《离散数学复习题及答案.pdf》由会员分享，可在线阅读，更多相关《离散数学复习题及答案.pdf（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.写出命题公式（P（P Q）的真值表。答案：2.证明 答案：3.证明以下蕴涵关系成立：答案：4.写出下列式子的主析取范式：答案：)()(QPQPQPQ)P(Q)(PP)(QP)P(Q)(QQ)P(P)Q)P(Q)Q)P(P)Q(Q)P(QPQQPP)()()(RPQP 5.构造下列推理的论证：pq,pr,st,sr,t q 答案：st 前提 t 前提 s 拒取式 I12 sr 前提 r 假言推理 I11 pr 前提 p 拒取式 I12 pq 前提 q 析取三段论 I10 6.用反证法证明：p(rs)q),p,s q)()(RPQP)()(RPQP)()(RQPPQP)()()()(RQRPP
2、QPP)()()(QRPRPQRPQ)()()(PRQPRQQRP)()()(QRPRPQRPQ)(QRP 7.请将下列命题符号化：所有鱼都生活在水中。答案：令 F(x)：x 是鱼 W(x)：x 生活在水中)(W(x)F(x)x 8.请将下列命题符号化：存在着不是有理数的实数。答案：令 Q(x)：x 是有理数 R(x)：x 是实数 Q(x)x)(R(x)(9.请将下列命题符号化：尽管有人聪明，但并非一切人都聪明。答案：令 M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10.请将下列命题符号化：对于所有的正实数 x,y，都有 x+yx。答案：令 P(x):x 是正实数 S(x,
3、y):x+yx 11.请将下列命题符号化：每个人都要参加一些课外活动。答案：令 P(x):x 是人 Q(y):y 是课外活动 S(x,y):x 参加 y )()()()(xCxMxxCxMx),()()(yxSyPxPyx)(),()(yQyxSxPyx12.请将下列命题符号化：某些人对某些药物过敏。答案：令 P(x):x 是人 Q(y):y 是药 S(x,y):x 对 y 过敏 13.求)()()(yyRyQxPy的对偶式:答案：14.求下列谓词公式的前束范式：答案：15.证明：答案：),(),(),(uyxuQzyPzxzPyx),(),(),(uyxuQzyPzxzPyx),(),(),
4、(uyxuQzyPzxPzyx),(),(),(utsuQzyPxPyx),(),(),(utsQzyPxPuyx)(),()(yQyxSxPyx),(),(),(uyxuQzyPzxzPyx 16.用反证法证明：x(P(x)Q(x),xP(x)xQ(x)答案：17.证明：前提：x(C(x)W(x)R(x),x(C(x)Q(x).结论：x(Q(x)R(x).答案：(1)x(C(x)Q(x)前提引入 (2)C(a)Q(a)(1)ES (3)C(a)(2)化简规则 (4)x(C(x)W(x)R(x)前提引入 (5)C(a)W(a)R(a)(4)US (6)W(a)R(a)(3)(5)假言推理 (7
5、)R(a)(6)化简规则 (8)Q(a)(2)化简规则 (9)R(a)Q(a)(7)(8)合取引入规则 (10)x(Q(x)R(x)(9)EG 18.判断：下列命题是否正确？答案：(1)(2)(3)(4)(5)(6)(7)(8)19.列出下列集合的元素 (1)x|xNt(t2,3x=2t)(2)x|xNts(t0,1s3,4txs)(3)x|xNt(t 整除 2xt)答案：(1)4,6 (2)1,2,3 (3)3,4,5 20.S=0,1,2,3,4,5,6,7,8,9，A=2,4,5,6,8 B=1,4,5,9，C=x|xZ+,2x5 答案：21.一个学校有 507，292，312 和 34
6、4 个学生分别选择了 A,B,C,D 四门课程。有 14 人选了A 和 B，213 人选了 A 和 D，211 人选了 B 和 C，43 人选了 C 和 D。没有学生同时选择 A 和 C，也没有学生同时选择 B 和 D。问共有多少学生在这四门课程中选了课？答案：解：画文氏图 280+87+38+88+14+211+213+43=974 22.分别求下列集合的幂集(1)(2)(3)1,1 答案：解:(1)()=空集 的幂集的基数为 1 (2)()=,幂集的基数为 2 (3)(1,1)=,1,1,1,1 23.A=0,1,B=1,2,C=3,4,5,求 AB,BA,ABC,A2,C2.答案：AB=
7、(0,1),(0,2),(1,1),(1,2)BA=(1,0),(2,0),(1,1),(2,1)ABC=(0,1,3),(0,1,4),(0,1,5),(0,2,3),(0,2,4),(0,2,5),(1,1,3),(1,1,4),(1,1,5),(1,2,3),(1,2,4),(1,2,5)A2=(0,0),(0,1),(1,0),(1,1)C2=(3,3),(3,4),(3,5),(4,3),(4,4),(4,5),(5,3),(5,4),(5,5)24.1.设 A=1,2,3,4,5,6,7,8,下列选项正确的是（C）A.1A B.1,2,3 A C.4,5 A D.A 2.设 A=x
8、|x3 x=0,B=x|x2 40,xz,C=x|y=2x-1,D=x|x+y=5,xy=6则有（A）A.A=B B.A=C C.C=D D.C=A 25.求关系的定义域和值域：设 A=2，4，6，8，R 是 A 上的小于关系，即当 a,bA 且 a b 时，（a,b）R，求 R 及 D(R),C(R)答案：R=（2，4）,（2，6）,（2，8）,（4，6）,（4，8）,（6，8）.R 的定义域 D(R)=2，4，6，R 的值域 C(R)=4，6，8。26.设 A=a,b,c,d,求 A 上的恒等关系。答案：IA=(a,a),(b,b),(c,c),(d,d)。27.设 A=1,2,3,4,5
9、,R 是 A 上的小于等于关系,即当 a b 时,(a,b)R。求 R的关系矩阵和关系图。答案：解:易知 A 上的小于等于关系为 R=（1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5),(3,3),(3,4),(3,5),(4,4),(4,5),(5,5)其关系矩阵为 1000011000111001111011111RM 28.X=a,b,c，Y=1,2，关系 R=(a,1),(b,2),(c,1)S=(a,1),(b,1),(c,1)求 RS、RS 和 R 的补 答案：29.设 A=1，2，3，B=a,b,c,d,C=x,y,z，R
10、是 A 到 B 的二元关系，R=(1,a),(1,b),(2,b),(3,c)，S 是 B 到 C 的二元关系，S=(a,x),(b,x),(b,y),(b,z)。求复合关系 RS 的关系矩阵.答案：30.答案：31.设 A=a,b,c，R 是 A 上的二元关系，R=(a,a),(b,b),(a,b),(a,c),(c,a)，问：R 是自反的吗？是反自反的吗？是对称的吗？是反对称的吗？是可传递的吗？答案：由于 cA，而(c,c)，所以 R 不是自反的。由于(a,a)R，(b,b)R，所以 R 不是反自反的。由于(a,b)R，而(b,a)，所以 R 不是对称的。由于(a,c)R，且(c,a)R，
11、所以 R 不是反对称的。由于(c,a)R，且(a,c)R，但(c,c)，所以 R 不是可传递的。RRR 32.设 A=1,2,3，分析 A 上的下述 5 个关系具有哪些性质：L=,N=,S=,G=,答案：33.设 A=a,b,c,d，A 上的关系，R=(a,b),(b,a),(b,c),(c,d)求 r(R)、s(R)、t(R)答案：34.A=a,b,c,R=(a,b),(b,c),(c,a)，求 r(R),S(R)和 t(R)答案：c)(d,b),d),(c,(c,c),(b,a),(b,b),(a,c)(d,b),(c,b),(a,a),(b,d)(c,c),(b,a),(b,b),(a,
12、RRS(R)d)(d,c),b),(c,(b,a),(a,d),(c,c),(b,a),(b,b),(a,IRr(R)A234232432Rd)(b,b),(b,c),(a,a),(a,RRRc)(b,a),(b,d),(a,b),(a,RRRd)(b,b),(b,c),(a,a),(a,RRR而RRRRt(R)35.A=1,2,3,4，R=(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4),判断 R 是否是等价的。答案：36.判断下列关系是否为等价关系？(1)A=a,b,c,d，R=(a,a),(b,a),(b,b),(c,c),(d,d),(d,
13、c)(2)A=1,2,3,4，R=(1,1),(1,2),(1,3),(2,1),(2,2),(3,1),(2,3),(3,3),(4,4),(3,2)答案：（1）（2）37.A=1,2,3,4在幂集(A)上定义的二元关系如下：R=(S,T)|S,T(A)，|S|=|T|，写出商集(A)/R。答案：解：首先求(A)。(A)=,1,2,3,4,1,2,1,3,1,4,2,3,2,4,3,4,1,2,3,1,2,4,1,3,4,2,3,4,1,2,3,4 共 16 个元素！38.设集合 X=2166，243，375，648，455 X 中的关系 R 为：R=(x,y)|x,yX，并且 x 和 y
14、中有相同数字 问：R 是不是相容关系？答案：39.A=1，2，3，4，5，6，8，10，12，16，24，R 是 A 上的整除关系，请画出的哈斯图。答案：40.已知偏序集的哈斯图如图所示,试求出集合A和关系R的表达式.求 A 的极小元、最小元、极大元、最大元.设 Bb,c,d,求 B 的下界、上界、最大下界、最小上界.答案：极小元：a,b,c,g；极大元：a,f,h；没有最小元与最大元.B 的下界和最大下界都 不存在,上界有 d 和 f,最小上界为 d.41.以下关系矩阵所代表的关系是什么关系？答案：相容关系 42.设集合 A=1，2，3，4，5，6，8，10，12，16，24，R 是 A 上
15、的整除关系，请问关系R是否是偏序关系？是否是全序关系？画出的哈斯图，并根据图求集合A的极大极小元、最大最小元，设 B=2，3，4，求集合 B 的上界、最小上界、下界、最大下界。答案：是偏序关系，不是全序关系。A 的极大元：24,16,10 A 的极小元：1 A 的最大元：没有 A 的最小元：1 B 的上界：12,24 B 的最小上界：12 B 的下界：1 B 的最大下界：1 43.找出如下哈斯图中的子集a,b,c、j,h和a,c,d,f的上界和下界。1110011101M答案：a,b,c 上界：e,f,j,h 下界：a j,h 上界：无 下界：f,d,e,b,c,a a,c,d,f 上界：f,
16、j,h 下界：a 44.判断下列关系是否是映射？是否是单射？是否是满射？答案：映射（非单射、非满射）、映射（满射）映射（单射）、不是映射 45.X=x1,x2,x3,Y=y1,y2,Z=z1,z2 f:XY，g:YZ，求 h=gf 答案：46.下列哪些关系可以构成函数（映射）？a.f=(x,y)|x,yN,x+y10 b.f=(x,y)|x,yR,x2=y 答案：能 不能 47.判断下列函数是单射、满射或双射？a.f:NN,f(x)=x+2;b.f:NN,f(x)=x(mod 2);c.f:N(N),f(x)=x;答案：单射 什么都不是 单射 48.f1 f=？，ff1=？答案：f1f=IA，
17、ff1=IB 49.构造下列函数的反函数：1.f(x)=sinx 2.f(x)=x2 ,x(-，0)3.A=1,2,3,B=a,b,c,f:AB,f=(1,a),(2,c),(3,b)答案：f-1(x)=arcsinx f-1(x)=-x1/2 f-1=(a,1),(c,2),(b,3)50.答案：51.已知 x=a,b,c,Y=1,2,3,4 f:XY 如图所示,试构造函数 g:YX,使得 gf=Ix 答案：g=(1,a),(2,c),(3,b),(4,a)52.请给出图中各点的度数，以及图的最大度数和最小度数。答案：d(v1)=4,d(v2)=4,d(v3)=2,d(v4)=1,d(v5)
18、=3 D(G)=4,d(G)=1 53.请给出图中各点的出度和入，以及图的最大出度和最小入度。答案：d+(a)=4,d-(a)=1,d(a)=5,d+(b)=0,d-(b)=3,d(b)=3,+(D)=4,+(D)=0,(D)=3,(D)=1,(D)=5,(D)=3.54.(3,3,3,4),(2,3,4,6,8)能成为图的度数序列吗?答案：不可能.它们都有奇数个奇数.55.已知图 G 有 10 条边,4 个 3 度顶点,其余顶点的度数均小于等于 2,问 G 至少有多少个顶点?答案：设G有n个顶点.由握手定理,43+2(n-4)210 解得 n8 56.下面无向图中有几个顶点？(1)16 条边
19、，每个顶点都是 2 度顶点(2)21 条边，3 个 4 度顶点，其余的都是 3 度顶点(3)35 条边，每个顶点的度数至少为 3 的图最多有几个顶点？答案：57.确定下列各图的出度、入度和度数 答案：58.判断下列图是否同构 答案：是 是 不是 是 59.下图中，1.写出a,d,e的导出子图 2.画出它的一个生成子图 3.边集e4,e7,e6的导出子图 答案：60.试画出以下两个图的并图、交图和环和。答案：61.判断下列各图是否是连通图：答案：是、不是 62.指出下列有向图的连通性 答案：强连通图 单向连通图 弱连通图 强连通图 单向连通图 弱连通图 63.求下列图的强连通分支 答案：64.（
20、1）e5、e2、e3、e6、e4是否是下图的边割集？（2）v5、v2、v4、v3、v1、v2、v2、v3是否是下图的点割集？v1v2v3v4v5v6v7 答案：（1）是、是、是、否（2）是、是、是、否、否 65.求出下图的全部割点和桥 答案：66.下列图是否是树？如果是，找出树的分枝结点和树叶。答案：不是、是 分枝结点：e,f 树叶：a,b,c,d,g,h 67.设一棵树 T 有 2 个度数为 2 的结点，1 个度数为 3 的结点，3 个度数为 4 的结点，求 T有几片树叶。答案：68.已知无向树 T 有 5 片树叶,2 度与 3 度顶点各 1 个,其余顶点的度数均为 4.求 T 的阶数 n。
21、答案：69.求下列树的树根、树叶、树高、内点、分枝点、各个结点的层数 答案：a 是树根.b,e,f,h,i 是树叶.c,d,g 是内点.a,c,d,g 是分枝点.a 为 0 层;1 层有 b,c;2 层有 d,e,f;3 层有 g,h;4 层有 i.树高为 4.70.求下列树的树高、内点数、分枝点树、几叉树？答案：4、5、6、4 71.下列树是不是完全二叉树？是不是满二叉树？答案：4 叉树、完全 3 叉树 72.求下列二叉树的前序、中序、后序遍历 答案：前序：a b d e h c f g i j 中序：d b h e a f c i g j 后序：d h e b f i j g c a 73
22、.求下列二叉树的前序、中序、后序遍历 答案：abcdefghijklm 74.构造下列数的排序二叉树：15,3,1,6,18,7,10,20 答案：75.求树叶权为 4，2，3，5，1 的最优树。答案：最优树的权重 W(T)为：13+23+32+42+52=33 76.求带权图的最小生成树。答案：这棵最小生成树的权为:1+1+2+2+3+4=13.77.求下图的邻接矩阵 答案：78.写出下列表达式的“波兰表示式”(a 4b)c (7d+b)/(c+5a)答案：先表示成二叉树的形式 再对二叉树进行前序遍历即的波兰式为：/a4bc+7db+c5a 0110110000100110010110110A/-+X+c-aX4bX7dcX5ab