2011级离散数学AB原题与部分答案.doc

PAGE

第PAGE4页（共NUMPAGES7页）

(A)

一、数理逻辑（共40分）

1.判断下列语句，如果是命题的在后面打√，如果不是命题在后面打×。（5分）

（1）起来吧，我的朋友。（）

（2）只有小孩才爱哭。（）

（3）2+3=8。（）

（4）这句话是错的。（）

（5）喜马拉雅山最高。（）

2.用真值表证明等值式P→(Q→R)（P∧Q）→R。（6分）

3.求公式的主析取范式。（7分）

4.假设论述域为全总个体域，用谓词和量词符号化下列命题。（6分）

（1）有些人用左手写字。

（2）不是所有的火车都比所有的汽车快。

5.若论述域是{a,b,c}，试消去下列公式中的量词。(5分)

6.公安人员审一件盗窃案，已知：

甲或乙盗窃了电脑。甲盗窃了电脑仅当作案时间不能发生在午夜前。若乙证词正确，则在午夜时屋里灯光未灭。若乙证词不正确，则作案时间发生在午夜前。午夜时屋里灯光灭了。问谁是盗窃犯？

（第一步：找出原子命题（1分）；

第二步：对原命题进行符号化（5分）；

第三步：用（步骤命题依据）的形式，构造证明过程（5分））

二、集合、关系和函数（共36分）（原题与答案）

1.用文氏图表示集合。(2分)

答： 结果为灰色区域

2.计算集合{{1}，1}的幂集。（2分）

答：{Φ，{{1}}，{1}，{{1}，1}}

3.设，，

则分别求出=？,=？。（4分）

答：={2,3,4,6,8,9,12}

={6,12}

4.设,是上的关系，求出的元素。(2分)

答：{1,2,1,31,41,51,6,2,4,2,6,3,6}Is

5.设，定义在上的关系如下：.

(1)画出的关系图，并写出的关系矩阵.(4分)

(2)说明具备那些性质，并求出r(R),s(R),t(R).（6分）

答：

（1）

（2）反自反，不对称，不传递

r(R)=

s(R)={2,1,4,2,3,1}

t(R).={1,4}

6．设，画出集合关于整除关系的哈斯图，并指出它的极小元、最小元、极大元、最大元。（6分）

答：

极小元：1 极大元：6，8，9 最小元：1 最大元：无

7．已知f，g，h是R到R的函数。

；；。求，（6分）

(提示：(f1f2f3)(x)=f3(f2(f1(x))))

答：

8．函数f是N到N的函数：。证明f是单射不是满射。（4分）

答：

设,，则

，，则，所以f是单射

，设，此x在定义域内不存在，所以f不是满射

三、图论（共24分）

1.设n阶无向简单图G中，有16条边，每个顶点都是2度顶点，问图G中有几个顶点。（要求写出计算过程）？（4分）

答：

设有n个顶点

2*16=2*n

n=16

2.画出所有含有5个顶点，3条边的不同构的简单图。（4分）

答：

3.下面图是不是平面图？如果是，则请给出平面嵌入。（4分）

答：

4.设无向树T有3个3度，2个2度顶点，其余顶点都是树叶，问T中有几片树叶？（要求写出计算过程）并画出满足要求的非同构的无向树.。（4分）

答：

设有n个顶点

2*(n-1)=3*3+2*2+(n-3-2)*1

n=10

5.列出下图所有的割点与割边。（4分）

答：

割点：b,f

割边：(f,g)

6.设7个符号在通信中出现的频率为：A:20%,B:35%,C:15%,D:10%,E:10%,F:5%，G:5%以频率为权，求最优2元树。(4分)

答：

(B)

一、数理逻辑（共40分）

1.判断下列语句，如果是命题的在后面打√，如果不是命题在后面打×。（5分）

（1）2是素数吗?（）

（2）17只能被1和它本身整除。（）

（3）2+3=8。（）

（4）我正在说谎。（）

（5）如果太阳从从西方升起，你就可以长生不老。（）

2.写出命题公式的真值表。(6分)

3.求公式的主合取范式。（7分）

4.假设论述域为全总个体域，用谓词和量词，符号化下列命题。（6分）

（1）每个自然数都有后继数。

（2）某些人对某些食物过敏。

5设个体域为，则消去量词后为：__________。(5分)

6．构造下列命题的证明过程：

2是素数或合数。若2是素数，则是无理数。若是无理数，则4不是素数。所以，如果4是素数，则2是合数。

（第一步：找出原子命题（1分）；

第二步：对原命题进行符号化（4分）；

第三步：用（步骤命题依据）的形式，书写构造性证明过程（6分））

二、集合、关系和函数（共36分）（原题与答案）

1.