离散数学期末试卷及答案
一.判断题(共10小题,每题1分,共10分)
在各题末尾的括号内画 表示正确,画 表示错误:
1.设p 、q 为任意命题公式,则(p∧q) ∨p ⇔ p ( )
2.∀x(F(y)→G(x)) ⇔ F(y)→∃xG(x)。 ( )
3.初级回路一定是简单回路。 ( )
4.自然映射是双射。 ( )
5.对于给定的集合及其上的二元运算,可逆元素的逆元是唯一的。 ( )
6.群的运算是可交换的。 ( )
7.自然数集关于数的加法和乘法构成环。 ( )
8.若无向连通图G 中有桥,则G 的点连通度和边连通度皆为1。 ( )
9.设A={a,b,c},则A 上的关系R={,}是传递的。 ( )
10.设A 、B 、C 为任意集合,则A ⨯(B⨯C)=(A⨯B) ⨯C 。 ( )
二、填空题(共10题,每题3分,共30分)
11.设p :天气热。q :他去游泳。则命题“只有天气热,他才去游泳”可符号 化为 。
12.设M(x):x 是人。S(x):x 到过月球。则命题“有人到过月球”可符号 化为 。
13. p q 的主合取范式是 。
14.完全二部图K r,s (r
15.设A={a,b},, 则A 上共有个不同的偏序关系。
16.模6加群中,4是 阶元。
17.设A={1,2,3,4,5}上的关系R={,,,,},则R 的传递闭包t(R) = 。.
18.已知有向图D 的度数列为(2,3,2,3),出度列为(1,2,1,1),则有向图D 的入度
列为 。
19.n 阶无向简单连通图G 的生成树有 条边。
20.7阶圈的点色数是
三、运算题(共5小题,每小题8分,共40分)
21.求∃xF(x)→∃yG(x,y)的前束范式。
22.已知无向图G 有11条边,2度和3度顶点各两个,其余为4度顶点,求G 的顶点数。
23.设A={a,b,c,d,e,f},R=IA ⋃{,},则R 是A 上的等价关系。求等价类[a]R 、[c]R 及商集A/R。
24.求图示带权图中的最小生成树,并计算最小生成树的权。
25.设R *为正实数集,代数系统、、中的运算依次为普通加法、乘法和除法运算。试确定这三个代数系统是否为群?是群者,求其单位元及每个元素的逆元。
四、证明题(共3小题,共20分)
26 (8分)在自然推理系统P 中构造下述推理的证明:
前题:p →(q∨r) ,⌝s →⌝q , p ∧⌝s
结论:r
27 (6分)设是群,H={a| a∈G ∧ ∀g ∈G ,a *g=g*a},则是G 的子群
28.(6分)设G 是n(≥3) 阶m 条边、r 个面的极大平面图,则r=2n-4。
适用年级专业:2006级软件工程专业
试卷说明:闭卷考试,考试时间120分钟
一.判断题(共10小题,每题1分,共10分)
在各题末尾的括号内画 表示正确,画 表示错误:
1. ( ) 2. ( ) 3. ( ) 4. ( ) 5. ( )
6. ( ) 7. ( ) 8. ( ) 9. ( ) 10. ( )
二、填空题(共10题,每题3分,共30分)
11. q →p 12.∃x(M(x)∧ S(x))
13.(⌝p ∨q) ∧ (p∨⌝q) 14. r
15. 3 16. 3
17..R 18.(1,1,1,2)
19. n-1 20. 3
三、运算题(共5小题,每小题8分,共40分)
21.解:∃xF(x)→∃yG(x,y)⇔ ∃xF(x)→∃yG(w,y)
⇔∀x(F(x)→∃yG(w,y))
⇔∀x ∃y (F(x)→ G(w,y))
22.解:设图G 有n 个顶点m 条边,则
2m=2(2+3)+4(n-4),即22=10+4(n-4)
解之得n=7。
23.解:[a]R ={a,b},[c]R ={c},[d]R ={d},[e]R ={e},[f]R ={f},
A/R={{a,b},{c},{d},{e},{f}}
24.解:最小生成树T 如图中红线所示,W(T) = 12
25. 解:仅是群。其单位元为1。任意x ∈ R*,其逆元为1/x。
四、证明题(共3小题,共20分)
26 证明:① p ∧⌝s 前提引入
② p ①,化简
③ p →(q∨r) 前提引入
④ q ∨r ②③,假言推理
⑤ ⌝s ①,化简
⑥ ⌝s →⌝q 前提引入
⑦ ⌝q ⑤⑥,假言推理
⑧ r ④⑦,析取三段论
27 (6分)证:设e 是G 的单位元,∀g ∈G , e*g=g*e ,所以e ∈H, 故H 非空。
(1)∀a,b ∈H, ∀g ∈G ,有a *g=g*a, b*g=g*b, 那么
(a*b) *g=a*(b*g)= a*(g*b)=(a*g) *b=(g*a) *b=g*(a*b)
所以a *b ∈H 。
-1(2)∀a ∈H, ∀g ∈G ,有a *g=g*a ,a ∈G 。
a -1*g=a-1*g *e=a-1*g *a *a -1= a-1*(g*a) *a -1=a-1*(a*g) *a -1
=(a-1*a) *g *a -1=e*g *a -1=g*a -1
-1所以,a ∈H 。
根据子群判定定理一,H 是G 的子群。
28.(6分)证:极大平面图一定是连通图,由欧拉公式
r=2+m-n ………….(1)
又因为极大平面图每面的次数皆为3,从而
2m=3r……………….(2)
由(1)、(2)式联立解得
r=2n-4。