第 1 页
重 庆 科 技 学 院 200 5 /200 6 学年第 2 学期考试试卷 课程名称： 离散数学 课程代码： 专业班级： 计科普2004级 教学班号： 本卷为 大补考卷，共 4 页，考试方式： 闭卷 ，考试时间： 120 分钟
一、基本题：（每小题2分共20分） 1、填空：设p:小王走路,q:小王听音乐,
在命题逻辑中，命题“小王边走路边听音乐”的符号化形式为（ ） 2、填空题：解释（0，0）使命题公式q q p p A →→∨=))((的真值为（ ） 3、选择题：用P 表示：天下大雨；Q 表示：他乘公共汽车上班。
将“只有天下大雨，他才乘公共汽车上班。
”符号化正确的是（ ） A 、P →Q B 、 Q →P C 、P ∧Q D 、 P ∨Q 4、选择题：给定下列各序列，不能构成无向简单图的度数序列是（ ） A 、1，1，1，2，3； B 、 2，2，2，2； C 、 3，3，3，3； D 、1，3，3，3。
5、经过图中每个顶点一次且仅一次的通路，称为（ ）通路。
6、选择题：设Ａ＝{}φ，Ｂ＝P(P(A))，以下不正确的是（ ）。
Ａ、{}∈},{φφＢ Ｂ、{}}{φ∈Ｂ Ｃ、{}}{φ包含于Ｂ Ｄ、｛｛｛｛φ｝｝，φ｝｝包含于Ｂ 7、判断：设R 集合是A 上的等价关系, L 是由A/R 诱导A 上的等价关系，则 。
（ ） 8、填空题：写出()R P Q P →∧∨)(的对偶式（ ）。
9、填空题：设 是我校本科生全体构成的集合，两位同学等价当且仅当他们在同一个班，则等价类的个数为（ ），同学小王所在的等价类为（ ）。
10、填空题：在n 阶图中初级通路的长度不大于（ ）。
二、解答题（每小题6分共36分） 1、判断命题公式)(r q p p ∨∨→的类型，方法不限，要求有过程。
班 级：
姓
名： 学
号：
密
封
线
第 2 页
2、设有向简单图D 的度数列为2，2，3，3， 入度列为0，0，2，3，试求D 的出度列。
（说明原因）
3、设R 为一个偏序集，其中A={1，2，3，4，6，9，24，，27，72}R 是A 上的整除关系。
（1）画出的哈斯图；（2）求R 关于A 的极大元；（3）求B={4,6,9}的最小上界和最大下界。
4、（1）在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中，（1）应该有几片树叶？（2）画出两棵非同构的满足（1）中顶点度数的无向树T1和T2。
5、设A={a,b,c,d}，给定A 上的两个关系R 和L 分别为
(1)写出R 和L 的关系矩阵。
（２）求L R 及 )(L R t
6、说明下图是否为欧拉图,哈密尔顿图,平面图(写明原因)
三、证明题
第 3 页
1、（7分）对任何集合 A ，B ，Φ是空集，E 是全集 求证：E B A B A =⋃⇔⊆
2、（7分）证明：∃x(P(x)→Q(x))↔(∀xP(x)→∃xQ(x))是永真式。
3、（7分）对任何集合 A ，B 求证：)()()(c A B A C B A ⊕⋂=⊕⋂
四、应用题
第4页
1、（8分）用命题推理理论来论证下述推证是否有效？
甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜，如果甲不获胜，则丁不失败。
所以，如果丙获胜，则丁不失败。
2、（8分）用谓词推理理论来论证下述推证。
任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑自行车（可能这两种都喜欢）。
有的人不爱骑自行车，因而有的人不爱步行 (论域是人)。
3、（6分）画一棵带权为1，1，2，3，3，4，5，8的最优二元树T，并计算它的权W（T）和相应的二元前缀码
答案
第 5 页
一、 基本题
1、q p ∧
2、D
3、B
4、D
5、哈密尔顿通路
6、D
7、正确
8、()R P Q P ∧⌝∨∧)(
9、全校本科生班级数， 同班同学 10、n-1
二、解答题
1、解：真值表法或等值演算法或说明当前提为真时结论不可能为假
永真式 （6分）
2、解：因为有向图的出度总和等于入度总和且度总和等于边数的两倍（3分）
所以D 的出度列2，2，1，0
3、解：（1）哈斯图略（2分）（2）27，72（2分）（3），71，1 （2分）
4、解：（1）设有x 片树叶，则（1分）
()21423422⨯-++=+⨯+⨯x x （2分）得x=6即有6片树叶
（2）画出两棵非同构的满足（1）中顶点度数的无向树T1和T2图略（3分）
5、解：（1）（2分）
⎪⎪⎪⎪⎪⎭
⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=0101010100101000,0000000101000010L R （2）{}d c c b a b a L R ,,,,,= （2分）
()()1)(-⋃=L R L R L R t （2分）
6、解：是欧拉图（2分）,哈密尔顿图（2分）不是平面图（2分）
三、证明题
1、证明：)(E B A B A E B A A A B A ⊆⋃⋃⊆⇒⋃⊆⋃⇒⊆
E B A B A =⋃⇒⊆∴（3分） 又
()()()()B E A B B B B A B B B B A B B A E B A =⋂⋃⇒=⋃⋂⋃⇒=⋃=⋂⋃⇒⋂⇒=⋃φ B A A B A B A B ⊆⇒⋃⊆=⋃⇒)(（4分） 所以E B A B A =⋃⇔⊆
2、证明：()()()()()()x Q x P x x Q x P x ∨⌝∃⇔→∃（2分）
()()x xQ x P x ∃∨⌝∃⇔（2分）()()x xQ x xP ∃∨⌝∀⇔（2分）()()x xQ x xP ∃→∀⇔
3、证明： ()()()()()B C A C B A B C C B A C B A ⋂⋂⋃⋂⋂=⋂⋃⋂⋂=⊕⋂)( （3分）
又=⊕⋂)()(c A B A ()()B C A C B A ⋂⋂⋃⋂⋂（4分）
所以)()()(c A B A C B A ⊕⋂=⊕⋂
四、应用题
1、有效
解：P ：甲获胜，Q ：乙获胜，R ：丙获胜，S ：丁不失败
前提：S P Q R Q P →⌝→⌝→,,（3分）
第 6 页
结论：S R →（1分）
证明得此推理有效（4分）
2、解：P （x ）：x 喜欢步行，：P （x ）：x 喜欢步行，R （x ）：x 喜欢骑自行车 前提：()()()()()()()()()()x R x x R x Q x x Q x P x ⌝∃∨∀⌝→∀,,（3分） 结论：()()x P x ⌝∃（1分）
证明：此推理有效（4分）
（1） )()(x R x ⌝∃ P
(2) )(c R ⌝ (1)ES
(3) ))()()((x R x Q X ∨∀ P
(4) )()(c R c Q ∨ (3) US
(5) )(c Q (2)(4)T,I
(6) ))()()((x Q X P X ⌝→∀ P
(7) ))()(c Q c P ⌝→ (6)US
(8) )(c P ⌝ (5)(7)T,I
(9) )()(x P x ⌝∃ (8)EG
3、解：运用哈夫曼算法得
最上端结点为27（2分），W （T ）为74（2分），左0右1得前缀码（2分）。