离散数学试题及答案

巡山小妖精
726次浏览
2020年12月01日 20:43
最佳经验
本文由作者推荐

吉祥颂-腰扭伤

2020年12月1日发(作者:岑文本)


离散数学考试试题(A卷及答案)

一、(10分)某项工作需要派A、B、C和D 4个人中的2个人去完成,按下面3个条件,有几种派
法?如何派?
(1)若A去,则C和D中要去1个人;
(2)B和C不能都去;
(3)若C去,则D留下。
解 设A:A去工作;B:B去工作;C:C去工作;D:D去 工作。则根据题意应有:ACD,(B
∧C),CD必须同时成立。因此
(ACD)∧(B∧C)∧(CD)
(A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D)
(A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))
(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)
∨(C∧ D∧B∧C)∨(C∧ D∧B∧D)∨(C∧ D∧C)∨(C∧ D∧C∧D)
∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨ (C∧D∧C∧D)
F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F
(A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D)
(A∧C)∨(B∧C∧ D)∨(C∧D)
T
故有三种派法:B∧D,A∧C,A∧D。
二、(15分)在谓词逻辑中构造下面推理的证明 :某学术会议的每个成员都是专家并且是工人,有
些成员是青年人,所以,有些成员是青年专家。 解:论域:所有人的集合。
S
(
x
):
x
是专家;W
(
x
):
x
是工人;
Y
(
x
):
x
是青年人;则推理化
形式为:

x
(
S
(
x
)∧
W
(
x
)),

xY
(
x
)

x
(
S
(
x)∧
Y
(
x
))
下面给出证明:
(1)

x
Y
(
x
) P
(2)
Y
(c) T(1),ES
(3)

x
(
S
(
x
) ∧
W
(
x
)) P
(4)
S
( c)∧
W
( c) T(3),US
(5)
S
( c) T(4),I
(6)
S
( c)∧
Y
(c) T(2)(5),I
(7)

x
S
((
x
)∧< br>Y
(
x
)) T(6) ,EG
三、(10分)设A、B和C是三个集合,则AB(BA)。
证明:ABx( x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)


x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A ∧xB)∨x(x∈A∨xB)
(x(x∈A∧xB)∧x(x∈A∨xB)) (x(x∈A∧xB)∧x(x∈B→x∈A))
(BA)。
四、(15 分)设A={1,2,3,4,5},R是A上的二元关系,且R={<2,1>,<2,5>,<2,4>,< 3,
4>,<4,4>,<5,2>},求r(R)、s(R)和t(R)。
解 r(R) =R∪I
A
={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2> ,<1,1>,<2,2>,<3,
3>,<4,4>,<5,5>}
s(R)=R∪R={ <2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4 ,3>}
R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>}
R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>}
R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>}= R
t(R)=

R
i
={<2,1>,<2,5>,<2,4>, <3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,
i1

42
3
2
-1
5>}。
五、(10分)R是非空集合A上的二元关系,若R是对称的,则r(R)和t(R)是对称的。
证明 对任意的x、y∈A,若xr(R)y,则由r(R)=R∪I
A
得,xRy 或xI
A
y。因R与I
A
对称,所以有
yRx或yI
Ax,于是yr(R)x。所以r(R)是对称的。
下证对任意正整数n,R对称。
因R 对称,则有xRyz(xRz∧zRy)z(zRx∧yRz)yRx,所以R对称。若
R< br>n
对称,则
x
R
n1
yz(x
R
n< br>z∧zRy)z(z
R
n
x∧yRz)y
R
n1x,所以
R
n1
对称。因此,对任意正整数n,
R
n
对称。
对任意的x、y∈A,若xt(R)y,则存在m使得xRy,于是有yRx,即有yt(R) x。因此,t(R)是对称的。
六、(10分)若f:A→B是双射,则f:B→A是双射。
证明 因为f:A→B是双射,则f是B到A的函数。下证f是双射。
对任意x∈A,必存在y∈B使f(x)=y,从而f(y)=x,所以f是满射。
对任意的 y
1
、y
2
∈B,若f(y
1
)=f(y
2
)=x,则f(x)=y
1
,f(x)=y
2
。因为f:A→B是函数,则 y
1
=y
2

所以f是单射。
综上可得,f:B→A是双射。
七、(10分)设是一个半群,如果S是有限集,则必存在a∈S,使得a*a=a。
证明 因为是一个半群,对任意的b∈S,由*的封闭性可知,b=b*b∈S,b=b* b∈S,…,
b
n
∈S,…。
因为S是有限集,所以必存在j>i,使得< br>b
i

