离散数学形成性考核作业

1、离散数学形成性考核作业4姓名:学号:得分:教师签名：离散数学综合练习书面作业要求：学生提交作业有以下三种方式可供选择：解答题要有1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整,解答过程，完成作业后交给辅导教师批阅.2. 在线提交word文档.3. 自备答题纸张，将答题过程手工书写，并拍照上传.一、公式翻译题1 请将语句“小王去上课，小李也去上课”翻译成命题公式.设P:小王去上课。Q:小李去上课。则PAQ2 请将语句“他去旅游，仅当他有时间”翻译成命题公式.设P:他去旅游。Q:他有时间。则PQ3 请将语句“有人不去工作”翻译成谓词公式.设A(x):x是人B(x):去工作x(A(x)a

2、B(x)4 请将语句“所有人都努力学习”翻译成谓词公式.设A(x):x是人B(x):努力工作x(A(x)ab(x)二、计算题1设A=1,2,1,2,B=1,2,1,2，试计算(1)(A?B);(2)(AHB);(3)AXB.解：(1)(A?B)=1,2(2)(AHB)=1,2(3)AXB,v2,2,v2,1,22.设A=1,2,3,4,5,R=|x?A,y?A且x+y?4,S=|x?A,y?A且x+y0，试求R,S,R?S,S?R,R1,S1,r(S),s(R).解：R=,S=OR?S=oS?R=R=,S-1=Or(S)=,v3,3,v4,4,v5,5s(R=,3.设A=1,2,3,4,5,6

3、,7,8,R是A上的整除关系，B=2,4,6(1)写出关系R的表示式；(2)画出关系R的哈斯图；(3)求出集合B的最大元、最小元.解：(1)R=,7关系R的哈斯图(3)集合B没有最大元，最小元是24. 设G=,V=V1,V2,V3,V4,V5,E=(V1,V3),(V2,V3),(V2,v,(V3,V4),(V3,V5),(V4,V5)，试给出G的图形表示；(2)写出其邻接矩阵；画出其补图的图形.解：(1)00ViV30010000110(2)A(D)110110110100110V4deg(Vj(3)1、deg(V2)2、degM)4、degS)3、deg(Vs)2oV2o(3)求出每个结点

4、的度数；(4)oV45图G=,其中V=a,b,c,d,e,E=(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(c,d),(d,e)，对应边的权值依次为2、1、2、3、6、1、4及5,试(1)画出G的图形；(2)写出G的邻接矩阵；(3)求出G权最小的生成树及其权值.bc解：(1)。0110110011(2)A(D)10011011011111C(3)bcooooed其权值为：76设有一组权为2,3,5,7,17,31，试画出相应的最优二叉树，计算该最优二叉树的权.解：652357权值为657. 求P?Q?R的析取范式，合取范式、主析取范式，主合取范式.解：门P?(QVR

5、=nP?6R所以合取范式和析取范式都是门P?Q7R所以主合取范式就是门P?Q7R所以主析取范式就是(?P?Q?R)?(?P?Q?R)?(?P?Q?F)(?P?Q?R)?(P?Q?R)?(P?Q?R)?(P?Q?R)8. 设谓词公式(x)(P(x,y)(z)Q(y,x,z)(y)R(y,z).(1) 试写出量词的辖域；(2) 指出该公式的自由变元和约束变元.解：量词?x的辖域为P(x,y)?(?z)Q(y,x,z)量词?z的辖域为Q(y,x,z)量词?y的辖域为R(y,x)P(x,y)中的x是约束变元，y是自由变元Q(y,x,z)中的x和z是约束变元，y是自由变元R(y,x)中的x是自由变元，y

6、是约束变元9设个体域为D=ai,a2，求谓词公式(?y)(?x)P(x,y)消去量词后的等值式；解：？y?xP(x,y)=?xP(x,ai)?xP(x,a2)=(P(ai,a1)?P(a2,a1)?(P(ai,a2)?P(ai,a2)三、证明题1.对任意三个集合AB和C,试证明：若A?B=A?C,且A?，贝UB=C.证明：设x?A,y?B,则?A?B,因为A?B=A?C,故?A?C,则有y?C,所以B?C.设x?A,z?C,则?A?C,因为A?B=A?C,故?A?B,则有z?B,所以C?B.故得A=B2.试证明：若R与S是集合A上的自反关系，则RAS也是集合A上的自反关系.证明：Ri和R是自反的，？x?A,?Ri,?R，则?RGR,所以RiAF2是自反的.k3.设连通图G有k个奇数度的结点，证明在图G中至少要添加-条边才能使其2成为欧拉图.证明：由定理推论知：在任何图中，度数为奇数的结点必是偶数个，则k是偶数。又由欧拉图的充要条件是图G中不含奇数度结点。因此，只要在每对奇数度结点间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图。故最少要加k条边才能使其成为欧拉图。24.试证明(P?(Q?R)?P?Q与？(P?Q等价.证：(P?(Q?$)?P?Q?(?P?(Q?R)?P?Q?(?P?Q?R)?P?Q?(?P?P?Q?(Q?P?Q?(?R?P?Q?