当前位置：首页 > 湖南工程学院离散结构复习题及答案
一、选择题（可多选）
1. 下列语句中是命题的是（AD）
（a）7能被2整除（b）什么时候开会呀？
（c）2x+3<4 （d）3是素数当且仅当四边形内角和为360度 2. 下列语句中是命题的是（CD） （a）你去哪里？ （b）x+y>10。
（c）n是偶数当且仅当它能被3整除。（n为一固定的自然数） （d）吃一堑，长一智。
3. 下列语句中是简单命题的是（D） （a）请快开门！
（b）苹果树和梨树都是落叶乔木。 （c）2是质数或合数。
（d）豆沙包是由面粉和红小豆做成的。 4. 下列语句中是复合命题的是（D）
（a）7能被2整除（b）什么时候开会呀？
（c）2x+3<4 （d）3是素数当且仅当四边形内角和为360度 5. A与B均为含n个命题变元的公式，下列命题为真的是（BC） （a）AB 当且仅当 AB是可满足式 （b）A
B 当且仅当 A与B有相同的主析取范式
（c）若A为重言式，则A的主析取范式中含有2n个极小项 （d）若A为矛盾式，则A的主析取范式为1
6. 设A与B均为含n个命题变项的公式，下列命题为真的是（D） （a）若A为矛盾式，则A的主析取范式为1
（b）若A为矛盾式，则A的主合取范式为1 （c）任何公式A都能等值地化为联结词集{∧、∨} 中的公式 （d）任何公式A都能等值地化为联结词集{?、→、∧}中的公式
7. 设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备( D ). (a)自反性
(b)传递性
(c)对称性
(d)反对称性
8. 设集合A = {1,2,3,4}, A上的关系R＝{(1,1),(2,3),(2,4),(3,4)}, 则R具有( B )。 (a)自反性 (b)传递性 (c)对称性 (d)以上答案都不对
9. 设G、H是一阶逻辑公式，P是一个谓词，G＝?xP(x)，H＝?xP(x)，公式G?H是( C (a)永真的 (b)永假的 (c)可满足的 (d)前束范式. 10. 设命题公式G＝?(P?Q)，H＝P?(Q??P)，则G与H的关系是( A )。 (a)G?H (b)H?G (c)G＝H (d)以上都不是
11. 图相对于完全图的补图为（A）。
(a) (b) (c) (d)
)。.
12. 对图G：，则k(G)、?(G)、?(G)分别为（C）。 (a) 2、2、2(b) 1、1、2(c) 2、1、2(d) 1、2、2
13. 设G是5个顶点的完全图，则从G中删去( A )条边可以得到树。 (a)6 (b)5 (c)10 (d)4
?0?1G的邻接矩阵为??1??1?1?1010011011101011??0?，则1??1?0??14.无向图G的顶点数与边数分别为( D )。
(a)4，5 (b)5，6 (c)4，10 (d)5，8
15. 在任何图G中必有偶数个（B）
(a)度数为偶数的结点(b)度数为奇数的结点
(b)入度为奇数的结点 (c)出度为奇数的结点
16. 设A（G）是有向图G=
(a)(P∧Q)→(P∨Q) (b)(P?Q)?( (P→Q) ∧(Q→P))； (c)? (P→Q) ∧Q(d) P→(P∨Q)
18. 设R，S是集合A上的关系，则下列说法正确的是（A） (a) 若R，S 是自反的，则R?S是自反的； (b) 若R，S 是反自反的，则R?S是反自反的； (c) 若R，S 是对称的，则R?S是对称的；
(d) 若R，S 是传递的，则R?S是传递的。 19.公式A=?x(P(x)→Q(x)）的解释I为：个体域D={2}，P(x)：x>3，Q(x)：x=4，则A的真值为（A）。
(a) 1(b) 0(c)可满足式(d)无法判定。
20. 下列等价关系正确的是（B）。
(a) ?x(P(x)?Q(x))??xP(x)??xQ(x)；
(b) (c)
?x(P(x)?Q(x))??xP(x)??xQ(x)；
?x(P(x)?Q)??xP(x)?Q；
(d)?x(P(x)?Q)??xP(x)?Q。
21. 偏序集
一、填空题
1. 已知命题公式G＝? (P?Q)∧R，则G的主析取范式是__ P∧?Q∧R_________ 2. 设命题公式G＝? (P?(Q∧R))，则使公式G为真的解释有_____(1,0,0)_________，
6
(b)上界
(c)最小上界 (d)以上答案都不对
3 2 1 5 4
_____(1,0,1)______________,____(1,1,0)____________.
3. 设集合A＝{1,2,3,4}，A上的关系R1 = {(1,4),(2,3),(3,2)}，R2 = {(2,1),(3,2),(4,3)}，则 R1?R2 = ____{(1,3),(2,2),(3,1)}_____，R2?R1 =______{(2,4),(3,3),(4,2)} _________，R12 =______{(2,2),(3,3)}_____。
4. 设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为
______________{(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}______________________________. 5. 设一阶逻辑公式G = ?xP(x)??xQ(x)，则G的前束范式是___?x(?P(x) ∨Q(x))______________. 6. 设谓词的定义域为{a, b}，将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是____(R(a)∧R(b))?(S(a) ∨S(b))_____________。
7. 设命题公式G＝? (P?(Q∧R))，则使公式G为真的解释有_____(1,0,0)______________，______(1,0,1)_______________，_______(1,1,0)_____________。
8. 设集合A＝{1, 2, 3, 4}，A上的二元关系R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。则R?S＝____{(1,3),(2,2)}__________________,
9．设R是集合A上的二元关系，则s(R) = R∪R-1，t(R) = R∪R2∪R3∪…。
三、计算题
1.设集合A＝{1, 2, 3, 4, 6, 8, 9, 12}，R为整除关系。 （1）画出半序集
（2）写出A的子集B = {3,6,9,12}的上界、下界、最小上界、最大下界； （3）写出A的最大元、最小元、极大元、极小元。 解：( 1 )
( 2 )B无上界，无最小上界，下界1,3，最小下界3。
( 3 )A无最大元，最小元1，极大元8,12,9，极小元1。
2. 设集合A＝{1, 2, 4, 6, 8, 12}，R为A上整除关系。
（1）画出半序集(A,R)的哈斯图；
（2）写出A的最大元，最小元，极大元，极小元；
（3）写出A的子集B = {4, 6, 8, 12}的上界，下界，最小上界，最大下界. 解：( 1 )
( 2 ) A无最大元，最小元1，极大元8,12，极小元1。 ( 3 ) B无上界，无最小上界，下界1,2，最大下界2。
3．设命题公式G = ?(P→Q)∨(Q∧(?P→R))，求G的主析取范式。 解：G =?(P→Q)∨(Q∧(?P→R)) =?(?P∨Q)∨(Q∧(P∨R)) = (P∧?Q)∨(Q∧(P∨R)) = (P∧?Q)∨(Q∧P)∨(Q∧R)
= (P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R) = (P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(?P∧Q∧R) = m3∨m4∨m5∨m6∨m7 = ∑(3,4,5,6,7)
4．设R和S是集合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?R－1. 解：( 1 )
?1?0MR=??0??0000011000??0??0?0 MS=??01???0??0100001000??1? 0??1?( 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?R-1={(b,a),(d,c)}
5．设有如下有向图G=
（1）求G的邻接矩阵；（2）G中v1到v4的长度为4 的通路有多少条？（3）G中经过v1的长度为3 的回路有多少条？（4）G中长度不超过4 的通路有多少条？（要写出计算过程） 解：( 1 )
?1??1?0??0100011010??0? ?1?0?( 2 )
?1?1A=??0??010001101?20???0?2?1A=??01??0??011002110?31???1?3?2 A=??00??1??021004301?52???1?4?3 A=??01??0??0320074104??3? ?0?1? G中v1到v4的长度为4 的通路有4条 ( 3 ) G中经过v1的长度为3 的回路有3条 ( 4 ) G中长度不超过4 的通路有72条
本文作者：...共分享92篇相关文档
