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

第 1 页 共 7 页……………………………………………装………………………………订…………………………线……………………………………………………此处不能书写此处不能书写此处不能书写 此处不能书写此处不能书写 此处不能书写此处不能书写2011 ～ 2012学年第一学期《离散数学》期中试卷一、选择题（每小题2分，共10分）【得分： 】1.下列命题公式等值的是( )A. ,B. (),()C. (),D. (),P Q P QA AB A A B Q P Q Q P Q A A B B⌝∧⌝∨→→⌝→→→∨⌝∨∨⌝∨∧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 ∧(P ∨Q)=>⌝P B. Q ∨P =>Q C.⌝Q=>P →Q D.P=>P →Q4.对一阶逻辑公式∀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.设命题公式)(R Q P G →⌝→=，则使公式G 为假的赋值是 、 和 。

2. 设A ，B 是两个集合，A={1，2，3}，B={1，2}，则A 的幂集()P B=__________________，P A=_______________________，B的幂集()-=_____________________。

()()P A P B3. 设谓词公式：(,)x yP y x∃∀,个体域:{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.求命题公式((P∧Q)∨⌝R)→P的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值。

2.写出∀x(F(x)→G(x))→∀xF(x)的前束范式。

第2页共7页第 3 页 共 7 页……………………………………………装………………………………订…………………………线……………………………………………………此处不能书写此处不能书写此处不能书写 此处不能书写此处不能书写 此处不能书写 此处不能书写3．使用谓词、量词和逻辑联结词，将下列语句翻译成逻辑表达式。

1) 人无完人2) 不是每个人都很完美 3) 你的所有朋友都很完美 4) 你的某个朋友很完美 5) 班上的某个学生不想变富四、证明题（共2小题，每小题10分，共20分）【得分： 】 1.在命题逻辑中构造下面推理的证明：第4页共7页前提：P →（Q →R ），⌝S ∨P ，Q 结论：S →R2.试证明()()()~~~()A B A B A B A B ⋃⋂⋃=⋂⋃⋃答案一.选择题(每小题2分，共10分）1 C2 D3 A4 B5 D二.填空题(每小题2分，共40分）1 P Q R1 1 11 0 11 0 02 P(A)={φ，{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，{1，2，3}} P(B)={φ，{1}，{2}，{1，2}}P(A)-P(B)={{3},{1,3},{2,3},{1,2,3}}3 (P(1,1)∨P(1,2))∧(P(2,1)∨P(2,2))或（P(1,1)∧P(2,1))∨((P(1,2)∧P(2,2))4 (A(x)→B(y,x))∧∃zC(x,z)C(x,z)第 5 页 共 7 页……………………………………………装………………………………订…………………………线……………………………………………………此处不能书写此处不能书写此处不能书写 此处不能书写此处不能书写 此处不能书写 此处不能书写5 蕴含等值式：A →B ⇔﹁A ∨B德摩根律：﹁(A ∧B)⇔﹁A ∨﹁B ；﹁(A ∨B)⇔﹁A ∧﹁B分配律：A ∧(B ∨C)⇔(A ∧B)∨(A ∧C)；A ∨(B ∧C)⇔(A ∨B)∧(A ∨C)归谬论：(A →B)∧(A →﹁B)⇔﹁A6 TFF7 ∀x ∃yL(x,y)∀x ∃y ﹁L(x,y)﹁∃x ∀yL(x,y)∀xL(x,x)三.综合题（每小题10分，共30分）1 ((P ∧Q)∨﹁R)→P ⇔ ﹁((P ∧Q)∨﹁R)∨P ⇔ (﹁(P ∧Q)∧R)∨P ⇔ ((﹁P ∨﹁Q)∧R)∨P ⇔ (﹁P ∨﹁Q ∨P)∧(R ∨P) ⇔ R ∨P ⇔ R ∨P ∨0 ⇔ R ∨P ∨(Q ∧﹁Q) ⇔ (R ∨P ∨Q)∧(R ∨P ∨﹁Q) ⇔ (P ∨Q ∨R)∧(P ∨﹁Q ∨R) ⇔ M0∧M2(主合取范式) ⇔ m1∨m3∨m4∨m5∨m6∨m7（主析取范式）成真赋值：m1:001m3:011m4:100m5:101m6:110m7:111成假赋值：0000102 论域：所有人；F(x):x 是完美的；G(x)：x 是你的朋友；1) 人无完人﹁∃xF(x)；不存在人x ，x 是完美的∀x﹁F(x)；对于每一个人x，x都是不完美的2) 不是每个人都很完美﹁∀xF(x)∃x﹁F(x)；有人是不完美的3) 你的所有朋友都很完美∀x(G(x)→F(x))；对于每一个人x，如果x是你的朋友，那么x是完美的4) 你的某个朋友很完美∃x(G(x)∧F(x))；存在一个人x，x是你的朋友并且是完美的5) 班上的某个学生不想变富论域：所有人；P(x)：x是班上的学生；Q(x)：x想变富∃x（P(x)∧﹁Q(x))论域：全总个体域；F(x):x是完美的；G(x)：x是你的朋友；H(x)：x是人1) 人无完人﹁∃x(H(x)∧F(x))∀x(H(x)→﹁F(x))；对于每个个体x，如果x是人，那么x是不完美的2) 不是每个人都很完美﹁∀x(H(x)→F(x)∃x(H(x)∧﹁F(x));存在个体x，x是人并且是不完美的3) 你的所有朋友都很完美∀x((H(x)∧G(x))→F(x))4) 你的某个朋友很完美∃x(H(x)∧G(x)∧F(x))四.证明题（每小题10分，共20分）1 方法一：（使用等值逻辑式）[(P→(Q→R))∧(﹁S∨P)∧Q]→(S→R)⇔[(﹁P∨(﹁Q∨R))∧Q∧(﹁S∨P)]→(S→R)⇔[(﹁P∨﹁Q∨R)∧Q∧(﹁S∨P)]→(S→R)⇔[Q∧(﹁P∨R)∧(﹁S∨P)]→(﹁S∨R)⇔﹁(Q∧(﹁P∨R)∧(﹁S∨P))∨﹁S∨R⇔﹁Q∨﹁(﹁P∨R)∨﹁(﹁S∨P)∨﹁S∨R⇔﹁Q∨(P∧﹁R)∨(S∧﹁P)∨﹁S∨R⇔﹁Q∨(P∧﹁R)∨R∨(S∧﹁P)∨﹁S⇔﹁Q∨P∨R∨﹁P∨﹁S⇔ 1重言式,所以推理正确方法二：（1）﹁S∨P 前提引入（2）S 附加前提（3）P （1）（2）析取三段论第6页共7页第 7 页 共 7 页……………………………………………装………………………………订…………………………线……………………………………………………此处不能书写此处不能书写此处不能书写 此处不能书写此处不能书写 此处不能书写此处不能书写（4）P →(Q →R) 前提引入（5）Q →R （3）（4）假言推理（6）Q 前提引入（7）R （5）（6）假言推理所以该推理正确。

2 证明方法一:(从左式开始)(A ∪～B)∩(～A ∪B)= ((A ∪～B)∩～A)∪((A ∪～B)∩B) = (～A ∩～B)∪(A ∩B) = ～(A ∪B)∪(A ∩B) = (A ∩B)∪～(A ∪B) 方法二:(从右式开始)(A ∩B)∪～(A ∪B)= (A ∩B)∪(～A ∩～B)= ((A ∩B)∪～A)∩((A ∩B)∪～B) = (～A ∪B)∩(A ∪～B) = (A ∪～B)∩(～A ∪B)。