《离散数学集合、数理逻辑、图部分的综合练习题》由会员分享，可在线阅读，更多相关《离散数学集合、数理逻辑、图部分的综合练习题（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 是偶数。
