2009级(软件工程)离散数学试题答案
- 格式：pdf
- 大小：13.27 KB
- 文档页数：2
2009级离散数学A卷试题参考答案
一、填空题（每小题2分，共20分）
1．q→ｐ 2．∀x∀y(S(x)∧T(y)→H(x,y))/ ∃x∃y(S(x)∧T(y)∧H(x,y)) 3．(F(1, 1）∧F(1, 2)）∨( F(2, 1) ∧F(2, 2)) 4．4
5．f |f: B → A的函数 6．1、2、3、6 7．交换群、半群、分配律 8．D是强连通图且每个结点的出度等于入度
9．deg（u）+ deg（v）≥ n 10．n-1
二、判断题（每小题2分，共20分，正确的划v，错误的划×）
1．v 2．v 3．v 4．× 5．×
6．× 7．× 8．v 9．v 10．×
三、计算题（每小题5分，共15分）
1．Ｍ０１０（Ｍ２）
2．R1 ={<1，1>，<2，2>，<3，3>，<4，4>，<2，3>，<3，2>，<2，4>，<4，2>，<3，4>，<4，3>}
R2 ={<1，1>，<2，2>，<3，3>，<4，4>，<1，3>，<3，1>，<1，4>，<4，1>，<3，4>，<4，3>}
R3 ={<1，1>，<2，2>，<3，3>，<4，4>，<1，2>，<2，1>，<1，4>，<4，1>，<2，4>，<4，2>}
R4 ={<1，1>，<2，2>，<3，3>，<4，4>，<1，2>，<2，1>，<1，3>，<3，1>，<2，3>，<3，2>}
R5 ={<1，1>，<2，2>，<3，3>，<4，4>，<1，2>，<2，1>，<3，4>，<4，3>}
R6 ={<1，1>，<2，2>，<3，3>，<4，4>，<1，3>，<3，1>，<2，4>，<4，2>}
R7 ={<1，1>，<2，2>，<3，3>，<4，4>，<1，4>，<4，1>，<2，3>，<3，2>}
3．6
四、证明题（共45分）
1．对于任意z∈C，由fοg是满射，必存在x∈A，使得z=fοg（x）=g（f（x））；由f是A到B的函数，必存在y∈B，使得f（x）=y。即有z=g（y）成立。
2．①∃ｘ（Ｆ（ｘ）∧Ｉ（ｘ）） 前提引入
②Ｆ（ａ）∧Ｉ（ａ ） ①ＥＳ
③Ｆ（ａ） ②化简规则
④Ｉ（ａ） ②化简规则 ⑤(()())xFxGx∀→ 前提引入
⑥()()FaGa→ ⑤ＵＳ
⑦()Ga ③⑥假言推理
⑧()Ia∧()Ga ④⑦合取
⑨∃ｘ（Ｇ（ｘ）∧Ｉ（ｘ）） ⑧ＥＧ假言推理
3． (1)对任
4．(1)∀B、C∈P(A)，有B⊆A、C⊆A，则B⊕C=（B∪C）-（B∩C）⊆（B∪C）⊆A，B⊕C∈P(A)，满足封闭性。 (2)∀B、C、D∈P(A)，有B⊆A、C⊆A、D⊆A， 由⊕的性质知：(Ｂ⊕Ｃ） ⊕Ｄ＝Ｂ⊕ （Ｃ⊕Ｄ），满足结合性。 (3)∀B∈P(A)，Ｂ⊕Φ＝Φ⊕B ＝Ｂ， Φ是幺元。 （４）∀B∈P(A)，Ｂ⊕B＝Φ， Ｂ以自身为逆元。
5．设|a|=n，有an=e。则(a-1) n =(a-1) n ＊an= (a-1 ＊a)n=e。 若存在0 6．假设G中有桥，设e=(u,v)为其中一桥。考虑G-e产生k（k≥2）个连通分支，对任意连通分支Gi与Gj(i≠j)，它们之间的任何回路C都必经过e=(u,v)至少两次，u，v在C上重复出现，则C不是汉密顿回路。由C的任意性，问题得证。同理可证G中有割点的情况。
