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

1、离散数学习题答案习题二及答案：(P38)5、求下列公式的主析取范式，并求成真赋值：(2) (-1-9)A(9/r)解：原式 O ( V 夕)八 A O q A - O (-1 V ) 4 A r (r) A7 Ar)v(/? A6/Ar) ?3 V叫,此即公式的主析取范式， 所以成真赋值为Oil，111。 )6、求下列公式的主合取范式，并求成假赋值：(2) (/? A(y)v(-i/?vr)解：原式=(，)(-1 vt/vr) 0(-1 vgvr)此即公式的主合取范式，所以成假鼠值为100。7、求下列公式的主析取范式，再用主析取范式求主合取范式：(1)(P 八 q)7 r解：原式 o /?A7

2、A(-irvr)v(v/?)A(-ivt7)Ar)=(八 4 八厂)v (八 q a r) v (f)a q a r) v (1Ar) v(/? a q Ar)v(pa r) (-1 A xCl A r) V (77 Ar) V(/7 A f Af) V(/7 A Ar) V(/? Af) V 4 v m5 v m6 v ,此即主析取范式。主析取范式中没出现的极小项为?0, m2, m4,所以主合取范式中含有三个极大项M0,加2, “4,故原式的主合取 范式 % aM4 9、用真值表法求下面公式的主析取范式：(1) (/?v)v(-i/? Af) 解：公式的真值表如下：Pqr一pq/7 Ar0

3、001000001101101011010111111100:010110101011100101111010.1由其值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式o m v m2 v v m4 v m5 v 叫 v 啊习题三及答案：（P52-54）11、填充下面推理证明中没有写出的推理规则。前提：I结论：S证明：P前提引入前提引入q析取三段论F7r前提引入r析取三段论r f $ 前提引入）S假言推理15、在自然推理系统P中用附加前提法证明下面推理:（2）前提：（V9）一（r人5），（5丫，）一 结论：一证明：用附加前提证明法。P附加前提引入p

4、vq附加rA5SSV，（sv，）f 假言推理化简附加前提引入（ v夕）一（厂a s）前提引入U假言推理故推理正确.16、在自然推理系统P中用归谬法证明下面推理: ?（1）前提：一r，f7q,八 f 结论：一/，证明：用归谬法p结论的否定引入pff前提引入r假言推理f vq前提引入析取三段论rdf 前提引入化简Air合取 由于，/r = 0,所以推理正确。17、在自然推理系统P中构造下面推理的证明：只要A曾到过受害者房间并且11点以前没惑开，A就是谋杀嫌犯.A曾到过受害者房间。如果A在11点以前离开，看门 人会看见他。看门人没有看见他.所以，A是谋杀嫌犯.解：设p： A到过受宙者房间，q： A在

