离散数学习题答案(耿素云屈婉玲)

离散数学习题(耿素云屈婉玲) 离散数学习题答案 习题二及答案:(P38) 5、求下列公式的主析取范式，并求成真赋值: ()()，,,,pqqr(2) ,,,,()pqqr,，,,,()ppqr解:原式 ,,qr ,，,,,,,()()pqrpqr ，此即公式的主析取范式， ,,mm37 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值: ()()pqpr,,，,2) ( ,,，,,，,,()()pprpqr,，,,()pqr解:原式，此即公式的主合取范式， ,M4 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式: ()pqr,,(1) ,,,，,,，,,，,,pqrrppqqr()(()())解:原式 ,,,，,,,,，,，,,，,,,,，,,,,()()()()()()pqrpqrpqrpqrpqrpqr ,，,，,,，,,,,，,,,,，,,,()()()()()pqrpqrpqrpqrpqr ，此即主析取范式。 ,,,,,mmmmm13567 主析取范式中没出现的极小项为，，，所以主合取范式中含有三个极大项，，，故原式的主合取MMMmmm024024范式。 ,,,MMM024 9、用真值表法求下面公式的主析取范式: ()()pqpr,,，,(1) 解:公式的真值表如下: p ，p pq, ，,pr q r()()pqpr,,，, 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种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 ,,,,,,,mmmmmmm1234567 习题三及答案:(P52-54) 11、填充下面推理证明中没有写出的推理规则。 前提: ，,，,,pqqrrsp,,, 结论:s 证明: ? p 前提引入 ? 前提引入 ，,pq ? q ??析取三段论 ? 前提引入 ，,qr ? r ??析取三段论 ? 前提引入 rs, ? s ??假言推理 15、在自然推理系统P中用附加前提法证明下面推理: ()(),()pqrsstu,,,,,(2)前提: 结论: pu, 证明:用附加前提证明法。 ? p 附加前提引入 ? ?附加 pq, ()()pqrs,,,? 前提引入 ? ??假言推理 rs, ? s ?化简 ? ?附加 st, ()stu,,? 前提引入 ? u ??假言推理 故推理正确。 16、在自然推理系统P中用归谬法证明下面推理: (1)前提:pq,，，，,rq， rs,， 结论:，p 证明:用归谬法 ? p 结论的否定引入 ? 前提引入 pq,， ? ??假言推理 ，q ? 前提引入 ，,rq ? ??析取三段论 ，r 前提引入 ?rs,， ? r ?化简 ? ??合取 rr,， 由于，所以推理正确。 rr,，,0 17、在自然推理系统P中构造下面推理的证明: 只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间。如果A在11点以前离开，看门 人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。 解:设p:A到过受害者房间，q:A在11点以前离开，r:A是谋杀嫌犯，s:看门人看见过A。 ()pqr,，,则前提:，，， pqs,，s 结论: r 证明: ? 前提引入 qs, ? 前提引入 ，s ? ??拒取式 ，q ? 前提引入 p ? ??合取引入 pq,， ()pqr,，,? 前提引入 ? ??假言推理 r 习题五及答案:(P80-81) 15、在自然推理系统N中，构造下面推理的证明: , ,,xFxGx(()())，，xGx()3)前提:， ( ，xFx() 结论: 证明: ，，xGx()? 前提引入 ,，xGx()? ?置换 ，Gc()? ?UI规则 ,,xFxGx(()())? 前提引入 FcGc()(),? ?UI规则 Fc() ??析取三段论 ? ，xFx()? ?EG规则 22、在自然推理系统中，构造下面推理的证明: N, (2)凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。 解:设F(x):x为大学生，G(x):想是勤奋的，c:王晓山 ,,xFxGx(()())，Gc()则前提:， ，Fc() 结论: 证明: ,,xFxGx(()())? 前提引入 FcGc()(),? ?UI规则 ，Gc()? 前提引入 ，Fc()? ??拒取式 25、在自然推理系统N中，构造下面推理的证明: , 每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是 聪明的。所以，王大海在他的事业中将获得成功。(个体域为人类集合) 解:设F(x):x是科学工作者，G(x):x是刻苦钻研的，H(x):x是聪明的，I(x):x在他的事业中获得成功，c:王大海 ,,xFxGx(()()),,,xGxHxIx(()()())FcHc()(),则前提:，， Ic() 结论: 证明: FcHc()(),? 前提引入 Fc()? ?化简 Hc()? ?化简 ,,xFxGx(()())? 前提引入 FcGc()(),? ?UI规则 Gc()? ??假言推理 GcHc()(),? ??合取引入 ,,,xGxHxIx(()()()) 前提引入 ? GcHcIc()()(),,? ?UI规则 Ic()? ??假言推理 习题七及答案:(P132-135) R,1,3,1,4,2,3,2,4,3,4A,1,2,3,422、给定，A上的关系，试 ,,,,(1)画出R的关系图; (2)说明R的性质。 解:(1) 1 2 ? ? ? ? 3 4 (2)R的关系图中每个顶点都没有自环，所以R是反自反的，不是自反的; R的关系图中任意两个顶点如果有边的都是单向边，故R是反对称的，不是对称的; R的关系图中没有发生顶点x到顶点y有边、顶点y到顶点z有边，但顶点x到顶点z没有边的情况，故R是 传递的。 A,1,2,3,4,5,626 设，R为A上的关系，R的关系图如图7.13所示: ,, 23(1)求的集合表达式; RR, (2)求r(R), s(R), t(R)的集合表达式。 R,1,5,2,5,3,1,3,3,4,5解:(1)由R的关系图可得 ,, 232RRR,:,3,1,3,3,3,5RRR,:,3,1,3,3,3,5所以，， ,,,, nR,3,1,3,3,3,5,n>=2当可得; ,, r(R)=RI1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6,(2)， ,,A ,1sRR()R1,5,5,1,2,5,5,2,3,1,1,3,3,3,4,5,5,4,, ,, 232tRRR()RR...R1,5,2,5,3,1,3,3,4,5,3,5,,, ,,46、分别画出下列各偏序集的哈斯图，并找出A的极大元、极小元、最大元和最小元。 AR,, Radacabaebecede,,,,,,,,,,,,,,I(1) ,,,A 解:哈斯图如下: e b c d a A的极大元为e、极小元为a; A的最大元为e、最小元为a。 AR,B,S和AB，48、设为偏序集，在集合上定义关系T如下: ,,，abab,,,AB,1122 abTabaRabSb,,,,11221212 AB，证明T为上的偏序关系。 证明:(1)自反性: 任取，则:ab,AB,，11 RR为偏序关系，具有自反性，？aa11SbSb为偏序关系，具有自反性，？11 ？,aaRbSb1111 又，abTabaRabSb,,,,11221212 ？abTab,,T，故满足自反性1111 (2)反对称性: 任取，若且，则有:abababTababTab,,,AB,,,,,，112211222211 aRabSb,(1)1212 aRabSb,(2)2121 ？,,aRaaRaaa，又为偏序关系，具有反对称性，所以R122112 ？,,bSbbSb，又为偏序关系，具有反对称性，所以Sbb122112 ？,abab,,T，故满足反对称性1122 (3)传递性: 任取，，若且，则有:ababababTababTab,,,,AB,,,,,，11223311222233 abTabaRabSb,,,,11221212 abTabaRabSb,,,,22332323 ？,aRaaRaaRa,R又为偏序关系，具有传递性，所以 122313 ？,bSbbSb,SbSb又为偏序关系，具有传递性，所以122313 ？,,aRaabTabbSb,,T，故满足传递性。13131133 AB，综合(1)(2)(3)知T满足自反性、反对称性和传递性，故T为上的偏序关系。 习题九及答案:(P179-180) 8、 S=QQ,QSa,b,x,y，,,,为有理数集，为上的二元运算，有S a,bx,yax,ay+b,, ,运算在上是否可交换、可结合,是否为幂等的,S(1) ,运算是否有单位元、零元,如果有，请指出，并求出中所有可逆元素的逆元S(2)。 解:(1) xy,a,bxa,xb+y,, ,,,ax,bx+ya,b,xy ？,运算不具有交换律 xy,a,bc,d,,，， ,,ax,bx+yc,d ,acx,adx+bx+y 而xy,a,bc,d,,，， ,xy,*ac,ad+b ,,xac,xad+xb+yacx,adx+bx+y,,,xy,a,bc,d，， ？,运算有结合律 任取，则有:a,bs, 2 a,ba,ba,a,b,,，,adb ？,运算无幂等律 (2) 令对均成立a,b*,a,ba,bsxy,,, 则有:对均成立ax,ay+ba,ba,bs,,, ,axa,,,,ax10，，,？,,对成立a,b，，,,aybb，,ay0,,,, x10x1,,,,,？,必定有,,y0y0,,,, ？,,运算的右单位元为，，可验证，也为运算的左单位元，1010 ？,运算的单位元为，10 令，若存在使得对上述等式均成立，a,b*,,,a,bsxyxyxy,,, 则存在零元，否则不存在零元。 由a,b*,,xyxy, ,,ax,ay+b,xy ,a1x0,,,axx,，，,,,,,a1y+b0,,ayby，,，，,,,, 由于不可能对均成立，a1y+b0a,bs,,,,，， 故不可能对均成立，故不存在零元;a,b*,,a,bsxyxy,,, 设元素的逆元为，则令，a,b,a,b*,e10xyxy,, 1,x,,ax1,,,a,,,(当a0),,ayb0b，,,,y,, ,a, ？,当时，的逆元不存在;a0a,b 1b当aa,b,,,0时，的逆元是aa 11、 设，，S12SS?,,...,10，问下面的运算能否与构成代数系统，,, 如果能构成代数系统则说明运算是否满足交换律、结合律，并求运算的单位元和零元。,, (3); xyxy,=大于等于和的最小整数 xy=max(x,y),， 解:(3)由*运算的定义可知: x,yS,xySSS,,,,,有，故运算在上满足封闭性，所以运算与非空集合能构成代数系统; 任取有所以运算满足交换律;x,yS,xy=max(x,y)=max(y,x)=y,,,,,x 任取有x,y,zS,xy)z=max(max(x,y),z)=max(x,y,z)=max(x,max(y,z))=x(yz),,,,,,,(所以运算满足结合律; 任取，有所以运算的单位元是xSx1=max(x,1)=x=max(1,x)=1x,,,,,1; 任取，有所以运算的零元是xSx10=max(x,10)=10=max(10,x)=10x,,,,,10;16、 设其中表示取和之中较大的数。，V1,2,3,,1,xyV5,6,,6,::,,xy,,,,12 其中表示取和之中较小的数。求出和的所有的子代数。xy,xyVV12 指出哪些是平凡的子代数，哪些是真子代数。 解:(1)的所有的子代数是:;V1,2,3,,1,1,,1,1,2,,1,1,3,,1::::,,,,,,,,1 V1,2,3,,1,1,,1的平凡的子代数是:;::,,,,1 V1,,1,1,2,,1,1,3,,1的真子代数是:;:::,,,,,,1 (2)的所有的子代数是:，;V5,6,,66,,6,,,,,,2 V5,6,,66,,6的平凡的子代数是:，;,,,,,,2 V6,,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是格，求以下公式的对偶式: abcabac,,,,,,()()()(2) abcabac,,,,,,()()()解:对偶式为:，参见P208页定义11.2。 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，所以任何元素皆有补元，是有补格;cbdcac,,,,,(),()()cbcdfdd,,,,,,？,,,,,,cbdcbcd()()() ，所以对运算,,不满足分配律，所以不是分配格，所以不是布尔格; (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都没有补元，所以不是有补格，所以不是布尔格。