中南大学离散考试试卷.docVIP

中南大学考试试卷 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．设Ａ和Ｂ是两个命题公式，若Ａ=＞BR和S是自反的，则R(S是自反的。 （ ）5．设A、B和C是集合，若A∩B=A∩C，且，则B=C。 （ ）6．若R和S都是集合A上的二元关系，则dom(R)∪dom(S)=dom(R∪S)。 （ ）7．A ; R是全序集，则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≠( ③ A??B ④ B ? A （ ）4．设R是集合A上的偏序关系，R-1 是R的逆关系，则R∪R-1是 ①偏序关系 ②等价关系 ③非自反关系 ④非传递关系 （ ）5．若f、g是A上的双射，则 ① 是双射 ② -1 =f-1g-1 ③ ④ 以上答案都不对 （ ）6．任何无向图中结点间的可达关系是 ① 偏序关系 ② 等价关系 ③ 全序关系 ④ 拟序关系 填空（本大题共9小题，每空2分，共24分） 若简单连通平面图G有4个结点，3个面，则G有______条边。 下图G最少需要_____种颜色进行点着色。 若用谓词R(x)表示“x是实数”，L(x, y)表示“xy”，那么命题“对于任意实数x和y，若xy，则必存在实数z使得xz且zy”的谓词表达式为：_________________。 给定论域D={1,2}和谓词P：。则公式的真值为_____。 若A是n元集合（n0），则有______个不同的A上的即对称又反对称的关系。 一棵树有两个2度顶点，一个3 度顶点，三个4 度顶点，则该树有______片树叶 设集合A={a,b,c,d,e}上的偏序关系R的哈斯图如下图所示： 则A的最大元是________；A的最小元是________；A的极大元是________；A的极小元是________； 设N是自然数集合，f和g是N到N的函数，f (n)=2n+1,g (n)=n2，则复合函数 (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＝{a,1,b,1,c,2,d,1}是Ａ到Ｂ的函数，试找出f的所有左逆和右逆（如果存在的话）。 (8分)设集合A={a,b,c,d}上的关系R的关系矩阵M (R )= 分别作出R2，r (R )，sr(R )和tsr(R )的关系矩阵。 (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, e-f, e-g, f-g, g-h画一个图表示这些化学品不能混放的情况贮藏这 8 种化学药物至少需要房间. 一个房间最多贮藏种化学品假如每种化学品的专家一定熟悉与该种化学品不能混放的化学品的特性(例如化学品a的专家熟悉化学品c, f, h), 则至少需要聘任位专家, 才能使每种化学品都有对其特性熟悉的人, 判断是否是重言式，并说明理由。 证明: 任意一场聚会, 至少有两个人与相同数目的人握过手