第1页 / 共51页
第2页 / 共51页
第3页 / 共51页
第4页 / 共51页
第5页 / 共51页
第6页 / 共51页
第7页 / 共51页
第8页 / 共51页
山东大学离散数学题库及答案.doc
《离散数学》题库答案
一、选择或填空
（数理逻辑部分）
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 Q
(4)P (P→Q)=>Q
(5) (P→Q)=>P
(6) P (P Q)=> P
)
答：（2），（3），（4），（5），（6）
4、公式x((A(x)B(y，x)) z C(y，z))D(x)中，自由变元是(
)，约束变元是(
)。
答：x,y,
x,z
5、判断下列语句是不是命题。若是，给出命题的真值。(
)
(1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。
(3) 你喜欢唱歌吗？
(4) 若 7+8＞18，则三角形有 4 条边。
(5) 前进！
(6) 给我一杯水吧！
答：（1） 是，T
（2） 是，F
（3） 不是
（4） 是，T
（5） 不是
（6） 不是
6、命题“存在一些人是大学生”的否定是(
)，而命题“所有的人都是要死的”的否定是(
)。
答：所有人都不是大学生，有些人不会死
7、设 P：我生病，Q：我去学校，则下列命题可符号化为(
)。
(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校
(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校
P
Q
答：（1）
Q
（3）
P
Q
（4）
P
（2）
P
Q
8、设个体域为整数集，则下列公式的意义是(
)。
(1) xy(x+y=0)
(2) yx(x+y=0)
答：（1）对任一整数 x 存在整数 y 满足 x+y=0（2）存在整数 y 对任一整数 x 满足 x+y=0
9、设全体域 D 是正整数集合，确定下列命题的真值：
(1) xy (xy=y)
(
(3) xy(x+y=x)
(
)
)
(2) xy(x+y=y)
(4) xy(y=2x)
(
(
)
)
答：（1） F （2） F （3）F （4）T
10、设谓词 P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?(
)
(1) 自然数
(2) 实数
(3) 复数
(4)
(1)--(3)均成立
1
答：（1）
11、命题“2 是偶数或-3 是负数”的否定是（
）。
答：2 不是偶数且-3 不是负数。
12、永真式的否定是（
）
(1) 永真式 (2) 永假式 (3) 可满足式 (4)
(1)--(3)均有可能
答：（2）
13、公式( P Q) ( P Q)化简为（
答： P ，Q P
14、谓词公式x(P(x) yR(y)) Q(x)中量词x 的辖域是（
答：P(x) yR(y)
）。
），公式 Q (P (P Q))可化简为（
）。
15、令 R(x):x 是实数，Q(x):x 是有理数。则命题“并非每个实数都是有理数”的符号化表示为（
答： x(R(x) Q(x))
）。
（集合论部分）
16、设 A={a,{a}}，下列命题错误的是（ ）。
(1) {a} P(A)
(2) {a} P(A)
(3) {{a}}P(A) (4) {{a}} P(A)
答：(2)
17、在 0（ ） 之间写上正确的符号。
(1) =
(2) (3) (4)
答：(4)
18、若集合 S 的基数|S|=5，则 S 的幂集的基数|P(S)|=（ ）。
答：32
19、设 P={x|(x+1) 2 4 且 x R},Q={x|5 x 2 +16 且 xR},则下列命题哪个正确（
(1) Q P
(3) P Q
(2) Q P
(4) P=Q
）
答：（3）
20、下列各集合中，哪几个分别相等(
)。
(1) A1={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
答：（1）
2
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 为非空集，则 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）
（二元关系部分）
28、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到 B 的关系Ｒ＝｛〈x,y〉|x=y2｝，求(1)R
(2)
R-1 。
答：（1）R={<1,1>,<4,2>}
(2) R 1 ={<1,1>,<2,4>}
29、举出集合 A 上的既是等价关系又是偏序关系的一个例子。(
)
答：A 上的恒等关系
30、集合 A 上的等价关系的三个性质是什么？(
答：自反性、对称性和传递性
31、集合 A 上的偏序关系的三个性质是什么？(
答：自反性、反对称性和传递性
)
)
(2)
32、设 S={１,２,３,４}，Ａ上的关系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝
求(1)R R
答：R R ={〈1,1〉，〈1,3〉，〈2,2〉，〈2,4〉}
R-1 =｛〈2,1〉，〈1,2〉，〈3,2〉，〈4,3〉｝
R-1 。
33、设Ａ＝｛1，2，3，4，5，6｝，Ｒ是 A 上的整除关系，求 R= {(
)}。
答：R={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<1,2>,<1,3>,<1,4>,
<1,5>,<1,6>,<2,4>,<2,6>,<3,6>}
34、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到 B 的关系Ｒ＝｛〈x,y〉|x=2y｝，求(1)R
(2)
R-1 。
答：（1）R={<1,1>,<4,2>,<6,3>}
(2) R 1 ={<1,1>,<2,4>,(36>}
3
35、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到 B 的关系Ｒ＝｛〈x,y〉|x=y2｝，求 R 和 R-1 的关系矩阵。
答：R 的关系矩阵=
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
R 1 的关系矩阵=
1
0
0
0
0
0
0
0
0
0
1
0
00
00
00
36、集合 A={1,2,…,10}上的关系 R={|x+y=10,x,yA}，则 R 的性质为（ ）。
(1) 自反的
(2) 对称的
(3) 传递的，对称的 (4) 传递的
答：（2）
（代数结构部分）
37、设 A={2,4,6}，A 上的二元运算*定义为：a*b=max{a,b}，则在独异点中，单位元是(
)，零元是(
)。
答：2，6
38、设 A={3,6,9}，A 上的二元运算*定义为：a*b=min{a,b}，则在独异点中，单位元是(
)，零元是(
)；
答：9，3
（半群与群部分）
39、设〈G,*〉是一个群，则
(1) 若 a,b,x∈G，a x=b，则 x=(
(2) 若 a,b,x∈G，a x=a b，则 x=(
)；
)。
答： （1） a 1 b （2） b
40、设 a 是 12 阶群的生成元， 则 a2 是(
)阶元素，a3 是(
)阶元素。
答： 6,4
41、代数系统是一个群，则 G 的等幂元是(
)。
答：单位元
42、设 a 是 10 阶群的生成元， 则 a4 是(
)阶元素，a3 是(
)阶元素。
答：5，10
43、群的等幂元是(
)，有(
)个。
答：单位元，1
44、素数阶群一定是(
)群, 它的生成元是(
)。
答：循环群，任一非单位元
45、设〈G,*〉是一个群，a,b,c∈G，则
(1) 若 c a=b，则 c=(
)；(2) 若 c a=b a，则 c=(
)。
1 a
(2) b
答：（1） b
46、是的子群的充分必要条件是(
答：是群 或 a，b G， a bH，a-1 H 或 a,b G，a b-1 H
)。
4
47、群＜A,*＞的等幂元有(
)个，是(
)，零元有(
)个。
答：1，单位元，0
48、在一个群〈G,*〉中，若 G 中的元素 a 的阶是 k，则 a-1 的阶是(
)。
答：k
49、在自然数集 N 上，下列哪种运算是可结合的？（
）
(1) a*b=a-b
(2) a*b=max{a,b}
(3) a*b=a+2b
(4) a*b=|a-b|
答：(2)
50、任意一个具有 2 个或以上元的半群，它（ ）。
(1) 不可能是群
(2) 不一定是群
(3) 一定是群
(4) 是交换群
答：(1)
51、6 阶有限群的任何子群一定不是（
）。
(1) 2 阶
(2) 3 阶
(3) 4 阶
(4) 6 阶
答：(3)
（格与布尔代数部分）
52、下列哪个偏序集构成有界格（
(1) （N, ） (2) （Z, ）
）
(3) （{2,3,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，001，0011}
答：（2）
56、一个图的哈密尔顿路是一条通过图中(
)的路。
答：所有结点一次且恰好一次
57、在有向图中，结点 v 的出度 deg+(v)表示(
)，入度 deg-(v)表示(
)。
答：以 v 为起点的边的条数， 以 v 为终点的边的条数
5
58、设 G 是一棵树，则 G 的生成树有(
)棵。
(1) 0
(2) 1
(3) 2
(4) 不能确定
答：1
59、n 阶无向完全图 Kn 的边数是(
)，每个结点的度数是(
)。
答：
)1
( nn
2
, n-1
60、一棵无向树的顶点数 n 与边数 m 关系是(
)。
答：m=n-1
61、一个图的欧拉回路是一条通过图中(
)的回路。
答：所有边一次且恰好一次
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,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）
70、设 T 是一棵树，则 T 是一个连通且(
)图。
答：无简单回路
71、设无向图 G 有 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
6
答：(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
答：（1）
79、下列哪一种图不一定是树（
）。
(1) 无简单回路的连通图
(2) 有 n 个顶点 n-1 条边的连通图
(3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图
答：（3）
80、连通图 G 是一棵树当且仅当 G 中（
）。
(1) 有些边是割边
(2) 每条边都是割边
(3) 所有边都不是割边 (4) 图中存在一条欧拉路径
答：（2）
（数理逻辑部分）
二、求下列各公式的主析取范式和主合取范式：
1、(P→Q) R
解：(P→Q) R ( P Q ) R
( P R) (Q R) （析取范式）
( P (Q Q) R) (( P P) Q R)
( P Q R) ( P Q R) ( P Q R) (P Q R)
( P Q R) ( P Q R) (P Q R)（主析取范式）
7
((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)（主合取范式）
2、(P R) (Q R) P
解： (P R) (Q R) P（析取范式）
(P (Q Q) R) ((P P) Q R) ( P (Q Q) (R 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) ( P Q R) ( P Q R) ( P Q R)
(主析取范式)
（(P R) (Q R) P）
(P Q R) (P Q R）（原公式否定的主析取范式）
(P R) (Q R) P ( P Q R) ( P Q R)（主合取范式）
3、( P→Q) (R P)
解：( P→Q) (R P)
(P Q) (R P)（合取范式）
(P Q (R R)) (P (Q 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))
(P Q R) ( P Q R) ( P Q R) ( P Q R)
( P Q R)（原公式否定的主合取范式）
( P→Q) (R P)
( P Q R) (P Q R) (P Q R) (P Q R) (P Q R)
（主析取范式）
4、Q→(P R)
解：Q→(P R)
Q P R（主合取范式）
（Q→(P R)）
( P Q R) ( P Q R) ( P Q R) ( P Q R)
(P Q R) (P Q R) (P Q R）（原公式否定的主合取范式）
Q→(P R)
(P Q R) (P Q R) (P Q R) (P Q R) ( P Q R)
( P Q R) ( P Q R）（主析取范式）
5、P→(P (Q→P))
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
