浙江工业大学期终考试命题稿
2010 /2011 学年第1 学期
命题注意事项:
一、命题稿请用A4纸电脑打印,或用教务处印刷的命题纸,并用黑
墨水书写,保持字迹清晰,页码完整。
二、两份试题必须同等要求,卷面上不要注明A、B字样,由教务处
抽定A、B卷。
三、命题稿必须经学院审核,并在考试前两周交教务处。
浙江工业大学2012/2013 学年
第1学期试卷
课程________ 姓名 ________ 班级________ 学号 ________
题序 一 二 三 四 五 六 七 八 九 十 总分 计分
一、 1.下列语句是命题的是( A )。
A 、离散数学是重要的一门必修课。
B 、1+101=110?
C 、我正在说谎。
D 、全体起立! 2.图 的邻接矩阵为( C )。
A 、 1
111111*********⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭
B 、1
110011*********⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭
C 、0
110001*********⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭
D 、0
111101*********-⎛⎫ ⎪
- ⎪ ⎪-- ⎪-⎝⎭
3.下列排列能构成图的顶点度序列的是( A )。
A 、1,2,2,3,4
B 、2,3,4,5,6,7
C 、2,1,1,1,2
D 、3,3,5,6,0 4.设{}b a A ,=,则I A =(D )。
A 、 A ;
B 、A×I A ;
C 、 I A ×A ;
D 、{,,,}a a b b <><>。
5.下述命题公式中,是重言式的为( C )。
A 、)()(q p q p ∨→∧;
B 、))())(()(p q q p q p →∧→↔↔;
C 、q q p ∧→⌝)(;
D 、q p p ↔⌝∧)(。
二、填空题15分 (每小题 3分)
1已知一棵无向树T 有三个3度顶点,一个2度顶点,其余的都是1度顶点, 则T 中有 5 个1度顶点。
2.设A={1,2,3,4},A 上二元关系R={<2,2>,< 2,3>, < 3,2>, < 3,1>},则S(R)= {<2,2>,<2,3>,<3,2>,<3,1>,<1,3>}。
3.A={1,2,3,4,5,6},A 上二元关系}|,{是素数y x y x T ÷><=,则用列举法给出T={<2,1>,<3,1>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<4,2>,<6,3>,<5,1>,<6,2>}。
4.任何(n,m)图 G=(V,E),边数与顶点数的关系是 m=n-1/sum(d(v i ))=2m 5.设 P (x ):x 是素数, E(x):x 是偶数,O(x):x 是奇数 N (x,y):x 可以整数y 。
则谓词))),()(()((x y N y O y x P x wff
∧∃→∀的自然语言是
对于任何素数都存在一个能整除它的奇数
三、计算或推理题(30’,每题6分)
1、((,)())(,)xF x y yG y xH x y ∀→∃→∀ 求前束范式。
(((,)())(,))x y t F x z G y H t z ∀∀∀→→
2、证明:P ∨Q ,Q →R ,P →S ,⌝S ⇒ R
证明:
(1) ⌝S P 前提 (2) P →S P 前提
(3) ⌝P T(1)(2)I 拒取式 (4) P ∨Q P 前提
(5) Q T(3)(4)I 析取三段论 (6) Q →R P 前提
(7) R T(5)(6)I 假言推理
3.设A={a,b,c,d},R 为A 上的关系,R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},求r(R),s(R),t(R)。
r(R)={<a,a>,<a,b>,<b,b>,<b,a>,<b,c>,<c,c>,<c,d>,<d,d>,<d,b>} s(R)={<a,b>,<b,a>,<b,c>,<c,b>,<c,d>,<d,c>,<d,b>,<b,d>}
t(R)={<a,b>,<b,a>,<a,a>,<b,b>,<b,c>,<a,c>,<c,d>,<a,d>,<b,d>,<d,b>,<d,a>,<d,c>}
4.已知偏序集<A,R>的哈斯图如图所示,试求出集合A 和关系R 的表达式。
((,)())(,)xF x yG y xH x z z ⇔∀→∃→∀((,)())(,)xF x yG y H t z z t ⇔∀→∃→∀((,)())(,)x F x z yG y tH t z ⇔∃→∃→∀((,)())(,)x y F x z G y tH t z ⇔∃∃→→∀(((,)())(,))
x y F x z G y tH t z ⇔∀∀→→∀
A={a,b,c,d,e,f,g,h}
R={ <b,d>,<b,e>,<b,f>,<c,d>, <c,e>,<c,f>,<d,f>,<e,f>,
<g,h>}∪I A
5.列举集合A ={a,b,c,d}上所有不同的等价关系。
只要求出A 上的全部划分,即为等价关系。
划分为一个块的情况:1种,即{a,b,c,d} 划分为两个块的情况:7种,即 {{a,b},{c,d}},{{a,c},{b,d}},{{a,d},{b,c}} {{a},{b,c,d}},{{b},{a,c,d}},{{c},{a,b,d}}, {{d},{a,b,c}} 划分为三个块的情况:6种,即 {{a,b},{c},{d}},{{a,c},{b},{d}},{{a,d},{b},{c}}, {{a},{b},{c,d}},{{a},{c},{b,d}},{{a},{d},{b,c}} 划分为四个块的情况:1种,即{a},{b},{c},{d}} 因此,共有15种不同的等价关系。
四 逻辑推理(10’):
有些女孩喜欢各种香水,但女孩都不喜欢有毒物体,所以香水都不是有毒物体。
答:
M(x): x 是女孩, D(x): x 是香水, Q(x): x 是有毒的, L(x,y): x 喜欢y
前提:(()(()(,))(()(()(,))
x M x y D y L x y x M x y Q y L x y ∃∧∀->∀∧∀->⌝
结论:(()())x D x Q x ∀->⌝
(1)(()(()(,))(2)()(()(,))(1)(3)(()(()(,)))(2)(4)()(()(,))(3)(5)()(,)(4)(6)(()(()(,))(7)()(()(,)(6)(8)x M x y D y L x y P M a y D y L a y T ES y M a D y L a y T E M a D b L a b T US D b L a b T I
x M x y Q y L x y P M a y Q y L a y T US ∃∧∀->∧∀->∀∧->∧->->∀∧∀->⌝∧∀->⌝∀(()(()(,))(7)(9)()(()(,))(8)(10)()(,)(9)(11)(,)()(10)(12)()()(5)(11)(13)(()())(12)y M a Q y L a y T E M a Q b L a b T US Q b L a b T I L a b Q b T E D b Q b T I x D x Q x T UG
∧->⌝∧->⌝->⌝->⌝->⌝∀->⌝
五 树的应用(10’)
根据下图求最小生成树,假设生成树中五个节点a, b, c, d, e 的权重分别为12、8、15、7、6,求传输它们的最佳前缀码(构造最优二叉树)。
a
b
c
d
e
010
00
11
1
a: 00 c: 11 e: 101 b: 01 d: 100
六、(10’)
画出该图形的对偶图形,为对偶图按韦尔奇.鲍威尔方法按步骤进行着色(颜色用数字表示)。
要求着色的过程和每一步骤都要具体写出。
排序 :a b c d e f 第一次:a e 第二次:b f 第三次:c 第四次:d
七、包含排斥原理(10’)
24名科技人员,每人至少会1门外语.
英语:13; 日语:5; 德语:10; 法语:9 英日:2; 英德:4; 英法:4; 法德:4 会日语的不会法语、德语
求:只会 1 种语言人数,会 3 种语言人数
●
x+2(4-x)+y1+2=13
x+2(4-x)+y2=10
x+2(4-x)+y3=9
x+3(4-x)+y1+y2+y3=19。