中南大学考试试卷
2009 -- 2010 学年 一 学期期末考试试题 时间100分钟
离散数学课程48学时3学分 考试形式：闭卷
一、
判断（本大题共10小题，每小题1分，共10分）
（ ）1．ρ(A)?? ρ(B) <=> A是B的子集
（ ）2．Q∧R∨P∧R∨T∧?P∧R的对偶式为Q∨R∧P∨R∧F∨?P∨R （ ）3．设Ａ和Ｂ是两个命题公式，若Ａ=＞B且B是重言式，则A是重言式。 （ ）4．R和S都是集合A上的关系，若R和S是自反的，则R?S是自反的。 （ ）5．设A、B和C是集合，若A∩B=A∩C，且A??，则B=C。
（ ）6．若R和S都是集合A上的二元关系，则dom(R)∪dom(S)=dom(R∪S)。 （ ）7．是全序集，则A的任何非空子集必有唯一极小元。 （ ）8．有限集上的全序关系必是良序关系。 （ ）9．连通的4度正则图一定没有桥。
（ ）10.设无向图G具有割点，则G中一定不存在哈密尔顿通路。 二、
单项选择（本大题共6小题，每小题2分，共12分）
（ ）1．若公式A(P,Q,R)的主合取范式为∏（0，1，4，5），则下列公式哪个是A(P,Q,R)的主析取范式
① ∑（0，1，4，5） ② ∏（0，1，4，5） ③ ∑（2，3，6，7） ④ ∏（2，3，6，7）
（ ）2．设∏1和∏2都是非空集合A的划分，则下列集合哪个必定是A的划分
① ∏1∪∏2 ② ∏1∩∏2 ③ ∏1—∏2 ④（∏1∩（∏2—∏1））∪∏2
（ ）3．设A-B=?，则下列命题中正确的是?
① B=? ② B≠? ③ A??B
④ B ? A
（ ）4．设R是集合A上的偏序关系，R-1 是R的逆关系，则R∪R-1是
①偏序关系 ②等价关系
③非自反关系
④非传递关系
（ ）5．若f、g是A上的双射，则
①
f?g是双射
②
(f?g)-1 =f-1?g-1
③
f?g?g?f ④ 以上答案都不对
（ ）6．任何无向图中结点间的可达关系是 三、 1． 2． 3．
若用谓词R(x)表示“x是实数”，L(x, y)表示“x 填空（本大题共9小题，每空2分，共24分） 若简单连通平面图G有4个结点，3个面，则G有______条边。 下图G最少需要_____种颜色进行点着色。 ① 偏序关系 ③ 全序关系 ② 等价关系 ④ 拟序关系 式为：_________________。 4． 给定论域D={1,2}和谓词P： P(1,1)TP(1,2)TP(2,1)TP(2,2)F。则公式 ?x?y(P(x,y)?P(y,x))的真值为 _____。 5． 6． 7． 若A是n元集合（n>0），则有______个不同的A上的即对称又反对称的关系。 一棵树有两个2度顶点，一个3 度顶点，三个4 度顶点，则该树有______片树叶 设集合A={a,b,c,d,e}上的偏序关系R的哈斯图如下图所示： e b a c d 则A的最大元是________；A的最小元是________；A的极大元是________；A的极小元是________； 8． 9． 四、 1． 2． 3． 分别作出R，r (R )，sr(R )和tsr(R )的关系矩阵。 4． 2 设N是自然数集合，f和g是N到N的函数，f (n)=2n+1,g (n)=n，则复合函数f2?g (n)= ______ 集合Ａ={1,2,3,4,5}上的等价关系Ｒ= 将导致集合Ａ的划分，即商集Ａ/Ｒ={{1,2},{3},{4,5}}。 计算与作图（共36分） (8分) 设Ａ={ 2, 3, 12, 18, 24, 30, 36, 72}，｜为自然数的整除关系。画出<Ａ;｜>的Ｈasse图，并求{12, 24, 36}的上、下确界。 (8分) 设Ａ＝{a, b, c, d},Ｂ＝{1,2}，f＝{, 0 1 0 0 1 0 (12分) 有 8 种化学品 a, b, c, d, e, f, g, h 要放进贮藏室保管. 下列各对化学品不能贮藏在同一室内: a-c, a-f, a-h, b-d, b-f, b-h, c-d, c-g, d-e, d-g, 1 1 0 e-f, e-g, f-g, g-h (1) (5分)画一个图表示这些化学品不能混放的情况，并对你的图加以文字说明； (2) (4分)贮藏这 8 种化学药物至少需要几个房间. 一个房间最多贮藏多少种化学品，请写出一种方案； (3) (3分)假如每种化学品的专家一定熟悉与该种化学品不能混放的化学品的特性(例如化学品a的专家熟悉化学品c, f, h), 则至少需要聘任多少位专家, 才能使每种化学品都有对其特性熟悉的人，请给出一种聘任方案。 五、 1． 证明（本大题共3小题，每小题6分，共18分） 用形式推理的标准格式证明： A?B?C?D,D?E?P?A?P2． 3． 判断?x(P(x) 是否是重言式，并说明理由。 ?Q(x))?(?xP(x)??xQ(x))证明: 任意一场聚会, 至少有两个人与相同数目的人握过手。 评分标准 一、 判断 (1)T (2)F (3)F (4)T (5)F (6)T (7)F 二、 单项选择 1. ③ 三、 填空 1. 5 2. 3 3. ?x?y(R(x)∧R(y)∧L(x,y)→?z(R(z)∧L(x,z)∧L(z,y)))_或?x?y(R(x)∧R(y)→(L(x,y)→?z(R(z)∧L(x,z)∧L(z,y))))或 2. ④ 3. ③ 4. ② 5.① 6. ② (8)T (9)T (10)F 与之等价的其他形式。 4. T 8. 2n2+1 5. 2 n 6. 9 7. 最大元：无；最小元：a；极大元：b,e,d；极小元：a 9. {<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<1,2>,<2,1>,<4,5>,<5,4>} 四、 计算与作图 1. 72 24 36 （4分） 12 18 30 2 3 （上下确界各2分） {12, 24, 36}的上确界：72；下确界：12 2. 有右逆无左逆（2分） g1={<1,a>,<2,c>}；g2={<1,b>,<2,c>}；g3={<1,d>,<2,c>} （每个2分） 3. R2= 0 1 0 0 1 0 0 1 0 sr(R )= 1 1 1 1 1 1 （每个2分） 1 1 1 r (R )= tsr(R )= 1 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 4. (1) 节点表示化学药品，如果两种药品不能混放就在其间连一条边，图略；或者节点表示化学药品，如果两种药品能混放就在其间连一条边 (2) 如果是上述第一种画图法，即在图中寻找极大顶点无关集；如果是第二种画图法，即在图中寻找极大完全子图。至少需要3个房间，每个房间最多放3中药品。一种放置方案：{a,b,g}, {c,e,h}, {d,f}（不唯一） (3) 至少需要2人，比如请g和f的专家 五、 证明 1. A?B?C?D,D?E?P?A?PT⑴ I P ⑴ A P (附加前提) ⑵ A∨B ⑶ (A∨B)?(C∧D) ⑷ C∧D T⑵⑶ I ⑸ D ⑹ D∨E ⑺ (D∨E)?P P ⑻ P T ⑹⑺ I T⑷ I T⑸ I ⑼ A?P （格式不对酌情扣分） CP 2. 不是永真式，取解释如下 D= {1,2} P(1) P(2) Q(1) Q(2) F T F T 在该解释下?xP(x) 为T，?xQ(x)为F，所以?xP(x) →?xQ(x)为F；而(P(1) →Q(1))为T， (P(2) →Q(2))为T，所以?x(P(x) →Q(x))为T； 综上该公式不是永真式 3. 因为一个人若与同一人握手多次不会影响其握手的人数，所以该问题即证任一无向简单图中必有两个点的度相等 证明略 离散数学考试试题（A卷及答案） 一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？ 1)((P?Q)∧Q)?((Q∨R)∧Q) 2)?((Q?P)∨?P)∧(P∨R) 3)((?P∨Q)?R)?((P∧Q)∨R) 解：1)永真式；2）永假式；3)可满足式。 二、（8分）个体域为{1，2}，求?x?y（x+y=4）的真值。 解：?x?y（x+y=4）??x（（x+1=4）∨（x+2=4）） ?（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+1=4）） ?（0∨0）∧（0∨1） ?1∧1?0 三、（8分）已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？A到B的函数数是多少？ 解：因为|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元关系有2mn个。因为|BA|=|B||A|=mn，所以A到B的函数mn个。 四、（10分）已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。 解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>} t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>} 五、(10分) 75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。 解 设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合， |A∩B∩C|＝20，|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|＝55，|A|＋|B|＋|C|＝70/0.5＝140。 由容斥原理，得 |A∪B∪C|＝|A|＋|B|＋|C|―|A∩B|―|A∩C|―|B∩C|＋|A∩B∩C| 所以 |A∩B∩C|＝75－|A∪B∪C|＝75－(|A|＋|B|＋|C|)＋(|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|)＋|A∩B∩C|＝75－140＋55＋20＝10 没有乘坐过其中任何一种的儿童共10人。 六、（12分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。 解：?x∈A，因为R和S是自反关系，所以 ?x、y∈A，若 ?x、y、z∈A，若 总之R∩S是等价关系。 2）因为x∈[a]R∩S? ∩[a]S 所以[a]R∩S=[a]R∩[a]S。 七（10分）设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×C?B×D且?∈A×C，h()＝ 证明：1）先证h是满射。 ? 2）再证h是单射。 ?、∈A×C，若h()＝h()，则