离散数学复习题集
一、单项选择题 (1)
二、填空题 (10)
三、计算题 (13)
四、其他 (15)
一、单项选择题
1．下列语句中不．
是命题的只有（ ） A ．鸡毛也能飞上天？
B ．或重于泰山，或轻于鸿毛。
C ．不经一事，不长一智。
D ．牙好，胃口就好。
2．下列语句中为命题的是（ ）
A ．这朵花是谁的？
B ．这朵花真美丽啊！
C ．这朵花是你的吗？
D ．这朵花是他的。 3．下列句子不是．．
命题的是（ ） A ．中华人民共和国的首都是北京
B ．张三是学生
C ．雪是黑色的
D ．太好了！ 4下列句子为命题的是（ ）
A.全体起立!
B.x =0
C.我在说谎
D.张三生于1886年的春天 5.下列句子为命题的是（ ）
A.走，看电影去
B.x+y>0
C.空集是任意集合的真子集
D.你明天能来吗? 6．下列语句中是真命题的是（ ）
A ．我正在说谎
B ．严禁吸烟
C ．如果1+2=3，那么雪是黑的
D ．如果1+2=5，那么雪是黑的 7.下列命题为假．命题的是（ ） A.如果2是偶数，那么一个公式的析取范式惟一
B.如果2是偶数，那么一个公式的析取范式不惟一
C.如果2是奇数，那么一个公式的析取范式惟一
D.如果2是奇数，那么一个公式的析取范式不惟一
读书是掌握知识的捷径，勤奋是开启知识大门的钥匙， 思考是理解知识的利器，练习是巩固知识的方法，
讨论是理解知识的妙招，探求是创新知识的途径。
8.设p ：天下大雨,q ：他在室内运动,命题“除非天下大雨，否则他不．
在室内运动”可符合化为（ ）
A.?p ∧q
B.?p →q
C.?p →?q
D.p →?q
9．设p ：我们划船，Q ：我们跑步。命题“我们不能既划船又跑步”符号化为（ ）
A ．? p ∧? q
B ．? p ∨? q
C ．?（p ?q ）
D ．?（? p ∨? q ）
10．令p ：今天下雪了，q ：路滑，则命题“虽然今天下雪了，但是路不．
滑”可符号化为（ ） A ．p →q B ．p ∨q C ．p ∧q D ．p ∧q
11．设p ：他聪明，q ：他用功，命题“他虽聪明但不用功”的符号化正确的是（ ）
A ．? p ∧q
B ．p ∧? q
C ．p →? q
D ．p ∨? q
12．令p ：今天下雪了，q ：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）
A ．p →┐q
B ．p ∨┐q
C ．p ∧q
D ．p ∧┐q
13.在命题演算中，语句为真为假的一种性质称为( )
A.真值
B.陈述句
C.命题
D.谓词
14.设p ：明天天晴；q ：我去爬山；那么“除非明天天晴，否则我不去爬山。”可符号化为(
) A.q p ?→ B. q p ?→? C. q ???p D. q p →?
15.若p ：他聪明；q ：他用功；则“他虽聪明，但不用功”，可符号化为( )
A.p ∨q
B.p ∧┐q
C.p →┐q
D.p ∨┐q
16．下列为两个命题变元P ，Q 的极小项是（ ）
A ．p ∧q ∧? p
B ．? p ∨q
C ．? p ∧q
D ．? p ∨p ∨q
17．命题公式（p ∧（p →q ））→q 是（ ）
A ．矛盾式
B ．蕴含式
C ．重言式
D ．等价式
18．命题公式?（p ∧q ）→r 的成真赋值是（ ）
A ．000，001，110，
B ．001，011，101，110，111
C ．全体赋值
D ．无
19．下列命题公式为重言式的是（ ）
A ．q →（p ∧q ）
B ．p →（p ∧q ）
C ．（p ∧q ）→p
D ．（p ∨q ）→q
20．下列4个推理定律中，不．正确的是（ ）
A ．A ?（A ∧
B ） B ．（A ∨B ）∧A ?B
C ．（A →B ）∧A ?B
D ．（A →B ）∧B ?A
21．下面联结词运算不．可交换的是（ ）
A ．∧
B ．→
C ．∨
D ． ?
22．下列命题公式不．是重言式的是（ ）
A ．p →（p ∨q ）
B ．（p ∧q ）→p
C ．?（p ∧? q ）∧（?p ∨q ）
D ．（p →q ）?（? p ∨q ）
23．从真值角度看，命题公式的全部类型是（ ）
A ．永真式
B ．永假式
C ．永真式，永假式
D ．永真式，永假式，可满足式
24.下列命题公式是永真式的是( )
A.)p p (?∧?q
B.q )q p (∧→?
C. q )q p (∨→
D.)p p ()p p (?→∧∨
25．下列是两个命题变元p ，q 的极大项是（ ）
A ．p ∧┐p ∧q
B ．┐p ∨q
C ．┐p ∧q
D ．┐p ∨p ∨q
26．关于命题变元p 和q 的极大项M 2表示( )。
A.┐p ∧q
B.┐p ∨q
C.p ∨┐q
D.p ∧┐q
27.下列是命题公式p ∧(q ∨┓r)的成真赋值的是( )
A.110，111，100
B.110，101，011
C.所有赋值
D.无
28.下列等值式不正确的是（ ）
A ．┐(?x)A ?(?x)┐A
B ．(?x)(B →A(x))?B →(?x)A(x)
C ．(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)
D ．(?x)(?y)(A(x)→B(y))?(?x)A(x)→(?y)B(y)
29．设M （x ）：x 是人；F （x ）：x 要吃饭。用谓词公式表达下述命题：所有的人都要吃饭，其中错误．．
的表达式是（ ） A ．))x (F )x (M )(x (→?
B ．))x (F )x (M )(x (?∧??
C ．))x (F )x (M )(x (∨?
D ．))x (F )x (M )(x (∨??
30．设A （x ）:x 是人，B （x ）：x 犯错误，命题“没有不犯错误的人”符号化为（ ）
A ．))(
B )(A (x x x ∧?
B ．?→?)(A (x x ? B （x ））
C ．?))(B )(A (x x x ∧?
D ．?∧?)(A (x x ? B(x))
31.设论域为整数集，下列谓词公式中真值为假的是( )
A.)0y x )(y )(x (=???
B. )1y x )(y )(x (=???
C. )x y x )(x )(y (=???
D. )z y x )(z )(y )(x (=-???
32．下列公式是前束范式的是（ ）
A ．))y (G )x ,z (F )(y )(x (∨???
B ．)z (H ))y (G )y ()x (F )x ((∧?∨??
C ．)y (G )y ()y ,x (F )x (?→?
D ．))y ,x (G )y ()y ,x (F )(x (?→?
33．设论域为整数集，下列真值为真的公式是（ ）
A ．)0y x )(y )(x (=-??
B ．)0y x )(x )(y (=-??
C ．)0y x )(y )(x (=-??
D ．)0y x )(y ()x (=-????
34．下列是谓词演算中的合式公式的是（ ）
A ．)y )x (p )(x (?→?
B ．)y ,x (G )x (F )x (∧?
C ．)z ,y (Q )y ,x (P )x (?
D ．)y ,x (P x )x (∧??
35.设个体域是正整数集，则下列公式中真值为真的公式是( )
A.(?x)(?y)(x ·y=0)
B.(?x)(?y)(x ·y=1)
C.(? x)(?y)(x ·y=2)
D.(?x)(?y)(?z)(x-y=z)
36.令F(x):x 是金属，G(y):y 是液体，H(x,y):x 可以溶解在y 中，则命题“任何金属可以溶解在某种液体中”可符号化为( )
A.(?x)(F(x)∧(?y)(G(y)∧H(x,y)))
B.(?x)(?(x)F(x)→(G(y)→H(x,y)))
C.(?x)(F(x)→(?y)(G(y)∧H(x,y)))
D.(?x)(F(x)→(?y)(G(y)→H(x,y))
37.在个体域D={a,b}中，与公式(?x)A(x)等价又不含量词的公式是( )
A.A(a)∧A(b)
B.A(a)→A(b)
C.A(a)∨A(b)
D.A(b)→A(a)
38．设个体域A={a,b}，公式?xP(x)∧?xS(x)在A 中消去量词后应为（ ）
A ．P(x)∧S(x)
B ．P(a)∧P(b)∧(S(a)∨S(b))
C ．P(a)∧S(b)
D ．P(a)∧P(b)∧S(a)∨S(b)
39.设论域为{1，2}，与公式（?x）﹁A（X）等价的是（）
A.﹁A（1）∨﹁A（2）
B.﹁A（1）→﹁（A2）
C.﹁A（1）∧﹁A（2）
D. A（1）→A（2）
40.设论域为{l，2}，与公式)
A
x?等价的是（）
)
(x
(
A.A（1）∨A（2）
B. A（1）→A（2）
C.A（1）
D. A（2）→A（1）
41．.谓词公式(?x)(P(x,y))→(?z)Q(x,z)∧(?y)R(x,y)中变元x( )
A.是自由变元但不是约束变元。
B.既不是自由变元又不是约束变元
C.既是自由变元又是约束变元。
D.是约束变元但不是自由变元
42.公式(?x)(?y)(P(x,z)→Q(y))?S(x,y)中的(?x)的辖域是( )。
A.(?y)(P(x,z)→Q(y))
B.P(x,z)→Q(y)
C.P(x,z)
D.S(x,z)
43.下列等价式不成立
．．．的是( )。
A.┐(?x)A(x)?(?x)┐A(x)
B.┐(?x)A(x)?(?x)┐A(x)
C.(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)
D.(?x)(A(x)∨B(x))?(?x)A(x)∨(?x)B(x)
44.公式(?x)(?y)(P(x,y)∧Q(z))→R(x)中的x( )。
A.只是约束变元
B.只是自由变元
C.既是约束变元又是自由变元
D.既非约束变元又非自由变元
45.设A={a,{a}}，则下列各式正确的是( )。
A.{a}∈p(A)(A的幂集)
B.{a}?p(A)
C.{{a}}?p(A)
D.{a,{a}}?p(A)
46.集合的以下运算律不成立
．．．的是( )。
A.A∩B=B∩A
B.A∪B=B∪A
C.A⊕B=B⊕A
D.A-B=B-A
47．下列选项中错误
．．的是（）
A．??? B．?∈? C．??{?} D．?∈{?}
48．设A-B=?，则有（）
A．B=?B．B≠?C．A?B D．A?B
49．A，B是集合，P（A），P（B）为其幂集，且A∩B=?，则P(A)∩P(B)为（）A．?B．{?} C．{{?}} D．{?，{?}}
50．设A={?}，B=P(P(A))，以下正确的式子是（）
A．{?,{?}}∈B B．{{?,?}}∈B
C．{{?},{{?}}}∈B D．{?,{{?}}}∈B
51．下列命题中，不正确的是( )
A.{φ}∈{φ,{φ}}
B.{φ}∈{φ,{{φ}}}
C.{φ}?{φ,{φ}}
D.φ?{φ,{φ}}
52.下列式子正确的是( )
A. ?∈?
B.???
C.{?}??
D.{?}∈?
53.设A={1,2,3}，A 上二元关系R 的关系图如下：
R 具有的性质是
A.自反性
B.对称性
C.传递性
D.反自反性
54.设A={a,b,c}，A 上二元关系R={〈a,a 〉，〈b,b 〉,〈a,c 〉}，
则关系R 的对称闭包S(R)是( )
A.R ∪I A
B.R
C.R ∪{〈c,a 〉}
D.R ∩I A
55.设X={a,b,c},Ix 是X 上恒等关系，要使Ix ∪{〈a,b 〉，〈b,c 〉，〈c,a 〉，〈b,a 〉}∪R 为X 上的等价关系，R 应取( )
A.｛〈c,a 〉，〈a,c 〉｝
B.{〈c,b 〉，〈b,a 〉}
C.{〈c,a 〉，〈b,a 〉}
D.{〈a,c 〉，〈c,b 〉}
56.设集合A={a,b, c}上的关系如下，具有传递性的是（ ）
A.R={
B.R={
C.R={
D.R={
57．设A={a,b,c,d}，A 上的等价关系R={
A 的划分是（ ）
A ．{{a},{b, c},{d}}
B ．{{a, b},{c}, {d}}
C ．{{a},{b},{c},{d}}
D ．{{a, b}, {c,d}}
58．设A={a,b,c,d}，A 上的等价关系R={
A ．{{a},{b,c},{d}}
B ．{{a,b},{c},{d}}
C ．{{a},{b},{c},{d}}
D ．{{a,b},{c,d}}
59.设集合X={0,1,2,3}，R 是X 上的二元关系，R={<0,0>,<0,2>,<1,2>,<1,3>,<2,0>,<2,1>,<3,3,>}，则R 的关系矩阵M R 是( )
A ．????????????1100100000110101 B.????????????1000001111000101 C. ????????????0111101001011000 D. ?????
???????0101100011000111 60.下面的图是A=｛1,2,3｝上关系R 的关系图G(R),从G(R)可判断R 所具有的性质是( )
1。
2。 3。
A.自反，对称，传递
B.反自反，非对称
C.反自反，对称，非传递
D.反自反，对称，反对称，传递
61．集合A={1，2，3}上的下列关系矩阵中符合等价关系条件的是（ ）
A ．??????????100010101
B ．??????????101010101
C ．??????????101110011
D ．????
??????111011001 62.下列哪个关系矩阵所对应的关系具有自反性（ ）
A.??????????001111101
B.??????????101110001
C.??????????001100100
D.????
??????001010101
63.下列关系矩阵所对应的关系具有反自反性的是（ ）
A.??????????001110101
B.
??????????101110001 C. ??????????001100100 D. ????
??????001010101
64．在自然数集N 上，下列定义的运算中不可结合的只有（ ）
A ．a*b=min(a,b)
B ．a*b=a+b
C ．a*b=GCD(a,b)(a,b 的最大公约数)
D ．a*b=a(mod b)
65．设有代数系统G=〈A ，*〉，其中A 是所有命题公式的集合，*为命题公式的合取运算，则G 的幺元是（ ）
A ．矛盾式
B ．重言式
C ．可满足式
D ．公式p ∧q
66.在整数集上，下面哪个运算不是．．
二元运算（ ） A.加法 B.减法 C.乘法 D.除法
67.设A 是奇数集合，×为乘法运算，则是（ ）
A.半群
B.群
C.循环群
D.交换群
68.下面不满足．．．
结合律的运算是（ ） A.a*b=min （a ，b ）
B.a*b=max （a ，b ）
C.a*b=2（a+b ）
D.a*b=2ab
69．在实数集合R 上，下列定义的运算中不．
可结合的是（ ） A ．a*b=a+b+2ab B ．a*b=a+b
C ．a*b=a+b+ab
D ．a*b=a-b
70.半群、群及独异点的关系是（ ）
A.{群}?{独异点}?{半群}
B.{独异点}?{半群}?{群}
C.{独异点}?{群}?{半群}
D.{半群}?{群}?{独异点}
71.下列集合对所给的二元运算封闭的是（ ）
A.正整数集上的减法运算
B.在正实数的集R +上规定*为a *b=ab-a-b ?a,b ∈R +
C.正整数集Z +上的二元运算*为x *y=min(x,y) ?x,y ∈Z +
72.设A 是奇数集合，下列构成独异点的是（ ）
73.设A 是整数集，下列说法正确的是（ ）
A.有零元
B.有零元
C.有幺元
D.有幺元
74.下列说法不正确．．．
的是（ ） A.在实数集上，乘法对加法是可分配的
B.在实数集上，加法对乘法是可分配的
C.在某集合的幂集上，∪对∩是可分配的
D.在某集合的幂集上，∩对∪是可分配的
75.下列各代数系统中不含有零元素的是( )
A.〈Q ，*〉Q 是全体有理数集，*是数的乘法运算
B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算
C.〈Z， 〉，Z是整数集， 定义为x xy=xy, x,y∈Z
D.〈Z，+〉，Z是整数集，+是数的加法运算
76. 设〈G,*〉是群，且|G|>1，则下列命题不成立的是( )
A.G中有幺元
B.G中有零元
C.G中任一元素有逆元
D.G中除了幺元外无其他幂等元
77.设A是非空集合，P(A)是A的幂集，∩是集合交运算，则代数系统〈P(A),∩〉的幺元是( )
A.P(A)
B.φ
C.A
D.|φ|
78.右图的最大入度是（）
A.0
B.1
C.2
D.3
79．设D=
A．强连通图B．单向连通图C．弱连通图D．不连通图
80．在有n个结点的连通图中，其边数（）
A．最多有n-1条B．至少有n-1条
C．最多有n条D．至少有n条
81．连通图G是一棵树，当且仅当G中（）
A．有些边不是割边B．每条边都是割边
C．无割边集D．每条边都不是割边
82.含有5个结点，3条边的不．同构的简单图有（）
A.2个
B.3个
C.4个
D.5个
83．设简单图G所有结点的度数之和为12，则G一定有（）
A．3条边B．4条边C．5条边D．6条边
84．下列不．一定是树的是（）
A．无回路的连通图B．有n个结点，n-1条边的连通图
C．每对结点之间都有通路的图D．连通但删去一条边则不连通的图
85.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( )
A.汉密尔顿回路
B.欧拉回路
C.汉密尔顿通路
D.初级回路
86.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( )
A.10
B.12
C.16
D.14
87. 无向图G中有16条边，且每个结点的度数均为2，则结点数是( )
A.8
B.16
C.4
D.32
88.下列不是平面图的是( )
89．设G为有n个结点的简单图，则有（）
A．Δ(G)＜n B．Δ(G)?n C．Δ(G)＞n D．Δ(G)?n
90.下面既是汉密尔顿图又是欧拉图的图形是（）
91.下列可一笔画成的图形是（）
92. 下列各图不是欧拉图的是（）
93. 下列图是欧拉图的是（）
94.一棵树有5个3度结点，2个2度结点，其它的都是l度结点，那么这棵树的结点数是（）
A.13
B.14
C.16
D.17
95.一棵树有3个5度点、1个4度点、3个2度点，其它的都是1度，那么它的边数是（）
A.17
B.18
C.19
D.20
96. 设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶
点数是（）
A．3 B．4 C．5 D．6
97．设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（）A．2个面B．3个面C．4个面D．5个面
98.设群G=
A.a
B.b
C.G中零元素
D.G中幺元
99.设实数集R上的二元运算o为：xoy=x+y-2xy,则o不满足( )。
A.交换律
B.结合律
C.有幂等元
D.有零元
100.若(A，*)是一个代数系统，且满足结合律，则(A，*)必为( )。
A.半群
B.独异点
C.群
D.可结合代数
101.下列各图是平面图的是( )
102.下列各图是无向完全图的是（）
103．下列各有向图是强连通图的是（）
104．下列各图中既是欧拉图，又是汉密尔顿图的是（）
A．B．C．D．
105．设连通平面图Ｇ，共有n个结点，e条边，r个面，则欧拉证明成立的公式是（）A．e-n+r=2 B．n+r-e=2
C．n-r+e=2 D．n-e-r=2
106．设无向图G的边数为m，结点数为n，则G是树等价于（）
A．G连通且m=n+1 B．G连通且n=m+1
C．G连通且m=2n D．每对结点之间至少有一条通路
二、填空题
1.合式公式┐(q→p)∧p是永______式.
2. 设命题变元为p，q，r，则极小项m4=________，极大项M2=________。
3．命题公式（p∧q）→? p的成真赋值为__________，成假赋值为__________。
4.设p、q为两个命题，德摩根律可表示为_____________，吸收律可表示为____________。
5.设M(x):x是人，D(s):x是要死的，则命题“所有的人都是要死的”可符号化为(?x)______,
其中量词(?x)的辖域是______。
6.判断一个语句是否为命题，首先要看它是否为，然后再看它是否具有唯
一的。
7.公式(?x)A(x)→B(y)的前束范式为_ ___.
8.设个体域为D={-2,3,6},F(x):x≤3,G(x):x>5.则在此解释下公式(?x)(F(x)∧G(x))的真值为______.
9.谓词公式(?x)( ?y)（P(x,y)∨R(y))→Q(y)，则其约束变元是________，自由变元是________。
10.合取范式具有形式A1∧A2∧…∧A n(n?1)，其中A1，A2，…，A n是由________及其________所组成的析取式。
11.设命题p为“明天上午8点下雨”，q为“明天上午8点下雪”，r为“我去学校”，则“如果明天上午8点不下雨且不下雪则我去学校”可表示为公式_ _ _；而“只有当明天上午8点不下雪并且不下雨时我才去学校”可表示为公式__ __。12．设论域是{a,b,c}，则(?x)S(x)等价于命题公式；(x?)S(x)等价于命题公式。
13.不能再分解的命题称为____________，至少包含一个联结词的命题称为____________。
14．设A为任意集合，请填入适当的运算符，使式子A____________A=?；
A____________~A=?成立。
15.设A={1,2,3}，B={3,4,5}，则A⊕A=___________，A⊕B=___________。
16．设A={1，2}，B={2，3}，则A⊕A=__________，A⊕B=__________。
17．设A={1，2}，B={2，3}，则A-A=________，A-B=________。
18.设A={1，2，3，4}，B={2，4，6}，则A-B=________，A⊕B=________。
19.设A={1,2,3,4,5}，R?A×A，R={<1,2>，<3,4>,<2,2>}，则R的
自反闭包r(R)=__ ____，
对称闭包t(R)=___ ______。
20.A={1,2,3,4}上二元关系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的关系矩阵M R中m24=______,m34=______。
21.给出A={l，2}上的一个等价关系________，并给出其对应的划分________。
22.设A={l，2，3，4}，A上的二元关系R={<1，2>，<2，3>，<3，2>}，S={
23．设A={1，2，3，4}上关系R={<1,2>,<2,4>,<3,3>,<1,3>}，则R 的自反闭包r(R)= _________，
对称闭包S （R ）=__________。
24.设A={a,b,c}中的关系R={
25.设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},那么
dom(A ∪B)=_______, ran(A ∩B)= __________。
27．设A={0，1，2，3，6}，R={〈x,y 〉|x ≠y ∧(x,y ∈A)∧y ≡x(mod 3)}，则domR=____________，ranR=____________。
28．设X={1，2，3}，f ：X →X ，g ：X →X ，f={<1, 2>,<2,3>,<3,1>},
g={<1,2>,<2,3>,<3,3>}，则f g=________________，g f=________________。
29.给定集合A={1,2,3,4,5}，在集合A 上定义两种关系：R={<1,2>,<3,4>,<2,2>},
S={<4,2>,<2,5>,<3,1>,<1,3>}，则
_______________S R = ，_______________
R S = 。 30.设f ∶R →R,f(x)=x+3,g ∶R →R,g(x)=2x+1,则复合函数____________
))(g (f =x , __________________)x )(f (g = 。
31．设X={1，3，5，9，15，45}，R 是X 上的整除关系，则R 是X 上的偏序，其最大元是___，极小元是____。
32.设X={1,2,3}上的关系R 的关系图如下，从关系图可知R 具有________________，________和传递性等性质。
33.设A={2,3,6,12},?是A 上的整除关系，则偏序集〈A ，?〉的最大元是________，极小元是________。
34．设R 为A 上的关系，则R 的自反闭包r(R)= ，对称闭包s(R)= 。
35．集合A={a,b,c}上的二元关系R 具有对称性，反对称性，自反性和传递性，此关系R
是 ，其关系矩阵是 。
36．设Z 是整数集，在Z 上定义二元运算*为a*b=a+b+a ·b ，其中+和·是数的加法和乘法，
则代数系统
37．设e 是群G 上的幺元，若a ∈G 且a 2=e,则a -1=____ ,a -2=__________。
38.在实数集R 上定义运算a b=a+b+ab ，则幺元为________，元素2的逆元为________。
39．对实数的普通加法和乘法，____________是加法的幂等元，____________是乘法的幂等元。
40．设S 是非空有限集，代数系统
中，其中P （S ）为集合S 的幂集，则P （S ）
对∪运算的单位元是________，零元是________。
41．在 +>中，2的阶是________。 42．在代数系统〈A ，*〉中，A={a}，*是A 上二元运算，则该代数系统的单位元是____________，零元是____________。 43．有理数集Q 中的*运算定义如下：a *b =a +b -ab ，则*运算的单位元是__________，设a 有逆元，则其逆元a -1=__________。 44.设Z 是整数集，+是整数加法运算，则 45.无向图G= Δ(G)=_____________，G 的最小度δ(G)=_____________。 46.一个连通平面图G 有10条边，G 中度为1的顶点有2个，其余是度为6的顶点，则G 中共有___个顶点，____个面。 47.有向图D 如下：D 的邻接矩阵A=(a ij )3×3,则a 11=____,a 32=____。 48.一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 48.设图G ???????=0001001111011010A ，则 deg -(v 1)=_ ________, deg +(v 4)=____________。 50．设图D= ??????1001001111011010，则deg -（v 1）=________，从v 2到v 4长度为2的路有________条。 51．如下平面图有2个面R 1和R 2，其中deg(R 1)= ，deg(R 2)= 。 52．无向图G 具有一条欧拉回路，当且仅当G 是 ，并且所有结点的度数都是 。 53．在下图中，结点v 2的度数是 ，结点v 5的度数是 。 54.设图G 的邻接矩阵为M=???? ??????001011110，则G 的可达性矩阵为______. 55.设一个平面图有v 个结点，e 条边，r 个面，则它们的数量关系是______. 56.一个无向树中有6条边，则它有______个结点. 三、计算题 1. 求合式公式A=p →((p →q)∧┐(┐q ∨┐p))的主析取范式和主合取范式. 2. 请通过等值演算法求┐(p ∧q )→(p ∨q )的主析取范式和主合取范式。 3. 用等值演算求（p →q ）→r 的主析取范式和主合取范式。 4．求公式（)r q ()q p ∧→∨的主析取范式。 5．求下列公式的主合取范式和主析取范式：p ∨（? p →（q ∨（? q →r ））） 6．求命题公式（p →q ）→（q ∨p ）的主析取范式。 7．利用真值表判断公式（（P ∨Q ）∧（Q →R ））→（P ∧R ）是否为重言式。 8. 构造命题公式?（p ∨q ）?（?p ∧q ）的真值表。 9．构造命题公式（r q q p ∧→∨）→p ∧? r 的真值表。 10．已知A={{?}，{?，1}}，B={{?，1}，{1}}，计算A ∪B ，A ○+B ，A 的幂集P （A ）。 11．若集合A={1，{2，3}}的幂集为P （A ），集合B={{?，2}，{2}}的幂集为P （B ），求P(A)∩P(B)。 12. 设集合A={a,b,c},A 中的关系R={ 包t(R) .13．设A ={1,2,3,4}，给定A 上二元关系R ={<1,1>,<1,2>,<2,4>,<4,2>}，求R 的传递闭包。 14．设X={1，2，3，4}，R 是X 上的二元关系， R={<1,1>,<3,1>,<1,3>,<3,3>,<3,2>,<4,3>,<4,1>,<4,2>,<1,2>}。 （1）画出R 的关系图； （2）写出R 的关系矩阵； （3）说明R 是否具有自反、反自反、对称、传递性质。 15．设A={1，2，3，4，6，8，12，24}，R 为A 上的整除关系，试画的哈斯图， 并求A 中的最大元、最小元、极大元、极小元。 16．设A={a ,b ,c },P(A)是A 的幂集，R 为A 上的包含关系，试给出 出子集{{a ,b },{a ,c },{c }}的极大元、极小元、最大元、最小元。 17.设A={2，3，6，12，24，36}，请画出A 上整除关系的哈斯图，并给出子集{6，12，24，36}的下界、下确界、极大元、最大元。 18. 设集合A={1,3,5,7,9,11,13,15},A 上的一个划分S={{1,15},{3,9,11,13},{5,7}}。 试求由S 导出的A 上的等价关系R 。 19.(4分)设A={a,b,c,d},R={ 20．设A={a,b,c,d}, R={〈a,c〉，〈c,b〉，〈b,a〉，〈a,d〉}，求R，r(R),s(R),t(R)的关系图。21. 求公式下面谓词公式的前束范式。 （1）(?x)?(F(x)→(?y)G(,xy,z))→(?z)H(x,y,z)， （2）┐((?x)F(x,y)→(?y)G(x,y))∨(?x)H(x)， （3）)z,y,x( x )( (? ∧ ?。 )x(f ? → )y )z H ( ( )) G z,y,x( 22. 作出命题公式(p→(q∨r))→┓q的真值表，并写出其主析取范式。 23. 一棵树有2个4度结点，3个3度结点，其余结点是叶子，求该树的叶子数。 24. 设A={a,b,c,d}，A上的等价关系R={ 25. 设A={a, b, c, d, e}，R为A上的关系，R={ e>}∪I A，试画 R={ （1）写出R的关系矩阵； （2）判断R是不是偏序关系，为什么？ 27. 设A={a,b},P(A)是A的幂集，⊕是对称差运算，可以验证 数，求({a}-1{b}{a})n⊕{a}-n{b}n{a}n 28. 设A={1,2,3,4,5},A上偏序关系 R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪I A; (1)作出偏序关系R的哈斯图 (2)令B={1,2,3,5}，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。 29. 求┐(P→Q)?(P→┐Q)的主合取范式并给出所有使命题为真的赋值。 30．试画出结点数为3的（1）强连通图；（2）单向连通图；（3）弱连通图；（4）非连通图。31．求题31图的最小生成树。 32.给定图G如图所示，（1）G中长度为4的路有几条？其中有几条回路？（2）写出G的可达矩阵。 33. 设带权无向图G如下，求G的最小生成树T及T的权总和。 34．给定图G 如下所示，（1）写出G 的可达矩阵；（2）G 中长度为4的路有几条？ 35. 设A={1,2,3}，给定A 上二元关系R={<1,1>,<1,2>,<2,3>}，求r(R),s(R)和t(R)。 36.对如下有向图D ，求D 中长度为4的路有多少条?其中回路有多少条? 37. 设A={a,abc,bc,bcd,bd}，定义A 上二元关系R={ ①作出R 的哈斯图 ②向R 中最少添加几个序偶可使之成为等价关系?求出该等价关系所确定的集合A 的划分。 38． 设A={a,b,c }，P （A ）是A 的幂集，⊕是集合对称差运算。已知 39． 用等值演算法求公式┐(p →q) ?(p →┐q)的主合取范式 40． 画出5个具有5个结点5条边的非同构的无向连通简单图。 41． 在偏序集 的极大元，极小元，最大元，最小元，最小上界和最大下界。 四、其他 1. 用等值演算法证明((q ∧s)→r)∧(s →(p ∨r))?(s ∧(p →q))→r 2．用等值演算法证明：))Q )R P (()Q R (()Q P (→∨→→→→是永真式。 3. 用推理方法证明：)(,,,S P R R Q Q P ∧???∨?→ ? S ?。 4．用推理方法证明(A ∨B )→(C ∧D ),(D ∨F )→E ? A →E 。 5．构造下面推理的证明。 如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。 6.如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI 语言而且学过 C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。 请用命题逻辑推理方法，证明该推理的有效结论。 7.设 离散数学试题（A卷答案） 一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式 解：(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，， 离散数学考试试题（A 卷及答案） 一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有： 甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 离散数学考试题(后附详细答案) 一、命题符号化（共6小题，每小题3分，共计18分） 1.用命题逻辑把下列命题符号化 a)假如上午不下雨，我去看电影，否则就在家里读书或看报。 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（PQ）(PRS) b)我今天进城，除非下雨。 设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：Q→P或P→Q c)仅当你走，我将留下。 设P表示命题“你走”，Q表示命题“我留下”，命题符号化为：Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不是有理数 设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为： x(R(x) Q(x)) 或x(R(x) →Q(x)) b)对于所有非零实数x，总存在y使得xy=1。 设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为： x(R(x) E(x,0) →y(R(y) E(f(x,y),1)))) c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b. 设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为：F(f)a(A(a)→b(B(b) E(f(a),b) c(S(c) E(f(a),c) →E(a,b)))) 二、简答题（共6道题，共32分） 1.求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。 （5分） (P→(Q→R))(R→(Q→P))（PQR）(PQR) (（PQR）→(PQR)) ((PQR) →（PQR）). (（PQR）(PQR)) ((PQR) （PQR）) (PQR)(PQR) 这是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 （PQR（PQR（PQR（PQR（PQR（PQR 2.设个体域为{1,2,3}，求下列命题的真值（4分） a)xy(x+y=4) b)yx (x+y=4) a) T b) F 3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分） x(F(x)→G(x))→(xF(x)→xG(x)) x(F(x)→G(x))→(yF(y)→zG(z)) x(F(x)→G(x))→yz(F(y)→G(z)) xyz((F(x)→G(x))→(F(y)→G(z))) 4.判断下面命题的真假，并说明原因。（每小题2分，共4分） 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ). 试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统 二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。 离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 常熟理工学院20 ～20 学年第学期 《离散数学》考试试卷（试卷库01卷） 试题总分： 100 分考试时限：120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题（每题2分，共20分） 1.下列表达式正确的有( ) （A）（B）（C）（D） 2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为 真。 （A）（B）（C）（D） 3.集合A={1,2,…,10}上的关系R={ 1．n个命题变元组成的命题公式共有种不同的等价公式。 2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。 3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4．设T是一棵树，则T是一个连通且的图。 5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6．量词否定等价式? ("x)P(x) ?，? ($x)P(x) ?。 7．二叉树有5个度为2的结点，则它的叶子结点数为。 8．设 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{ 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 离散数学期末测验试题（有几套带答案1) ————————————————————————————————作者: ————————————————————————————————日期: ? 离散数学试题(A卷及答案） 一、证明题（10分） １)(?P∧(?Q∧Ｒ)）∨(Q∧R）∨(P∧R）?Ｒ 证明：左端?(?P∧?Q∧R)∨（(Q∨Ｐ)∧R)?（(?P∧?Q)∧R))∨((Ｑ∨Ｐ)∧R） ?(?(P∨Q）∧R)∨((Q∨P)∧Ｒ)?(?(P∨Q)∨(Ｑ∨Ｐ))∧R ?(?(P∨Q)∨(Ｐ∨Ｑ))∧R?T∧R(置换）?R 2）?x(Ａ（ｘ)→B(x)）??xＡ(x）→?xB(x) 证明:?x(A(x)→Ｂ(x））??x（?A（x)∨B(x))??x?A(x)∨?xB(x)???xA（x)∨?xB(x)??xA(x)→?xＢ(ｘ） 二、求命题公式(P∨(Q∧Ｒ))→(Ｐ∧Q∧R）的主析取范式和主合取范式(１０分) 证明:(P∨（Ｑ∧Ｒ））→(P∧Q∧R)??(P∨(Ｑ∧Ｒ）)∨（P∧Q∧R)) ?（?P∧（?Q∨?R)）∨(Ｐ∧Q∧Ｒ） ?(?P∧?Ｑ)∨(?P∧?R)）∨(Ｐ∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Ｑ∧?R）∨(?Ｐ∧Q∧?R)）∨(?P∧?Q∧?R)）∨(Ｐ∧Ｑ∧R) ?m0∨ｍ1∨m2∨ｍ７ ?Ｍ3∨M4∨M5∨M6 三、推理证明题(10分) 1）Ｃ∨D， (C∨D)→?E, ?Ｅ→(A∧?B), (A∧?B)→(R ∨S)?R∨S 证明:(1) (C∨D）→?E (２) ?E→（A∧?Ｂ) ?? (3）（C∨D）→（A∧?Ｂ) （４) （Ａ∧?B)→(R∨Ｓ) ?? (5) （C∨D）→（R∨Ｓ) ? (6) C∨Ｄ?? (7) R∨S 2) ?x(P(ｘ)→Q(ｙ）∧R(x)），?xP(x)?Q(y）∧?x（P(x)∧R(x)) 证明（1)?xP(ｘ) (2）P(a) （3)?ｘ(P(x)→Q(y）∧R(x)) (4）P（a)→Q(y)∧R(a) (５)Q(y)∧Ｒ(a) (6)Q(y) （７)R(a） (8)P(a) (9)P(ａ)∧R(a) （10)?x(Ｐ(x)∧R(ｘ)) (11)Q（ｙ)∧?x(P（x）∧R(x)） 五、已知Ａ、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) （１5分) 证明∵x∈A-（Ｂ∪C)?x∈A∧x?（Ｂ∪C)?x∈A∧(x?Ｂ∧ｘ?C）?(x∈A∧x?B)∧（x∈A∧x?C）?x∈（Ａ-B)∧ｘ∈(A－C）?x∈(A－B）∩（A-Ｃ)∴A-(B∪Ｃ）=（A-B)∩(A-C） 六、已知R、S是N上的关系，其定义如下：Ｒ=｛＜x，ｙ>| x，y∈N∧y=x2｝，Ｓ={ 填空10% （每小题 2 分） 1、若P，Q，为二命题，P Q 真值为0 当且仅当。 2、命题“对于任意给定的正实数，都存在比它大的实数” 令F（x）：x 为实数，L（x, y） : x y 则命题的逻辑谓词公式为。 3、谓词合式公式xP（x） xQ（x）的前束范式为。 4、将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为 换名规则。 5、设x 是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y 是自由的，则被称为存 在量词消去规则，记为ES。 选择25% （每小题分） 1、下列语句是命题的有（）。 A、明年中秋节的晚上是晴天； C、xy 0 当且仅当x 和y 都大于0； D 、我正在说谎。 2、下列各命题中真值为真的命题有（）。 A、2+2=4当且仅当3是奇数； B、2+2=4当且仅当 3 不是奇数； C、2+2≠4 当且仅当3是奇数； D、2+2≠4当且仅当 3 不是奇数； 3、下列符号串是合式公式的有（） A、P Q ； B、P P Q； C、( P Q) (P Q)； D、(P Q) 。 4、下列等价式成立的有（ ）。 A、P QQ P ； B、P(P R) R； C、P (P Q) Q； D 、P (Q R) (P Q) R。 5、若A1,A2 A n和B为 wff ，且A1 A2 A n B 则 （ ）。 A、称A1 A2 A n 为 B 的前 件； B 、称 B 为A1,A2 A n 的有效结论 C 、 x(M (x) Mortal (x)) ； D 、 x(M(x) Mortal (x)) 8、公式 A x(P(x) Q(x))的解释 I 为：个体域 D={2} ，P(x) ：x>3, Q(x) ：x=4则 A 的 真 值为（ ） 。 A 、 1； B 、 0； C 、 可满足式； D 、无法判定。 9、 下列等价关系正确的是（ ）。 A 、 x(P(x) Q(x)) xP(x) xQ(x)； B 、 x(P(x) Q(x)) xP(x) xQ(x)； C 、 x(P(x) Q) xP(x) Q ； D 、 x(P(x) Q) xP(x) Q 。 10 、 下列推理步骤错在（ ）。 ① x(F(x) G(x)) P ② F(y) G(y) US ① ③ xF(x) P ④ F(y) ES ③ ⑤G(y) T ②④I ⑥ xG(x) EG ⑤ A 、②； B 、④； C 、⑤； D 、⑥ 逻辑判断 30% 1、 用等值演算法和真值表法判断公式 A ((P Q) (Q P)) (P Q) 的类型。 C 、当且仅当 A 1 A 2 A n D 、当且仅当 A 1 A 2 A n B F 。 6、 A ，B 为二合式公式，且 B ，则（ ）。 7、 A 、 A C 、 A B 为重言式； B 、 B ； E 、 A B 为重言式。 人总是要死的”谓词公式表示为（ ）。 论域为全总个体域） M （x ） ： x 是人； Mortal(x) x 是要死的。 A 、 M (x) Mortal (x) ； B M (x) Mortal (x) 精品文档院术师范学广东技模拟试题 科目：离散数学 120 分钟考试时间: 考试形式：闭卷 姓名：学号：系别、班级： 2分，共10分）一．填空题（每小题__________。?x?y?P(x)∨Q(y) 1. 谓词公式的前束范式是 __)xxQ(?xP(x)????????____，，2. 设全集A?_{4,5}B =__则A∩ {2}__,,?E?1,2,3,4,55,A?21,,32,B_____ __ {1,3,4,5}??BA????b,c}} __________，则3. 设__ ， b?,c,b,a,A?Ba???B(A)?)(_____Φ_______。???)(AB()?4. 在代数系统（N，+）中，其单位元是0，仅有_1___ 有逆元。 ne条边，则G有___e+2-n____个面。5．如果连通平面图G有个顶点，二．选择题（每小题2分，共10分） P?(Q?R)等价的公式是（1. 与命题公式） （A）（B）（C）（D）R?P?Q)()?R)R?(QPP?(Q?R?Q)(P??????b?b,?a,aA??a,b,cR?,不具备关系( 2. 设集合上的二元关系,A)性质 （A）(A)传递性(B)反对称性(C)对称性(D)自反性 G??V,E?中,结点总度数与边数的关系是3. 在图( ) ??E?Edeg(v)deg(v)?2deg(v)?Evdeg()?2E(A)(C)(B) (D) iiiiVv?Vv?4. 设D是有n个结点的有向完全图,则图D的边数为( ) n(n?1)n(n?1)n(n?1)/2n(n?1)/2(A)(B)(D)(C) 5. 无向图G是欧拉图,当且仅当( ) (A)G的所有结点的度数都是偶数(B)G的所有结点的度数都是奇数 精品文档． 精品文档 (C)G连通且所有结点的度数都是偶数(D) G连通且G的所有结点度数都是奇数。 三．计算题（共43分） p?q?r的主合取范式与主析取范式。（1. 求命题公式6分） 解：主合取方式：p∧q∨r?(p∨q∨r)∧(p∨?q∨r)∧(?p∨q∨r)= ∏0.2.4 主析取范式：p∧q∨r?(p∧q∧r) ∨(p∧q∧?r)∨(?p∧q∧r) ∨(?p∧?q∧r) ∨(p∧?q∧r)=∑1.3.5.6.7 1000????0111?????Md,A?a,b,c,的上的二元关集2. 设合系R关系矩阵为求 ??R0000????1000??)tR(),(RsRr()(),(),(rRsRtR),的关系图。R的关系矩阵，并画出分）10（， 一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 6．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为 则 R= 。 8．图的补图为 。 9．设A={a ，b ，c ，d} ，A 上二元运算如下： 那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。 10．下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ? ； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A ．{4，3}Φ?； B ．{Φ，3，4}； C ．{4，Φ，3，3}； D ． {3，4}。 3、设A={1，2，3}，则A 上的二元关系有（ ）个。 A．23 ；B．32 ；C．332?；D．223?。 4、设R，S是集合A上的关系，则下列说法正确的是（） R 是自反的； A．若R，S 是自反的，则S R 是反自反的； B．若R，S 是反自反的，则S R 是对称的； C．若R，S 是对称的，则S R 是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s p R= t s ∈ =则P（A）/ R=（） < > ∧ A ) (| || |} ( , {t , | s A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 6、设A={Φ，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（） 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = 离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ （2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={ 离散数学试题与答案试卷一 一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 6．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 8．图的补图为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ?； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A B C ?；B．{Φ，3，4}；C．{4，Φ，3，3}；D．{3，4}。 A．{4，3}Φ 3、设A={1，2，3}，则A上的二元关系有（）个。 A．23 ；B．32 ；C．332?；D．223?。 4、设R，S是集合A上的关系，则下列说法正确的是（） Rο是自反的； A．若R，S 是自反的，则S Rο是反自反的； B．若R，S 是反自反的，则S Rο是对称的； C．若R，S 是对称的，则S Rο是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s t s p A R= ∧ =则P（A）/ R=（） < > ∈ s (| || |} {t ) , ( | , A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = 离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝_____{3}______________; ρ(A) - ρ(B)＝ ____{{3}，{1，3}，{2,3},{1,2,3}}__________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = ___2^(n^2)________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是____A1 = {(a,1), (b,1)}, A2 = {(a,2), (b,2)}, A3 = {(a,1), (b,2)}, A4 = {(a,2), (b,1)},_________ _____________, 其中双射的是______A3, A4__________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取式是____P∧?Q∧R (m5)____. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为___12______，分枝点数为_______3_________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝______{4}______; A?B＝____{1,2,3,4}_________;A－B＝______{1,2}_______ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______自反性____________, _________对称性_________, _________传递性_____________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有_____（1,0,0）__________， ______(1,0,1)________, ________(1,1,0)________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(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)}_________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = ______2^(m*n)___________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = _____{x | -1 ≤x < 0, x ∈R}_______ , B-A = ______{x | 1 < x < 2, x ∈R}_____ , A∩B = ______{x | 0 ≤x ≤1, x ∈R}__________ , . 13.设集合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)}_________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束式是_____?y?x(P(y)→Q(x))________ _____.(完整版)离散数学试卷及答案
离散数学期末试题
离散数学考试题详细答案
离散数学期末试题及答案
离散数学试题与答案
离散数学期末试题及答案完整版
离散数学题库
离散数学期末试卷及答案
离散数学期末试卷A卷及答案
离散数学期末测验试题(有几套带答案1)
离散数学试卷及答案
最新离散数学期末考试试题配答案
离散数学试卷及答案(1)
离散数学期末考试试题及答案
离散数学全部试卷
离散数学试题及答案
相关主题
文本预览