上海交通大学试卷(（A卷) (2009至2010学年第1学期) 班级号 学号 姓名 课程名称 离散数学 成绩 一、 选择题（40°，每题2) A卷：CBBCD CDAAB D(C)CDDB DACCC B卷：BCCBA BADDC A(B)BADC AABBB 二、 填空题（20°，每空2) 1.Q→P 2.(PPAQ)(PAQ)Vo.13 3.(PQ)↓(PQ) 4.每个人都有唯一的父亲 5.(Vy)(Vz)P(a,y,z,f(y,z)) 6.(P(1,1)VP(2.1))∧(P(1,2)VP(2.2) 7.5 8.n-k 9.50 10.1 三.(6)公安机关正在调查一宗盗窃案，现获得事实如下： 1.A或B盗窃了文物 2.若A盗窃了文物，则作案时间不可能在午夜前 3.若B证词正确，则在午夜前屋里灯光未灭 4.若B证词不正确，则作案时间发生在午夜前 5.午夜时屋里灯光灭了 试问谁是盗窃犯？试写出推导过程。设P:“A盗窃了文物”，Q:“B盗窃了文物”，R:“作案时间发生在午 夜前”，S:“午夜前屋里灯光灭了”，T:“B证词正确”。 解答：B是盗窃犯或Q- --1 (1)PvQ (2)P→一R (3)T→S (4)一T→R (5)S -2 证： (1)S 前提引入 A卷总8页第—页
A 卷 总 8 页 第 页 班级号_______________________ 学号______________ 姓名 课程名称 离散数学 成绩 一、 选择题（40’， 每题 2’） A 卷：CBBCD CDAAB D（C）CDDB DACCC B 卷：BCCBA BADDC A（B）BADC AABBB 二、 填空题（20’，每空 2’） 1． Q→P 2． (P Q)( P Q)( P Q) 或 0, 1,3 3． (PQ) (PQ) 4． 每个人都有唯一的父亲 5． (y)(z) P(a,y,z,f(y,z)) 6． (P(1,1)∨P(2,1)) ∧ (P(1,2)∨P(2,2)) 7． 5 8． n-k 9． 50 10．1 三.(6') 公安机关正在调查一宗盗窃案，现获得事实如下： 1. A 或 B 盗窃了文物 2. 若 A 盗窃了文物，则作案时间不可能在午夜前 3. 若 B 证词正确，则在午夜前屋里灯光未灭 4. 若 B 证词不正确，则作案时间发生在午夜前 5. 午夜时屋里灯光灭了 试问谁是盗窃犯？试写出推导过程。设 P：“A 盗窃了文物”，Q：“B 盗窃了文物”，R：“作案时间发生在午 夜前”，S：“午夜前屋里灯光灭了”，T：“B 证词正确”。 解答：B 是盗窃犯 或 Q ----------------1’ (1) P Q (2) P → ¬ R (3) T → ¬ S (4) ¬ T → R (5) S----------------------------------------------2’ 证： (1) S 前提引入 上 海 交 通 大 学 试 卷（ A 卷） （ 2009 至 2010 学年 第 1 学期 ）
(2)T→一S 前提引入 (3)S→T (2)置换 (4)一T (1),(3)分离 (5)T→R 前提引入 (6)R (4),(⑤)分离 (7P→一R 前提引入 (8)R→一P (7)置换 (9)一P (6),(8)分离 (10)PVQ 前提引入 (11)Q (9),(10)永真蕴涵-… 3 四.(6)任用一种推理方法证明：(P→Q)→(R→Q)→(PR)→Q) 用等值演算证明： (P→Q)→(R→Q)→(PVR)→Q) =PVQ)V(RVQ)V(PVR)VQ)) =(PA-Q)v(RA-Q)v-((PVR)A-Q) =((PVR)-Q)V-((PVR)A-Q) =T 五.(6)求公式（臼x)P(x)→(（臼y)Q(y)A(x)R(x))的前束范式。 原式=（臼x)P(x)v(y)Q(y)V(3x)-R(x) =(Vx)-P(x)v (Vy)-Q(y)v (z)-R(z)) =(Vx)(Vy)(3z)(P(x)vQ(y)v=R(z)) 六.(6)判断以下公式是否是普遍有效式并说明理由。 （臼x)P(x)→（臼x)Q(x)→（臼x)(P(x)Q(x)) 答案：是普遍有效式。-一 一2 (臼x)P(x)→（臼x)Q(x)→（臼x)(P(x)→Q(x) =-((臼x)P(x)V(臼x)Q(x)V(臼x)(-P(x)VQ(x) =((自x)P(x)∧（臼x)Q(x)V(臼x)P(x)V(臼x)Q(x) =(臼x)P(x)V(臼x)P(x)∧(（臼x)Q(x)V(臼x)P(x))V(臼x)Q(x) =a(臼x)Q(x)V(臼x)P(x)V(臼x)Q(x) =T- -4 A一卷总8页第一页
A 卷 总 8 页 第 页 (2) T → ¬ S 前提引入 (3) S → ¬ T (2) 置换 (4) ¬ T (1), (3) 分离 (5) ¬ T → R 前提引入 (6) R (4), (5) 分离 (7) P → ¬ R 前提引入 (8) R → ¬ P (7) 置换 (9) ¬ P (6), (8) 分离 (10) P Q 前提引入 (11) Q (9), (10)永真蕴涵--------------------------------3’ 四. (6')任用一种推理方法证明： (P→Q) →((R→Q) →((PR)→Q)) 用等值演算证明： (P→Q) →((R→Q) →((PR)→Q)) =(PQ) ((RQ)( PR) Q)) =(PQ) (RQ) (( PR) Q) =((PR)Q) (( PR) Q) =T 五．(6') 求公式(x)P(x) ((y) Q(y) (x)R(x))的前束范式。 原式＝ (x)P(x) (y)Q(y) (x)R(x) ＝(x) P(x) (y)Q(y) (z)R(z)) ＝(x)(y)(z)(P(x) Q(y) R(z)) 六．(6') 判断以下公式是否是普遍有效式并说明理由。 ((x)P(x) (x)Q(x)) (x)(P(x) Q(x)) 答案：是普遍有效式。-------------------------------------2’ ((x)P(x) (x)Q(x)) (x)(P(x) Q(x)) = ((x)P(x)∨(x)Q(x))∨(x) (P(x)∨Q(x)) = ( (x)P(x)∧ (x)Q(x))∨(x) P(x)∨(x)Q(x) = (((x)P(x)∨(x) P(x))∧( (x)Q(x)∨(x) P(x)))∨(x)Q(x) = (x)Q(x)∨(x) P(x)∨(x)Q(x) = T-------------------------------------------------------4’
七.(8)现有100个字符组成的字符串，这些字符取自集合{a,b,c,d,e,f,g,h,i,在100个字符中，a 出现了8次，b出现了20次，c出现了3次，d出现了12次，e现了12次，f出现了10次，g 出现了12次，h出现了5次，i出现了18次。请对字符集合{a,b,c,d,e,f,g,h,i}中的每个字 符编码成二进制比特串，使得这100个字符组成的字符串编码后长度最短。试求各字符的二进 制编码以及这100个字符最优编码的二进制长度。 304-- ----2 a,b,c,d,e,f,g,h.1编码不唯-，长度分别为4,2,5,3,3,3,3,5,3-- ----6 八.(8)下图是一所房子的俯视图，除了粗边代表的墙以外，每一面墙都有一个门。问能否从某个房间 开始过每扇门一次且仅一次最后返回。 答：将粗边缩为一个点，问题归结为下图的对偶图是否存在欧拉回路。 d 由于d的在的域的边界为3，则相应对偶图该点的度为3，根据欧拉回路的充要条件知无欧拉回路， 5 所以不可能从某个房间开始过每扇门一次且仅一次最后返回。 -3 A卷总8页第页
A 卷 总 8 页 第 页 七．(8') 现有 100 个字符组成的字符串，这些字符取自集合{a,b,c,d,e,f,g,h,i}，在 100 个字符中，a 出现了 8 次，b 出现了 20 次，c 出现了 3 次，d 出现了 12 次，e 现了 12 次，f 出现了 10 次，g 出现了 12 次，h 出现了 5 次，i 出现了 18 次。请对字符集合{a,b,c,d,e,f,g,h,i}中的每个字 符编码成二进制比特串，使得这 100 个字符组成的字符串编码后长度最短。试求各字符的二进 制编码以及这 100 个字符最优编码的二进制长度。 304-------------------------------------------------------------------2’ a,b,c,d,e,f,g,h,I 编码不唯一，长度分别为 4，2，5，3，3，3，3，5，3-------------6’ 八．(8') 下图是一所房子的俯视图，除了粗边代表的墙以外，每一面墙都有一个门。问能否从某个房间 开始过每扇门一次且仅一次最后返回。 答：将粗边缩为一个点，问题归结为下图的对偶图是否存在欧拉回路。 由于 d 的在的域的边界为 3，则相应对偶图该点的度为 3，根据欧拉回路的充要条件知无欧拉回路， ----------------------------------------------------------------------------------------5’ 所以不可能从某个房间开始过每扇门一次且仅一次最后返回。----------------------------------3’
