内容发布更新时间 : 2025/1/9 4:31:37星期一 下面是文章的全部内容请认真阅读。

河 南 科 技 大 学

2015至2016学年第一学期试卷A标准答案

课程 离散数学 年级、专业 2015 计算机科学与技术和物联网技术

一、计算题

1(参考答案)

解：

(1)等值演算和范式

P→（（Q→P）∧（?P?Q）） ?P→((?Q?P)∧（?P?Q）） ??P?((?Q?P)∧（?P?Q）） ?((?P??Q?P)∧（?P??P?Q）） ?((1??Q)∧（?P?Q）） ?1∧（?P?Q）） ??P?Q ?M2(范式) ?m0?m1?m3(范式) 真值表： P 0 0 1 1 Q 0 1 0 1 Q→P 1 0 1 1 ?P 1 1 0 0 ?P?Q 1 1 0 1 （Q→P）∧（?P?Q） 1 0 0 1 P→（（Q→P）∧（?P?Q）） 1 1 0 1 (2) 等值演算和范式 ?(Q)?(P?Q)?Q?P ??Q?P?(Q?Q)?P ??Q?P?Q?P ??Q?Q?P?P ?0?P ?0(范式)

?M0?M1?M2?M3(范式) 真值表：

P 0 0 1 1 Q 0 1 0 1 ?(Q) 1 0 1 0 (P?Q) 0 0 0 1 ?(Q)?(P?Q) 0 0 0 0 ?(Q)?(P?Q)?Q 0 0 0 0 ?(Q)?(P?Q)?Q?P） 0 0 0 0 2 (参考答案)

解：抽取简单命题如下：

P：A队得第一；Q：B队获亚军；R：C队获亚军；S:D队获亚军 前提：P→（QVR）或P→（(?Q?R)V(Q??R）），R→?P，S→?Q，P 结论：?S 或

前提：P→（QVR）或P→（(?Q?R)V(Q??R）），R→?P，S→?Q，P 结论：P→?S

3 (参考答案)

解：（1）R?S=（R-S）?（S-R）

={,}?{,,} ={,,,,}

RXS={<,>,<,>,<,>, <,>,<,>,<,>} R?S={}

(2)R满足反自反、对称性，S满足反自反、反对称和传递 (3)r(R)=R?IA={,,,,,} s(R)= R?R-1={,}

t(R)= R?R2?R3?R4=={,,,}

4 (参考答案)

解：（1）（1）关系的集合A={a,b,c,d,e,f},

R={,,,,,,

,, ,

,,,, ,,}

关系的矩阵：矩阵的行和列与集合A中元素对应；关系图：需要在下图每个节点上加环

f1 1 1 1 1 1

0 1 0 0 1 0

ed0 0 1 1 1 1

0 0 0 1 0 1

bc0 0 0 0 1 0

0 0 0 0 0 1

a

（2）该关系不是格，原因是e,f没有上界，后面性质是针对格的，为此均为否定。

5 (参考答案)

解：（1）G=

V={v1,v2,v3,v5,v6}

E={,,,,,,,} （2）图为单向连通图，任一对节点间存在通路，但没有节点可以到达v3。

（3）v1到V3长度为3的通路为0条，因为v3入度为0，没有箭头指向v3的边.

6 (参考答案)

解：（1）根据哈夫曼算法构造的最优二叉树如右图，

1326312674281695（2）两种计算方法，一种是叶节点权值乘以对应的层数，二是各个内点权值相加。 W(T)=3+6+12+9+16+28=74

二、证明题

1(参考答案)

证明：

由xv =yu且R是正整数上的关系得x/y =u/v 自反性：

(1) ??A, x/y =x/y

? <,>?R ? R自反

(2) ?<,>?R 对称前提

? x/y =u/v 题意 ? u/v =x/y 等值 ? <,>?R 题意

? R对称 对称定义

(3) ?<,>?R 且<,>?R 传递前提

? x/y =u/v? u/v=s/t 题意 ? x/y =s/t 等值 ? <,>?R 题意 ? R传递 传递定义 由（1）（2）（3）知：R是A上的等价关系。

2(参考答案)

证明：要证G是群，需证G满足封闭性、结合律成立，同时有单位元，每个元素有逆元。 封闭性：显然?是G上的二元运算（即满足封闭性）， 结合性：?a,b,c?G，有

(a?b)?c=(a*x*b)*x*c 题目前提

=a*x*(b*x*c) *的结合性 =a?(b?c)

?运算是可结合的。

-1

含幺元：x是的单位元。?a?G，经验证有

-1-1-1-1

右幺元：a?x=a*x*x=a; 左幺元：x?a=x*x*a=a

-1-1-1

有逆元：?a?G ，x*a*x是a在中的逆元。因为，

-1-1-1-1-1-1-1

a?（x*a*x)=a*x*（x*a*x)=x

-1-1-1-1-1-1-1

（x*a*x)?a=（x*a*x)*x*a=x 由以上证明，是群。

三、问答题

1(参考答案)

答：逻辑是一种推理方法，包括命题逻辑和谓词逻辑，前者推理简单适用范围小，后者复杂适用范围大。每种逻辑解决问题

都包含符号化和推理。命题逻辑符号化包括抽取命题，选择连接词，确定推理的前提和结论；推理方法包括真值表、等值演算和范式。谓词逻辑符号化包括确定论域，抽取谓词，选择连接词，确定推理的前提和结论；推理方法包括解释、演算和前束范式。集合论是一种表示方法，包括集合、关系和函数，关系是特殊的集合，函数是特殊的关系。关系是重点，内容包括关系的计算、关系的性质、闭包、等价关系和偏序关系。代数系统是对多种运算系统的抽象，包括运算符、特殊元素和特殊系统。图论是问题的直观描述，包括图和树两大部分，树是一种特殊的图。

逻辑和集合论构成了计算的全部，两者相辅相成，类似于计算机中的算法和数据结构；代数系统和图论从两个不同的方向研究问题，代数系统是一种抽象问题或者现实问题信息化的方法，图论虽然也包括现实问题的抽象，但最核心的优点是直观，把问题以友好的方式描述。它们对问题的处理方式代表了信息技术的主要方法。形式化方法、研究特殊元素方法、类比方法和图形化方法等。如可以把各个概念以层次化图形描述，既能使概念更直观，也能方便概念间关系的提取。 从中掌握了离散数学的特征和其在计算机科学中的位置，通过各个内容的学习为学习相关课程打下了基础、了解了学习各个课程内容的方法。

四、综合题

1(参考答案)

解：(1) 用Kruskal算法求产生的最优树。

权值排序为2,2,3,4,5,7,8,8,9,11,12,13 选择次序为：

w(v1,v6)=2 选e1=v1v6 w(v6,v4)=2 选e2=v6v4 w(v4,v2)=3 选e3=v4v2

w(v2,v1)=4 选e4=v1v2,构成环，舍去重选 w(v6,v5)=5 选e4=v5v6

w(v2,v6)=7 选e5=v2v6,构成环，舍去重选 w(v2,v3)=8 选e5=v2v3或者 w(v6,v3)=8 选e5=v3v6 结果如图： v1v23v42v6582v5v3 (2) 树权C(T)=2+2+3+5+8=20，即为总成本。