离散数学复习材料

《离散数学复习材料》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、离散数学复习材料1.（10分）求「（P/X0）分「（「Pt/?）的主析取范式与主合取范式。解「（"OoTiPtT?）o(「(PAQ)T十PT/?))A(「(「P->/?)T7PA2))（1分，这里等价式的变换用其他方法也正确）<=>((PaQ)V-!(-!?T/?))A((「PT/?)V「(PA2))O((PAQ)V(iPA「/?))A((PV/?)V(iPV「0))U>(PV-}R)A(-1PV2)A(2V—)/?)OJP7Q7—i/?)A(PV-yQV—>/?)A(~iPV(?V/?)A(-iPV2V—i/

2、?)A(PVQV—)/?)A(~iPVQv-i/?)（1分）（1分）（1分）（1分）oM]/M3aA/4aM5（2分）<=>加()vm2v加§vm7（1分）U>(-iPA-yQA-i/?)V(-iPAgA-i/?)V(PAgA-i/?)V(PAgA/?)（2分）（说明：若用真值表做，真值表正确共6分，结果每个2分，共4分；屮间步因为笔误出错，方法思路正确的扣2分）2.（15分）在谓词逻辑中构造下面推理的证明：“前提：每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车，有的人不喜欢骑白行车。结

3、论：有的人不喜欢步行。”解：论域：所有人的集合。A（X）：X喜欢步行；3（兀）：兀喜欢坐汽车；C（X）:X喜欢骑自行车；则推理化形式为：（每个题设正确得1分）VX（4（%）->-!«（%））,Vx（«（x）VC（x））,-）VXC（x）l~3X-yA（X）（2分）下面给出证明：（下面每步1分，共10分）(1)-10Xc(x)P(2)3x->c(x)T(l),E(3)「C(c)T(2),ES⑷X/x(^(x)Vc(x))P(5)B(c)VC(c)T(4),US⑹B(c)T(3)(5),I(7)VX(4(X)->-

4、)〃(X))P⑻A（C）T「B（C）T(7),US(9)-4(C)T(6)(8),I(10)3x-iA(x)T(9),EG3.（15分）设正整数的序偶集合A,在A上定义的一个二元关系R如下：«x,y>,,<1,2>,<1,3>,<2,1>,<2,2>,<2,4>,<2,6>,<4,1>,<4,2>},试写出R所决定的人上的划分。（5分）证明：（1）xv=yw<=>—=—（3分）（3分）（4分）a.白反性xXV

5、>eA,—=—<=>Ryyb.对称性RRyvvyc・传递性若R,则且£=£,显然，-=即va,h>Rhddfbf（2）{{<1,1>,v2,2>},{<1,2>,<2,4>},{vl,3>,<2,6>},{<2,1>,<4,2>},{<4,1>}}（5个分块各1分，共5分）4.（15分）设函数/：RXRtRXR,/定义为：/«x,y»=.（1）证明/是单射。（2）证明/是满射。证明

6、：（1）对任意的兀,y,兀1,y£R,若/«x,y>）=f«xi,y】>）,贝ij=,x+y=x+yi,兀一y=xi—）“，从而兀=»,y=y】，故于是单射。（5分，写出单射定义的给2分）（2）对任意旳W〉GRXR,令兀=,y=,则/（=2222225,w>,所以/是满射。（5分，写岀满射定义的给2分）5.（10分）设/是所冇整数的集合，在/上定义运算*如下：Vx,yw/,x*y=x+y-2证明：是群。（3分）（2分）（3分）Vx,y

7、e/,兀*y=兀+y—2w/b.结合性Vx,y,ze/,（兀*y）*z=（兀*y）+z_2=兀+y+z_2x*（y*z）=x+（y*z）_2=x+y+z_2故，O*y）*z=x*（y*z）a.单位元是2b.Pxwl,x的逆元存在，为x~]=4-xe/6.（15分）设是一个群,这里+6是模6加法,Z6={[0],[1],[2],[3L[4],[5]}o（1）试写出的每个了群；（6分）⑵写出每个子群的左陪集形成的划分；（6分）⑶是否构成循环群？若是，试写出所冇生成元。（3分

8、）（1）1阶子群:<{[0]},+6>（1分）2阶子群：v{[0],[3]},+6>（2分）3阶了群：<{[0],[2],[4]},+6>（2分）6阶子群：（1分）⑵1阶子群：{{⑹},{[1]},{[2]},{[3]},{[4]},{[5]}}（1分）2阶子群：{{[0],[3]},{[1],[4]},{[2],[5]}}（2分）3阶子群：{{[0],[2],[4]},