一、数理逻辑（共40分）
1.判断下列语句，如果是命题的在后面打√，如果不是命题在后面打×。（5分） （1）起来吧，我的朋友。（ ） （2）只有小孩才爱哭。（ ） （3）2+3=8。（ ） （4）这句话是错的。（ ） （5）喜马拉雅山最高。（ ）
2.用真值表证明等值式P→(Q→R)? （P∧Q）→R。（6分）
3.求公式(?p?q)?(?q?p)的主析取范式。（7分）
4.假设论述域为全总个体域，用谓词和量词符号化下列命题。（6分） （1）有些人用左手写字。
（2）不是所有的火车都比所有的汽车快。
5.若论述域是{a,b,c}，试消去下列公式中的量词。(5分)
?xR(x)??xS(x)
6.公安人员审一件盗窃案，已知：
甲或乙盗窃了电脑。甲盗窃了电脑仅当作案时间不能发生在午夜前。若乙证词正确，则在午夜时屋里灯光未灭。若乙证词不正确，则作案时间发生在午夜前。午夜时屋里灯光灭了。问谁是盗窃犯？
（第一步：找出原子命题（1分）；
第二步：对原命题进行符号化（5分）；
第三步：用（步骤 命题 依据）的形式，构造证明过程（5分））
二、集合、关系和函数（共36分）
1. 用文氏图表示集合~A?(B?C)。(2分)
第 1 页（共 7 页）
2. 计算集合{{1}，1}的幂集。（2分）
3. 设M?{x|1?x?12,x被2整除，x?Z}，N?{x|1?x?12,x被3整除，x?Z}，
则分别求出M?N=？,M?N=？。（4分）
4. 设S?{1,2,?,6},R是S上的关系，R?{?x,y?|x,y?S?x是y的倍数(2分) }求出R的元素。
5. 设A?{1,2,3,4}，定义在A上的关系R如下：R?{?1,2?,?2,4?,?3,3?,?1,3?}.
(1)画出A的关系图，并写出R的关系矩阵.(4分)
(2)说明A具备那些性质，并求出r(R), s(R), t(R). （6分）
6．设A?{1,2,?,9}，画出集合A关于整除关系的哈斯图，并指出它的极小元、最小元、极大
元、最大元。（6分）
7．已知f，g，h是R到R的函数。
1；h(x)?x4。求f?f，f?g?h（6分） f(x)?x3?4x；g(x)?2x?1(提示：(f1?f2?f3)(x)= f3( f2( f1(x))) )
8．函数f是N到N的函数：f(n)?n?1。证明f是单射不是满射。（4分）
三、图论（共24分）
1. 设n阶无向简单图G中，有16条边，每个顶点都是2度顶点，问图G中有几个顶点。（要
第 2 页（共 7 页）
求写出计算过程）？（4分）
2. 画出所有含有5个顶点，3条边的不同构的简单图。（4分）
3. 下面图是不是平面图？如果是，则请给出平面嵌入。（4分）
4. 设无向树T有3个3度，2个2度顶点，其余顶点都是树叶，问T中有几片树叶？（要求写出计算
过程）并画出满足要求的非同构的无向树.。（4分）
5. 列出下图所有的割点与割边。（4分）
abcgd
6.设7个符号在通信中出现的频率为：A:20%, B:35%, C:15%, D:10%, E:10%, F:5%，
fe
G:5%以频率为权，求最优2元树。(4分)
第 3 页（共 7 页）
一、数理逻辑（共40分） 1.判断下列语句，如果是命题的在后面打√，如果不是命题在后面打×。（5分） （1）2是素数吗?（ ）
（2）17只能被1和它本身整除。（ ） （3）2+3=8。（ ） （4）我正在说谎。（ ）
（5）如果太阳从从西方升起，你就可以长生不老。（ ） 2. 写出命题公式的真值表 (?p?q)?(?q?r)。(6分)
3.求公式(?p?q)?(?q?p)的主合取范式。（7分）
4.假设论述域为全总个体域，用谓词和量词，符号化下列命题。（6分）
（1）每个自然数都有后继数。 （2）某些人对某些食物过敏。 5设个体域为A?{a,b}，则?x(F(x)?G(x))消去量词后为：__________。(5分)
6．构造下列命题的证明过程：
2是素数或合数。若2是素数，则 2 是无理数。若 2 是无理数，则4不是素数。 所以，如果4是素数，则2是合数。 （第一步：找出原子命题（1分）；
第二步：对原命题进行符号化（4分）；
第三步：用（步骤 命题 依据）的形式，书写构造性证明过程（6分））
二、集合、关系和函数（共36分）
1. 用文氏图表示集合A?(~B?C)。(2分)
第 4 页（共 7 页）
2. 计算集合{1，2}的幂集。（2分）
3. 设全集E?{1,2,3,4,5}，它的子集：A?{1,3}，B?{1,4,5},C?{4,3}
则分别求出A?B=? (A?B)?C=?。（4分）
4. A?{1,3},B?{1,3,5},R?{?x,y?|x,y?A?B}?A?B,求出R的元素。(2分)
5. 设A?{1,2,3,4}，定义在A上的关系R如下：R?{?1,2?,?2,4?,?1,4?}. (1)画出A的关系图，并写出R的关系矩阵.(4分)
(2)说明A具备那些性质，并求出r(R), s(R), t(R). （6分）
6．设A?{1,2,3,4,6,8,12,24}，画出集合A关于整除关系的哈斯图，并指出它的极小元、最小元、极大元、最大元。（6分）
7. 已知f，g，h是R到R的函数。
f(x)?x?4x；
3g(x)?14x2?1；h(x)?x。求g?g，g?h?f（6分）
(提示：(f1?f2?f3)(x)= f3( f2( f1(x))) )
0,n?1}。证明g是满射不是单射。8．函数f是N到N的函数：g(n)?max{（4分）
第 5 页（共 7 页）