离散数学习题答案.pdf

. - - -可修编. 离散数学习题答案 习题一及答案： （P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设 p：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与 X 威都学过法语 解：设 p：王强学过法语；q：X 威学过法语；则命题符号化的结果是pq （9）只有天下大雨，他才乘班车上班 解：设 p：天下大雨；q：他乘班车上班；则命题符号化的结果是qp （11）下雪路滑，他迟到了 解：设 p：下雪；q：路滑；r：他迟到了；则命题符号化的结果是()pqr 15、设 p：2+3=5. q：大熊猫产在中国. r：太阳从西方升起. 求下列复合命题的真值： （4）()(())pqrpqr  解：p=1，q=1，r=0， ()(1 10)1pqr ， (())(( 11)0)(00)1pqr   ()(())111pqrpqr    19、用真值表判断下列公式的类型： （2）()ppq   解：列出公式的真值表，如下所示： p q p q ()pp  ()ppq    . - - -可修编. 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 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： ()10p00pq 所以公式的成真赋值有：01，10，11 习题二及答案： （P38） 5、求下列公式的主析取 X 式，并求成真赋值： （2）()()pr  解：原式()prqr()ppqr   ()()pqrpqr  37mm，此即公式的主析取 X 式， 所以成真赋值为 011，111 6、求下列公式的主合取X 式，并求成假赋值： （2）()()pqpr   解：原式()()pprpqr   ()pqr  4M，此即公式的主合取 X 式，  . - - -可修编. 所以成假赋值为 100 7、求下列公式的主析取 X 式，再用主析取 X 式求主合取 X 式： （1）()pqr 解：原式()(()())pqrrppr      ()()()()()()pqrpqrpqrpqrpqrpqr       ()()()()()pqrpqrpqrpqrpqr       13567mmmmm，此即主析取 X 式。

主析取 X 式中没出现的极小项为0m，2m，4m，所以主合取 X 式中含有三个极大项0M，2M，4M，故原式的主合取 X 式024MMM 9、用真值表法求下面公式的主析取 X 式： （1）()()pqpr   解：公式的真值表如下： p q r p pq pr  ()()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 种成真赋值所对应的极小项的析取即为主析取 X 式，故主析取 X 式1234567mmmmmmm 习题三及答案： （P52-54） 11、填充下面推理证明中没有写出的推理规则。

前提：,,,pr rs p   结论：s 证明： ① p 前提引入 ②pq  前提引入 ③ q ①②析取三段论 ④qr  前提引入 ⑤ r ③④析取三段论 ⑥rs 前提引入 ⑦ s ⑤⑥假言推理 15、在自然推理系统 P 中用附加前提法证明下面推理： （2）前提：()(),()pqrsstu  . - - -可修编. 结论：pu 证明：用附加前提证明法 ① p 附加前提引入 ②pq①附加 ③()()pqrs 前提引入 ④rs②③假言推理 ⑤s④化简 ⑥st⑤附加 ⑦()stu 前提引入 ⑧ u ⑥⑦假言推理 故推理正确 16、在自然推理系统 P 中用归谬法证明下面推理： （1）前提：pq，rq ，rs 结论：p 证明：用归谬法 ① p 结论的否定引入 ②pq 前提引入 ③q①②假言推理 ④rq  前提引入 ⑤r③④析取三段论 ⑥rs 前提引入 ⑦ r ⑥化简  . - - -可修编. ⑧rr⑤⑦合取 由于0rr ，所以推理正确。

17、在自然推理系统 P 中构造下面推理的证明： 只要 A 曾到过受害者房间并且 11 点以前没离开，A 就是谋杀嫌犯A 曾到过受害者房间如果 A 在 11 点以前离开，看门人会看见他看门人没有看见他所以，A 是谋杀嫌犯 解：设 p：A 到过受害者房间，q：A 在 11 点以前离开，r：A 是谋杀嫌犯，s：看门人看见过 A 则前提：()pqr，p，qs，s 结论：r 证明： ①qs 前提引入 ②s 前提引入 ③q①②拒取式 ④p 前提引入 ⑤pq③④合取引入 ⑥()pqr 前提引入 ⑦r⑤⑥假言推理 习题四及答案： （P65-67） 5、在一阶逻辑中将下列命题符号化： （2）有的火车比有的汽车快  . - - -可修编. 解：设 F(x)：x 是火车，G(y)：y 是汽车，H(x,y)：x 比 y 快；则命题符号化的结果是： ( ( )( )( , ))x y F xG yH x y  （3）不存在比所有火车都快得汽车。

