《通关答案-21年6月考试《离散数学X》考核作业6666》由会员分享，可在线阅读，更多相关《通关答案-21年6月考试《离散数学X》考核作业6666（9页珍藏版）》请在金锄头文库上搜索。
1、学习中心： 院校学号： 姓名 东 北 大 学 继 续 教 育 学 院 离散数学 X 试 卷（作业考核 线上2） A 卷（共 4 页）总分题号一二三四五六七八九十得分-完整答案附后-一、 (13分)有两个小题1分别说明联结词、和在自然语言中表示什么含义。2分别列出PQ、PQ、PQ、PQ的真值表(填下表)。PQPQPQPQPQ二、 (10分)写出命题公式 (QP)Q 的主合取范式。（要求有解题过程）三、(14分) 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。 xC(x), $x(A(x)B(x), x(B(x)C(x) $xA(x)四(12分)令集合A=1,1,B=1
2、，P(A)表示A的幂集。分别计算： （注意：要求有计算过程，不能直接写出结果！）(1) AP(B)(2) AB(3) P(A)P(B)五. (25分)给定集合A=1,2,3,定义A上的关系如下：R=, S=AA(完全关系（全域关系）)T=,M=,1.写出关系R的矩阵；再画出上述各个关系的有向图。2.判断各个关系性质。用“”表示“是”，用“”表示“否”，填下表：自反的反自反的对称的反对称的传递的RSTM3.上述四个关系中，哪些是等价关系？哪些是偏序关系？对等价关系，写出此等价关系的各个等价类。4.求复合关系RoT六. (12分) R是实数集合，给出R上的运算如下：、+、|x-y|、min、max
3、,分别表示乘法、加法、x-y的绝对值、两个数中取最小的、两个数中取最大的运算。1. 判断各个运算性质。用“”表示“是”，用“”表示“否”，填下表：|x-y|max min+有交换性有结合性有幂等性有幺元有零元2.指出R对上面哪些运算构成群？.七. (14分) 有三个小题 1. 指出下面各个图中哪些是彼此同构的.2.上面图b与c显然是不同构的，请说明不同构的理由（说明一个即可。）3.请画出五个具有五个结点的无向图，使之分别满足： (1) 是欧拉图但不是汉密尔顿图。 (2) 既是欧拉图也是汉密尔顿图。 (3) 是完全图K5。(4) 是棵树。(5) 是汉密尔顿图但不是欧拉图 。 完整答案附后答案见一
4、下页 东 北 大 学 继 续 教 育 学 院 离散数学 X 试 卷 （作业考核 线上2） A 卷（共 4 页）总分题号一二三四五六七八九十得分一、 (13分)有两个小题1分别说明联结词、和在自然语言中表示什么含义。解：“”表示“不成立”，“不”。“”表示“并且”、“不但而且.”、“既又 .”等。“”表示“或者”， 是可兼取的或。“”表示 如果 ，则 ；只要 ，就 ； 只有 , 才； 仅当 。“”表示“当且仅当”、“充分且必要”。2分别列出PQ、 PQ、PQ 、PQ的真值表(填下表)。PQPQ PQPQPQ解：PQPQ PQPQPQFFTFTFFTFTTFTFFTFFTTTTTT二、 (10分)
5、写出命题公式 (QP)Q 的主合取范式。（要求有解题过程）解： 方法1：等价变换 (QP)Q (QP)Q ( 去 ) (QP)Q ( 摩根定律 ) Q ( 吸收律 ) (PP)Q （互补、同一律 ） (PQ)(PQ) ( 分配律 )方法2：真值表法先列(QP)Q的真值表如下：PQPQP(QP)QFFTTFFTTTTTFFTFTTFFT从真值表看出，该命题公式的主合取范式含有大项M0和M2，即(PQ)和(PQ)。于是此命题公式的主合取范式为：(QP)Q (PQ)(PQ)三、(14分) 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。 xC(x), $x(A(x)B(x)
6、, x(B(x)C(x) $xA(x)解： $x(A(x)B(x) P A(a)B(a) ES xC(x) P C(a) US x(B(x)C(x) P B(a)C(a) US B(a) T I A(a) T I $xA(x) EG 四(12分)令集合A=1,1,B=1，P(A)表示A的幂集。分别计算： （注意：要求有计算过程，不能直接写出结果！）(1) AP(B)(2) AB(3) P(A)P(B)解： A=1,1, B=1， AP(B)1,1 ,1 , AB(AB)(AB) =(1,11) (1,1 1)1,111。 P(A)P(B),1,1, 1,1,1 1, 1,1五. (25分)给定
7、集合A=1,2,3,定义A上的关系如下：R=, S=AA(完全关系（全域关系）)T=,M=,1.写出关系R的矩阵；再画出上述各个关系的有向图。2.判断各个关系性质。用“”表示“是”，用“”表示“否”，填下表：自反的反自反的对称的反对称的传递的RSTM3.上述四个关系中，哪些是等价关系？哪些是偏序关系？对等价关系，写出此等价关系的各个等价类。4.求复合关系RoT解：关系R的矩阵如下：1.下面是几个关系的有向图：T。132。132M。132R。132S2.判断各个关系性质。用“”表示“是”，用“”表示“否”，填下表：自反的反自反的对称的反对称的传递的RSTM解：自反的反自反的对称的反对称的传递的R
8、STM3.上述四个关系中，哪些是等价关系？哪些是偏序关系？对等价关系，写出此等价关系的各个等价类。解：T和R是等价关系。 M是偏序关系。 A/T=1,2,3 A/R=1,2,34.求复合关系RoT解：RoT,六. (12分) R是实数集合，给出R上的运算如下：、+、|x-y|、min、max,分别表示乘法、加法、x-y的绝对值、两个数中取最小的、两个数中取最大的运算。1. 判断各个运算性质。用“”表示“是”，用“”表示“否”，填下表：|x-y|max min+有交换性有结合性有幂等性有幺元有零元2.指出R对上面哪些运算构成群？.解:1.|x-y|maxmin有交换性有结合性有幂等性有幺元有零元2. 构成半群的有：， ， , . 构成独异点的有： ， 。 构成群的有： 。七. (14分) 有三个小题 1. 指出下面各个图中哪些是彼此同构的.解：同构的有：AR,BD,CMSW,EFTY,H,KX,VN2.上面图b与c显然是不同构的，请说明不同构的理由（说明一个即可。）解：同构的充要条件是两图的接点和边分别存在一一对应且保持关联关系。B、c接点不同且不存在一一对应的关系，显然二图不是同构的。3.请画出五个具有五个结点的无向图，使之分别满足： (1) 是欧拉图但不是汉密尔顿图。 (2)
