天津理工大学离散数学(魏雪丽版)检测题目解析

天津理工大学《离散数学》第一章检测题答案一、填空题（每空2分，共30分）1.PfQ2.「PfQ 3•二，v，?，(),v，1,J,—t。4(-1P△Q△-1R)v(P△―।Q△―।R)v(P△―।Q△R),(PvQvR)△(PvQv「R)△(Pv「Qv「R)△(「Pv「QvR)△(「Pv「Qv「R)5.(」PfQ)△(Pf(RvS))6.「Qf「P7.(P△[Q)v(Q△[P)二、单项选择题（每小题2分，共20分）12345678910得分DBCBCDAACB三、简答题（每小题6分，共12分）1.构造命题公式Pv（QfR）的真值表.0001100111010000111110011101111100111111PQRQfRPv(QfR)2.求命题公式((PvQ)fR)fP的主析取范式和主合取范式。((PvQ)fR)fPo」(」(PvQ)vR)vP(1分)o((PvQ)△[R)vP(1分)o(PlR)v(QlR)vPoPv(QlR)

o(P△(Qv「Q)△(Rv[R))v((Pv「P)△(Q△[R))(1分)o(P△Q△R)v(P△[Q△R)v(P△Q△[R)v(P△[Q△[R)v(P△Q△「R)v(「P△Q△「R)(1分)o(P△Q△R)v(P△[Q△R)v(P△Q△[R)v(P△[Q△[R)v(「P△Q△[R)omvmvmvmvm(这是主析取范式))(1分)2 4 5 6 7oM△MAM(这是主合取范式)o(PvQvR)a(PvQv「R)a(Pv「Qv「R)(1分)3.判断命题公式(PTQ)A(PTR)与(PTQAR)是否等价。解：A=(PTQ)A(PTR)o(「PvQ)A(「PvR)B=PT(QaR)o「Pv(QaR)o(「PvQ)a(「PvR)等价.证明题（共32分）1.(10分)用CP规则证明「Pv(「QvR),Qt(RtS),PnQtS；P「PvP「Pv(「QvR)「QvRQQT(RTS)PPT(1,2)I(2分)P(附加前提)P(RtS)RS(QtS)T(4,5)I(2分)T(3,4)I(2分)T(6,7)I(2分)CP(2分)2.（10分）用归谬法证明At「B,（「CvB）,Ca「Sn^A.证：1AP（附加前提）（1分）2AT「BP3「BTI (2分)1,24—।CvBP5「CTI (2分)3,46CA「SP7CTI (2分)68CA「CTI(25,7

分)由8得出了矛盾，根据归谬法说明原推理正确(1分)3．(12分)公安人员审理某珠宝商店的钻石项链的失窃案，已知侦察结果如下：(1)营业员A或B盗窃了钻石项链(2)若B作案，则作案时间不在营业时间(3)若A提供的证词正确，则货柜未上锁(4)若A提供的证词不正确，则作案发生在营业时间(5)货柜上了锁试问：作案者是谁？要求写出推理过程。解:令A表示〃营业员A盗窃了钻石项链”；B表示〃营业员B盗窃了钻石项链”；P表示“作案时间在营业时间”；Q表示“A提供的证词正确”；R表示“货柜上了锁”。则侦察结果如下：AvB，Bf「P，Qf「R，「QfP，R.由此可推出作案者是A(4分)推理过程如下：R P (6) Bf「PPQf「R P (7) 「BT⑸，(6) I(2分)「Q T⑴，(2)I(2分)(8)AvB P(9)A(9)AT(7)，(8)I(2分)(5)P(5)PT⑶，(4)I(2分)天津理工大学《离散数学》第二章检测题答案一、填空题(每空3分，共30分).(Vx)(G(x)fF(x))△["x)(F(x)fG(x))或(Vx)(G(x)fF(x))△(3y)(F(y)△[G(y)).(Vx)(3z)(3w)[(「P(x)v「R(x,w))△(「Q(z,y)v「R(x,w))].P(a)△P(b)△P(c)△(Q(a)vQ(b)vQ(c)).(「P(a)△「P(b)△[P(c))v(P(a)△P(b)△P(c)) 5.「P(x),(Vx)(3y)「P(x,y)6.(x,y；y)7.(P(x)v3yR(x,y)) 8.(3x)(「F(x)v「G(x))三、简答题(每小题6分，共12分).求需词公式(Vx)(P(x)fQ(x,y))f((3y)P(y)△(3z)Q(y,z))的前束析取范式.(Vx)(P(x)fQ(x,y))f((3y)P(y)△(3z)Q(y,z))o「(Vx)(「P(x)vQ(x,y))v((3y)P(y)△(3z)Q(y,z))o3x(P(x)△「Q(x,y))v((3y)P(y)△(3z)Q(y,z))o3x(P(x)△「Q(x,y))v((3u)P(u)△(3z)Q(y,z))o(3x)(3u)(3z)[(P(x)△「Q(x,y))v(P(u)△Q(y,z))],证明：3x(P(x)fQ(x))oVxP(x)f3xQ(x)

证：左式二3x(P(x)fQ(x))o3x「P(x)vQ(x))o3x(—iP(x))v3xQ(x)n—iVxP(x)v3xQ(x)oVxP(x)f3xQ(x))．证明题（共38分）1．（12分）用谓词演算的推理规则证明:Vx(P(x)fQ(x)),Vx(Q(x)△R(x)fS(x))，P(a)△R(a)nS(a)(1)Vx(P(x)fQ(x))P(2)P(a)fQ(a)US(1)(2分)(3)P(a)△R(a)P(4)Q(a)T(2)(3)I(2分)(5)Vx(Q(x)△R(x)fS(x))P(6)Q(a)△R(a)fS(a)US(5)(2分)(7)R(a)T(3)I(2分)(8)Q(a)△R(a)T(4)(7)I(2分)(9)S(a)T(6)(8)I(2分)2．（10分）指出下面推理证明过程中的错误，并给出正确的证明．用谓词演算的推理规则证明：Vx(Q(x)fR(x))△3x(Q(x)△Z(x))n3x(R(x)△Z(x))证:：（1）Vx(Q(x)fR(x))P(6)Z(a)T(4)I(2)Q(a)fR(a)US(1)(7)R(a)T(2),(5)I(3)3x(Q(x)△Z(x))P(8)R(a)△Z(a)T(6),(7)I(4)Q(a)△Z(a)ES(3)(9)3x(R(x)△Z(x))EG(8)(5)Q(a) T(4)I该证明的错误在于:(1)、(2)与(3)、(4)的顺序颠倒了，应该先指定存在后指定全称。(2分)正确的证明是：(4分)(1)3x(Q(x)aZ(x)) P (6)Z(a) T(2)I(1分)⑵Q(a)aZ(a) ES(1)(2分)(7)R(a) T(4),(5)I(1分)⑶Vx(Q(x)-R(x))P (8)R(a)aZ(a) T(6),(7)I(1分)Q(a)fR(a)US(3)(2分)(9)3x(R(x)aZ(x)) EG(8) (1分)Q(a) T(2)I3．(16分)符号化下列命题并推证其结论．任何人如果他喜欢音乐,他就不喜欢体育．每个人或者喜欢体育，或者喜欢美术.有的人不喜欢美术.因而有的人不喜欢音乐.(设M(x)：x喜欢音乐，S(x)：x喜欢体育，A(x):x喜欢美术.)该推理符号化为：(Vx(M(x)f「S(x))aVx(S(x)vA(x))a3xY(x))n(3x「M(x))或前提：Vx(M(x)f「S(x)),Vx(S(x)vA(x)),3xY(x)结论：3x「M(x) (4分)证：(1)3xY(x) P (2)Y(a) ES(1)(2分)(3)Vx(S(x)vA(x)) P (4)S(a)vA(a) US(3)(2分)(5)S(a) T(2)(4)I(2分)(6)Vx(M(x)f「S(x)) P(7)M(a)f「S(a) US(6)(2分)(8)S(a)f「M(a)T(7)E(1分)

(9)「M(a) T(5)(8)I(2分)(10)3x「M(x)EG(9)(1分)天津理工大学《离散数学》第三、四章检测题答案{①,{{a,{b,c}}}{①,{{a,{b,c}}}}nx2n2.{{①，{①}},①),{①，{①}}，{①})3.4.反对称，传递。5.RR-14.反对称，传递。5.RR-1；8 一Ri6.IA，或单位矩阵7．4,6， 2,3 ，无i=1U128.f1=9O,潜}」；},f2={砂,1"{叫,0)}。9．单射，满射；既是单射又是满射；I；IBA二、单项选择题（每小题2分，共20分）12345678910得分(1)(2)(1)(3)(2)(2)(1)(3)(3)(1)三、简答题（共30分）1.（6分）设A={1,2,356,10,15.30}, “/”为集合A上的整除关系。〈A，/〉是否为偏序集?若是，画出其哈斯图；解：〈A，/〉是偏序集。其哈斯图为：解：〈A，/〉是偏序集。其哈斯图为：（12分）对下图所给的偏序集,;AV,求下表所列集合的上（下）界，上（下）确界，并将结果填入表中。子集上界下界上确界下确界{a,b,c}adad{c,d,e}a,c无c无Aa无a无（6分）设A={1,2,3,456},集合A上的关系R={〈1,3〉,〈1,5〉,〈2,5〉,〈4,4〉,〈4,5〉,〈5,4〉,〈6,3〉,〈6,6〉}。（1）画出R的关系图，并求它的关系矩阵；(2)求r(R),S(R)及t(R)。解：（1）R的关系图为R的关系矩阵为「0010101解：（1）R的关系图为R的关系矩阵为「00101010000100000000110(2分)00100(2)r(R=R{1,1；,；2,2，;3,3，：5,5:},(1分)S(R)=欣{3,1泊5,1,;5,2*36} (1分)t(R)=R{1,4,24,55；} (2分)4.设Z是整数集,R是Z上的模3同余关系，即R={X,y)|^,yeZ,X三y(mod3)},试根据等价关系R决定Z的一个划分。答案：由R决定的Z的划分为：M,H,U}， 其中：RRR0r={…,—9,-6,—3,036,9,…}1『={…,-8,-5,-2,1,4,7，…}国={…,-7,-4,-1,2,5,8，…}R．证明题（共10分）1.设a,beR,a<b,定义f：[a,b]f[0,1]为f(x)==a，证明：f是双射，并求出b—a其逆映射。证：1）先证明f是入射（2分）对任意的x,xe[,bl若f（x）=f（x）则有S__a=X2a，从而有x=x12 1 2b—a b—a 1 2故f是入射。2）再证明f是满射（2分）对任意的yehll都存在X=（b-a）y+aela,b1使得f（x）=y,从而f是满射。综合（1、（2）知f是双射。f-i：[0,1]f[a,b]为f-i(x)=(b-a)x+a，对任意xeQ1」。(1分)天津理工大学《离散数学》第五章检测题答案一、填空题（每空2分，共30分）1.b-1*a-12.a3.中,S,S,①4.a;15.S关于十运算不封闭6-2，a-1=4—a7循环群，生成元8.9.B关于*封闭1.设*是实数集R上的二元运算，其定义如下：a*b=a+b+2ab（1）求2*3，3*（-5）和7*1/2。（2）；R,*是半群吗？*可交换吗？（3）求R中关于*的单位元。（4）R中哪些元素有逆元素，其逆元素是什么？答案：（1）17,-32,14.5。2）产*是半群，*可交换。（3）0。(4)当aeR,aw—1/2时，a有逆元素，a-1=-a/(1+2a)。2.设A={a,b,c,d},M,*：,是交换群，a是,；A*：的单位元。*的运算表如下:TOC\o"1-5"\h\z* a b c da a b c db b a x xb 1 2求X,X,X,X,X,X，并说明道理。123456答案：x=d,x=c,x=b,x=d,x=c,x=b。因为有限群的运算表中的每行、每列都123456是群中元素的一个置换。3.设集合G={1,3,4,5,9},*是定义在G上的模11乘法(即任意a,beG,有a*b=(axb)(modll),x是普通乘法)，问;G,*是循环群吗？若是，试找出它的生成元。答：：G,*的运算表如下表所示。从运算表可知，*在G上封闭、有幺元1,且1二35,3二31,4二34,5二33,9二32,再由*是可结合的得;G,*是循环群，3,4,5和9均为其生成元。．证明题(共20分).(4分)设,;G*；是独异点，e为其幺元，且对vaeG，有a*a=e，证明G*是一个交换群。证明：对vaeG，由于a*a=e，则a-1=a,即G中的每一个元素a都有逆元素，故:G,*是一个群。又对va,beG，有a*b=a-i*b-i=(b*a)-1=b*a,所以;G,*)是一个Abel群。.(6分)设,;G*)是一个群，aeG,f:GfG,VxeG，有f(x)=a*x*a-i试证明f是;6*：一个自同构.证：首先证明f是入射。(3分)对Vx,xeG,若f(x)=f(x),则有a*x*a-i=a*x*a-1,12 1 2 1 2该式两边同时左乘a-1及右乘a,得x=x,故f为入射f.12其次证明f是满射。对VyeG,都存在x=a-1*y*aeG,使得y=f(x),因止匕f是满射.综合以上两点，知f是双射。(3分)最后,对Vx,xe6,都有f(x*x)=a*x*x*a-1=(a*x*a-1)*(a*x*a-1)12 1 2 1 2 1 2=f(x)*f(x),从而f是G到6的自同构.12天津理工大学《离散数学》第六章检测题答案一、填空题(每空2分，共40分)1.上确界和下确界，a,b2,至少有一个补元素，不一定 3,0,1；1,2n三、简答题（共30分）4.ava=1,aaa=05.aab;avb2n三、简答题（共30分）4.ava=1,aaa=05.aab;avb6. |A|IAn,|A|1.下面哈斯图表示的格中哪个元素无补元？对有补元的元素求出它们的补元.解：c无补元（1分），a的补元为e（1分），b的补元为d（1分），d的补元为b、分），e的补元为a、d（1分），0与1互为补元。（1分）2.设：B,v,a1,0J,是一个布尔代数且5={0,a,b,1},求布尔表达式f(x,x,x)=(a△x△x)v(x△(xvb))12312 1 3的析取范式和合取范式并计算f（b,1,a）的值。解：f（xi，x2，々）的析取范式为:(xaxax)v(xaxax)v(xaxax)v(baxaxax)(4分)123 123 123123f（A"2，々）的合取范式为：(xvxvx)△(xvxvx)△(xvxvx)△(xvxvx)△(bvxvxvx)123 123 123 12312（4分）f(b,1,a)=b(2分)3.设3.设A={1,2,3,5,6,10,15,30},“/”为集合A上的整除关系。⑴.〈A，/〉是否为偏序集?若是，画出其哈斯图；30⑵.〈⑴.〈A，/〉是否为偏序集?若是，画出其哈斯图；30⑵.〈A，/〉是否构成格？为什么？⑶.〈A，/〉是否构成布尔代数？为什么？解：（1）.〈A，/〉是偏序集。其哈斯图为：6⑵.〈A，/〉构成格。因为其任意两个元素都有上确界和下确界。⑶.〈A，/〉构成布尔代数。因为它是有界分配格，且其任意元素都有唯一补元素。．证明题（共10分）.（4分）设尹可是独异点，e为其幺元，且对VaeG，有a*a=e，证明:G,*:是一个交换群。证明：对VaeG,由于a*a=e，则a-1=a,即G中的每一个元素a都有逆元素，故a*b=a-i*b-i=(b*a)-1=b*a,所以；：G,*是一个Abel群。.(6分)设”产)是一个群，aeG,f:GfG,VxeG，有f(x)=a*x*a-i试证明f是;：6*：；,一个自同构.证：首先证明f是入射。(3分)对Vx,xeG,若f(x)=f(x),则有a*x*a-i=a*x*a-1,12 1 2 1 2该式两边同时左乘a-1及右乘a,得x=x,故f为入射f.12其次证明f是满射。对VyeG,都存在x=a-1*y*aeG,使得y=f(x),因止匕f是满射.综合以上两点，知f是双射。(3分)最后,对Vx,xe&都有f(x*x)=a*x*x*a-1=(a*x*a-1)*(a*x*a-1)12 1 2 1 2 1 2=f(x)*f(x),从而f是G到6的自同构.12

离散数学第七章检测题答案单项选择题(每小题2分，共20分)12345678910得分2424324213填空题（每空3分，共45分）1.^, 3 。 2._0,_1__o_0,_0。3."之V,V=V4.2|E| ,偶数。5.5一__9一2 12 1 -6. 3 ， 1 。7.J三、简答题(每小题5分，共25分).对有向图G=;V,E求解下列问题：(1)写出邻接矩阵A；(2)G=",E),中长度为3的不同的路有几条？其中不同的回路有几条？解：(1)邻接矩阵为：

010010 0 10 0A= 0 0 00 1110000 0 01 0-00110--110010000100010(2)A2=00010，A3