5、11点以前离开，门A是谋杀嫌犯，S：看门人看见过A.则前提：r, p , qfs,5结论：r 证明： qfs5rpF（八T）（r前提引入前提引入拒取式前提引入合取引入r前提引入假言推理习题五及答案：(P80-81)15、在自然推理系统N；中，构造下面推理的证明(3)前提：Vx(F(x)vG(x), -3xG(x)结论：BxF(x)证明：-dxG(x) VxG(x)-G(c) Va(F(x)vG(x) F(c) v G(c) F(c) BxF(x)前提引入置换UI规则前提引入UI规则析取三段论EG规则22、在自然推理系统N；中，构造下面推理的证明:(2)凡大学生都是勤奋的。王晓山不勘奋。所以王晓

6、山不是大学生。解：设F(X)： x为大学生，G(x)：想是勤奋的，c：王晓山则前提:V.r(F(x)G(x), -iG(c)结论：尸(c)证明:Vx(/(x)f G(x)前提引入尸(c) -G(c)ui规则前提引入G(c)拒取式25、在自然推理系统中，构造下面推理的证明：每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功.王大海是科学工作者，并且是 聪明的所以，王大海在他的事业中将获得成功.(个体域为人类集合)解,设F(x)： x是科学工作者，G(x)： x是刻苦钻研的，H(x)： x是聪明的，l(x)： x在他的事业中获得成功，c：王大海则前提：Vx(/(x)f

7、G(x), Vx(G(x)八(x)f/(x), F(c)a/7(c)结论:/(c) F(c)a/7(c) F(c) H(c) Va(F(x)G(x) F(c)G(c) G(c) G(c)a(c)证明：前提引入化简化简前提引入UI规则假言推理合取引入 Vx(G(x) a H(x) - Z(x 前提引入 G(c)/H(c)/(c)ui 规则/(c)假言推理习题七及答案：(P132-135)22、给定 A = 1,2,3,4, A 上的关系 R = (1,3)。4M2,3),(2,4,(3,4,试(1)画出R的关系图；(2)说明R的性质。1解：(2) R的关系图中每个顶点都没有自环，所以R是反自反的

8、，不是自反的；R的关系图中任意两个顶点如果有边的都是单向边，故R是反对称的，不是对称的； R的关系图中没有发生顶点x到顶点y有边、顶点y到顶点z有边，但顶点x到顶点z没有边的情况，故R是 传递的.26设A = 1,2,3,4,5,6, R为A上的关系，R的关系图如图所示：(1)求的集合表达式；(2)求r(R),s(R),t(R)的集合表达式。解：(1)由 R 的关系图可得K = (1,5),2,5),(3,1),3,3),4,5)所以斤=/?。=(3,1,3,3,3,5),=,可得, = 3,1),3,3,(3,5),当 n=2:(2) r(R)=R UIA = 1,5),(2,5),(3,1

9、),(3,3),(4,5), (1,1),(2,2),(4,4),(5,5), (6,6),Gs(R) = R U 内=(L 5),(5,1),(2,5),(5,2),(3,1),(1,3),(3,3),(4,5),(5,4)f(R) = R U 代 U R，U =R U a=L 5),2,5,3,(4,5,(3,5)46、分别画出下列各偏序集(A, Rj的哈斯图，并找出A的极大元、极小元、最大元和最小元。(1) &=,但e,e)U【A解：哈斯图如下:eA的极大元为e、极小元为a；A的最大元为e、最小元为a.48、设和(B,S)为偏序集，在集合AxB上定义关系T如下：AxB,(%，4)丁(小也

10、) = aRa2 八Sb?证明T为AxB上的偏序关系.证明：(1)自反性：任取(q，4)AxB,则：,R为偏序关系,具有自反性,.4RqS为偏序关系,具有自反性,.bSb/. qRq AbjSb,又i，b)T也八ASb?,:.回b)T3b),故T满足自反性(2)反对称性：任取(，口包也)eAxB,若i，b)T他也且他也7i，b),则有: axRa 八bSb,( 1)a2R% 八b?Sb(2):.aiR%八%Rai，又R为偏序关系,具有反对称性,所以q =%：bSbSb,又S为偏序关系，具有反对称性，所以b|=b,.,盼=他也，故T满足反对称性(3)传递性：任取也)，也e AxB,若&也)且生也

11、丁的也)，则有: (ai，b)T他也=axRa2 /bxSb2(外也)7小/) = /R%人45么.阳/人的夫叼乂口为偏序关系，具有传递性，所以。曲3.山韵2人仇55,乂5为偏序关系，具有传递性，所以bSb3A b,Sb3 =神幻r他也)，故T满足传递性。综合(1)(2)(3)知T满足自反性、反对称性和传递性，故T为AX B上的偏序关系。习题九及答案：(P179-180)8、S=QxQ,Q为有理数集,*为S上的二元运算,V(a,b),(x,y) e S有(a,b) * (x,y) = (ax,ay+b)(1) *运算在s上是否可交换、可结合？是否为幕等的？(2) *运算是否有单位元、零元？如果

