离散数学习题答案.doc

.
离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 pÙq解：设p：王强学过法语；q：刘威学过法语；则命题符号化的结果是 （9）只有天下大雨，他才乘班车上班 q®p解：设p：天下大雨；q：他乘班车上班；则命题符号化的结果是 （11）下雪路滑，他迟到了 解：设p：下雪；q：路滑；r：他迟到了；则命题符号化的结果是(pÙq)®r 15、设p：2+3=5. q：大熊猫产在中国. r：太阳从西方升起. 求下列复合命题的真值： (pÙqÙØr)«((ØpÚØq)®r)（4） 解：p=1，q=1，r=0， (pÙqÙØr)Û(1Ù1ÙØ0)Û1， ((ØpÚØq)®r)Û((Ø1ÚØ1)®0)Û(0®0)Û1 \(pÙqÙØr)«((ØpÚØq)®r)Û1«1Û1 19、用真值表判断下列公式的类型： (p®Øp)®Øq（2） 解：列出公式的真值表，如下所示： pØpØqq (p®Øp)(p®Øp)®Øq 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。 20、求下列公式的成真赋值：
（4）Ø(pÚq)®q 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： pÛ0Ø(pÚq)Û1ììÞ ííqÛ0qÛ0îî成真赋值有：01，10，11。 所以公式的 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2） (Øp®q)Ù(qÙr)解：原式 Û(pÚq)ÙqÙrÛ(ØpÚp)ÙqÙrÛqÙr ，此即公式的主析取范式， ÛmÚmÛ(ØpÙqÙr)Ú(pÙqÙr)37所以成真赋值为011，111。 *6、求下列公式的主合取范式，并求成假赋值： （2） (pÙq)Ú(ØpÚr)解：原式，此即公式的主合取范式， ÛMÛ(pÚØpÚr)Ù(ØpÚqÚr)Û(ØpÚqÚr)4所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1） (pÙq)Úr解：原式 ÛpÙqÙ(ØrÚr)Ú((ØpÚp)Ù(ØqÚq)Ùr) Û(pÙqÙØr)Ú(pÙqÙ)rÚ(ØpÙqØ)Ùr(ÚpØqÙ)rÙ(ÚpÙqØ)rÙ(ÚpqÙrÙ Û(ØpÙØqÙr)Ú(pØÙq)Ùr(ÚpÙqØ)rÙ(ÚpqÙ)ÙrØ(ÚpqÙrÙ ，此即主析取范式。 ÛmÚmÚmÚmÚm13567主析取范式中没出现的极小项为，，，所以主合取范式中含有三个极大项，，MMmmm02024，故原式的主合取范式。 MÛMÙMÙM4024 9、用真值表法求下面公式的主析取范式：
（1） (pÚq)Ú(ØpÙr)解：公式的真值表如下： pØppÚqØpÙrq r (pÚq)Ú(ØpÙr) 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 ÛmÚmÚmÚmÚmÚmÚm1234567 习题三及答案：（P52-54） 11、填充下面推理证明中没有写出的推理规则。 前提： ØpÚq,ØqÚr,r®s,p结论：s 证明： ① p 前提引入 ② 前提引入 ØpÚq③ q ①②析取三段论 ④ 前提引入 ØqÚr⑤ r ③④析取三段论 r®s⑥ 前提引入 ⑦ s ⑤⑥假言推理 15、在自然推理系统P中用附加前提法证明下面推理： （2）前提： (pÚq)®(rÙs),(sÚt)®u 结论： p®u证明：用附加前提证明法。 ① p 附加前提引入
② ①附加 pÚq③ 前提引入 (pÚq)®(rÙs)rÙs④ ②③假言推理 ⑤ s ④化简 ⑥ ⑤附加 sÚt⑦ 前提引入 (sÚt)®u⑧ u ⑥⑦假言推理 故推理正确。 16、在自然推理系统P中用归谬法证明下面推理： rÙØs（1）前提：，， p®ØqØrÚq 结论： Øp证明：用归谬法 ① p 结论的否定引入 ② 前提引入 p®Øq③ ①②假言推理 Øq④ 前提引入 ØrÚq⑤ ③④析取三段论 ØrrÙØs⑥ 前提引入 ⑦ r ⑥化简 ⑧ ⑤⑦合取 rÙØr由于，所以推理正确。 rÙØrÞ017、在自然推理系统P中构造下面推理的证明： 只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间。如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。 解：设p：A到过受害者房间，q：A在11点以前离开，r：A是谋杀嫌犯，s：看门人看见过A。 Øs则前提：，，， pq®s(pÙØq)®r 结论： r证明： ① 前提引入 q®sØs② 前提引入 ③ ①②拒取式 Øq④ 前提引入 p
⑤ ③④合取引入 pÙØq⑥ 前提引入 (pÙØq)®r⑦ ⑤⑥假言推理 r 习题四及答案：（P65-67） 5、在一阶逻辑中将下列命题符号化： （2）有的火车比有的汽车快。 解：设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；则命题符号化的结果是： $x$y(F(x)ÙG(y)ÙH(x,y)) （3）不存在比所有火车都快的汽车。 解：方法一： 设F(x)：x是汽车，G(y)：y是火车，H(x,y)：x比y快；则命题符号化的结果是： Ø$x(F(x)Ù"y(G(y)®H(x,y)))"x(F(x)®$y(G(y)ÙØH(x,y)))或 方法二： 设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；则命题符号化的结果是： Ø$x(G(x)Ù"y(F(y)®H(x,y)))Ø$x"y(G(x)Ù(F(y)®H(x,y)))或 9、给定解释I如下： (a) 个体域为实数集合R。 -a=0 (b) 特定元素。-f(x,y)=x-y,x,yÎR (c) 函数。--F(x,y):x=y,G(x,y):x<y,x,yÎR (d) 谓词。 给出以下公式在I下的解释，并指出它们的真值： "x"y(F(f(x,y),a)®G(x,y))（2） "x"y(x-y=0®x<y)解：解释是：，含义是：对于任意的实数x，y，若x-y=0则x<y。 该公式在I解释下的真值为假。14、证明下面公式既不是永真式也不是矛盾式： "x(F(x)®$y(G(y)ÙH(x,y)))（1） I解：取解释如下：个体域为全总个体域， F(x)H(x,y)G(y)：x是兔子，：y是乌龟，：x比y跑得快，则该公式在解释I下真值是1； ''IIH(x,y)取解释如下：：x比y跑得慢，其它同上，则该公式在解释下真值是0；
故公式（1）既不是永真式也不是矛盾式。 此题答案不唯一，只要证明公式既不是永真式也不是矛盾式的每个解释合理即可。 习题五及答案：（P79-81） 5、给定解释I如下： (a) 个体域D={3,4} ---f(x):f(3)=4,f(4)=3 (b) -----F(x,y):F(3,3)=F(4,4)=0,F(3,4)=F(4,3)=1 (c) 试求下列公式在I下的真值： "x$yF(x,y) (1) 解：方法一：先消去存在量词 "x$yF(x,y)Û"x(F(x,3)ÚF(x,4)) Û(F(3,3Ú)F(3,Ù4)F)(Ú(4F,3) Û(0Ú1)Ù(1Ú0) Û1 15、在自然推理系统中，构造下面推理的证明： Nx（3）前提：， "x(F(x)ÚG(x))Ø$xG(x) 结论： $xF(x)证明： ① 前提引入 Ø$xG(x)② ①置换 "xØG(x)③ ②UI规则 ØG(c)④ 前提引入 "x(F(x)ÚG(x))⑤ ④UI规则 F(c)ÚG(c)⑥ ③⑤析取三段论 F(c)⑦ ⑥EG规则 $xF(x)
*22、在自然推理系统中，构造下面推理的证明： Nx（2）凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。 解：设F(x)：x为大学生，G(x)：x是勤奋的，c：王晓山 则前提：， "x(F(x)®G(x))ØG(c) 结论： ØF(c)证明： ① 前提引入 "x(F(x)®G(x))② ①UI规则 F(c)®G(c)③ 前提引入 ØG(c)④ ②③拒取式 ØF(c)25、在自然推理系统中，构造下面推理的证明： Nx每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的。所以，王大海在他的事业中将获得成功。（个体域为人类集合） 解：设F(x)：x是科学工作者，G(x)：x是刻苦钻研的，H(x)：x是聪明的，I(x)：x在他的事业中获得成功，c：王大海 则前提：，， "x(F(x)®G(x))"x(G(x)ÙH(x)®I(x))F(c)ÙH(c) 结论： I(c)证明： ① 前提引入 F(c)ÙH(c)② ①化简 F(c)③ ①化简 H(c)④ 前提引入 "x(F(x)®G(x))⑤ ④UI规则 F(c)®G(c)⑥ ②⑤假言推理 G(c)⑦ ③⑥合取引入 G(c)ÙH(c)⑧ 前提引入 "x(G(x)ÙH(x)®I(x))
⑨ ⑧UI规则 G(c)ÙH(c)®I(c)⑩ ⑦⑨假言推理 I(c)习题六及答案（P99-100） 28、化简下述集合公式： ((A-B)-C)È((A-B)ÇC)È((AÇB)-C)((AÇB)ÇC)（3） ((A-B)-C)È((A-B)ÇC)È((AÇB)-C)((AÇB)ÇC)解： =(A-B)È(AÇB) =A 30、设A,B,C代表任意集合，试判断下面命题的真假。如果为真，给出证明；如果为假，给出反例。 (AÈB)-A=B（6） (AÈB)-A=B-AB-A=BBÇA=Æ，如果，则解：该命题为假，，否则B-A=BB-A¹B，故为假。 (AÈB)-A={3}¹BA={1,2},B={1,3},举反例如下：则 。AÈB=AÈCÞB=C（8） AÈB=AÈC一定成立，解：该命题为假，举反例如下：如果B，C都是A的子集，则B={1}C={2}1,2}A={AÈB=AÈC=AB=C但不一定成立，例如：，则，, ， B¹C 但。33、证明集合恒等式： AÇ(BÈ:A)=BÇA（1） AÇ(BÈ:A)证明： =(AÇB)È(AÇ:A) =(AÇB)ÈÆ =BÇA=AÇB
习题七及答案：（P132-135） {}A=1,2,3,4,5,6 26 设，R为A上的关系，R的关系图如图7.13所示： 23（1）求的集合表达式； R,R（2）求r(R), s(R), t(R)的集合表达式。 {} 解：（1）由R的关系图可得 R=1,5,2,5,3,1,3,3,4,5{}{}232所以，， R=R°R=3,1,3,3,3,5R=R°R=3,1,3,3,3,5{}n可得； R=3,1,3,3,3,5,当n>=2 {} （2）， r(R)=RUI=1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6A{}-1 s(R)=RUR=1,5,5,1,2,5,5,2,3,1,1,3,3,3,4,5,5,4{}232 t(R)=RURURU...=RUR=1,5,2,5,3,1,3,3,3,5,4,541、设A={1，2，3，4}，R为A´A"<a,b>,<c,d>ÎA´A上的二元关系，，<a,b>R<c,d>Ûa+b=c+d （1）证明R为等价关系； （2）求R导出的划分。 （1）只需证明R具有自反性、对称性和传递性即可，证明过程如下： "<a,b>ÎA´A\<a,b>R<a,b>a+b=a+b（a）任取，有，，所以R具有自反性； "<a,b>,<c,d>ÎA´A<a,b>R<c,d>（b）任取，若， \<c,d>R<a,b>a+b=c+d\c+d=a+b则有，，，所以R具有对称性； "<a,b>,<c,d>,<e,f>ÎA´A<a,b>R<c,d><c,d>R<e,f>（c）任取，若且， c+d=e+f\a+b=e+f\<a,b>R<e,f>a+b=c+d则有且，，，所以R具有传递性， A´A综合（a）（b）（c）可知：R为集合上的等价关系； A´A（2）先求出集合的结果： A´A={<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,1>,<3,2>,<3,3>,<3,4>,<4,1>,<4,2>,<4,3>,<4,4>}A´A再分别求集合各元素的等价类，结果如下： [<1,1>]={<1,1>}, R[<1,2>]=[<2,1>]={<1,2>,<2,1>}, RR
[<1,3>]=[<2,2>]=[<3,1>]={<1,3>,<2,2>,<3,1>}, RRR[<1,4>]=[<2,3>]=[<3,2>]=[<4,1>]={<1,4>,<2,3>,<3,2>,<4,1>}, RRRR[<2,4>]=[<3,3>]=[<4,2>]={<2,4>,<3,3>,<4,2>}, RRR[<3,4>]=[<4,3>]={<3,4>,<4,3>}, RR[<4,4>]={<4,4>}。 RA/RA/R等价关系R导出的划分就是集合A关于R的商集，而集合A关于R的商集是由R的所有等价类作为元素构成的集合，所以等价关系R导出的划分是： {{<1,1>},{<1,2>,<2,1>},{<1,3>,<2,2>,<3,1>},{<1,4>,<2,3>,<3,2>,<4,1>},{<2,4>,<3,3>,<4,2>},{<3,4>,<4,3>},{<4,4>}} A,R46、分别画出下列各偏序集的哈斯图，并找出A的极大元、极小元、最大元和最小元。 £{}（1） R=a,d,a,c,a,b,a,e,b,e,c,e,d,eUI £A解：哈斯图如下： e b c d f a A的极大元为e、f，极小元为a、f； A的最大元和最小元都不存在。 {}{} A=1,2,3,4*22、给定，A上的关系，试 R=1,3,1,4,2,3,2,4,3,4（1）画出R的关系图； （2）说明R的性质。 解：（1） 1 2 ● ● ● ● 3 4 （2）R的关系图中每个顶点都没有自环，所以R是反自反的，不是自反的； R的关系图中任意两个顶点如果有边的都是单向边，故R是反对称的，不是对
称的； R的关系图中没有发生顶点x到顶点y有边、顶点y到顶点z有边，但顶点x到顶点z没有边的情况，故R是传递的。 A,R和B,S*48、设为偏序集，在集合上定义关系T如下： A´B "a,b,a,bÎA´B,1122 a,bTa,bÛaRaÙbSb11221212证明T为上的偏序关系。 A´B证明：（1）自反性： 任取a,bÎA´B，则：11R为偏序关系，具有自反性，\aRaQ11S为偏序关系，具有自反性，\bSbQ11 \aRaÙbSb1111 又a,bTa,bÛaRaÙbSb，11221212 \a,bTa,b，故T具有自反性1111（2）反对称性： 任取a,b,a,bÎA´B，若a,bTa,b且a,bTa,b，则有：112211222211aRaÙbSb（1）1212aRaÙbSb（2）2121 \aRaÙaRa，又R为偏序关系，具有反对称性，所以a=a122112\bSbÙbSb，又S为偏序关系，具有反对称性，所以b=b122112 \a,b=a,b，故T具有反对称性1122（3）传递性： 任取a,b,a,b，a,bÎA´B，若a,bTa,b且a,bTa,b，则有：11223311222233 a,bTa,bÛaRaÙbSb11221212 a,bTa,bÛaRaÙbSb22332323\aRaÙaRa,又R为偏序关系，具有传递性，所以aRa 122313\bSbÙbSb,又S为偏序关系，具有传递性，所以bSb122313 \aRaÙbSbÞa,bTa,b，故T具有传递性。13131133综合（1）（2）（3）知T具有自反性、反对称性和传递性，故T为上的偏序关系。 A´B
习题九及答案：（P179-180） 8、 S=Q´Q,Q为有理数集，为*S上的二元运算，"a,b,x,yÎS有 a,b*x,y=ax,ay+b（1） *运算在S上是否可交换、可结合？是否为幂等的？（2）。 *运算是否有单位元、零元？如果有，请指出，并求出S中所有可逆元素的逆元解：（1） x,y*a,b=xa,xb+y =ax,bx+y¹a,b*x,y \*运算不具有交换律 () x,y*a,b*c,d =ax,bx+y*c,d =acx,adx+bx+y() 而x,y*a,b*c,d =x,y*ac,ad+b =xac,xad+xb+y=acx,adx+bx+y() =x,y*a,b*c,d\*运算有结合律 任取a,bÎs，则有： 2 a,b*a,b=a,ab+b¹a,b\*运算无幂等律 （2） 令a,b*x,y=a,b对"a,bÎs均成立 则有：ax,ay+b=a,b对"a,bÎs均成立()ìax=aìax-1=0ï()\Þ对"a,b成立ííay+b=bay=0ïîî x-1=0x=1ìì\必定有Þííy=0y=0îî\*运算的右单位元为1，0，可验证1，0也为*运算的左单位元， \*运算的单位元为1，0
令a,b*x,y=x,y，若存在x,y使得对"a,bÎs上述等式均成立，则存在零元，否则不存在零元。 由a,b*x,y=x,y Þax,ay+b=x,y()ìa-1x=0ìax=xïïÞíí()a-1y+b=0ay+b=yïïîî() 由于a-1y+b=0不可能对"a,bÎs均成立，故a,b*x,y=x,y不可能对"a,bÎs均成立，故不存在零元； 设元素a,b的逆元为x,y，则令a,b*x,y=e=1，01ìx=ï ax=1ìïaÞÞ（当a¹0）ííay+b=0bîïy=- ïaî \当a=0时，a,b的逆元不存在； 1b当a¹0时，a,b的逆元是,- aa11、{}设S=12，，...,10，问下面的运算能否与S构成代数系统S，*? 如果能构成代数系统则说明*运算是否满足交换律、结合律，并求*运算的单位元和零元。（3）； x*y=大于等于x和y的最小整数解：（3）由*运算的定义可知：， x*y=max(x,y) x,yÎS,有x*yÎS，故*运算在S上满足封闭性，所以*运算与非空集合S能构成代数系统； 任取x,yÎS,有x*y=max(x,y)=max(y,x)=y*x,所以*运算满足交换律；任取x,y,zÎS,有(x*y)*z=max(max(x,y),z)=max(x,y,z)=max(x,max(y,z))=x*(y*z),所以*运算满足结合律； 任取xÎS，有x*1=max(x,1)=x=max(1,x)=1*x,所以*运算的单位元是1； 任取xÎS，有x*10=max(x,10)=10=max(10,x)=10*x,所以*运算的零元是10；
16、 {}{} 设V=1,2,3,°,1,其中x°y表示取x和y之中较大的数。V=5,6,*,6，12其中x*y表示取x和y之中较小的数。求出V和V的所有的子代数。 12指出哪些是平凡的子代数，哪些是真子代数。解：（1）V中°运算的单位元是1，1{}{}{}{} V的所有的子代数是：1,2,3,°,1,1,°,1,1,2,°,1,1,3,°,1；1 {}{} V的平凡的子代数是：1,2,3,°,1,1,°,1；1{}{}{} V的真子代数是：1,°,1,1,2,°,1,1,3,°,1；1（2）V中*运算的单位元是6，2{}{} V的所有的子代数是：5,6,*,6，6,*,6；2 {}{} V的平凡的子代数是：5,6,*,6，6,*,6；2{} V的真子代数是：6,*,6。2 习题十一及答案：（P218-219） 1、图11.11给出了6个偏序集的哈斯图。判断其中哪些是格。如果不是格，说明理由 解：（a）、（c）、（f）是格；因为任意两个元素构成的集合都有最小上界和最大下界； （b）不是格，因为{d,e}的最大下界不存在； （d）不是格，因为{b,c}的最小上界不存在； （e）不是格，因为{a,b}的最大下界不存在。 2、下列各集合低于整除关系都构成偏序集，判断哪些偏序集是格。 （1）L={1，2，3，4，5}； （2）L={1，2，3，6，12}； 解：画出哈斯图即可判断出：（1）不是格，（2）是格。 4、设L是格，求以下公式的对偶式： aÚ(bÙc)£(aÚb)Ù(aÚc)（2） aÙ(bÚc)³(aÙb)Ú(aÙc)解：对偶式为：，参见P208页定义11.2。 a,b,cÎLa£b£caÚb=bÙc6、设L为格，，且，证明。 Qa£b,\aÚb=b,证明： Qb£c,\bÙc=b, \aÚb=bÙc
9、针对图11.11中的每个格，如果格中的元素存在补元，则求出这些补元。 解： （a）图：a,d互为补元，其中a为全下界，d为全上界，b和c都没有补元； （c）图：a,f互为补元，其中a为全下界，f为全上界，c和d的补元都是b和e，b和e的补元都是c和d； （f）图：a,f互为补元，其中a为全下界，f为全上界，b和e互为补元，c和d都没有补元。 10、说明图11.11中每个格是否为分配格、有补格和布尔格，并说明理由。 解： （a）图：是一条链，所以是分配格，b和c都没有补元，所以不是有补格，所以不是布尔格； （c）图：a,f互为补元，c和d的补元都是b和e，b和e的补元都是c和d，所以任何元素皆有补元，是QcÚ(bÙd)=cÚa=c,(cÚb)Ù(cÚd)=fÙd=d\cÚ(bÙd)¹(cÚb)Ù(cÚd)有补格； ，所以ÚÙ对运算不满足分配律，所以不是分配格，所以不是布尔格； （f）图：经过分析知图（f）对应的格只有2个五元子格：L1={a,c,d,e,f}, L2={a,b,c,d,f}。画出L1和L2的哈斯图可知L1和L2均不同构于钻石格和五角格，根据分配格的充分必要条件（见P213页的定理11.5）得图（f）对应的格是分配格；c和d都没有补元，所以不是有补格，所以不是布尔格。
整理文档