东大《离散数学X》离线考核

学习中心： 院校学号： 姓名 东 北 大 学 继 续 教 育 学 院 离散数学X 试 卷（作业考核 线上2） A 卷（共 4 页） 总分题号一二三四五六七八九十得分一. (13分)有两个小题。1分别说明联结词、和在自然语言中表示什么含义。解：“”表示“不成立”，“不”。“”表示“并且”、“不但而且.”、“既又 .”等。“”表示“或者”， 是可兼取的或。“”表示 如果 ，则 ；只要 ，就 ； 只有 , 才； 仅当 。“”表示“当且仅当”、“充分且必要”。2分别列出PQ、 PQ、PQ 、PQ的真值表(填下表)。PQPQPQPQPQ解：PQPQPQPQPQFFTFTFFTFTTFTFFTFFTTTTTT二. (10分) 1.指出下面的命题公式中哪些是永真式(1、2、3)。 (1). (P(PQ)Q (2). P(PQ) (3). (PQ)Q (4). (PQ)P2.然后对上面的永真式任选其中一个给予证明(方法不限)。解：证明公示3：设前件（PQ）为真，则得Q为真。所以，(PQ)Q是永真式。3.上面哪个不是永真式（找出一个即可），请说明它为什么不是永真式。解：(PQ)P不是永真式。三. (14分) 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。 "x(B(x)C(x), $xA(x), "x(A(x)C(x) $xB(x)解：(1)$xA(x) P(2)A(a) ES(1)(3)"x(A(x)C(x) P(4)A(a)C(a) US(3)(5)C(a) T(2)(4) I(6)"x(B(x)C(x) P(7)B(a)C(x)v US(6)(8)B(a) T(5)(7) I(9)$xB(x) EG(8)四(12分) 令全集E=1,2,A=1, P(A)表示集合A的幂集。（注意：要求有计算过程，不能直接写出计算结果！）1. 指出 P(E)和P(A)各有多少个元素。即求|P(E)|和|P(A)|。解：因为P(E),1,2,1,2所以P(E)有4个元素。即|P(E)|4。P(A),1所以P(A)有2个元素。即|P(A)|2。2. 计算 P(E)P(A)解：P(E)P(A)P(1,2)P(1),1,2,1,2,12,1,23计算AE解：因为AEA=1,2-1=2AE21,2(21,2)(21,2)1,221五. (25分)给定集合A=1,2,3,定义A上的关系如下： R= AA(完全关系（全域关系）) S=<1,2>,<2,3>,<3,1> T=<1,1>,<1,2>,<2,1>,<2,2>,<3,3> M=<1,1>,<1,2>,<1,3>,<2,2>,<3,3> 1.写出关系S的矩阵；再画出上述各个关系的有向图。解：关系S的矩阵如下：下面是几个关系的有向图：T。132。132M。132R。132S2. 判断各个关系性质。用“”表示“是”，用“”表示“否”，填下表：自反的反自反的对称的反对称的传递的RSTM解：自反的反自反的对称的反对称的传递的RSTM3.上述四个关系中，哪些是等价关系？哪些是偏序关系？对等价关系，写出此等价关系的各个等价类。解：T和R是等价关系。 M是偏序关系。 A/T=1,2,3 A/R=1,2,34.求复合关系SoT解：SoT<1,1>,<1,2>,<2,3>,<3,1>,<3,2>六. (12分) R是实数集合，给出R上的运算如下：、+、min、max、|x-y|,分别表示乘法、加法、两个数中取最小的、两个数中取最大的、x-y的绝对值运算。1. 判断各个运算性质。用“”表示“是”，用“”表示“否”，填下表：min|x-y|+max有交换性有结合性有幂等性有幺元有零元2.指出R对上面哪些运算构成群？.解:1.|x-y|maxmin有交换性有结合性有幂等性有幺元有零元2. 构成半群的有：<R,>， <R,>， <R,max>, <R,min>. 构成独异点的有： <R,>， <R,>。 构成群的有： <R,>。七. (14分) 有三个小题 1. 给定图的集合G=A,B,C,D,E,F,H,K,M,N,R,S,T,V,W,X,Y,其中各个图如下所示，请指出这些图中哪些是彼此同构的。解：同构的有：AR,BD,CMSW,EFTY,H,KX,VN2.图A与图B显然不同构，请说明一个不同构的理由即可。解：同构的充要条件是两图的接点和边分别存在一一对应且保持关联关系。A、B接点不同且不存在一一对应的关系，显然二图不是同构的。3.请画出五个具有五个结点的无向图，使之分别满足： (1) 是棵树。 (2) 既是欧拉图也是汉密尔顿图。(3) 是完全图K5。 (4) 是欧拉图但不是汉密尔顿图。 (5) 是汉密尔顿图但不是欧拉图。解：a)既是欧拉图也是汉密尔顿图。b)是欧拉图但不是汉密尔顿图。c)是汉密尔顿图但不是欧拉图。d)是完全图。e)是棵树。a) b) c） d) e)5离散数学