12、有，请指出，并求出S中所有可逆元素的逆元.解：(1)x,y*a,b)= (xa,xb+y)=(ax,bx+y)*(a,b)* (a y).*运算不具有交换律=(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，*a，b)*c，d).J运算有结合律任取g,bes,则有：(a,b) * (a,b)= (a? ,ad + /?)=(a,b)运算无暴等律(2)令a,b*x,) = (a,b)对 V (a,b)e s 均成立 则有:ax,ay+b)=a,b)对V(a,b

13、)e s均成立 ,ax = a =卜(x-l) = 对仪通)成立ay + b = b ay = 0，必定有x-1 = 0y = 0.J运算的右单位元为1,0，可验证1,0也为*运算的左单位元, 二.*运算的单位元为1,0)令(a,b)*(x5 y) =x, y)，若存在y)使得对V(a,b)e s上述等式均成立, 则存在零元，否则不存在零元。由(a,b)*(x, =(%,)=(ax,ay+b) = (x, y)ax = x (a-l)x =0ay + b = y (a-1) y+b = 0由于(a -1) y+b =。不可能对V (a,b) e s均成立，故(a,b* (x,) = (x, y

14、)不可能对V(a,b) e s均成立，故不存在零元；设元素阿b的逆元为 y),则令(a,b*x,y) = e = (1,0)ax = 1ay + b = 012(当aWO) by = 一一a当a = OW,a,b)的逆元不存在；当aWO时,(a,b)的逆元是(；,-胃11设5 = 1,2, .,10,问下面的运算能否与S构成代数系统S,*？如果能构成代数系统则说明*运算是否满足交换律、结合律，并求*运算的单位元和零元。(3) 乂*丫=大于等于x和y的最小整数;解：(3)由*运算的定义可知：X * y=max(x,y), x,yeS,有x*yeS,故*运算在S上满足封闭性，所以*运算与非空集合S

15、能构成代数系统；任取x,y e S,有x * y=max(x,y)=niax(y,x)=y * x,所以*运算满足交换律：任取x,y,z eS,有(x *y)*z=max(max(x,y),z)=max(x,y,z)=max(x,max(y,z)=x *(y *z),所以*运算满足结合律;任取x eS,有x * 1 =max(x, 1 )=x=max( 1 ,x)=l*x,所以*运算的单位元是1；任取x eS,有x *10=max(x,10)=10=max(10,x)=10*x,所以*运算的零元是 10：16、设Y =61,2,3,。),其中X。)，表示取x和y之中较大的数。V2=(5,6,*

16、6), 其中表示取x和y之中较小的数。求出Y和V?的所有的子代数。指出哪些是平凡的子代数，哪些是真子代数。解:(1) Y的所有的子代数是:1,2,3,。,1),(1,。,1),1,2卜。,(1,3,。,1)； Y 的平凡的子代数是Y 的真子代数是:(2) V2的所有的子代数是：(5,6,*,6(6,*,6)；%的平凡的子代数是:5,6,*,6),(6,*,6)；V?的真子代数是：(6,*,6)。习题十一及答案：(P218-219)1、图给出了 6个偏序集的哈斯图。判断其中哪些是格。如果不是格，说明理由解：(a)、(c)、(f)是格；因为任意两个元素构成的集合都有最小上界和最大下界；(b)不是格

17、，因为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是格，求以下公式的对偶式：(3) 6/ v (Z? a c) (6/ A Z?) V A C),参见 P208 页定义。9、针对图中的每个格，如果格中的元素存在补元，则求出这些补元.解：(a)图：a,d互为补元，其中a为全下界，d为全上界，b和c都没有补元；(O图：a,f互为补元，其中a为全下界，f为全上界，c和d的补元都是b和e, b和e的补元都是c和d；(0图：a,f互为补元，其中a为全下界，f为全上界，b和e互为补元，c和d都没有补元。10、说明图中每个格是否为分配格、有补格和布尔格，并说明理由。解：(a)图：是一条链，所以是分配格，b和c都没有补元，所以不是有补格，所以不是布尔格；(O图：a,f互为补元，c和d的补元都是b和e, b和e的