离散数学形成性考核作业

离散数学形成性考核作业4离散数学综合练习书面作业要求：学生提交作业有以下三种方式可供选择：1.可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅．2.在线提交word文档．3.自备答题纸张，将答题过程手工书写，并拍照上传．一、公式翻译题1．请将语句“小王去上课，小李也去上课．”翻译成命题公式．设P：小王去上课。Q:小李去上课。则P^Q2．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．设P：他去旅游。Q:他有时间。则P→Q3．请将语句“有人不去工作”翻译成谓词公式．设A(x):x是人B(x):去工作x(A(x)^B(x))4．请将语句“所有人都努力学习．”翻译成谓词公式．设A(x):x是人B(x):努力工作x(A(x)^B(x))姓名：学号：得分：教师签名：二、计算题1．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算（1）(A?B)；（2）(A∩B)；（3）A×B．解：（1）（A?B）={{1},{2}}（2）（A∩B）={1,2}(3)A×B{{1},1,{1},2,{1},{1,2},{2},1,{2},2,{2},{1,2},1,1,1,2,1,{1,2},2,1,2,2,2,{1,2}}2．设A={1，2，3，4，5}，R={x，y|x?A，y?A且x+y?4}，S={x，y|x?A，y?A且x+y0}，试求R，S，R?S，S?R，R-1，S-1，r(S)，s(R)．解：R={1,1,1,2,1,3,2,1,2,2,3,1}S=ΦR?S=ΦS?R=ΦR-1={1,1,2,1,3,1,1,2,2,2,1,3}S-1=Φr(S)={1,1,2,2,3,3,4,4,5,5}s(R)={1,1,1,2,1,3,2,1,2,2,3,1}3．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}．(1)写出关系R的表示式；(2)画出关系R的哈斯图；(3)求出集合B的最大元、最小元．解：(1)R={1,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8,2,2,2,4,2,6,2,8,3,3,3,6,4,4,4,8,5,5,6,6,7,7,8,8}(2)(3)集合B没有最大元，最小元是24．设G=V，E，V={v1，v2，v3，v4，v5}，E={(v1,v3)，(v2,v3)，(v2,v4)，12346578关系R的哈斯图(v3,v4)，(v3,v5)，(v4,v5)}，试(1)给出G的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数；(4)画出其补图的图形．解：（1）1v°2v°°3v4v°°5v（2）0110010110110110110000100)(DA（3）)deg(1v1、)deg(2v2、)deg(3v4、)deg(4v3、)deg(5v2（4）°1v2v°°3v4v°°5v5．图G=V,E，其中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）。。21a。64213。。e5d（2）0111110110110011100110110)(DA（3）bc。。21a。13。。ed其权值为：76．设有一组权为2,3,5,7,17,31，试画出相应的最优二叉树，计算该最优二叉树的权．解：65174851217312357权值为65。7．求P?Q?R的析取范式，合取范式、主析取范式，主合取范式．解：┐P?(Q∨R）=┐P?Q∨R所以合取范式和析取范式都是┐P?Q∨R所以主合取范式就是┐P?Q∨R所以主析取范式就是(?P??Q??R)?(?P??Q?R)?(?P?Q??R)(?P?Q?R)?(P??Q?R)?(P?Q??R)?(P?Q?R)8．设谓词公式()((,)()(,,))()(,)xPxyzQyxzyRyz．（1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元．解：(1)量词?x的辖域为P(x,y)?(?z)Q(y,x,z)量词?z的辖域为Q(y,x,z)量词?y的辖域为R(y,x)(2)P(x,y)中的x是约束变元，y是自由变元Q(y,x,z)中的x和z是约束变元，y是自由变元R(y,x)中的x是自由变元，y是约束变元9．设个体域为D={a1,a2}，求谓词公式(?y)(?x)P(x,y)消去量词后的等值式；解：?y?xP(x,y)=?xP(x,a1)??xP(x,a2)=(P(a1,a1)?P(a2,a1))?(P(a1,a2)?P(a1,a2))三、证明题1．对任意三个集合A,B和C，试证明：若A?B=A?C，且A?，则B=C．证明：设x?A，y?B，则x，y?A?B，因为A?B=A?C，故x，y?A?C，则有y?C，所以B?C．设x?A，z?C，则x，z?A?C，因为A?B=A?C，故x，z?A?B，则有z?B，所以C?B．故得A=B．2．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．证明：R1和R2是自反的，?x?A，x,x?R1，x,x?R2，则x,x?R1∩R2，所以R1∩R2是自反的．3．设连通图G有k个奇数度的结点，证明在图G中至少要添加2k条边才能使其成为欧拉图．证明：由定理推论知：在任何图中，度数为奇数的结点必是偶数个，则k是偶数。又由欧拉图的充要条件是图G中不含奇数度结点。因此，只要在每对奇数度结点间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图。故最少要加2k条边才能使其成为欧拉图。4．试证明(P?(Q??R))??P?Q与?(P??Q)等价．证：(P?(Q??R))??P?Q?(?P?(Q??R))??P?Q?(?P?Q??R)??P?Q?(?P??P?Q)?(Q??P?Q)?(?R??P?Q)?(?P?Q)?(?P?Q)?(?P?Q??R)??P?Q（吸收律）??(P??Q)（摩根律）5．试证明：?(A∧?B)∧(?B∨C)∧?C??A．证明：①c前提引入；②cb前提引入；③b①②析取三段论；④)(BA前提引入；⑤BA置换；④⑥B③⑤析取三段论。