嘉应学院离散数学期末考试卷2013-12月本科A(应该小明出的)

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