离散数学复习题集
一、单项选择题
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(∧
p(?
∧?q B.q
)q
C. q
→
p(?
∨
)p
∧
)q
p(
p(∨
→ D.)p
25．下列是两个命题变元p，q的极大项是（）
A．p∧┐p∧q B．┐p∨q
C．┐p∧q D．┐p∨p∨q
26．关于命题变元p和q的极大项M2表示( )。
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
(?
)(
?
)x(
?
∧
M
M
x(F
x(F
)(
)x(
?B．))
(→
x
C．))
)(
x
M
?
?
(∨
)x(
)(
)x(
x(F
M
x
?D．))
(∨
x(F
30．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（）A．))
(
?)
A
(x
x? B（x））
?B．?→
)
(
(B
A
(x
x
x∧
C．?))
?)
?D．?∧
(
A
x? B(x))
x∧
(x
)
x
(
(B
A
(x
31.设论域为整数集，下列谓词公式中真值为假的是( )
A.)0
y
)(
x
x
)(
?
?
y
?
(=
?
y
)(
x
? B. )1
)(
y
x
?
(=
C. )x
y
)(
)(
x
z
?
)(
?
?
-
(=
y
)(
x
)(
x
y
(=
y
? D. )z
?
x
?
32．下列公式是前束范式的是（）
A．))
)y
(
))
G
y(
)x(F)x
(
?
∨
?
(∧
?
?
)(
)x,z(F
H
y(
y
G
)(
?
?B．)z(
(∨
x
C．)y(
)y,x(F
(
)y
)(
G
→
(?
x
?
(
)y
G
y,x(
)y,x(F)x
?D．))
→
(?
33．设论域为整数集，下列真值为真的公式是（）
A．)0
x
)(
x
)(
y
?
-
(=
y
?
y
)(
x
y
)(
x
?
-
(=
?B．)0
C．)0
(
x
y
)(
)x
(=
?
?
?
-
?
?
y
)(
y
y
)(
x
?D．)0
x
-
(=
34．下列是谓词演算中的合式公式的是（）
A．)y
G
)x(F)x
(∧
?
?B．)y,x(
)x(p
→
x
)(
(?
C．)z,y(
(∧
?
)x
?
x
)y,x(P)x
Q
(?D．)y,x(P
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}，与公式)
x?等价的是（）
A
(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},{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是奇数集合，下列构成独异点的是（）
A.
B.
C.
D.
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 中m 24=______,m 34=______。
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={ .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 上的包含关系，试给出 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的幂集，⊕是集合对称差运算。已知 40．画出5个具有5个结点5条边的非同构的无向连通简单图。 41．在偏序集 四、其他 1. 用等值演算法证明((q∧s)→r)∧(s→(p∨r))?(s∧(p→q))→r 2．用等值演算法证明：)) P(→ Q (( ) → →是永真式。 → → ∨ R ) R P Q Q ) (( 3. 用推理方法证明：) ? ? P∧ ? →?S ∨ ? Q , , ( ,S P R R Q ?。 4．用推理方法证明(A∨B)→(C∧D),(D∨F)→E ?A→E。 5．构造下面推理的证明。 如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。 6.如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过 C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。 请用命题逻辑推理方法，证明该推理的有效结论。 7.设 试卷二试题与参考答案 一、填空 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、下面偏序集( )能构成格。 离散数学考试试题（A卷及答案） 一、（10分）证明?(A∨B)→?(P∨Q)，P，(B→A)∨?P A。 证明：(1)?(A∨B)→?(P∨Q) P (2)(P∨Q)→(A∨B) T(1)，E (3)P P (4)A∨B T(2)(3)，I (5)(B→A)∨?P P (6)B→A T(3)(5)，I (7)A∨?B T(6)，E (8)(A∨B)∧(A∨?B) T(4)(7)，I (9)A∧(B∨?B) T(8)，E (10)A T(9)，E 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 解符号化命题，设A：甲参加了比赛；B：乙参加了比赛；C：丙参加了比赛；D：丁参加了比赛。 依题意有， (1)甲和乙只有一人参加，符号化为A⊕B?(?A∧B)∨(A∧?B)； (2)丙参加，丁必参加，符号化为C→D； (3)乙或丁至多参加一人，符号化为?(B∧D)； (4)丁不参加，甲也不会参加，符号化为?D→?A。 所以原命题为：(A⊕B)∧(C→D)∧(?(B∧D))∧(?D→?A) ?((?A∧B)∨(A∧?B))∧(?C∨D)∧(?B∨?D)∧(D∨?A) ?((?A∧B∧?C)∨(A∧?B∧?C)∨(?A∧B∧D)∨(A∧?B∧D))∧((?B∧D)∨(?B∧?A)∨(?D∧?A)) ?(A∧?B∧?C∧D)∨(A∧?B∧D)∨(?A∧B∧?C∧?D)?T 但依据题意条件，有且仅有两人参加竞赛，故?A∧B∧?C∧?D为F。所以只有：(A∧?B∧?C∧D)∨(A∧?B∧D)?T，即甲、丁参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误？为什么？给出正确的推理形式。 (1)?x(P(x)→Q(x)) P (2)P(y)→Q(y) T(1)，US (3)?xP(x) P (4)P(y) T(3)，ES (5)Q(y) T(2)(4)，I (6)?xQ(x) T(5)，EG 解 (4)中ES错，因为对存在量词限制的变元x引用ES规则，只能将x换成某个个体常元c，而不能将其改为自由变元。所以应将(4)中P(y)改为P(c)，c为个体常元。 正确的推理过程为： (1)?xP(x) P (2)P(c) T(1)，ES (3)?x(P(x)→Q(x)) P (4)P(c)→Q(c) T(3)，US (5)Q(c) T(2)(4)，I (6)?xQ(x) T(5)，EG 四、（10分）设A＝{a，b，c}，试给出A上的一个二元关系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分） 离散数学期末试题及答 案 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的补元( ). 离散数学试题（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 ＝{，，，，，，，， 离散数学 2^m*n 一、选择题（2*10） 1．令P：今天下雨了，Q：我没带伞，则命题“虽然今天下雨了，但是我没带伞”可符号化为（）。 （A）P→?Q （B）P∨?Q （C）P∧Q （D）P∧?Q 2．下列命题公式为永真蕴含式的是（）。 （A）Q→（P∧Q）（B）P→（P∧Q） （C）（P∧Q）→P （D）（P∨Q）→Q 3、命题“存在一些人是大学生”的否定是(A)，而命题“所有的人都是要死的”的否定 是（）。 （A）所有人都不是大学生，有些人不会死 （B）所有人不都是大学生，所有人都不会死 （C）存在一些人不是大学生，有些人不会死 （D）所有人都不是大学生，所有人都不会死 4、永真式的否定是（）。 （A）永真式（B）永假式（C）可满足式（D）以上均有可能 5、以下选项中正确的是（）。 （A）0= ? （B）0 ? （C）0∈? （D）0?? 6、以下哪个不是集合A上的等价关系的性质？（） ）。 （A）2 （B）4 （C）3 （D）5 10．连通图G是一棵树，当且仅当G中（）。 （A）有些边不是割边（B）每条边都是割边 （C）无割边集（D）每条边都不是割边 二、填空题（2*10） 1、命题“2是偶数或-3是负数”的否定是________。 2、设全体域D是正整数集合，则命题?x?y(xy=y)的真值是______。 3、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为 4 5 6、设 7 8 (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下 五、（15分）设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质： 《离散数学》期末考试题(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 是欧拉图. 二、单选题(每小题3分，共15分) 1.设R 是集合A 上的偏序关系，1-R 是R 的逆关系，则1 -?R R 是A 上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元p 和q 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设p 是素数且n 是正整数，则任意有限域的元素个数为 (A)n p + (B)pn (C)n p (D)p n 4.设R 是实数集合，≤是其上的小于等于关系，则(R, ≤)是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图3K 的不同构的生成子图有 (A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”. 1.若一个元素a 既存在左逆元l a ，又存在右逆元r a ，则r l a a =. ( ) 2.命题联结词→不满足结合律. ( ) 3.在Z 8 = {0，1，2，3，4，5，6，7}中，2关于“?8”的逆元为 4. ( ) 4.整环不一定是域. ( ) 离散数学期末考试试卷(A卷) 一、判断题：（每题2分，共10分） （1） （1） （2）对任意的命题公式, 若, 则 （0） （3）设是集合上的等价关系, 是由诱导的上的等价关系，则。（1） （4）任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。 （0） （5）设是上的关系，分别表示的对称和传递闭包，则 （0） 二、填空题：（每题2分，共10分） (１) 空集的幂集的幂集为（）。 (２) 写出的对偶式（）。 （３）设是我校本科生全体构成的集合，两位同学等价当且仅当他们在 同一个班，则等价类的个数为（），同学小王所在 的等价类为（）。 （４）设是上的关系，则满足下列性质的哪几条：自反的，对称的，传递的，反自反的，反对称的。 （） (5)写出命题公式的两种等价公式( ）。 三、用命题公式符号化下列命题（１）（２）（３），用谓词公式符号化下列命题（４）（５）（６）。（12分） （１）（１）仅当今晚有时间，我去看电影。 （２）（２）假如上午不下雨，我去看电影，否则就在家里读书。 （3）你能通你能通过考试，除非你不复习。 （４）（４）并非发光的都是金子。 （５）（５）有些男同志，既是教练员，又是国家选手。 （６）（６）有一个数比任何数都大。 四、设，给定上的两个关系和分别是 （１）（１）写出 和 的关系矩阵。（２）求 及 （1２分） 五、求 的主析取范式和主合取范式。（１０分） 六、设 是 到 的关系， 是 到 的关系，证明： （8分） 七、设 是一个等价关系，设 对某一个 ,有 ，证明： 也是一个等价关系。（10分） 八、（1０分）用命题推理理论来论证 下述推证是否有效？ 甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获 胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。 九、（１０分） 用谓词推理理论来论证下述推证。 任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑 自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行 (论 域是人)。 十、(8分) 利用命题公式求解下列问题。 甲、乙、丙、丁四人参加考试后，有人问他们，谁的成绩最好， 甲说：“不是我，”乙说：“是丁，”丙说：“是乙，” 丁说：“不是我。” 四人的回答只有一人符合实际，问若只有一人成绩最 好，是谁？ 离散数学期末考试试卷答案(A 卷) 一、判断题：（每题2分，共10分） （1）}}{{}{x x x -∈ （ ∨） (2) 对任意的命题公式C B A ,,, 若 C B C A ∧?∧, 则B A ? ( ? ) （3）设R 是集合A 上的等价关系, L 是由 R A 诱导的A 上的等价关系，则L R =。 ( ∨ ) （4） 任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等 价。 （ ? ） （5）设R 是A 上的关系，)(),(R t R s 分别表示R 的对称和传递闭包，则 )()(R st R ts ? （ ? ） 二、填空题：（每题2分，共10分） 常熟理工学院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．设 一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c) B.(a∧b)∨(a’∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交 运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z， Z是整数集， 定义为x xy=xy,?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设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 9.设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〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x 离散数学试题(Ｂ卷答案１） 一、证明题(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={ 试卷二十三试题与答案 一、单项选择题：（每小题1分，本大题共10分） 1．命题公式)(P Q P ∨→是（ ）。 A 、 矛盾式； B 、可满足式； C 、重言式； D 、等价式。 2．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨?； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 3．谓词公式)())()((x Q y yR x P x →?∨?中的 x 是（ ）。 A 、自由变元； B 、约束变元； C 、既是自由变元又是约束变元； D 、既不是自由变元又不是约束变元。 4．在0 Φ之间应填入（ ）符号。 A 、= ； B 、?； C 、∈； D 、?。 5．设< A ， > 是偏序集，A B ?，下面结论正确的是（ ）。 A 、 B 的极大元B b ∈且唯一； B 、B 的极大元A b ∈且不唯一； C 、B 的上界B b ∈且不唯一； D 、B 的上确界A b ∈且唯一。 6．在自然数集N 上，下列（ ）运算是可结合的。 （对任意N b a ∈,） A 、b a b a -=*； B 、),max(b a b a =*； C 、b a b a 5+=*； D 、b a b a -=*。 7．Q 为有理数集N ，Q 上定义运算*为a*b = a + b – ab ,则 精品文档 离散数学 10.设仃限集丸 B. |A|■申 p|p |p(AxB)| = 带伞”可符号化为( ) (C ) P A Q (D ) P A Q 2 ?下列命题公式为永真蕴含式的是( ) (A ) C H( P A Q ) ( B ) P -( P A Q ) (C ) (P A Q — P ( D (P V Q)— Q 3、 命题“存在一些人是大学生”的否定是(A)，而命题“所有的人都是要死 的”的否定是( )。 (A) 所有人都不是大学生，有些人不会死 (B) 所有人不都是大学生，所有人都不会死 (C) 存在一些人不是大学生，有些人不会死 (D) 所有人都不是大学生，所有人都不会死 4、 永真式的否定是()。 (A )永真式 (B )永假式 (C )可满足式 (D )以上均有可能 5、以下选项中正确的是()。 (A ) 0= ? (B ) 0 ? (C 0€ ? (D ) 0?? 6、以下哪个不是集合A 上的等价关系的性质？( ) (A )自反性 (B )有限性 (C )对称性 (D ) 传递性 7、集合 A={1,2,…;10}上的关系 R={ 离散数学试题(B卷答案1） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R 2) ?x (A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x)) ??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D， (C∨D)→?E，?E→(A∧?B)， (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2)，I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4)， I (6) C∨D P (7) R∨S T(5)，I 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P 一、判断正误20% （每小题2分） 1、设A.B. C是任意三个集合。 （1）若A∈B且B?C，则A?C。（） （2）若A?B且B∈C，则A?C。（） （3）若A?B且B∈C，则A?C。（） （4）A) ( ) ( ) (C A B A C B ⊕ = ⊕。（） （5）(A–B)?C=(A?C)-(B?C)。（） 2、可能有某种关系，既不是自反的，也不是反自反的。（） ３、若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（） ４、一个图是平面图，当且仅当它包含与Ｋ 3， 3 或Ｋ 5 在２度结点内同构的子图。（） ５、代数系统中一个元素的左逆元并一定等于该元素的右逆元。（） ６、群是每个元素都有逆元的半群。（） 二、8% 将谓词公式)) , ( ) ( ) ( ) (( )) , ( ) ( )( (z y Q z y P y y x Q x P x? ∧ ? → → ?化为前束析取范式与前束合取范式。 三、8% 设集合Ａ＝{a,b,c,d}上的关系Ｒ＝{ 五、10% 证明：若图Ｇ是不连通的，则Ｇ的补图G 是连通的。 六、10% 证明：循环群的任何子群必定也是循环群。 七、12% 用ＣＰ规则证明： １．F A F E D D C B A →?→∨∧→∨,。 ２．?∨??∨?(()()())()()((x P x x Q x P x )()x Q x 。 八、10% 用推理规则证明下式： 前提: ))()()(()),()()(())()()(((y W y M y y W y M y x S x F x ?∧?→?→∧? 结论：?→?)()((x F x S ))(x 九、13% 若集合Ｘ＝｛（１，２），（３，４），（５，６），……｝ }|,,,{12212211y x y x y x y x R +=+>><><<= 1、证明R 是X 上的等价关系。 2、求出X 关于R 的商集。 一、 填空 20%（每小题2分） 《离散数学》期末考试试题 一、 填空题（每空2分，合计20分） 1. 设个体域为{2,3,6}D =-, ():3F x x ≤，():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生，:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________，A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =，在集合A 上定义两种关系： {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>， 则_______________S R =ο，_______________R S =ο。 6. 设e 是群G 上的幺元，若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7． 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系，则偏序集,A <>p 的最大元是________，极小元是_ _。 9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一 个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =，若G 的邻接矩阵????????????=0001001111011010A ，则1()deg v -=________, 4()deg v +=____________。 二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 离散数学试题(A卷及答案） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R 2)?x(A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分） 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D, (C∨D)→?E, ?E→(A ∧?B), (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E (2) ?E→(A∧?B) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D (7) R∨S 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明（1）?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) 离散数学试题与答案试卷一 一、填空 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) = 离散数学试题与答案
离散数学考试试题(A卷及答案)
离散数学考试题详细答案
离散数学期末试题及答案完整版
(完整版)离散数学试卷及答案
离散数学试题及解答
【浙江工商大学】《离散数学》期末考试题(B)
离散数学期末考试试卷(A卷)
离散数学题库
离散数学试卷及答案一
离散数学期末考试试题及答案
离散数学试卷二十三试题与答案
的幺元为（ ）。 A 、a ； B 、b ； C 、1； D 、0。 8．给定下列序列，（ ）可以构成无向简单图的结点度数序列。 A 、（1，1，2，2，3）； B 、（1，1，2，2，2）； C 、（0，1，3，3，3）； D 、（1，3，4，4，5）。 9．设G 是简单有向图，可达矩阵P(G)刻划下列 （ ）关系。 A 、点与边； B 、边与点； C 、点与点； D 、边与边。 10．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（ ）。 A 、5； B 、7； C 、9； D 、8。
离散数学试题及解答
离散数学期末考试试题及答案
离散数学试卷及答案(17)
《离散数学》期末考试试题
离散数学期末考试试题(有几套带答案)
离散数学全部试卷