如果⊙满足结合律，则也满足结合律。(5分)
3、给定代数结构<A,*>，且*是可结合的。若对A中任意元a和b，有a*b=b*a，证明，*满足等幂律。(5分)
4、说明如下三个代数结构之间的关系，并用一个公式来表示后两个结构之间和联系。(5分)
1
0
1
1
0
0
0
0
⊙
0
1
0
0
1
1
1
1
*
学院班级姓名学号
…………………密……………封……………线……………密……………封……………线…………………
4、证明：RS可从前提P(QS)，┐R∨P和Q推出。(5分)
5、使用推理规则，论证推理形式(5分)
PQ, R┐Q ,R∨S, SQ├┐P
二、谓词逻辑部分题（每题5分，共15分）
得
分
1、写出谓词的含义、一个谓词公式的解释应包含什么内容。(5分)
2、数学分析中函数f (x)在点a连续的定义为:对任意的>0,存在一个>0,使得对所有x,若|x – a|<,则|f (x) – f (a)|<。将此命题符号化。(5分)
得
分
五、图论部分题：（每题10分，共20分）
1、写出Dijkstra算法，并计算图中从v1到其他结点的最短链长度。(10分)
2、给定PERT图，求图的关键路径(8分)，解释分配给时间为0的边的作用(2分)
(共10分)。
1、计算下表中各公式的真值表，并写出公式(pq)的主析取范式与主合取范式
(5分)
pq
p
pq
(pq)
(pq)q
0 0
0 1
1 0
1 1
1
1
0
1
2、设A、B是两个命题公式，用等价公式ABABBA来说明两个命题公式A与B“等价”，“蕴涵”之间的关系.(5分)
3、证明：Q→(P→R)┐R→(Q→┐P)(5分)
1)计算关系R的传递闭包t(R)，并在上图中画出其余的有向连接边。(5分)
2)若用矩阵来表示关系R，写出Mt(R)的形成过程。(5分)
得
分
四、代数部分题（每题5分，共20分）
1、给定代数结构<S，⊙>，且| S |＞1。如果θ，e∈S，其中θ和e分别为关于⊙的零元和幺元，证明：θ≠e。(5分)
2、已知两个代数结构<X，⊙><Y，>且f为其满同态映射，证明：
得
分
三、集合与关系部分题（20分）
1、证明：对任何集合S1和S2，都有┐(S1∈S2∧S2∈S1)。(5分)
2、证明：一个集合A是传递集当且仅当AP(A)。(5分)
3、已知集合{a,b,c,d,e}上的一个关系R={<a,b>,<b,c>,<c,d>,<d,e>}，若将其中的有序对<x,y>解释成为：从结点x到结点y的有向边连接，则关系R可表示为如下有向图模型，(共10分)
学院班级姓名学号
…………………密……………封……………线……………密……………封……………线…………………
嘉应学院计算机学院2013-2014学年第1学期期末考试试卷
《离散数学》试题(A卷)
（考试形式：闭卷，考试时间：120分钟）
题号
一
二
三
四
五
六
七
总分
复核人
得分
评卷人
得
分
一、命题逻辑部分题（每题5分，共25分）
3、令B为没有x出现的公式，A(x)为有x自由出现的公式，写出已有公式的等价公式。
(5分)
(1)(x)(A(x)∨B)
(2)(x)(A(x)→B)
(3)(x)(A(x)∧B)
(4)(x)(B→A(x))
(5)┐(x)A(x,y)
学院班级姓名学号
…Hale Waihona Puke ……………密……………封……………线……………密……………封……………线…………………