离散数学期末考试试题(有几套带答案)

失散试卷及答案失散数学试题(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))∧RT∧R(置换)R2)x（A(x)B（x))xA（x)xB(x）证明：x（A（x）B(x））x(A(x)∨B（x）)xA(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∨m7M3∨M4∨M5∨M6三、推理证明题（10分）1）C∨D,（C∨D）E,E(A∧B),(A∧B)(R∨S）R（2)E（A∧B)∨S（3)(C∨D）（A∧B)证明：（1)(C∨D）E（4）（A∧B）（R∨S)第1页共18页失散试卷及答案（4）P（a)Q（y）∧R(a）(5)(C∨D)（R∨S)6)C∨D7）R∨Sx（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）)

5）Q(y）∧R(a)(6）Q（y）(7)R（a)8）P(a）(9）P（a）∧R(a)x(P(x）∧R(x）)（11)Q(y)∧x(P（x）∧R（x））四、设m是一个取定的正整数,证明：在任取m＋1个整数中,最少有两个整数，它们的差是m的整数倍证明设，，，为任取的m＋1个整数，用m去除它们所得余数只能是0，1，，m－1,由抽屉原理可知，，,，这m＋1个整数中最少存在两个数和，它们被m除所得余数相同，所以和的差是m的整数倍。五、已知A、B、C是三个会集，证明A-（B∪C)=（A-B)∩（A—C）（15分）证明∵xA-（B∪C）xA∧x（B∪C）xA∧(xB∧xC）（xA∧xB）∧(xA∧xC）x(A-B)∧x（A—C)x（A-B）∩（A—C）∴A-（B∪C）=(A—B）∩(A—C）六、已知R、S是N上的关系,其定义以下：R=｛〈x，y〉｜x,yN∧y=x2}，S=｛<x,y>｜x,yN∧y=x+1｝。求R—1、R*S、S＊R、R{1，2｝、S[｛1,2}］（10分）解：R-1=｛〈y,x>｜x,yN∧y=x2｝，R＊S=｛〈x,y>｜x，yN∧y=x2+1},S*R=｛〈x，y〉|x,yN∧y=（x+1）2}，第2页共18页失散试卷及答案七、若f：A→B和g:B→C是双射，则（gf)-1=f-1g—1（10分).证明:因为f、g是双射,所以gf:A→C是双射，所以gf有逆函数(gf）-1：C→A。同理可推f-1g—1：C→A是双射。因为<x，y〉∈f-1-1-1g存在z（<x,z〉∈g（〈y,z〉∈f<z，x>∈g)〈y,x〉∈gf<x,y

〈z，y〉∈f—1）存在z〉∈(gf）—1,所以（gf）—1=f-1g—1.R｛1，2｝=｛<1，1〉,<2,4>}，S[｛1,2}]=｛1，4｝。八、（15分）设<A,＊>是半群,对A中任意元a和b，如a≠b必有a＊b≠b＊a，证明：(1）对A中每个元a，有a＊a＝a。（2）对A中任意元a和b，有a*b＊a＝a.对A中任意元a、b和c，有a*b＊c＝a＊c。证明由题意可知，若a＊b＝b*a，则必有a＝b。由（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*c。九、给定简单无向图G＝<V，E>,且|V｜＝m,|E|＝n。试证:若n≥＋2，则G是哈密尔顿图2证明若n≥＋2，则2n≥m－3m＋6(1）.若存在两个不相邻结点、使得d()＋d（)＜m，则有2n＝＜m＋（m－2）（m2矛盾。所以，关于G中任意两个不相邻结点、－3)＋m＝m－3m＋6，与（1)都有d()＋d(）≥m,所以G是哈密尔顿图。第3页共18页失散试卷及答案失散数学试题（B卷及答案）一、证明题（10分）1)（(P∨Q）∧(P∧(Q∨R）))∨(P∧Q)∨（P∧R）T证明左端（（P∨Q）∧（P∨(Q∧R))）∨（(P∨Q)∧(P∨R))(摩根律)((P∨Q）∧（P∨Q）∧（P∨R））∨(（P∨Q）∧（P∨R)）（分配律）(（P∨Q）∧(P∨R）)∨（（P∨Q)∧(P∨R))(等幂律)T（代入）2)x（P(x)Q(x））∧xP（x）x（P（x）∧Q(x))证明x(P（x）Q(x）)∧xP（x)x（（P（x）Q（x）∧P（x))x（(P（x）∨Q(x)∧P(x）)x(P（x）∧Q(x）)xP（x）∧xQ（x)xP(x）∧Q（x))二、求命题公式(PQ）(P∨Q)的主析取范式和主合取范式（10分）解:(PQ)(P∨Q)(PQ)∨(P∨Q）（P∨Q)∨(P∨Q）（P∧Q）∨（P∨Q）（P∨P∨Q)∧（Q∨P∨Q）(P∨Q）M1m0∨m2∨m3三、推理证明题（10分）1）(P（QS)）∧(R∨P)∧T(3)(4），IQRS（6)QP证明：（1）R附加前提（7）ST(2）R∨PP（5)(6)，I(3）PT(1）(2），（8）RSCPI2)x(P（x)∨Q(x））,xP(x）(4)P(QS)PxQ（x）(5)QS证明:(1)xP（x）P第4页共18页失散试卷及答案（2)P(c）TT（2)(4)，I（1)，US(6）xQ（x）(3）x（P（x)∨Q（x）)PT(5),EG(4）P（c)∨Q（c）T（3)，US（5）Q(c）四、例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形(可能是退化的）面积不高出1/8（10分）.证明：把边长为1的正方形分成四个全等的小正方形，则最少有一个小正方形内有三个点,它们组成的三角形（可能是退化的)面积不高出小正方形的一半，即1/8.五、已知A、B、C是三个会集，证明A∩（B∪C）=(A∩B）∪(A∩C)（10分）证明：∵xA∩（B∪C）xA∧x（B∪C)xA∧(xB∨xC）（xA∧xB）∨（xA∧xC）x（A∩B）∨xA∩Cx（A∩B）∪（AC）∴A∩（B∪C)=（A∩B)∪（A∩C）六、={A1，A2，，An｝是会集A的一个划分，定义R=｛〈a,b>｜a、b∈Ai，I=1，2，，n}，则R是A上的等价关系(15分）。证明：a∈A必有i使得a∈Ai，由定义知aRa,故R自反。a，b∈A,若aRb,则a，b∈Ai，即b,a∈Ai，所以bRa,故R对称。a，b，c∈A,若aRb且bRc,则a，b∈Ai及b,c∈Aj.因为i≠j时Ai∩Aj=，故i=j,即a，b,c∈Ai，所以aRc，故R传达.总之R是A上的等价关系。七、若f：A→B是双射,则f—1：B→A是双射（15分)。证明：对任意的x∈A,因为f是从A到B的函数，故存在y∈B,使<x，y>∈f，第5页共18页失散试卷及答案<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,*>的子群，证明：若A∪B＝G，则A＝G或B＝G（10分）.证明假设A≠G且B≠G，则存在aA，aB，且存在bB,bA(否则对任意的aA，aB，从而AB，即A∪B＝B，得B＝G，矛盾.）关于元素a＊bG,若a*bA，因A是子群,a-1A，从而a—1＊（a＊b）＝bA，所以矛盾，故a*bA。同理可证a＊bB,综合有a*bA∪B＝G。综上所述，假设不成立，得证A＝G或B＝G。九、若无向图G是不连通的，证明证明设无向图G是不连通的，其若和不在图G的同一个连通分支中若和在图G的同一个连通分支中，的另一连通分支上取一结点，则[,]都是的边.综上可知,无论那种情况通的.

G的补图是连通的(10分）。个连通分支为、、、。任取结点、∈G,则［，］不是图G的边,所以［，]是图的边；不如设其在连通分支（1≤≤）中,在不相同于和［,]都不是图G的边，,所以［，]和［，］和都是可达的。由和的任意性可知，是连一、选择题。(每题2分,总计30）给定语句以下：(1)15是素数（质数）2）10能被2整除，3是偶数。3）你下午有会吗？若无会，请到我这儿来!4）2x+3〉0.第6页共18页失散试卷及答案5）只有4是偶数，3才能被2整除。6）明年5月1日是晴天.以上6个语句中，是简单命题的为（A）,是复合命题的为(B）,是真命题的为（C），是假命题的是(D),真值待定的命题是（E）A:①(1）(3）（4)（6）②(1）(4)(6）③(1)（6）B：①（2）（4)②（2）（4)（6）③（2)（5）C:①(1）(2)(5)（6）②无真命题③（5）D:①(1）（2）②无假命题③（1)(2）(4）（5）E：①(4)（6)②（6）③无真值待定的命题将以下语句符号化：1)4是偶数或是奇数。（A）设p：4是偶数，q：4是奇数2）只有王荣努力学习，她才能获取好成绩。（B）设p：王荣努力学习,q：王荣获取好成绩3）每列火车都比某些汽车快。（C）设F（x)：x是火车,G(y)：y是汽车，Hx，y）:x比y快。A：①p∨q②p∧q③p→qB:①p→q②q→p③p∧qC：①x＄y（(F（x)∧G（y））→（H（x,y)）②x(F（x）→＄y(G（y)∧H(x,y）)）③x（F(x）∧y(G(y)∧H（x,y）))设S={1，2，3},以下列图给出了S上的5个关系,则它们只拥有以下性质：R1是(A）,R2是（B）,R3是（C）。ABC:①自反的，对称的，传达的②反自反的，对称的③自反的反对称的⑤对称的⑥自反的，对称的，反对称的，传达的第7页共18页失散试卷及答案4.设S=｛Ф，{1},｛1，2}},则有（1）(A）S（2）（B)S(3)P（S）有（C）个元数。（4）（D）既是S的元素，又是S的子集A：①｛1，2}②1B：③｛{1，2｝}④{1｝C：⑤3⑥6⑦7⑧8D:⑨{1｝⑩Ф二、证明(本大题共2小题，第1小题10分，第2小题10分，总计20分）1、用等值演算算法证明等值式（p∧q）∨(p∧q)p2、构造下面命题推理的证明若是今天是星期三，那么我有一次英语或数学测试；若是数学老师有事，那么没有数学测试；今天是星期三且数学老师有事，所以我有一次英语测试。三、计算（本大题共4小题，第1小题5分，第2小题10分,第3小题15分,总计30分）1、设，求公式：的真值。2、设会集上的关系,求出它的自反闭包，对称闭包和传达闭包.3、设上的整除关系，可否为上的偏序关系？若是，则：1、画出的哈斯图;(10分）2、求它的极小元,最大元，极大元，最大元。（5分)四、用推导法求公式的主析取范式和主合取范式.（本大题10分）答案：一、选择题1.A:③B:③C:③D:①E：②2。A:①B：②C：②3.A：③B:④C：⑥4。A：①B：③C：⑧D:⑩第8页共18页失散试卷及答案二、证明题1.证明左边（(p∧q）∨p）∧（（p∧q)∨q)）（分配律）p∧（(p∧q）∨q))(吸取律）p∧（(p∨q）∧(q∨q)）（分配律）p∧(（p∨q)∧1)（排中律）p∧(p∨q）（同一律）p（吸取律)解：p:今天是星期三。：我有一次英语测试。：我有一次数学测试.数学老师有事。前提：p(q∨r)，sr，p∧s结论：q证明:①p∧s前提引入②p①化简③p（q∨r）前提引入④q∨r②③假言推理⑤s①化简⑥sr前提引入⑦r⑤⑥假言推理⑧q④⑦析取三段论推理正确。三、计算第9页共18页失散试卷及答案1。该公式的真值是1，真命题.也许2、3、（1）是上的偏序关系。（2)极小元、最小元是1,极大元、最大元是24.四、安徽大学2004-2005学年第二学期《失散数学》期末考试一试卷（A卷）参照答案一、单项选择1在自然数集上，以下哪一种运算是可结合的？（）A.B。C。D。2以下代数系统〈，＊>中,哪个是群？（）A。，*是模7加法B.（有理数会集），＊是一般乘法C。（整数会集）,＊是一般减法D.，*是模11乘法3若〈，*>是<，＊〉的真子群，且，,则有（）.A.整除B。整除C.整除且整除D.不整除且不整除4下面哪个会集关于指定的运算组成环？(）A。,关于数的加法和乘法阶实数矩阵，关于矩阵的加法和乘法aC.，关于数的加法和乘法bdecg第10页共18页f失散试卷及答案，关于矩阵的加法和乘法5在代数系统中，整环和域的关系为（）。A.域必然是整环B。域不用然是整环C。整环必然是域D.域必然不是整环6是自然数集,是小于等于关系，则是（）。A.有界格B.有补格C.分配格D。有补分配格7图1-1给出的哈斯图表示的格中哪个元素无补元？（）A。B.C。D.图1-18给定以下序列，可组成无向简单图的结点度数序列的是（）。A。（1，1，2,2，3)B。(1,3，4，4，5)C。（0，1，3，3，3）D.（1，1，2，2,2)9欧拉回路是（）.A。路径B.简单回路C。既是基本回路也是简单回路D.既非基本回路也非简单回路10哈密尔顿回路是（）.A。路径B。简单回路C.既是基本回路也是简单回路D.既非基本回路也非简单回路二、填空题（以下每个下划线为一空,请按要求填入合适的内容。每空2分，共30分).1设是非空有限集，代数系统中，对运算的单位元是＿＿＿＿，零元是＿＿＿＿，对运算的单位元是＿＿＿＿。2在运算表2-1中空白处填入合适符号，使成为群。①＿＿＿＿，②＿＿＿＿，③＿＿＿＿，④＿＿＿＿。

abca①a②babcc③c④第11页共18页失散试卷及答案设，是群的子群,其中，是模12加法，则有＿＿＿＿个真子群,的左陪集＿＿＿＿，＿＿＿＿。设是一个布尔代数，若是在上定义二元运算为:，则是一个＿＿＿＿。表2-1任何一个拥有个元素的有限布尔代数都是＿＿＿＿。若连通平面图有4个结点，3个面，则有＿＿＿＿条边。一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，它有＿＿＿＿个度数为1的结点。无向图是由（）棵数组成的森林，最少要增加＿＿＿＿条边才能使成为一棵树。三、求解题(20分)1试写出中每个子群及其相应的左陪集。（6分）若一个有向图是欧拉图，它可否必然是强连通的？若一个有向图是强连通1的，它可否必然是欧拉图?说明原由。（6分）有向图如图3—1所示。（1)求的毗邻矩阵；（2分）