离散数学习题答案47568

1、离散数学习题答案习题一及答案：(P14-15)14、将下列命题符号化：(5) 李辛与李末是兄弟解：设 p:李辛与李末是兄弟，则命题符号化的结果是p(6) 王强与刘威都学过法语解：设 p :王强学过法语；q :刘威学过法语；则命题符号化的结果是p q(9)只有天下大雨，他才乘班车上班解：设 p:天下大雨；q：他乘班车上班；则命题符号化的结果是q p(11)下雪路滑，他迟到了解：设 p:下雪；q :路滑；r:他迟到了；则命题符号化的结果是(p q) r1515、 设 p p: 2+3=5.2+3=5.q q :大熊猫产在中国 r r：太阳从西方升起求下列复合命题的真值：(4 4)(p q r) (

2、 p q) r)解：p=1p=1，q=1q=1，r=0r=0，(p q r) (1 10)1，(p q) r) ( 11)0)(00)1(p q r) ( p q) r) 1111919、用真值表判断下列公式的类型：(2 2)(p p) q解：列出公式的真值表，如下所示:pqpq(pp)(p p) q001111011010100101110001由真值表可以看出公式有 3 个成真赋值，故公式是非重言式的可满足式。20、求下列公式的成真赋值：(4)( p q) q解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：( p q) 1 p 0q 0 q 0所以公式的成真赋值有：

3、 01，10， 11。习题二及答案： ( P38)5、求下列公式的主析取范式，并求成真赋值：(2)( p q) (q r )解：原式( p q) q rq r( p p) q r所以成真赋值为 011， 111 6、求下列公式的主合取范式，并求成假赋值：(2)( p q) ( p r)解：原式(p p r) ( p q r) ( p q r) M4，此即公式的主合取范式， 所以成假赋值为 100。7、求下列公式的主析取范式，再用主析取范式求主合取范式： (1)( p q) r解：原式p q ( r r )(pp)( q q) r )( p q r) (pqr)(p q r ) ( pqr) (

4、 p qr) ( p q r)( p q r ) (pqr)( p q r) (pqr ) ( p qr)m1m3m5m6m7，此即主析取范式。主析取范式中没出现的极小项为m0，m2，m4，所以主合取范式中含有三个极大项M0，M2，M4，故原式的主合取范式M0M2M4。9、用真值表法求下面公式的主析取范式：(1)(p q) ( p r)解：公式的真值表如下:pqrpp qp r(p q) ( p r)( p q r ) ( p q r)m3m7，此即公式的主析取范式，000100000110110101101011111110001011 :010 10111001011110101由真值表可

5、以看出成真赋值的情况有7 种，此 7 种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式m1m2m3m4m5m6g习题三及答案：(P52-54)11、填充下面推理证明中没有写出的推理规则。前提： p q, q r,r s, p结论：s证明：1p前提引入2pq前提引入3q析取三段论4qr前提引入5r析取三段论6r s前提引入7s假言推理15、在自然推理系统 P 中用附加前提法证明下面推理:(2)前提：(p q) (r s),(s t) u结论：p u证明：用附加前提证明法。1p 附加前提引入 p q附加(p q)(r s)前提引入r s假言推理s化简 s t附加(s t)u前提引入u假言

6、推理故推理正确。16、在自然推理系统 P 中用归谬法证明下面推理： (1)前提： pq， r q，rs结论： p证明：用归谬法1p 结论的否定引入2pq 前提引入3q 假言推理4rq前提引入5r析取三段论6rs前提引入7r化简8rr合取由于 rr 0 ，所以推理正确。17、在自然推理系统 P 中构造下面推理的证明：只要 A 曾到过受害者房间并且 11 点以前没离开，A 就是谋杀嫌犯。A 曾到过受害者房间。如 果 A 在11 点以前离开，看门人会看见他。看门人没有看见他。所以，A 是谋杀嫌犯。解：设 p: A 到过受害者房间，q： A 在 11 点以前离开，r： A 是谋杀嫌犯，s：看门人看见过