解：设 F(x)：x 是汽车，G(y)：y 是火车，H(x,y)：x 比 y 快；则命题符号化的结果是： ( ( )( ( )( , )))x F xy G yH x y或( ( )( ( )( , )))x F xy G yH x y  9、给定解释 I 如下： (a) 个体域为实数集合 R (b) 特定元素0a (c) 函数( , ), ,f x yxy x yR (d) 谓词( , ):,( , ):, ,F x yxy G x yxy x yR 给出以下公式在 I 下的解释，并指出它们的真值： （2）( ( ( , ), )( , ))x y F f x y aG x y  解：解释是：(0)x y xyxy ，含义是：对于任意的实数 x，y，若 x-y=0 则 x

此题答案不唯一，只要证明公式既不是永真式也不是矛盾式的每个解释合理即可 习题五及答案： （P80-81） 15、在自然推理系统N中，构造下面推理的证明： （3）前提：( ( )( ))x F xG x，( )xG x 结论：( )xF x  . - - -可修编. 证明： ①( )xG x 前提引入 ②( )x G x ①置换 ③( )G c②UI 规则 ④( ( )( ))x F xG x 前提引入 ⑤( )( )F cG c④UI 规则 ⑥( )F c③⑤析取三段论 ⑦( )xF x⑥EG 规则 22、在自然推理系统N中，构造下面推理的证明： （2）凡大学生都是勤奋的王晓山不勤奋所以王晓山不是大学生 解：设 F(x)：x 为大学生，G(x)：x 是勤奋的，c：王晓山 则前提：( ( )( ))x F xG x，( )G c 结论：( )F c 证明： ①( ( )( ))x F xG x 前提引入 ②( )( )F cG c①UI 规则 ③( )G c 前提引入 ④( )F c②③拒取式 25、在自然推理系统N中，构造下面推理的证明： 每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。

王大海是科学工作者，并且是聪明的所以，王大海在他的事业中将获得成功 （个体域为人类集合）  . - - -可修编. 解：设 F(x)：x 是科学工作者，G(x)：x 是刻苦钻研的，H(x)：x 是聪明的，I(x)：x 在他的事业中获得成功，c：王大海 则前提：( ( )( ))x F xG x，( ( )( )( ))x G xH xI x，( )( )F cH c 结论：( )I c 证明： ①( )( )F cH c前提引入 ②( )F c①化简 ③( )H c①化简 ④( ( )( ))x F xG x前提引入 ⑤( )( )F cG c④UI 规则 ⑥( )G c②⑤假言推理 ⑦( )( )G cH c③⑥合取引入 ⑧( ( )( )( ))x G xH xI x 前提引入 ⑨( )( )( )G cH cI c⑧UI 规则 ⑩( )I c⑦⑨假言推理 习题六及答案  . - - -可修编. 1 2 4 3 习题七及答案： （P132-135） *22、给定1,2,3,4A，A 上的关系1,3 , 1,4 , 2,3 , 2,4 , 3,4R ，试 （1）画出 R 的关系图； （2）说明 R 的性质。

解： （1） ●● ●● （2）R 的关系图中每个顶点都没有自环，所以 R 是反自反的，不是自反的； R 的关系图中任意两个顶点如果有边的都是单向边，故 R 是反对称的，不是对称的； R 的关系图中没有发生顶点 x 到顶点 y 有边、顶点 y 到顶点 z 有边，但顶点 x 到顶点 z 没有边的情况，故 R 是传递的 26 设1,2,3,4,5,6A，R 为 A 上的关系，R 的关系图如图 7.13 所示： （1）求23,RR的集合表达式； （2）求 r(R), s(R), t(R)的集合表达式 解： （1）由 R 的关系图可得1,5 , 2,5 , 3,1 , 3,3 , 4,5R  所以23,1 , 3,3 , 3,5RR R，323,1 , 3,3 , 3,5RRR，  . - - -可修编. 可得3,1 , 3,3 , 3,5,n>=2nR 当； （2）Ar(R)=RI1,5 , 2,5 , 3,1 , 3,3 , 4,5 , 1,1 , 2,2 , 4,4 , 5,5 , 6,6， 1( )R1,5 , 5,1 , 2,5 , 5,2 , 3,1 , 1,3 , 3,3 , 4,5 , 5,4s RR 232( )RR...R1,5 , 2,5 , 3,1 , 3,3 , 3,5 , 4,5t RRR 46、分别画出下列各偏序集,A R的哈斯图，并找出 A 的极大元、极小元、 最大元和最小元。

