上海交通大学试卷（A卷) (2009至2010学年第1学期) 班级号 学号 姓名 课程名称 离散数学 成绩 一、选择题(40°，每题2'，每题只有一个选项正确，请将答案写在题号前的括号里) （)1.下面不是命题的是 A.火星上有生命存在 B.雪是白的 C.我正在说谎 D.10+11=101 ()2.所有使命题公式P(QvR)的真值为T的解释是(P,Q,R)=一 A.(F,F,F),(F,F,T),(T,F,F): B.(f,T,T),(F,T,F),(F,F,F): C.(T,F,F),(T,F,T),(T,T,F): D.(T,T,F),(T,F,T),(T,T,T). ()3.下面关于命题公式的叙述不正确的是 A.不是可满足的公式必永假 B.如果P是重言式，对其使用代入规则得到的公式Q不一定是重言式 C.如果P<Q是重言式，那么P=Q D.如果P→Q是重言式，那么Q→一P是重言式 ()4.下面的联结词集合不是完备集的是一 A.[个们（个表示与非） B.{,→} C.【, D.{h, （)5.下面不正确的是 A.一QA(P→Q)→P B.P-PvO C.P→Q→Q→P D.(P→Q)v-Q→P A一卷总8页第一页
A 卷 总 8 页 第 页 班级号_______________________ 学号______________ 姓名 课程名称 离散数学 成绩 一、 选择题（40’， 每题 2’，每题只有一个选项正确，请将答案写在题号前的括号里） （ ）1. 下面不是命题的是___ A．火星上有生命存在 B．雪是白的 C．我正在说谎 D．10 + 11= 101 （ ）2. 所有使命题公式P(QR)的真值为 T 的解释是（P,Q,R）=___ A．(F, F, F), (F, F, T), (T, F, F); B．(F, T, T), (F, T, F), (F, F, F); C．(T, F, F), (T, F, T), (T, T, F); D．(T, T, F), (T, F, T), (T, T, T). （ ）3. 下面关于命题公式的叙述不正确的是___ A．不是可满足的公式必永假 B．如果 P 是重言式，对其使用代入规则得到的公式 Q 不一定是重言式 C．如果 PQ 是重言式，那么 P=Q D．如果 P→Q 是重言式，那么Q→P 是重言式 （ ）4. 下面的联结词集合不是完备集的是______ A．{} （表示与非） B．{, →} C．{, } D．{, } （ ）5. 下面不正确的是______ A．Q (P Q) P B． P P Q C． P Q Q P D．(P Q) Q P 上 海 交 通 大 学 试 卷（ A 卷） （ 2009 至 2010 学年 第 1 学期 ）
题号 三 四 五 六 七 八 我承诺，我将严 二 格遵守考试纪律。 得分 承诺人： 批阅人（流水阅 卷教师签名处) ()6.下列公式中是重言式 A.P→(PAQ) B.(QA(P→Q)→P C.Q→(P→Q) D.(P→Q)→((P→R)→(Q→R)) ()7.设A(x):×是成功人士，B(x):×出身名门，命题“成功人士未必都出身名门” 符号化为 A.(x)(A(x)B(x)) B.(臼x)(A(x)B(x) C.(x)(A(x)∧B(x) D.(x)(A(x)→B(x) ()8.设个体域为{-1,1}，并对P(x,y)设定为P(-1,-1)=T,P(-1,1)=F,P(1,-1)=T, P(1,1)=F,其真值为T的公式为 A.(tx)(臼y)P(x,y） B.(臼x)(ty)P(x,y) C.(Vx)(Vy)P(x,y) D.(y)(臼x)P(x,y) ()9.(臼x)(P(a,x)→(y)Q(x,b,y)的前束范式为 A.(x)(Vy)(P(a,x)VQ(x,b,y)) B.(Vx)(y)(P(a.x)A-Q(x,b.y)) C.(臼x)(y）(P(a,x)∧Q(x,b,y) D.(x)(P(a.x)V (Vy)Q (x,b,y) （)10.下列公式普遍有效的是 A.((臼x)P(x)A(臼x)(Q(x))→（臼x)(P(x)AQ(x) B.(臼x)P(x)V(臼x)(Q(x)(臼x)(P(x)VQ(x) C.(臼x)(P(x)AQ(x)→(x)(P(x)vQ(x)) D.(Vx)(P(x)VQ(x))>((x)P(x)V(x)0(x)) A一卷总8页第一页
A 卷 总 8 页 第 页 我承诺，我将严 格遵守考试纪律。 承诺人： （ ）6. 下列公式中______是重言式 A．P→(PQ) B．(Q(P→Q))→P C．Q →(P →Q) D．(P →Q)→((P→R) →(Q→R)) （ ）7. 设 A(x)：x 是成功人士，B(x)：x 出身名门，命题“成功人士未必都出身名门” 符号化为______ A．(x)(A(x) B(x)) B．(x)(A(x)B(x)) C．(∀x)(A(x)∧B(x)) D．(∀x)(A(x)B(x)) （ ）8. 设个体域为{-1,1}，并对 P(x,y)设定为 P(-1,-1)=T, P(-1,1)=F, P(1,-1)=T, P(1,1)=F,其真值为 T 的公式为______ A．(∀x)(y)P(x,y) B．(x)(∀y)P(x,y) C．(∀x)(∀y)P(x,y) D．(∀y)(x)P(x,y) （ ）9. (x)(P(a,x) (∀y)Q(x,b,y))的前束范式为______ A. (x)(∀y)(P(a,x)∨Q(x,b,y)) B. (∀x)(y)(P(a,x)∧Q(x,b,y)) C. (x) (∀y)( P(a,x)∧Q(x,b,y)) D. (x) (P(a,x)∨(∀y)Q(x,b,y)) （ ）10.下列公式普遍有效的是______ A．((x)P(x) (x)(Q(x)) (x)(P(x) Q(x)) B．((x)P(x) (x)(Q(x)) (x)(P(x) Q(x)) C．(x)(P(x) Q(x)) (x)(P(x) Q(x)) D．(x)(P(x) Q(x)) ((x)P(x) (x)Q(x)) 题号 一 二 三 四 五 六 七 八 得分 批阅人(流水阅 卷教师签名处)
班级 学号 姓名 ()11.下列公式与（付x)(白y)P(y)→0(x)等值的是 A.(x)(臼y)(P(y)→Q(x) B.(x)(y)(-P(y)→Q(x)) C.(x)(-Q(x)→(y)-P(y) D.(臼y)P(y)→(x)Q(x) ()12.根据归结推理规则，子句P(x)VQ(a,x)与P(y)V0(y,b)的归结式是 A.P(a) B.P(b) C.P(a)vP(b) D.P(a)P(b) （)13.下列说法错误的是 A.给定G,的某个子图H,如果在G2中找不到与H同构的子图，则G,和G2一定不同构 B.任一非空无向图中的道路有无穷条 C.任何非平面图中一定存在一个子图是K0型图或者K②型图 (K型图指K的同胚，K®型图指K2,3的同胚) D.给定赋权的叶子结点集合，则相应的Huffman树是唯一的 （)14.下图中不存在欧拉回路 A D （)15.下面说法错误的是 A若简单图每个结点的度大于等于父，则6有H回路 B.Kn的H回路含有nn-1)条边 C.如果一个图G的子图是非平面图，则G一定是非平面图 D.简单图G的任意结点v,v,之间恒有d(y)+d(y,)≥n,则G存在H回路 A一卷总8页第一页
A 卷 总 8 页 第 页 班级 学号 姓名 （ ）11. 下列公式与(x)((y)P(y)Q(x))等值的是______ A．(x)(y)(P(y) Q(x)) B．(x)(y)(P(y) Q(x)) C．(x)(Q(x) (y)P(y)) D．(y)P(y) (x)Q(x) （ ）12. 根据归结推理规则，子句 P(x) Q(a,x)与 P(y) Q(y,b)的归结式是______ A．P(a) B．P(b) C．P(a) P(b) D．P(a) P(b) （ ）13. 下列说法错误的是______ A．给定 G1的某个子图 H，如果在 G2中找不到与 H 同构的子图，则 G1和 G2一定不同构 B．任一非空无向图中的道路有无穷条 C．任何非平面图中一定存在一个子图是 K (1) 型图或者 K (2) 型图 (K (1) 型图指 K5的同胚，K (2) 型图指 K3，3的同胚) D．给定赋权的叶子结点集合，则相应的 Huffman 树是唯一的 （ ）14. 下图中______不存在欧拉回路 （ ）15. 下面说法错误的是______ A．若简单图每个结点的度大于等于 2 n ，则 G 有 H 回路 B． Kn 的 H 回路含有 ( 1) 2 1 n n 条边 C．如果一个图 G 的子图是非平面图，则 G 一定是非平面图 D．简单图 G 的任意结点 vi，vj之间恒有 d v d v n ( i) ( j) ，则 G 存在 H 回路
()16.一个无向图有五个结点，其中4个的度数是1,2,3,4，则第5个结点的度数 不可能是一 A.0 B.2 C.4 D.5 ()17.在平面图G的某个域内增加一个结点及连接该结点与该域的边界上某结点的一条 边，得到一个新图G,那么以下正确的是 A.G'CG' (G为G的对偶图) B.G'G' C.G'=G" D.以上都不对 （)18.下列说法错误的是 A.K2是边数最少的非平面图 B.K是结点数最少的非平面图 C.K中不存在”型子图 D.K,去掉任意一条边所形成的图是可平面图 ()19.下图中存在H回路的图有个 ☒.☒二 A.0B.1C.2D.3 ()20.下列图中，和M图同构的图（不计M图本身）有个 A.1 B.2 C.3 D.4 A卷总8页第页
A 卷 总 8 页 第 页 （ ）16. 一个无向图有五个结点，其中 4 个的度数是 1, 2, 3, 4，则第 5 个结点的度数 不可能是______ A．0 B．2 C．4 D．5 （ ）17. 在平面图 G 的某个域内增加一个结点及连接该结点与该域的边界上某结点的一条 边，得到一个新图 G，那么以下正确的是______ A．G *G* （G *为 G 的对偶图） B．G *G* C．G *=G* D．以上都不对 （ ）18. 下列说法错误的是______ A．K3,3是边数最少的非平面图 B．K5是结点数最少的非平面图 C．K6中不存在 K (1)型子图 D．K3,3去掉任意一条边所形成的图是可平面图 （ ）19. 下图中存在Ｈ回路的图有______个 A．0 B．1 C．2 D．3 （ ）20. 下列图中，和 M 图同构的图（不计 M 图本身）有______个 A．1 B．2 C．3 D．4
班级 学号 姓名 二、 填空题（20°，每空2) 1.设P:天下大雨，Q:小王乘公共汽车上班，命题“只有天下大雨，小王才乘公共汽车上班” 的符号化形式为 2.命题公式P→Q的主析取范式为 3.PvQ可以用↓（↓表示或非）表示为 4. 设个体域是人类，谓词F(x,y)表示“×的父亲是y”,则公式 (x)(白y)(f(x,y)Az(z≠y→F(x,z) 的自然语言含义是， 5.公式（臼x)(y)(付z)(臼w)P(x,y,z,w)的Skolem标准型（仅保留全称量词的前束形）是 6. 在论域{1,2}上公式(y)(臼x)P(x,y)可写成命题逻辑公式 7.已知一棵树T中有9个结点，度为4、3的结点各一个，度为2的结点有两个，其余为 树叶结点，T的树叶结点数为 8.一个林中有n个结点，k个连通支，则边数m= 9.下图中最短树的权值总和是 vI 30 10 30 0 15 15 20 40 10 10.平面图G有n个结点，m条边，d个域，k个连通支，则G的对偶图G*的连通支的个数为 A卷总8页第—页
A 卷 总 8 页 第 页 班级 学号 姓名 二、 填空题（20’，每空 2’） 1． 设 P:天下大雨，Q:小王乘公共汽车上班，命题“只有天下大雨，小王才乘公共汽车上班” 的符号化形式为____________________________________________________________。 2． 命题公式 P→Q 的主析取范式为_______________________________________________。 3． PQ 可以用（表示或非）表示为 __________________________________________________________________________。 4． 设个体域是人类，谓词 F(x,y)表示“x 的父亲是 y”，则公式 (x)(y)(F(x,y) z(z y F(x,z)) 的自然语言含义是_______________________________________________________。 5． 公式(x)(y)(z)(w)P(x,y,z,w)的 Skolem 标准型(仅保留全称量词的前束形)是 __________________________________________________________________________。 6． 在论域{1,2}上公式(∀y) (x)P(x,y)可写成命题逻辑公式 __________________________________________________________________________。 7． 已知一棵树 T 中有 9 个结点，度为 4、3 的结点各一个，度为 2 的结点有两个，其余为 树叶结点，T 的树叶结点数为_________________________________________________。 8． 一个林中有 n 个结点，k 个连通支，则边数 m=__________________________________。 9． 下图中最短树的权值总和是__________________________________________________。 10．平面图 G 有 n 个结点，m 条边，d 个域，k 个连通支，则 G 的对偶图 G*的连通支的个数为 _________________________________________________________________________
三.(6)公安机关正在调查一宗盗窃案，现获得事实如下： 1.A或B盗窃了文物 2.若A盗窃了文物，则作案时间不可能在午夜前 3.若B证词正确，则在午夜前屋里灯光未灭 4.若B证词不正确，则作案时间发生在午夜前 5.午夜时屋里灯光灭了 试问谁是盗窃犯？试写出推导过程。设P:“A盗窃了文物”，Q:“B盗窃了文物”，R:“作案时间发生在午 夜前”，S:“午夜前屋里灯光灭了”，T:“B证词正确”。 四.(6)任用一种推理方法证明：(P→Q)→(R→Q)→(PVR)→Q) A一卷总8页第一页
A 卷 总 8 页 第 页 三.(6') 公安机关正在调查一宗盗窃案，现获得事实如下： 1. A 或 B 盗窃了文物 2. 若 A 盗窃了文物，则作案时间不可能在午夜前 3. 若 B 证词正确，则在午夜前屋里灯光未灭 4. 若 B 证词不正确，则作案时间发生在午夜前 5. 午夜时屋里灯光灭了 试问谁是盗窃犯？试写出推导过程。设 P：“A 盗窃了文物”，Q：“B 盗窃了文物”，R：“作案时间发生在午 夜前”，S：“午夜前屋里灯光灭了”，T：“B 证词正确”。 四. (6')任用一种推理方法证明： (P→Q) →((R→Q) →((PR)→Q))
班级 学号 姓名 五.(6')求公式（臼x)P(x)→一(3y)Q(y)A(x)R(x)的前束范式。 六.(6)判断以下公式是否是普遍有效式并说明理由。 （(臼x)P(x)→（臼x)Q(x)→（臼x)(P(x)→Q(x)) A一卷总8页第一页
A 卷 总 8 页 第 页 班级 学号 姓名 五．(6') 求公式(x)P(x) ((y) Q(y) (x)R(x))的前束范式。 六．(6') 判断以下公式是否是普遍有效式并说明理由。 ((x)P(x) (x)Q(x)) (x)(P(x) Q(x))
七.(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个字符最优编码的二进制长度。 八.(8)下图是一所房子的俯视图，除了粗边代表的墙以外，每一面墙都有一个门。问能否从某个房间 开始过每扇门一次且仅一次最后返回。 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 个字符最优编码的二进制长度。 八．(8') 下图是一所房子的俯视图，除了粗边代表的墙以外，每一面墙都有一个门。问能否从某个房间 开始过每扇门一次且仅一次最后返回