1、 1 离散数学题库 与答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？ ( ) (1) Q=Q P (2) Q=P Q (3)P=P Q (4) P (P Q)= P 答： 在第三 章里面有公式 （ 1） 是附加律 ，（ 4） 可以由第二章的蕴含等值式求出 （注意与吸收律区别） 2、下列公式中哪些是永真式？ ( ) (1)( P Q) (Q R) (2)P (Q Q) (3)(P Q) P (4)P (P Q) 答：（ 2），（ 3），（ 4） 可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式 ?( ) (1)P=P Q (2) P Q=P (3) P Q=P
2、 Q (4)P (P Q)=Q (5) (P Q)=P (6) P (P Q)= P 答：（ 2） 是第三章的化简律 ，（ 3） 类似附加律 ，（ 4） 是假言推理 ， （ 3）， （ 5），（ 6） 都可以用蕴含等值式来证明出是永真蕴含式 4、公式 x(A(x)B(y， x) z C(y， z)D(x)中，自由变元是 ( )，约束变元是 ( )。 答： x,y, x,z（考察定义在公式 x A 和 x A 中，称 x为指导变元， A为量词的辖域。在 x A 和 x A 的辖域中， x 的所有出现都称为约束出现，即 称 x 为约束变元， A中不是约束出现的其他变项则称为自由变元 。于是 A(x
3、)、 B(y，x)和 z C(y， z)中 y为自由变元 ， x 和 z 为约束变元，在 D(x)中 x 为自由变元 ） 5、判断下列语句是不是命题。若是，给出命题的真值。 ( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若 7+8 18，则三角形有 4条边。 (5) 前进！ (6) 给我一杯水吧！ 2 答：（ 1） 是， T （ 2） 是， F （ 3） 不是 （ 4） 是， T （ 5） 不是 （ 6） 不是 （ 命题必须满足是陈述句，不能是疑问句或者祈使句。 ） 6、命题“存在一些人是大学生”的否定是 ( )，而命题“所有的人都
4、是要死的”的否定是 ( )。 答：所有人都不是大学生，有些人不会死 （命题的否定就是把 命题前提中的量词 “ 换成存在 ， 换成 ” ，然后将命题的结论否定 ， “ 且变或 或变且 ” ） 7、设 P：我生病， Q：我去学校，则下列命题可符号化为 ( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当 且仅当我生病时，我才不去学校 (4) 若我不生病，则我一定去学校 答：（ 1） PQ （注意“只有才”和“除非就” 两者 都是一个形式的 ） （ 2） QP （ 3） QP （ 4） QP 8、设个体域为整数集，则下列公式的意义是 ( )。 (1) xy(x+y
5、=0) (2) yx(x+y=0) 答：（ 1）对任一整数 x存 在整数 y 满足 x+y=0 （ 2）存在整数 y 对任一整数 x满足 x+y=0 9、设全体域 D是正整数集合，确定下列命题的真值： (1) xy (xy=y) ( ) (2) xy(x+y=y) ( ) (3) xy(x+y=x) ( ) (4) xy(y=2x) ( ) 答：（ 1） F (反证法：假若存在，则（ x- 1） *y=0 对所有的 x都成立，显然这个与前提条件相矛盾 ) （ 2） F （同理） （ 3） F （同理） （ 4） T（ 对任一整数 x 存在整数 y 满足 条件 y=2x 很明显 是正确的） 10
6、、设谓词 P(x)： x 是奇数， Q(x)： x 是偶数，谓词公式 x(P(x)Q(x)在哪个个体域中为真 ?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)-(3)均成立 答：（ 1） （在某个体域中满足不是奇数就是偶数，在整数域中才满足条件，而自然数子整数的子集，当然满足条件了） 11、命题“ 2是偶数或 -3是负数”的否定是（ ）。 3 答： 2 不是偶数且 -3 不是负数。 12、永真式的否定是（ ） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)-(3)均有可能 答：（ 2） （这个记住就行了） 13、公式 ( P Q) ( P Q)化简为（ ）
7、，公式 Q (P (P Q)可化简为（ ）。 答： P ， Q P（ 考查 分配率和蕴含等值式 知识 的掌握） 14、谓词公式 x(P(x) yR(y)Q(x)中量词 x的辖域是（ ）。 答： P(x) yR(y)（一对括号就是一个辖域） 15、令 R(x):x是实数， Q(x):x 是有理数。则命题“并非每个实数都是有理数”的符号化表示为（ ）。 答： x(R(x) Q(x) （集合论部分） 16、设 A=a,a，下列命题错误的是（ ）。 (1) aP(A) (2) a P(A) (3) aP(A) (4) a P(A) 答： (2) （ a是 P（ A）的一个元 素 ） 17、在 0（ ）
8、 之间写上正确的符号。 (1) = (2) (3) (4) 答： (4)（空集没有任何元素，且是任何集合的子集） 18、若集合 S的基数 |S|=5，则 S的幂集的基数 |P(S)|=（ ）。 答： 32（ 2的 5次方 考查幂集的定义 ，即幂集是集合 S的全体子集构成的集合 ） 19、设 P=x|(x+1)2 4 且 xR,Q=x|5 x2 +16 且 xR,则下列命题哪个正确（ ） (1) QP (2) Q P (3) P Q (4) P=Q 答：（ 3） （ Q是集合 R， P 只是 R 中的一部分，所以 P是 Q的真子集） 20、下列各集合中，哪几个分别相等 ( )。 4 (1) A1
9、=a,b (2) A2=b,a (3) A3=a,b,a (4) A4=a,b,c (5) A5=x|(x-a)(x-b)(x-c)=0 (6) A6=x|x2-(a+b)x+ab=0 答： A1=A2=A3=A6， A4=A5（集合具有无序性、确定性和互异性） 21、若 A-B=，则下 列哪个结论不可能正确？ ( ) (1) A= (2) B= (3) A B (4) B A 答：（ 4） （差集的定义） 22、判断下列命题哪个为真 ?( ) (1) A-B=B-A = A=B (2) 空集是任何集合的真子集 (3) 空集只是非空集合的子集 (4) 若 A 的一个元素属于 B，则 A=B 答
10、：（ 1） （考查空集和差集的相关知识） 23、判断下列命题哪几个为正确？ ( ) (1) , (2) , (3) (4) (5) a,b a,b,a,b 答：（ 2），（ 4） 24、判断下列命题哪几个正确？ ( ) (1) 所有空集都不相等 (2) (4) 若 A 为非空集，则 A A 成立。 答：（ 2） 25、设 A B=A C， A B=A C，则 B( )C。 答： =（等于） 26、判断下列命题哪几个正确？ ( ) (1) 若 A B A C，则 B C (2) a,b=b,a (3) P(A B) P(A) P(B) （ P(S)表示 S的幂集） (4) 若 A 为非空集，则
11、A A A成立 。 答：（ 2） 27、，是三个集合，则下列哪几个推理正确： (1) A B， B C= A C (2) A B， B C= A B (3) A B， B C= A C 答：（ 1） （ 3）的反例 C为 0， 1， 0 B 为 0， 1， A 为 1 很明显 结论 不对 ） 5 （二元关系部分） 28、设 1,2,3,4,5,6， B=1,2,3，从到 B 的关系 x,y |x=y2求 (1)R (2) R-1 答：（ 1） R=, (2) R1 =,（考查二元关系的定义 ， R1 为 R的逆关系，即 R1 = | R） 29、举出集合 A上的既是等价关系又是偏序关系的一个例
12、子。 ( ) 答： A 上 的恒等关系 30、集合 A上的等价关系的三个性质是什么？ ( ) 答：自反性、对称性和传递性 31、集合 A上的偏序关系的三个性质是什么？ ( ) 答：自反性、反对称性和传递性 (题 29， 30， 31 全是考查定义 ) 32、设 S= , , , ，上的关系 1,2， 2,1， 2,3， 3,4 求 (1)R R (2) R-1 。 答： R R = 1,1， 1,3， 2,2， 2,4 （ 考查 F G =|t( F G)） R-1 = 2,1， 1,2， 3,2， 4,3 33、设 1， 2， 3， 4， 5， 6，是 A 上的整除关系，求 R= ( ) R
13、=, 34、设 1,2,3,4,5,6， B=1,2,3，从到 B的关系 x,y |x=2y，求 (1)R (2) R-1 。 答：（ 1） R=, (2) R1 =,(36 35、 设 1,2,3,4,5,6， B=1,2,3，从到 B 的关系 x,y |x=y2 ，求 R 和 R-1的关系矩阵。 6 答： R 的关系矩阵 =000000001000000001R1 的关系矩阵 =000000010000000001 36、集合 A=1,2, ,10上的关系 R=|x+y=10,x,yA，则 R 的性质为（ ）。 (1) 自反的 (2) 对称的 (3) 传递的，对称的 (4) 传递的 答：（
14、 2） （考查自反 对称 传递的定义） （ 代数系统 部分 ） 37、设 A=2,4,6， A 上的二元运算 *定义为： a*b=maxa,b，则在独异点中，单位元是 ( )，零元是 ( )。 答： 2， 6（单位元和零元的定义 ，单位 元： e。 x=x 零元：。 x= ） 38、设 A=3,6,9， A 上的二元运算 *定义为： a*b=mina,b，则在独异点中，单位元是 ( )，零元是 ( )； 答： 9， 3 （半群与群部分） 39、设 G,*是一个群，则 (1) 若 a,b,x G， a x=b，则 x=( )； (2) 若 a,b,x G， a x=a b，则 x=( )。 答：
15、 （ 1） a 1 b （ 2） b （考查群的性质 ，即群满足消去律 ） 40、设 a是 12 阶群的生成元， 则 a2是 ( )阶元素， a3是 ( )阶元素。 答： 6,4 41、代数系统 是一个群，则 G的等幂元是 ( )。 答：单位元 （ 由 a2=a,用归纳法可证 an=a*a(n-1)=a*a=a，所以等幂元一定是幂等元，反之若 an=a 对一切 N 成立，则对 n=2 也成立，所以幂等元一定是等幂元 ，并且 在群中，除幺元 即单位元 e 外不可能有任何别的幂等 元 ） 42、设 a 是 10 阶群的生成元， 则 a4是 ( )阶元素， a3是 ( )阶元素 7 答： 5， 10
16、（ 若一个群 G 的每一个元都是 G 的某一个固定元 a 的乘方，我们就把G 叫做循环群；我们也说， G 是由元 a 生成的，并且用符号 G=表示，且称 a为一个生成元 。并且 一元素的阶整除群的阶 ） 43、群 的等幂元是 ( )，有 ( )个。 答：单位元， 1 （ 在群 中，除幺元 即单位元 e 外不可能有任何别的幂等元 ） 44、素数阶群一定是 ( )群 , 它的生成元是 ( )。 答：循环群，任 一非单位元 （证明如下： 任一元素的阶整除群的阶。现在群的阶是素数 p，所以元素的阶要么是 1 要么是 p。 G 中只有一个单位元，其它元素的阶都不等于 1，所以都是 p。任取一个非单位元，
17、它的阶等于 p，所以它生成的 G 的循环子群的阶也是p，从而等于整个群 G。所以 G 等于它的任一非单位元生成的循环群 ） 45、设 G,*是一个群， a,b,c G，则 (1) 若 ca=b，则 c=( )； (2) 若 c a=ba，则 c=( )。 答：（ 1） b 1a (2) b（群的性质） 46、 是 的子群的充分必要条件是 ( )。 答： 是群 或 a， b G， a bH， a-1H 或 a,b G， a b-1H 47、群 A,*的等幂元有 ( )个，是 ( )，零元有 ( )个。 答： 1，单位元， 0 48、在一个群 G,*中，若 G中的元素 a 的阶是 k，则 a-1的
18、阶是 ( )。 答： k 49、在自然数集 N上，下列哪种运算是可结合的？（ ） (1) a*b=a-b (2) a*b=maxa,b (3) a*b=a+2b (4) a*b=|a-b| 答： (2) 50、任意一个具有 2个或以上元的半群，它（ ）。 (1) 不可能是群 (2) 不一定是群 (3) 一定是群 (4) 是交换群 答： (1) 51、 6 阶有限群的任何子群一定不是（ ）。 8 (1) 2 阶 (2) 3 阶 (3) 4 阶 (4) 6 阶 答： (3) （格与布尔代数部分） 52、下列哪个偏序集构成有界格（ ） (1) （ N, ） (2) （ Z, ） (3) （ 2,3,
19、4,6,12,|（整除关系） (4) (P(A), ) 答： (4)（考查幂集的定义） 53、有限布尔代数的元素的个数一定等于（ ）。 (1) 偶数 (2) 奇数 (3) 4 的倍数 (4) 2 的正整数次幂 答： (4) （图论部分） 54、设 G 是一个哈密尔顿图，则 G一定是 ( )。 (1) 欧拉图 (2) 树 (3) 平面图 (4) 连通图 答： (4)（考察图的定义） 55、下面给出的集合中，哪一个是前缀码？ ( ) (1) 0， 10， 110， 101111 (2) 01， 001， 000， 1 (3) b， c， aa， ab， aba (4) 1， 11， 101， 00
20、1， 0011 答：（ 2） 56、一个图的哈密尔顿路是一条通过图中 ( )的路。 答：所有结点一次且恰好一次 57、在有向图中，结点 v的出度 deg+(v)表示 ( )，入度 deg-(v)表示 ( )。 答：以 v 为起点的边的条数， 以 v 为终点的边的条数 58、设 G 是一棵树，则 G 的生成树有 ( )棵。 (1) 0 (2) 1 (3) 2 (4) 不能确定 答： 1 59、 n 阶无向完全图 Kn 的边数是 ( )，每个结点的度数是 ( )。 9 答： 2 )1( nn , n-1 60、一棵无向树的顶点数 n与边数 m关系是 ( )。 答： m=n-1 61、一个图的欧拉回
21、路是一条通过图中 ( )的回路。 答：所有边一次且恰好一次 62、有 n 个结点的树，其结点度数之和是 ( )。 答： 2n-2（结点度数的定义） 63、下面给出的集合中，哪一个不是前缀码 ( )。 (1) a， ab， 110， a1b11 (2) 01， 001， 000， 1 (3) 1， 2， 00， 01， 0210 (4) 12， 11， 101， 002， 0011 答： (1) 64、 n 个结点的有向完全图边数是 ( )，每个结点的度数是 ( )。 答： n(n-1),2n-2 65、一个无向图有生成树的充分必要条件是 ( )。 答：它是连通图 66、设 G 是一棵树， n,
22、m分别表示 顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 答：（ 3） 67、设 T= V,E是一棵树，若 |V|1，则 T中至少存在 ( )片树叶。 答： 2 68、任何连通无向图 G至少有 ( )棵生成树，当且仅当 G 是 ( )，G 的生成树只有一棵。 答： 1， 树 69、设 G 是有 n个结点 m条边的连通平面图，且有 k个面，则 k等于 : (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 答：（ 1） 10 70、设 T 是一棵树，则 T是一 个连通且 ( )图。 答：无简单回路 71、设无向图 G有
23、 16 条边且每个顶点的度数都是 2，则图 G 有 ( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 答：（ 4） 72、设无向图 G有 18 条边且每个顶点的度数都是 3，则图 G 有 ( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12 答： (4) 73、设图 G=， V=a， b， c， d， e， E=,则 G 是有向 图还是无向图？ 答：有向图 74、任一有向图中，度数为奇数的结点有 ( )个。 答：偶数 75、具有 6 个顶点， 12 条边的连通简单平面图中，每个面都是由 ( )条边围成？ (1) 2 (2) 4 (3) 3 (4) 5 答：（ 3） 76、在有 n个顶点的连通图中，其边数（ ）。 (1) 最多有 n-1 条 (2) 至少有 n-1 条 (3) 最多有 n 条 (4) 至少有 n 条 答：（ 2） 77、一棵树有 2个 2 度顶点， 1 个 3度顶点， 3个 4 度顶点，则其 1 度顶点为（ ）。 (1) 5 (2) 7 (3) 8 (4) 9 答：（ 4） 78、若一棵完全二元（叉）树有 2n-1个顶点，则它（ ）片树叶。 (1) n (2) 2n (3) n-1 (4) 2
