离散复习附部分答案.doc

一、范式 1、的主合取范式为 。2、 利用主析取范式，求公式的类型。 解、 它无成真赋值，所以为矛盾式。3、 求命题公式(PQ)(PR)的主合取范式。 解：(PQ)(PR)（(PQ)(PR)）（(PR)(PQ)）（(PQ)(PR)）（(PR)(PQ)）(PQ)(PR)(PR)（QP）（QR）(PQR)(PQR)（PQR）（PQR）M1M3M4M54、 设命题公式G = (PQ)(Q(PR), 求G的主析取范式。 G = (PQ)(Q(PR)= (PQ)(Q(PR)= (PQ)(Q(PR)= (PQ)(QP)(QR)= (PQR)(PQR)(PQR)(PQR)(PQR)(PQR)= (PQR)(PQR)(PQR)(PQR)(PQR)= m3m4m5m6m7 = S(3, 4, 5, 6, 7).5、 通过求主析取范式判断下列命题公式是否等价：(1) G = (PQ)(PQR) (2) H = (P(QR)(Q(PR) G(PQ)(PQR)(PQR)(PQR)(PQR)m6m7m3 (3, 6, 7)H = (P(QR)(Q(PR)(PQ)(QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)m6m3m7 (3, 6, 7) G,H的主析取范式相同，所以G = H.6、用等值演算法和真值表法判断公式的类型。 （1）等值演算法（2）真值表法P QA1 1111111 0010010 1100010 011111所以A为重言式。7、设命题A1，A2的真值为1，A3，A4真值为0，求命题的真值。（5分）8、公式的主合取范式是 二、推理证明1、叙述并证明苏格拉底三段论解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。符号化：F（x）：x是一个人。G（x）：x要死的。A：苏格拉底。命题符号化为x（F（x）G（x），F（a）G（a）证明：（1）x(F(x)G(x) P（2）F(a)G(a) T(1),US（3）F(a) P（4）G(a) T(2)(3),I2、设论域D=a , b , c，求证：。 3、用反证法证明。 4、用CP规则证明。 5、演绎推理：所有的有理数都是实数，所有的无理数也是实数，虚数不是实数。因此，虚数既不是有理数，也不是无理数。6、利用形式演绎法证明：AB, CB, CD蕴涵AD。(1) AD(附加)(2) ABP(3) BQ(1)(2)(4) CBP(5) BCQ(4)(6) CQ(3)(5)(7) CDP(8) DQ(6)(7)(9) ADD(1)(8)所以 AB, CB, CD蕴涵AD.7、P（附加前提）TIPTITITIPTICP8、P（附加前提）USPUSTIUGCP9、所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。证明：设P(x)：x 是个舞蹈者； Q(x) ：x很有风度； S(x)：x是个学生； a：王华上述句子符号化为：前提：、 结论： 3分PPUSTI TITITIEG10、符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证其结论。解： 证明：PESTITIPUSTITEUSUSTIUG11、符号化语句：“有些病人相信所有的医生，但是病人都不相信骗子，所以医生都不是骗子”。并推证其结论 解：F(x)：x是病人，G(x)：x是医生，H(x)：x是骗子，L(x,y)：x相信y符号化：前提：结论：PESTITIPUSTITEUSUSTIUG3、 集合1、已知A、B、C是三个集合，证明A(BC)=(AB)(AC)证明：x A（BC） x Ax（BC） x A（xBxC）（ x AxB）（x AxC） x（AB）x AC x（AB）（AC） A（BC）=（AB）（AC）2、1设 （N：自然数集，E+ 正偶数） 则 0，1，2，3，4，6； 。3、A，B，C表示三个集合，文图中阴影部分的集合表达式为 A B C 。4、= 。5、集合的幂集= 。并搜集为 ，交搜集为 6、 4、 二元关系1、 设A=2，3，4，5，6上的二元关系，则R= , （列举法）。R的关系矩阵MR= 。2、设集合A= a ,b , c , d 上关系R= , , , 要求 1、写出R的关系矩阵和关系图。（4分） 2、用矩阵运算求出R的传递闭包。（6分）； 关系图2、 t (R)= , , , , , , , , 。3、设R和S是集合Aa, b, c, d上的关系，其中R(a, a),(a, c),(b, c),(c, d), S(a, b),(b, c),(b, d),(d, d).(1) 试写出R和S的关系矩阵；(2) 计算RS, RS, R1, S1R1. 解、 (1) (2)RS(a, b),(c, d),RS(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d), R1(a, a),(c, a),(c, b),(d, c),S1R1(b, a),(d, c). 4、设Aa，b，c，d，R是A上的二元关系，且R，求r(R)、s(R)和t(R)。解 r(R)RIA，s(R)RR-1，R2，R3，R4，R2t(R)，5、设R是集合A = a, b, c, d. R是A上的二元关系, R = (a,b), (b,a), (b,c), (c,d),(1) 求出r(R), s(R), t(R)；(2) 画出r(R), s(R), t(R)的关系图.(1) r(R)RIA(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d),s(R)RR1(a,b), (b,a), (b,c), (c,b) (c,d), (d,c),t(R)RR2R3R4(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)；(2)关系图:6、已知A=1,2,3,4,5和R=,，求r(R)、s(R)和t(R)。解：r(R)=,s(R)=,t(R)=,7、集合上的关系，写出关系矩阵，画出关系图并讨论R的性质。 解： R的关系图为 R是自反、对称的。8、设A=，1，1，3，1，2，3则A上包含关系“”的哈斯图为9、设S=1 , 2 , 3 , 4, 6 , 8 , 12 , 24，“”为S上整除关系，问：（1）偏序集的Hass图如何？（2）若，求的极小元、最小元、极大元、最大元，上界，上确界，下界，下确界=,，,covS=, ,10、设A=1，2，3，4，5，A上的偏序关系为求A的子集3，4，5和1，2，3，的上界，下界，上确界和下确界，极大、极小元，最大最小元。11、集合上的偏序关系为整除关系。设，试画出的哈斯图，并求A，B，C的最大元素、极大元素、下界、上确界。 解：的哈斯图为集合最大元极大元下界上确界A无24，36无无B12126，2，312C66无612、设集合A1, 2, 4, 6, 8, 12，R为A上整除关系。(1) 画出半序集(A,R)的哈斯图；(2) 写出A的最大元，最小元，极大元，极小元；(3) 写出A的子集B = 4, 6, 8, 12的上界，下界，最小上界，最大下界.解 (1) (2) 无最大元，最小元1，极大元8, 12; 极小元是1.(3) B无上界，无最小上界。下界1, 2; 最大下界2.13、设集合A1, 2, 3, 4, 6, 8, 9, 12，R为整除关系。（1）画出半序集(A,R)的哈斯图；（2）写出A的子集B = 3,6,9,12的上界，下界，最小上界，最大下界；（3）写出A的最大元，最小元，极大元，极小元。 (1)(2) B无上界，也无最小上界。下界1, 3; 最大下界是3.(3) A无最大元，最小元是1，极大元8, 12, 90+; 极小元是1.14、设A=a,b,c,d，A上的二元关系R=,，求R所诱导的等价关系，并求出等价关系中各元素的等价类。15、设X=1,2,3,4,5，X上的关系R= , , , , ，求R所诱导的等价关系，划分等价类并求秩16、设A=1，2，3，4，S=1，2，3，4，为A的一个划分，求1）由S导出的等价关系。2）求五、图论1、已知：D=，V=1,2,3,4,5，E=,，求D的邻接距阵A和可达距阵P。解：D的邻接距阵A和可达距阵P如下：01010111110010011111A=00011P=11111000000000010000111112、给定图G如图所示，（1）G中长度为4的路有几条？其中有几条回路？（2）写出G的可达矩阵。3、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。解： 用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：树权C(T)=23+1+4+9+3+17=57即为总造价。4、求图的可达性矩阵，并求图的强分图，弱分图，单向分图 5、下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。 图中奇数点为E、F ，d(E)=3,d(F)=3,d(E,F)=28 p=EGF复制道路EG、GF，得图G，则G是欧拉图。由D开始找一条欧拉回路：DEGFGEBACBDCFD。道路长度为：35+8+20+20+8+40+30+50+19+6+12+10+23=2816、求带权图G中的最优投递路线。邮局在v1点。解：图中有4个奇数结点，（1） 求任两结点的最短路再找两条道路使得它们没有相同的起点和终点，且长度总和最短：（2） 在原图中复制出，设图G，则图G中每个结点度数均为偶数的图G存在欧拉回路，欧拉回路C权长为43。7、已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。答案：二叉树形态 8、画出与下图所示的森林相对应的二叉树，并指出森林中的叶子结点在二叉树中具有什么特点。已知有向图G如下所示，根据迪杰斯特拉算法求顶点v0到其他顶点的最短距离。（给出求解过程）答案：终点从v0到各终点的d值和最短路径的求解过程i=1i=2i=3i=4v112 (v0,v1)12 (v0,v1)7 (v0,v4,v1)v24 (v0,v2)v39 (v0,v3)8 (v0,v2,v3)7 (v0,v4,v3)7 (v0,v4,v3)v45 (v0,v4)5 (v0,v4)vjv2v4v1v3sv0,v2v0,v4v0,v4,v1v0,v4,v36、已知图G如下所示，根据Prim算法，构造最小生成树。（要求给出生成过程）答案：prim算法求最小生成树如下：已知图G如下，根据克鲁斯卡尔算法求图G的一棵最小生成树。（要求给出构造过程）答案：kruskal算法的最小生成树 12、已知图G如下所示，求从顶点a到其余各顶点的最短路径。（给出求解过程）543223356abdfce答案：终点最短路径求解过程b6 (a,b)5 (a,c,b)c3 (a,c)d6 (a,c,d)6 (a,c,d)e7 (a,c,e)7 (a,c,e)7 (a,c,e)f9 (a,c,d,f)9 (a,c,d,f)vjcbdefSa,ca,c,ba,c,da,c,ea,c,d,f5、 函数1、 设 f，g是自然数集N上的函数，则 2(x+1) 。2、确定下列函数的类型(1)设定义如下：满设 （2）设定义为：单射 (3)设定义为：双射 3、判断下列函数的类型设定义如下：(1)单非满(2)满非单(3)双射