（1）A,,,,,,,,,,,,,IRa da ca ba eb ec ed e 解：哈斯图如下： A 的极大元为 e、f，极小元为 a、f； A 的最大元和最小元都不存在 48、设,B,SA R 和为偏序集，在集合A B上定义关系 T 如下： 112211221212,,,AB,,,a ba ba b T a ba RabSb 证明 T 为A B上的偏序关系 证明： （1）自反性： e a b c d f  . - - -可修编. 1111111111112212121111,ABRRSb SbRb Sb,,,,Ta baaaaa b T a ba RabSba b T a b任取，则：为偏序关系，具有自反性，为偏序关系，具有自反性，又，，故 具有自反性 （2）反对称性： 112211222211121221211221121221121122,,,AB,,,,RSbb,,Ta ba ba b T a ba b T a ba RabSba Rab Sba Raa RaaabSbb Sba ba b任取，若且，则有：（1 ）（2 ），又 为偏序关系，具有反对称性，所以，又 为偏序关系，具有反对称性，所以，故 具有反对称性 （3）传递性： 11223311222233112212122233232312231312231313131133,,,,AB,,,,,,,,,R,Sb Sbb Sb,,Ta ba ba ba b T a ba b T a ba b T a ba RabSba b T a ba Rab Sba Raa Raa RabSbb Sba Raa b T a b任取，，若且，则有：又 为偏序关系，具有传递性，所以又 为偏序关系，具有传递性，所以，故 具有传递性。

综合（1） （2） （3）知 T 具有自反性、反对称性和传递性，故 T 为A B上的偏序关系 习题九及答案： （P179-180） 8、 S=,QSa,b , x,ya,bx,yax,ay+bS为有理数集，为上的二元运算，有 （1）S运算在 上是否可交换、可结合？是否为幂等的？  . - - -可修编. （2）S运算是否有单位元、零元？如果有，请指出，并求出中所有可逆元素的逆元 解： （1） ,a,bxa,xb+yax,bx+ya,b,x yx y运算不具有交换律 ,a,bc,dax,bx+yc,dacx,adx+bx+y,a,bc,d,* ac,ad+bxac,xad+xb+yacx,adx+bx+y,a,bc,dx yx yx yx y而运算有结合律 2a,bsa,ba,ba ,a,badb任取，则有：运算无幂等律 （2） a,b *,a,ba,bsax,ay+ba,ba,bsaxaa x10a,baybbay0x10x1y0y0101010x y  令对均成立则有：对均成立对成立必定有运算的右单位元为 ， ，可验证 ， 也为 运算的左单位元，运算的单位元为 ，  . - - -可修编. a,b *,,,a,bsa,b *,,ax,ay+b,a1 x0axxa1 y+b0aybya1 y+b0a,bsa,b *,,a,bsx yx yx yx yx yx yx yx y令，若存在使得对上述等式均成立，则存在零元，否则不存在零元。

由由于不可能对均成立，故不可能对均成立，故不存在零元； a,b,a,b *,e101xax1aaayb0byaa0a,b1baa,b,aax yx y  设元素的逆元为，则令，（当0 ）当时，的逆元不存在；当0 时，的逆元是 11、S12SS?设， ，...,10，问下面的运算能否与构成代数系统，如果能构成代数系统则说明运算是否满足交换律、结合律，并求运算的单位元和零元 （3）xyxy = 大于等于 和 的最小整数； 解： （3）由*运算的定义可知：xy=max(x,y)， 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(y z),任取有(所以 运算满足结合律；xSx 1=max(x,1)=x=max(1,x)=1x,任取，有所以 运算的单位元是 1 ； xSx 10=max(x,10)=10=max(10,x)=10x,任取，有所以 运算的零元是 10； 16、  . - - -可修编. 1212V1,2,3 , ,1 ,xyV5,6 , ,6xyVVx yxy设其中表示取 和 之中较大的数。

其中表示取 和 之中较小的数求出和的所有的子代数指出哪些是平凡的子代数，哪些是真子代数     111V1,2,3 , ,1 , 1 , ,1 , 1,2 , ,1 , 1,3 , ,1V1,2,3 , ,1 , 1 , ,1V1 , ,1 , 1,2 , ,1 , 1,3 , ,1解：（1 ） 的所有的子代数是：；的平凡的子代数是：；的真子代数是：；    222V5,6 , ,66 , ,6V5,6 , ,66 , ,6V6 , ,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 是格，求以下公式的对偶式： （2）()()()abcabac 解：对偶式为：()()()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 都没有补元，所以不是有补格，所以不是布尔格 。