b
j
。令p=j-i,则
b
j

b
p
*
b
j
。所以对q≥i,有
b
q

b
p
*
b
q

因为p≥1,所以总可 找到k≥1,使得kp≥i。对于
b
kp
∈S,有
b
kp

b
p
*
b
kp

b
p
*(
b
p
*
b
kp
)=…=


232-1
-1
-1-1
-1-1
-1-1
-1
mm
222
n


b
kp
*
b
kp

令a=
b
kp
,则a∈S且a*a=a。

八、(20分) (1)若G是连通的平面图,且G的每个面的次数至少为l(l≥3),则G的边数m与结
点数n有如下 关系:
m≤
r
l
(n-2)。
l2
l
证明 设G有r个面,则2m=
2)。

d(f)
≥lr。由欧拉公式得,n

m+r=2。于是, m≤
l2
(n-
i
i1
(2)设平面图G=是自对偶 图,则| E|=2(|V|-1)。
证明 设G=是连通平面图G=的对偶图,则G G,于是|F|=|V*|=|V| ,
将其代入欧拉公式|V|-|E|+|F|=2得,|E|=2(|V|-1)。
**

















离散数学考试试题(B卷及答案)

一、(10分)证明(P∨Q)∧(PR)∧(QS)S∨R
证明 因为S∨RRS,所以,即要证(P∨Q)∧(PR)∧(QS)RS。
(1)R 附加前提
(2)PR P
(3)P T(1)(2),I
(4)P∨Q P
(5)Q T(3)(4),I
(6)QS P
(7)S T(5)(6),I
(8)RS CP
(9)S∨R T(8),E
二、(15分)根据推理理论证明:每个考生或者勤奋或者聪明,所有勤奋的人都将有所作为,但并非所有考生都将有所作为,所以,一定有些考生是聪明的。
设P(e):e是考生,Q(e):e 将有所作为,A(e):e是勤奋的,B(e):e是聪明的,个体域:人的集合,
则命题可符号化为: x(P(x)(A(x)∨B(x))),x(A(x)Q(x)),x(P(x)Q(x)) x(P(x)∧B(x))。
(1)x(P(x)Q(x)) P
(2)x(P(x)∨Q(x)) T(1),E
(3)x(P(x)∧Q(x)) T(2),E
(4)P(a)∧Q(a) T(3),ES
(5)P(a) T(4),I
(6)Q(a) T(4),I
(7)x(P(x)(A(x)∨B(x)) P
(8)P(a)(A(a)∨B(a)) T(7),US
(9)A(a)∨B(a) T(8)(5),I
(10)x(A(x)Q(x)) P
(11)A(a)Q(a) T(10),US
(12)A(a) T(11)(6),I
(13)B(a) T(12)(9),I
(14)P(a)∧B(a) T(5)(13),I
(15)x(P(x)∧B(x)) T(14),EG
三、(10分)某班有25名学生,其中14人会打篮球,12人会打排球,6人会 打篮球和排球,5人会


打篮球和网球,还有2人会打这三种球。而 6个会打网球的人都会打另外一种球,求不会打这三种球的
人数。
解 设A、B、C分别表示会打排球、网球和篮球的学生集合。则:
|A|=12,|B|=6,|C|= 14,|A∩C|=6,|B∩C|=5,|A∩B∩C|=2,|(A∪C)∩B|=6。
因为|( A∪C)∩B|=(A∩B)∪(B∩C)|=|(A∩B)|+|(B∩C)|-|A∩B∩C|=|(A∩B )|+5-2=6,所以|(A∩
B)|=3。于是|A∪B∪C|=12+6+14-6-5-3+2 =20,
|ABC|
=25-20=5。故,不会打这三种球的
共5人。
四、(10分)设A
1
、A
2
和A
3
是全集U的子集,则 形如

A
i
(A
i
为A
i

A
i
)的集合称为由A
1
、A
2

i1
3
A
3
产生的小项。试证由A
1
、A
2
和A
3
所产生的所有非空小项的集合构成全集U的一个划分。
证明 小项共8个,设有r个非 空小项s
1
、s
2
、…、s
r
(r≤8)。
对任 意的a∈U,则a∈A
i
或a∈
A
i
,两者必有一个成立,取Ai
为包含元素a的A
i

A
i
,则a∈
< br>A
i
,
i1
3
即有a∈

s
i
,于是U

s
i
。又显然有

s
iU,所以U=

s
i

i1i1i1i1
rrrr
任取两个非空小项s
p
和s
q
,若s
p
≠ s
q
,则必存在某个A
i

A
i
分别出现在sp
和s
q
中,于是s
p
∩s
q
=。
综上可知,{s
1
,s
2
,…,s
r
}是U的一个划分。
五、(15分)设R是A上的二元关系,则:R是传递的R*RR。
证明 (5)若R 是传递的,则∈R*Rz(xRz∧zSy)xRc∧cSy,由R是传递的得xRy,即有< x,
y>∈R,所以R*RR。
反之,若R*RR,则对任意的x、y、z∈A,如果x Rz且zRy,则∈R*R,于是有∈R,
即有xRy,所以R是传递的。 六、(15分)若G为连通平面图,则n-m+r=2,其中,n、m、r分别为G的结点数、边数和面数。
证明 对G的边数m作归纳法。
当m=0时,由于G是连通图,所以G为平凡图,此时n=1,r=1,结论自然成立。
假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。
设e是 G的一条边,从G中删去e后得到的图记为G,并设其结点数、边数和面数分别为n、m
和r。 对e分为下列情况来讨论:
若e为割边,则G有两个连通分支G
1
和G
2
。G
i
的结点数、边数和面数分别为n
i
、m
i
和 r
i
。显然n
1
+n
2
=n=n,m
1
+m
2
=m=m-1,r
1
+r
2
=r+1=r+1。 由归纳假设有n
1
-m
1
+r
1
=2,n
2
-m
2
+r
2
=2,
从而(n
1
+n
2
)-(m
1
+m
2
)+(r
1
+r
2)=4,n-(m-1)+(r+1)=4,即n-m+r=2。
若e不为割边,则n=n,m =m-1,r=r-1,由归纳假设有n-m+r=2,从而n-(m-1)+r
-1=2, 即n-m+r=2。
由数学归纳法知,结论成立。
七、(10分)设函数g:A→B,f:B→C,则:
(1)fg是A到C的函数;


(2)对任意的x∈A,有fg(x)=f(g(x))。
证明 (1)对任意的x∈A,因为g:A→B是函数,则存在y∈B使∈g。对于y∈B ,因f:B→C
是函数,则存在z∈C使∈f。根据复合关系的定义,由∈g和< y,z>∈f得∈g*f,即
∈fg。所以D
f

g
=A。
对任意的x∈A,若存在y
1
、y
2
∈C,使得< x,y
1
>、2
>∈fg=g*f,则存在t
1
使得1
>∈g且
1
, y
1
>∈f, 存在t
2
使得2
>∈g且2
,y
2< br>>∈f。因为g:A→B是函数,则t
1
=t
2
。又因f:B→C是< br>函数,则y
1
=y
2
。所以A中的每个元素对应C中惟一的元素。
综上可知,fg是A到C的函数。
(2)对任意的x∈A,由g:A→B是函数,有∈g且g(x)∈B,又由f:B→C是函数,得f(g(x))>∈f,于是 ∈g*f=fg。又因fg是A到C的函数,则可写为fg(x)=f(g(x) )。
八、(15分)设的子群,定义R={|a、b∈G且a1
*b∈H},则R是G中的

一个等价关系,且[a]
R
=a H。
证明 对于任意a∈G,必有a
1
∈G使得a
1
*a=e∈ H,所以∈R。
--
∈R,则a
1
*b∈H。因为 H是G的子群,故(a
1
*b)
1
=b
1
*a∈H。所以< b,a>∈R。
----
∈R,∈R,则a
1
*b ∈H,b
1
*c∈H。因为H是G的子群,所以(a
1
*b)*(b
1
*c)=a
----

1
*c∈H,故∈R。
综上可得,R是G中的一个等价关系。
对于任意的b∈[a]
R
,有∈R,a
1
*b∈H,则存在h∈H使得a
1
*b=h,b=a*h,于 是b∈aH,
--
[a]
R
aH。对任意的b∈aH,存在h∈H使得b= a*h,a
1
*b=h∈H,∈R

故aH[a]
R< br>。所以,[a]
R

=aH。



发到哪?给个邮箱啊~~~~~~~一、填空 20% (每小题2分)
1.设 (N:自然数集,E¬¬¬+ 正偶数) 则 。
2.A,B,C表示三个集合,文图中阴影部分的集合表达式为



3.设P,Q 的真值为0,R,S的真值为1,则
的真值= 。
4.公式 的主合取范式为

5.若解释I的论域D仅包含一个元素,则 在I下真值为

6.设A={1,2,3,4},A上关系图为






则 R2 = 。
7.设A={a,b,c,d},其上偏序关系R的哈斯图为





则 R= 。
8.图 的补图为 。
9.设A={a,b,c,d} ,A上二元运算如下:

* a b c d
a
b
c
d a b c d
b c d a
c d a b
d a b c
那么代数系统的幺元是 ,有逆元的元素为 ,它们的逆
元分别为 。
10.下图所示的偏序集中,是格的为 。





二、选择 20% (每小题 2分)
1、下列是真命题的有( )
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. ; D. 。
4、设R,S是集合A上的关系,则下列说法正确的是( )
A.若R,S 是自反的, 则 是自反的;
B.若R,S 是反自反的, 则 是反自反的;
C.若R,S 是对称的, 则 是对称的;
D.若R,S 是传递的, 则 是传递的。
5、设A={1,2,3,4},P(A)(A的幂集)上规定二元系如下
则P(A) R=( )
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) =
C.f : R I , f (x) = [x] ; D.f :I N, f (x) = | x | 。
(注:I—整数集,E—偶数集, N—自然数集,R—实数集)
8、图 中 从v1到v3长度为3 的通路有( )条。

A. 0; B. 1; C. 2; D. 3。
9、下图中既不是Eular图,也不是Hamilton图的图是( )

10、在一棵树中有7片树叶,3个3度结点,其余都是4度结点则该树有( )个4度
结点。
A.1; B.2; C.3; D.4 。

三、证明 26%
1、 R是集合X上的一个自反关系,求证:R是对称和传递的,当且仅当
< a, b> 和在R中有<.b , c>在R中。(8分)
2、 f和g都是群到< G2, *>的同态映射,证明的一个子群。
其中C= (8分)
3、 G= (|V| = v,|E|=e ) 是每一个面至少由k(k 3)条边围成的连通平面图,则 ,
由此证明彼得森图(Peterson)图是非平面图。(11分)

四、逻辑推演 16%
用CP规则证明下题(每小题 8分)
1、
2、

五、计算 18%
1、设集合A={a,b,c,d}上的关系R={
,< b , a > ,< b, c > , < c , d >}用矩阵运算
求出R的传递闭包t (R)。 (9分)

2、如下图所示的赋权图表示某七个城市 及预先算出它们之间的一些直接通信线路造价,
试给 出一个设计方案,使得各城市之间能够通信而且总造价最小。 (9分)

试卷一答案:
一、填空 20% (每小题2分)
1、{0,1,2,3,4,6}; 2、 ;3、1; 4、 ; 5、1;6、{<1,1>, <1,3>, <2,2>, <2,4> };
7、{,,,,} IA ;8、
9、a ;a , b , c ,d ;a , d , c , d ;10、c;
二、选择 20% (每小题 2分)
题目 1 2 3 4 5 6 7 8 9 10
答案 C D B、C C A D C A D B A



三、证明 26%
1、 证:
“ ” 若 由R对称性知 ,由R传递性得
“ ” 若 , 有 任意 ,因 若 所以R是对称的。
若 , 则 即R是传递的。
2、 证 ,有 ,又
★ ★
★ < C , ★> 是 < G1 , ★>的子群。
3、 证:
①设G有r个面,则 ,即 。而 故 即得 。(8分)
②彼得森图为 ,这样 不成立,






所以彼得森图非平面图。(3分)

二、 逻辑推演 16%
1、 证明:
① P(附加前提)
② T①I
③ P
④ T②③I
⑤ T④I
⑥ T⑤I
⑦ P
⑧ T⑥⑦I
⑨ CP
2、证明
① P(附加前提)
② US①
③ P
④ US③
⑤ T②④I
⑥ UG⑤
⑦ CP

三、 计算 18%
1、 解:


t (R)={
, , < a , c> , , , < b ,b > , < b , c . > ,
< b , d > , < c , d > }


2、 解: 用库斯克(Kruskal)算法求产生的最优树。算法略。结果如图:

树权C(T)=23+1+4+9+3+17=57即为总造价。



面给出证明:
(1) Some x is Y(x) P

(2) Y(c) (1)
T(1),ES


(3)Some(S(x)∧W(x))

(4)S(c)∧W(c)

(5)S(c) T(4),I

(6)S(c)∧Y(c)

(7)(Every)S((x)∧Y(x))




P
T(3),US
T(2)(5),I
T(6),EG



紫川录-最新游戏网名


心累了-封神演义作者


编辑图片大小-初心房间


商务英语高级-疑神疑鬼


教育在线论坛-海鲜疙瘩汤


如何提高英语听力-监督检查


秦俑-孤独的牧羊人歌词


欲盖弥彰什么意思-怎么填报高考志愿