离散数学期末考试试题.docx
《离散数学期末考试试题.docx》由会员分享，可在线阅读，更多相关《离散数学期末考试试题.docx（18页珍藏版）》请在冰点文库上搜索。
离散数学期末考试试题
离散数学试题（A卷及答案）
一、证明题（10分）
1）（-PA（—QAR））V（QAR）V（PAR）=R
证明：
左端=（-PA-QAR）V（（QVP）AR£（（—PA-Q）AR））V（（QVP）AR）
：
=（^PVQ）AR）V（（QVP）AR匕（一（PVQ）V（QVP））AR
：
=（「PVQ）V（PVQ））AfcTAR置换）：
=R
2）x（A（x）—.B（x））：
=-xA（x）_._xB（x）
证明：
x（A（x）>B（x）〉=x（f（x）VB（x））=x—A（x）VxB（x）=—-xA（x）VxB（x）=-xA（x）-lx
B（x）
、求命题公式（PV（QAR））>（PAQAR）的主析取范式和主合取范式（10分）
证明：
（PV（QAR））「（PAQAR>=—（PV（QAR））V（PAQAR））
二（—PA（一QV-R））V（PAQAR）
二（一PA—Q）V（-PA-R））V（PAQAR）
二（_PA_QR）V（_PA_QA一R）V（_PAQA_R））V（_PA_QA_R））V（PAQR）
二m0Vm1Vm2Vm7
uM3VM4VM5VM6
三、推理证明题（10分）
1）
CVD,
（CVD）》-E,-E>（AA-B）,（AA
证明
（1）xP（x）
—B）r（RVS）「：
RVS
（2）P（a）
证明：
（1）（CVD）—；「E
（3）-x（P（x）>Q（y）AR（x））
（2）-E>（AA-B）
（4）P（a）>Q（y）AR（a）
（3）（C
VD）—.（AA-B）
（5）Q（y）AR（a）
⑷（A
A-B）_.（RVS）
（6）Q（y）
（5）（C
VD）_（RVS）
（7）R（a）
⑹c
VD
（8）P（a）
⑺R
VS
（9）P（a）AR（a）
2）
-x（P（x）—；Q（y）AR（x））,xP（x）二Q（y）A
（10）x（P（x）AR（x））
x（P（x）AR（x））
（11）Q（y）Ax（P（x）AR（x））
四、设m是一个取定的正整数，证明：
在任取耐1个整数中，至少有两个整数，它们的差是m的整数倍证明设印,a2，…，am1为任取的1个整数，用m去除它们所得余数只能是0,1,…，m-1，由
抽屉原理可知，耳,a2，…，amd这m+1个整数中至少存在两个数as和at，它们被m除所得余数相
同，因此as和a的差是m的整数倍。
五、已知A、B、C是三个集合，证明A-（BUC）=（A-B）n（A-C）（15分）
证明•••x三A-（BUC）：
jx三AAxp（BUC）=xwAA（x^BAx^C）：
二（x三AAx^B）A（xwA
Ax「O=x-（A-B）Ax.（A-C）=x•（A-B）A（A-C）「・A-（BUC）=（A-B）A（A-C）
六、已知R、S是N上的关系，其定义如下：
R={|x,y三NAy=x},S={|x,y三NAy=x+1}。
求
R1、R*S、S*R、R{1,2}、S[{1,2}]（10分）
1222解：
R-={|x,yeNAy=x},R*S={|x,ywNAy=x+1},S*R={|x,yeNAy=（x+1）},
七、若f:
AtB和g:
BtC是双射，则（gf）-1=f-1g-1（10分）。
证明：
因为f、g是双射，所以gf:
Atc是双射，所以gf有逆函数（gf）-1:
Cta。
同理可推f-1g-1:
CtA是双射。
因为€f-1g：
=存在z（€g-1€f-1厂二存在z（€f€g）:
二€gf：
=€（gf）-1,所以（gf）-1=f-1g-1。
R{1,2}={<1,1>,<2,4>},S[{1,2}]={1,4}。
八、（15分）设是半群，对A中任意元a和b,女口b必有a*b^b*a,证明：
（1）对A中每个元a,有a*a=a。
（2）对A中任意元a和b,有a*b*a=a。
（3）对A中任意元a、b和c,有a*b*c=a*c。
证明由题意可知，若a*b=b*a,则必有a=b。
（1）由（a*a）*a=a*（a*a），所以a*a=a。
（2）由a*（a*b*a）=（a*a）*（b*a）=a*b*（a*a）=（a*b*a）*a,所以有a*b*a=a。
（3）由（a*c）*（a*b*c）=（a*c*a）*（b*c）=a*（b*c）=（a*b）*c=（a*b）*（c*a*c）=（a*b*c）*（a*c）,所以有a*b*c=a*co
九、给定简单无向图G=,且|V|=mIE=n。
试证：
若nA+2,贝VG是哈密尔顿图
证明若nAcm：
+2,贝V2n》ni-3mF6
（1）。
若存在两个不相邻结点u、v使得d（u）+d（v）vn,则有2n=送d（w）vmb（n—2）（n—3）+m=ni-3mF
w^V
6，与
（1）矛盾。
所以，对于G中任意两个不相邻结点u、v都有d（u）+d（v）An所以G是哈密尔顿
图。
离散数学试题（B卷及答案）
一、证明题（10分）
1）（（PVQ）A-（—PA（—QV-R）））V（—PA-Q）V（~PA—R）二T
证明左端二（（PVQ）A（PV（QAR）））V-（（PVQ）A（PVR））（摩根律）：
=（（PVQ）A（PVQ）A（PVR））V
—（（PVQ）A（PVR））（分配律）=（（PVQ）A（PVR））V_（（PVQ）A（PVR））（等幕律）=T（代入）
2）-x（P（x）>Q（x））A-xP（x）hx（P（x）AQ（x））
证明—x（P（x）>Q（x））A-xP（x）：
=-x（（P（x）>Q（x）AP（x））二-x（（~P（x）VQ（x）AP（x））：
二-x（P（x）A
Q（x））hxP（x）A-xQ（x）hx（P（x）AQ（x））
二、求命题公式（一P》Q）》（PV-Q）的主析取范式和主合取范式（10分）
解：
（一P>Q）>（PV-Q）=—（-P>Q）V（PV—Q）二—（PVQ）V（PV—Q）=（—PA—Q）V（PV—Q）=（—PVP
V-Q）A（—QVPV—Q）=（PV—Q）=MJm0Vm2Vm3
四、例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过1/8（10分）。
证明：
把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。
五、已知A、B、C是三个集合，证明An（BUC）=（AnB）U（AnC）（10分）
证明：
■/x三An（BUC）：
=x三AAx三（BUC）：
=x三AA（x三BVx三C）：
二（x三AAx三B）V（x三AAx三C）ux•（AnB）VAndx（AnB）U（AnC）.・.An（BUC）=（AnB）U（AnC）
六、-={A1,A2,…，An}是集合A的一个划分，定义R={＜a,b＞|a、b€A,I=1,2,…，n}，贝UR是A上的等
价关系（15分）。
证明：
-a€A必有i使得a€A,由定义知aRa,故R自反。
-a,b€A,若aRb，贝Ua,b€A,即卩b,a€A，所以bRa,故R对称。
_a,b,c€A,若aRb且bRc,则a,b€A及b,c€A。
因为i丰j时AnA="，故i=j，即a,b,c€A，所以aRc,故R传递。
总之R是A上的等价关系。
七、若f:
AtB是双射，则f1:
BtA是双射（15分）。
证明：
对任意的x€A,因为f是从A到B的函数，故存在y€B,使＜x,y＞€f,＜y,x＞€f-1。
所以,f-1是满射。
对任意的x€A,若存在y1,y2€B,使得＜y1,x＞€f-1且＜y2,x＞€f-1,则有＜x,y1＞€f且＜x,y2＞€f。
因为f是函数，则y1=y2。
所以，f-1是单射。
因此f-1是双射。
八、设＜G,*＞是群，＜A,*＞和＜B,*＞是＜G*＞的子群，证明：
若AUB=G,则A=G或B=G（10分）。
证明假设AmG且BmG则存在aAaB,且存在bB,b'A（否则对任意的aA,aB,从而A=B,即A
UB=B,得B=G矛盾。
）
对于元素a*b.二G,若a*b.二A因A是子群，a-1“，从而a-1*（a*b）=b.A,所以矛盾，故a*b.「A。
同理
可证a*bFB，综合有a*b.-'AUB=G
综上所述，假设不成立，得证A=G或B=G
九、若无向图G是不连通的，证明G的补图G是连通的（10分）。
证明设无向图G是不连通的，其k个连通分支为Gi、G2、…、Gk。
任取结点u、v€G,若u和v不在图G的同一个连通分支中，则［u,v］不是图G的边，因而［u,v］是图G的边；若u和v在图G的同一个连通分支中，不妨设其在连通分支Gi（1综上可知，不管那种情况，u和v都是可达的。
由u和
v的任意性可知，G是连通的。
一、选择题.（每小题2分，总计30）
1.给定语句如下：
（1）15是素数（质数）
（2）10能被2整除，3是偶数。
（3）你下午有会吗？
若无会，请到我这儿来！
（4）2x+3>0.
（5）只有4是偶数，3才能被2整除。
（6）明年5月1日是晴天。
以上6个语句中，是简单命题的为（A）,是复合命题的为（B）,是真命题的为（C）,是假命题的是（D）,
真值待定的命题是（E）
A:
①⑴（3）（4）（6）②
（1）（4）（6）③
（1）（6）B:
①⑵（4）②⑵（4）（6）③⑵（5）
C:
①
（1）
（2）（5）（6）②无真命题3（5）D:
①
（1）
（2）②无假命题③
（1）
（2）（4）（5）
E:
①⑷（6）笑（6）③无真值待定的命题
2.将下列语句符号化：
（1）4是偶数或是奇数。
（A）设p：
4是偶数，q:
4是奇数
（2）只有王荣努力学习，她才能取得好成绩。
（B）设p：
王荣努力学习，q:
王荣取得好成绩
（3）每列火车都比某些汽车快。
（C）设F（x）:
x是火车，G（y）:
y是汽车，H（x,y）:
x比y快。
A:
①pVq②pAq③pqB:
①pq②qp③pAq
C:
①-xy（（F（x）AG（y））（H（x,y））②-x（F（x）y（G（y）AH（x,y）））③-x（F（x）Ay（G（y）A
H（x,y）））
C:
⑤3⑥6⑦7⑧8D:
⑨⑴⑩①
二、证明（本大题共2小题，第1小题10分，第2小题10分，总计20分）
1、用等值演算算法证明等值式（pAq）V（p人一q）二p
2、构造下面命题推理的证明
如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。
三、计算（本大题共4小题，第1小题5分，第2小题10分，第3小题15分，总计30分）
1、设Px,y为x整除y,Qx为x:
:
2,个体域为'1,2?
，求公式：
-xyPx,y>Qx的真值。
2、设集合A31,2,3,4]A上的关系R」£1,1,1,2,2,1,2,3,3,4二求出它的自反闭包，对称闭包和传递
闭包。
3、设A=〈1,2,4,8,12,24,1上的整除关系R&1总「印耳•A®整除a^f,R是否为A上的偏序关系？
若是
则：
1、画出R的哈斯图；（10分）
2、求它的极小元，最大元，极大元，最大元。
（5分）
四、用推导法求公式p、q：
」・p的主析取范式和主合取范式。
（本大题10分）答案:
选择题
1.A:
③B:
③C:
③D:
①E:
②2.A:
①B:
②C:
②
、证明题
1.证明
左边=（（pAq）Vp）A（（pAq）V「q））
（分配律）
二pA（（pAq）V「q））（
吸收律）
二pA（（pV-q）A（qVr））
（分配律）
二pA（（pV-q）A1）
（排中律）
二pa（pvr）
（同一律）
二p
（吸收律）
2.解：
p：
今天是星期三。
q:
我有一次英语测验。
r
我有一次数学测验。
s:
数学老师有事。
前提:
L（qVr）,s
t-1r,pAs
结论：
q
证明：
①pAs
前提引入
②p
①化简
③p->（qVr）
前提引入
④qVr
②③假言推理
⑤s
①化简
⑥stf
前提引入
⑦
⑤⑥假言推理
⑧q
④⑦析取三段论
推理正确。
三、计算
-xyPx,y>Qx
r=yP1,y>Q1上P2,y>Q2
=P1,1>Q1上p2,1>Q2P1,2>Q1上P2,2>Q2
P1,1=1,P1,2=1,P2,1=0,P2,2=1,Q1=1,Q2=0
.二1》1上0》0打[[1>1讥[1>0
=1
该公式的真值是1，真命题。
—xyPx,y》Qx二-xPx,1）QxPx,2>Qx
或者=P1,1>Q1P1,2>Q1P2,1>Q2P2,2>Q2
T>TT>TF>FT>F
=TT]iTF：
=TT：
=T
2、r（R）二「1,1.,1,2,2,1,2,3,3,4,2,2,3,3,4,4：
?
s（R）—1,1,1,2,2,1,2,3.,3,4,3,2,4,3；?
3、
（1）R是A上的偏序关系。
t（R）—1,1,1,2,2,1,2,3,3,4,1,3,2,2,2,4,1,4./
（2）极小元、最小元是1,极大元、最大元是24。
四、
p）q）---pqp
-p_qP
-p
=pq_q
-p_qpq
二Z（2,3）
二主合取范式口（0，）
安徽大学2004-2005学年第二学期《离散数学》期末考试试卷（A卷）参考答案
一、单项选择
1在自然数集N上，下列哪种运算是可结合的？
（）
A.a*b=a-bB.a*b=max{a,b}
C.a*b=a2bD.a*b=ab（mod3）
2下列代数系统中，哪个是群？
（）
A.S二{0,1,3,5}，*是模7加法B.S二Q（有理数集合），*是一般乘法
A.｛ab^2|a,^Z｝，关于数的加法和乘法
B.｛n阶实数矩阵｝，关于矩阵的加法和乘法
A.有界格B.有补格C.分配格D.有补分配格
图1-1给出的哈斯图表示的格中哪个元素无补元？
（）
对运算的单位元是.
2在运算表2-1中空白处填入适当符号，使（｛a,b,c｝,）成为群。
①一，②一，③一“④一一。
3设H二｛0,4,8｝，:
:
H,12•是群：
:
：
N12,12的子群，其中
N12二｛0,1,2,…,11｝，12是模12加法，则＜N12,12■有
个真子群，H的左陪集3H二，4H二°
4设：
:
:
代，，一.是一个布尔代数，如果在A上定义二元运算二为:
a㊉b=（a严、b）（aab），则c代㊉a是一个。
表2-1
5任何一个具有2n个元素的有限布尔代数都是_。
6若连通平面图G有4个结点，3个面，则G有条边。
7一棵树有两个结点度数为2，一个结点度数为3,三个结点度数为4,它有个度数为
8无向图G是由k（k_2）棵数组成的森林，至少要添加条边才能使G成为一棵树。
三、求解题（20分）
1的结点。
1试写出:
:
N6,6冲每个子群及其相应的左陪集。
（6分）
2若一个有向图G是欧拉图，它是否一定是强连通的？
若一个有向图明理由。
（6分）
3有向图G如图3-1所示。
是欧拉图？
说
（1）求G的邻接矩阵A；
（2分）
（2）
G中v1到v4长度为
4的路径有几条？
（2分）
（3）
G中V1到自身长度为
3的回路有几条？
（2分）
（4）G是哪类连通图？
（2分）
G是强连通的，它是否
图3-1
四、证明题（30分）
1设:
G,*•是一群，G。
定义：
a^a*x*b,-a,b・G。
证明:
:
G/也是一群。
2证明：
（1）证明在格中成立：
（a*b）二（c*d）_（a二c）*（b二d）。
（5分）
（2）证明布尔恒等式：
（a*c）二（a*b）二（b*c）=（a*c）二（a，*b）。
（5分）
3证明：
（1）在6个结点12条边的连通平面简单图中，每个面由3条边围成。
（5分）
（2）证明当每个结点的度数大于等于3时，不存在有7条边的简单连通平面图。
安徽大学2004-2005学年第二学期《离散数学》期末考试试卷（A卷）参考答案
、单项选择
1.B;2.D;3.A;4.C;5.A;6.C;7.B;8.D;9.B;10.C.二、填空题
1：
：
」，S,S；2c,b,b,a;35,{3,7,11},{4,8,0}；4交换群；
5同构；65;79;8k—1。
三、求解题
1解：
子群有：
：
｛0｝,6,：
：
｛0亀6,：
：
｛0,2,4｝,6。
:
：
{0},6的左陪集为：
{0},{1},{2},{3},{4},{5}
:
{0,3},6的左陪集为：
{0,3},{1,4},{2,5}
:
:
:
{0,2,4},6•的左陪集为:
{0,2,4},{1,3,5}
2答：
（1）一个有向欧拉图一定是强连通图。
因为G是欧拉图，存在欧拉回路C,G中的每个结点至少在C中
（2）—个强连通图不一定是有
出现一次。
因而G中任意两点u，v都在C中，相互可达，故G是强连通的。
向欧拉图。
因为强连通图中每个结点的入度不一定等于其出度。
3解：
（4）G是单向连通图。
四、证明题
1证明：
显然•是G上的二元运算（即满足封闭性），要证G是群，需证结合律成立，同时有单位元，每个元素有逆元。
-a,b,cG，有
（ab）c=（a*x*b）*x*c=a*x*（b*x*c）=a（bc）运算是可结合的。
其次，x」是：
:
:
G/的单位元。
事实上，—a-G，有
144」
ax二a*x*x二a；xa二x*x*a=a
最后证明，-a・G，x」*a'*x'是a在：
:
:
G/中的逆元。
事实上,
斗斗*.4比-4-4
a（x*a*x）=a*x*x*a*xx
（x*a*x）a=x*a*x*x*a=x由以上证明，:
：
G/是群。
2证明：
（1）（a*b）=（c*d）_（（a*b）=c）*（（a*b）=d）（公式（13）分配不等式）
又因为a*b^a，a*b_b，所以（a*b）二（c*d）乞（a二c）*（b二d）。
（2）因为a二a、1,1*（b*c）=（b*c），所以有，
（a*c）二（a*b）二（b*c）=（a*c）二（a*b）二（（a二a）*（b*c））
-（a*c）二（a*b）二（（a4*b*c）二（a*b*c”
V1
-（（a*c）二（a*c*b））二（（a*b）二（a*b*c））（吸收律）
=（a*c）二（a*b）
即等式成立。
3证明：
（1）因图中结点数和边数分别为n=6,m=12，根据欧拉公式n_m・k=2，得k=8。
又
、deg（vj=2m=24，而简单连通平面图的每个面至少由3条边围成，所以在6个结点12条边的连通平面简
单图中，每个面由3条边围成。
（2）设（n,m）图为简单连通平面图，有k个面。
（反证法）
214
若m=7，由欧拉公式知n•k=m•2=9，而每个面至少由3条边围成，有3k乞2m，则km
33
214
且k是整数，所以k_4；又对任结点vV，deg（v）_3，有3n_2m，故n<-^14，且n是整数，所
33
以n岂4。
这样就有n岂4・4=8，与n二9矛盾，所以结论正确。
安徽大学2007—2008学年第2学期
《离散数学（下）》考试试卷（A卷）
一、单项选择题（每小题2分，共20分）
1.下列集合关于数的加法和乘法运算不能构成环的是（）
A.自然数集合；B.整数集合；C.有理数集合；D.实数集合。
2.设I为整数集合，则下列集合关于数的加法运算不能构成独异点的是（）
A.I；B.{2k|k1}；C.{2k1|k1}；d.{3m5n|m,n1}。
3.设N
升级会员 