《离散数学集合、数理逻辑、图部分的综合练习题》由会员分享,可在线阅读,更多相关《离散数学集合、数理逻辑、图部分的综合练习题(5页珍藏版)》请在金锄头文库上搜索。
1、集合、数理逻辑、图部分的综合练习题一、单选题:1、设 A、B 为集合,则下列命题为真的是_。A若Ax,)(BPA,则)(BPx. B若Ax,)(BPA,则)(BPx. C若Ax,)(BPA,则)(BPx. D若Ax,)(BPA,则)(BPx. 2、设 R 是实数集,其子集:X = x | -3 x, ,S=,则 RS= _。A, B, C D6、设 X=1 ,2 , R=|x,yX,x+y ,则关系R 的自反且传递的闭包是_。A, B, , C, , D, , 8、设 X= a,则 P(X) X= _。A B, C, D 9、设 R 和 S是集合 A 上的关系,则下列命题为真的是_。A若 R
2、和 S都是自反的,RS也是自反的B若 R 和 S都是对称的,RS也是对称的C若 R 和 S都是反对称的,R S也是反对称的D若 R 和 S都是传递的,RS也是传递的10、设 A= a,b, c,d,下列 _是 A 的一个划分。A a,b, b,c, c,d B a,b,c ,d,a , b ,c, d C a,b, c ,d D a,b , c 11、下列句子中 _是命题。A63xB将手机关掉!C2是有理数。D天气真冷啊!12、下列命题中_是简单命题。A张三和李四都是大学生B张三和李四是同学C张三和李四不是同学D如果张三是二年级的,则李四就是三年级的13、下列推理依据(蕴涵式)不正确的是_。A
3、ABA)(BABBA)(CBABA)(DABAB)(14、以下公式中不是可满足式的是_。A (Q P)PB(PQ) PC(PQ)QD(QP)P15、在 P,Q,R 为原子生成的极小项中,对应于二进制数101 的是 _。A PQ RB P Q RC PQ RD P QR16、设 P:天下雨, Q:我骑自行车上班,命题“除非天下雨,否则我骑自行车上班”可符号化为_。APQBQPC P QD QP17、设 P:2 是素数, Q:3 是素数, R:3是有理数。下列公式中为真的是_。A (PQ) R BR( PQ)CR ( P Q)D (RP) Q 18、在下列各组公式中,_不是等值式。A)(BxAx与
4、BxxA)(B)(BxAx与BxxA)(C)(BxAx与BxxA)(D)(xABx与)(xxAB19、设 I 是如下的解释:个体域 D=1 ,2,F(1,2) =F(2,2)=0,F(1,1)=F(2,1)=1 在 I 下,下列公式真值为1 的是 _。A)2,()1 ,(xFxFxB)2,()1 ,(xFxFxC)2,()1 ,(xFxFxD),(yxyFx20、由 n 个命题原子组成的不等值的命题公式的个数是_。A2nB2nCn2Dn2221、下列四组数中,可以对应做4 阶图(无向、简单)四个点的度的是_。A1,2,3,4 B0, 2,2,3 C1, 1,2,2 D1,3,3,3 22、设
5、G 为 7 阶图,则下列命题可能为真的是_。AG 的每个点的度都是3 BG 的每个点的度都是5 CG 的每个点的度都是6 DG 的每个点的度都是7 23、在有 n 个点的连通图中,其边数_。A最多有n-1 条B最多有n 条C最少有n-1 条D最少有n 条24、下列图中,_不是树。A无回路的连通图B有 n 个点 n-1 条边的连通图C每对点之间都有通路的图D连通但任意删去一条边就不连通的图二、填空题1、设 A = 0 ,1,3 ,B = 0 ,3,6 ,R 是 A 到 B 的关系: R = |x,yAB ,则 R 的关系矩阵是_。2、设集合A= 1 , 2,3,4,5, 6,7,8,9,10,1
6、1,12 ,R 是 A 上的整除关系,子集B=2 ,4,6的最大元是 _,最小元是 _,上界是 _,下界是 _。3、设集合A= 1 , 2,3,4,5, 6,8,10,24, 36,R 是 A 上的整除关系,子集B=1 , 2, 3, 4 的上界是 _, 下界是 _, 上确界是 _, 下确界是 _。4、设集合A=2 ,3,4,5,6,8,10,12 ,R 是 A 上的整除关系,A 的极大元是 _,极小元是 _。5、设非空集合A 满足 |A|=n,则从 A 到 A 的双射函数有 _个。6、设 A = a, a ,a ,B = a, a ,则BA=_ 。7、设 A、B 是集合,则命题A- B= A
7、 = B 的真值是 _。8、P Q 的主合取范式中含_个极大项。9、设 F(x): x 是人, G(x):x 呼吸,命题“所有人都呼吸”可符号化为_。10、设 F(x):x 是实数, G(x):x 是有理数, H(x):x 是无理数,命题“实数不是有理数就是无理数”可符号化为_。11、设 F(x):x 是熊猫, G(x):x 产在中国,命题“熊猫都产在中国”可符号化为_。12、在个体域D=1 ,2,3 中,公式)()(yyGxxF消去量词后的形式是_。13、公式 pq 在联结词完备集, 中的等值式是 _。14、 n 阶 m 条边得到图G 是树的充分必要条件是G 连通且 m=_。15、完全图Kn
8、的边数为 _。16、 n 阶 k 度正则图的边数为_。17、 n 阶图(无向简单图)中各点度的最大值不超过_。18、设图 G 有 12 条边,有 6 个度为 3 的点,其余点的度都小于3,则 G 至少有 _个点。三、计算题1、设集合A= 1 , 2,3,4,5, 6,7,8,9,10,12,画出 A 上整除关系的哈斯图。2、设 f:RR, f(x)=x2+1,g:RR, g(x)=x+2,求 fg3、求 p( pqr)的主析取范式和主合取范式。4、构造下面推理的证明,要求每步都写出依据。前提: pq, qr, r结论: ps5、化简公式( (PQ)( Q P) ) R 6、用真值表判断( ( PQ)( QR) )( P R)是否重言式。7、写出),()(yxyGxxF的前束范式。8、设有向图G=,其中: V= a,b,c,d, e,A=, ,写出 G 的邻接矩阵。9、对下图,求v1 到其余各点的最短路径。v27 v42 v63 1 8 v1 2 5 4 9 7 9 v34 v5v710、求上图的最小生成树(最优树)。四、证明题1.证明( P( PQ) R)= PR2.证明推理 “任何人只有不遵守学校的纪律才会被处分;小张被处分了。 所以小张必然违反了学校的某条纪律。 ”3.证明一个图中度为奇数的点的个数必为偶数。4.若有 n 个人,每个人在其中恰好有3 个朋友,证明n 是偶数。