7、 A。合取引入(p q) r前提引入r假言推理则前提：(pq) r， p ， q s，s结论：r证明： q s前提引入s前提引入 q拒取式p前提引入习题四及答案： ( 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(

8、G(y) H(x, y)9 9、给定解释 I I 如下:(a)(a) 个体域为实数集合 R R。(b)(b) 特定元素a 0。(c)(c) 函数f (x,y) x y,x,y R。(d)(d) 谓词F(x,y):x y,G(x,y):x y,x,y R。给出以下公式在 I I 下的解释，并指出它们的真值:(2)x y(F(f (x,y),a) G(x, y)解：解释是：x y(x y 0 x y)，含义是：对于任意的实数 x x, y y,若 x-y=0 x-y=0 则 xyx=2 ；(2)r(R)=R UIA.1,5 ,：2,5；,；3,1 , 3,3 , 45：,；1,T ,2,2；, 4

9、,4 , 5,5 ,：6,6,s(R) RUR11,5,5,1,25,52,3,1, 1,3 注 3,3 , 4,5 / 5,4.t(R) R U R2UR3U. R U R2；1,5 , 2,5 , . 3,1 ,；3,3. ,：3,5 , 4,5：46、分别画出下列各偏序集:A,R ；的哈斯图，并找出 A 的极大元、极小元、最大元和最小元。(1)R：a,d, ac；a,b , ae,：b,e：c,e,：d,e UIA解:(1)R 是反自反的，不是自反的;1 1 2 2解：哈斯图如下：A 的极大元为 e、f，极小元为 a、f;A 的最大元和最小元都不存在。48、设A, R 和 B,S 为偏序

10、集，在集合 A B 上定义关系 T 如下：ahrab；A B,a1,b. T :a2, b2：a1Ra2dSR证明 T 为 A B 上的偏序关系。证明：(1)自反性：任取 A B,贝 U:Q R 为偏序关系，具有自反性，aiRaiQS 为偏序关系，具有自反性，b1Sb1aiRai biSbi又 a.T a2,p：aiRa2Sb，：aI, T ai,bi.，故 T 具有自反性(2) 反对称性：任取:ai,d Tad：A B，若冃,b旦应且丑,鸟订：冃,，则有:aIRa2dSR(i)a2Ra b2Sb(2)aIRa2a2Rai，又 R 为偏序关系，具有反对称性，所以 aia2asp b2Sb,又

11、S 为偏序关系，具有反对称性，所以 bib2ai,b:a2,b2；：，故 T 具有反对称性e ea ad dO(3) 传递性：任取 ,biJa2,b2；,a3,bs,A B，若:db：TQb；：且:a?；T a .,则有：.a1,b1:T a2,b2a1Ra2bjSb,a2,b2；T .a3,b3azRasbzSQa1Ra2a2Ra3,又 R 为偏序关系，具有传递性，所以a1Ra3b1St2dSR,又 S 为偏序关系，具有传递性，所以b1Sb3a1Ra3b1Sb3：a1, biT:a3,b3；，故 T 具有传递性。综合（1） （2） （3）知 T 具有自反性、反对称性和传递性，故T 为 A B

12、 上的偏序关系习题九及答案：（P179-180）8、S=Q Q,Q 为有理数集，为S 上的二元运算，：ab；,：x,y S 有：a,b x,y：:ax,ay+b ;（1）运算在 S 上是否可交换、可结合？是否为幕等的？（2）运算是否有单位元、零元？如果有，请指出，并求出S 中所有可逆元素的逆元解: （ 1）X, y. ab； xa,xb+y :.:ax,bx+y,：；a,b :x, y运算不具有交换律x，r .a,b :：c,dax,bx+y； ：c,d；：:acx,adx+bx+y而 x,y. a,b c,dx, y * ac,ad+b.:xac,xad+xb+y；: acx,adx+bx+

13、y:x,y；a,b c,d运算有结合律任取，;a,b s,则有：:a,b a,b :；a2, ad b；a,b；运算无幕等律(2)令；ab *：x, y.；a,b：对a，s 均成立贝 V 有：:.ax,ay+b:a,b；对a,bs 均成立ax aa x 10对a,b 成立ay b bay 0必定有0 x1y0y0运算的右单位元为1,0，可验证,也为 运算的左单位元，运算的单位元为：1,0：令；ab-*x,y.；x, y，若存在,y 使得对:a,b s 上述等式均成立,则存在零元，否则不存在零元。由 a,b；*：x,y；:x,yax,ay+b；:x, y；ax xa 1 x 0ay b y a

14、1 y+b 0由于 a 1 y+b 0 不可能对：a,b s 均成立，故:a,b*；：x,y：；x, y；不可能对a,b s 均成立，故不存在零元；设兀素（a,b）的逆兀为（x, y），则令（a,b*（x, y） e（1,0）ax 1ay b 0当 a 0 时，a,b 的逆元不存在；当 a 0 时,（a，b 的逆元是（丄，-aa1x -a(当 a 0) by -a11设 S 1,2,10，问下面的运算能否与 S 构成代数系统:S，?如果能构成代数系统则说明运算是否满足交换律、结合律，并求运算的单位元和零元。(3)x y二大于等于 x 和 y 的最小整数；解：(3)由*运算的定义可知：x y二m

15、ax(x,y),x,y S,有 x y S,故 运算在 S 上满足封闭性，所以运算与非空集合 S 能构成代数系统；任取 x,y S,有 x y=max(x,y)=max(y,x)=yx,所以 运算满足交换律；任取 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)=1x,所以 运算的单位元是 1 ；任取 x S，有 x 10=max(x,10)=10=max(10,x)=10 x,所以 运算的零元是 10 ；16、设 V1:

16、; 1,2,3 , ,1,其中 x y 表示取 x 和 y 之中较大的数。V2: 5,6 , ,6；，其中 x y 表示取 x 和 y 之中较小的数。求出 VV2的所有的子代数。指出哪些是平凡的子代数，哪些是真子代数。解：(1)M 的所有的子代数是：f 1,2,3 , ,1；,；1 , ,1 ,f 1,2 , ,i；1,3 , ,1 ；V1的平凡的子代数是：1,2,3 , ,1；,：1 , ,1；V1的真子代数是：f1 , ,1；丄 1,2 , ,1 小 1,3 , ,1 ；(2) V2的所有的子代数是：5,6 ,6：，6 , ,6)；V2的平凡的子代数是：:.5,6 , ,6；，6 , ,6

17、；V2的真子代数是：6 , ,6；：。习题一及答案：(P218-219)1、 图给出了 6 个偏序集的哈斯图。判断其中哪些是格。如果不是格，说明理由解：(a a)、(c c)、(f f)是格；因为任意两个元素构成的集合都有最小上界和最大下界；(b b)不是格，因为d,ed,e的最大下界不存在；(d) 不是格，因为b,cb,c的最小上界不存在；(e) 不是格，因为a,ba,b的最大下界不存在。2 2、 下列各集合低于整除关系都构成偏序集，判断哪些偏序集是格。(1) L=L=1 1, 2 2, 3 3，4 4, 5 5；(2) L=L=1 1, 2 2, 3 3，6 6，1212；解：画出哈斯图即

18、可判断出：(1 1 )不是格，(2 2)是格。4 4、设 L L 是格，求以下公式的对偶式：(2 2)a (b c) (a b) (a c)解：对偶式为：a (b c) (a b) (a c)，参见 P208P208 页定义。9 9、 针对图中的每个格，如果格中的元素存在补元，则求出这些补元。解：(a a)图：a,da,d 互为补元，其中 a a 为全下界，d d 为全上界，b b 和 c c 都没有补元；(c c)图：a,fa,f 互为补元，其中 a a 为全下界，f f 为全上界，c c 和 d d 的补元都是 b b 和 e e，b b 和 e e 的补元都是 c c 和 d d；(f) 图：a,fa,f 互为补元，其中 a a 为全下界，f f 为全上界，b b 和 e e 互为补元，c c 和 d d 都没有补元。1010、说明图中每个格是否为分配格、有补格和布尔格，并说明理由。解：(a a)图：是一条链，所以是分配格，b b 和 c c 都没有补元，所以不是有补格，所以不是布尔格；(c c)图：a,fa,f 互为补元，c c 和 d d 的补元都是 b b 和 e e， b b 和 e e 的补元都是 c c 和 d d，所以任何元素皆有补元，是有补格；Q