《离散数学》期中试卷(2011年10月)及答案.docVIP

2011 ～ 2012学年第一学期《离散数学》期中试卷 诚信声明 考场是严肃的，作弊是可耻的，对作弊人的处分是严厉的。 我承诺遵守考场纪律，不存在抄袭及其它违纪行为。 考生（承诺人）签字： 专业： 班级： 学号： 适用年级专业： 试卷说明：闭卷，考试时间90分钟 题号 一 二 三 四 总分 得分 一、选择题（每小题2分，共10分）【得分： 】 1.下列命题公式等值 2．设个体域为D（正整数集合），确定下列公式为真的是（ ） A．(x(y (xy=y) B. (x(y(x+y=y) C．(x(y(x+y=x) D. (x(y(y=2x) 3. 下列哪些公式为永真蕴含式( ) A.P(PQ)=P B. QP =Q C.Q=P→Q D.P=P→Q 4.对一阶逻辑公式(x (y (P(x,y)(Q(y,z)) ((xP(x,y)的说法正确的是( ) A.x是约束的，y是约束的，z是自由的; B.x是约束的，y既是约束的又是自由的，z是自由的; C.x是约束的，y既是约束的又是自由的，z是约束的; D.x是约束的，y是约束的，z是约束的. 5．设A={a,{a}}，下列命题错误的是（ ） A.{a}P(A) B. {{a}}P(A) C.{{a}}P(A) D.{a}P(A) 二、填空题（每空2分,共40分）【得分： 】 1.设命题公式，则使公式G为假的赋值是 、 和 。 2. 设A，B是两个集合，A={1，2，3}，B={1，2}，则A的幂集=_______________________，B的幂集=__________________，_____________________。 3. 设谓词公式：,个体域:{1, 2},将其中的量词消去，写出与之等值的命题公式为 . 4．公式(x((A(x)(B(y，x))((zC(x，z))(D(x)中，约束变元x的辖域是 ，约束变元z的辖域是 。 5. 写出下列命题逻辑等值式： 蕴含等值式： ； 德摩根律： ； 分配律： ； 归谬论： ； 6．判断下列命题是否为真（填写“T”或“F”）： φ?φ： ；φ∈φ： ；{φ}∈{φ，{{φ}}}： 。 7．设个体域为D={x|x是人}，L(x,y)：x喜欢y。将下列命题符号化： 所有的人都喜欢某些人： ； 所有的人都不喜欢某些人： ； 没有人喜欢所有的人： ； 每个人都喜欢自己： ； 三、综合题（共3小题，每小题10分，共30分）【得分： 】 1.求命题公式((PQ)R)→P的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值。 2.写出(x(F(x)(G(x))((xF(x)的前束范式。 3．使用谓词、量词和逻辑联结词，将下列语句翻译成逻辑表达式。 人无完人 不是每个人都很完美 你的所有朋友都很完美 你的某个朋友很完美 班上的某个学生不想变富 四、证明题（共2小题，每小题10分，共20分）【得分： 】 1.在命题逻辑中构造下面推理的证明： 前提：P(（Q(R），(S(P，Q 结论：S(R 2.试证明 答案 一.选择题(每小题2分，共10分） 1 C 2 D 3 A 4 B 5 D 二.填空题(每小题2分，共40分） 1 P Q R 1 1 1 1 0 1 1 0 0 2 P(A)={φ，{1}，{2}，{3}，{1，2}，{1，3}，{2，3