【精选】离散数学复习知识点.docx

离散数学复习知识点
复习知识点：
第1章
命题、真命题、假命题
命题符号化〔连接词〕
设P：天下大雨，Q：他在室内运动，命题“除非天下大雨，否那么他不在室内运动〞可符合化为〔　D　〕
A． c}。求以下集合：
〔1〕A´{0, 1}´B； 〔2〕B2´´A； 〔3〕(A´B)2； 〔4〕r (A)´A。
解：
〔1〕A´{0, 1}´B={<a, 0, c>, <a, 1, c>, <b, 0, c>, <b, 1, c>}；
〔2〕B2´A={<c, c, a>, <c, c, b>}；
〔3〕(A´B)2={<a, c, a, c>, <a, c, b, c>, <b, c, a, c>, <b, c, b, c>}；
〔4〕r (A)´A={<Ф, a>, <Ф, b>, <{a}, a>, <{a}, b>, <{b}, a>, <{b}, b>, <a, a>, <a, b>}。
关系
1. 设A={a,b,c}，那么A上的二元关系有 23*3 或512 个 。
2. 集合A={1, 2, …, 10}上的关系R={<x, y>：x+y=10, x, yÎA}，那么R 的性质为〔B〕
A．自反的 B．对称的 C．传递的，对称的 D．传递的
设A={Ф, {1}, {1, 3}, {1, 2, 3}}，那么A上包含关系“Í〞的哈斯图为〔C〕
A． B．
C． D．
集合A上的等价关系的三个性质是 自反性 、 对称性 和 传递性 。
集合A上的偏序关系的三个性质是自反性 、 反对称性 和 传递性 。
A上的偏序关系的Hasse图如下。
〔1〕以下哪些关系式成立：ab，ba，ce，ef，df，cf；
〔2〕分别求出以下集合关于的极大〔小〕元、最大〔小〕元、上〔下〕界及上〔下〕确界〔假设存在的话〕：
〔a〕A； 〔b〕{b, d}； 〔c〕{b, e}； 〔d〕{b, d, e}。

解：
〔1〕 ba，ce，df，cf成立；
〔2〕〔a〕的极大元为a, e, f，极小元为c；无最大元，c是最小元；
无上界，下界是c；无上确界，下确界是c。
〔b〕的极大元为b, d，极小元为b, d；无最大元和最小元；
上界是e，下界是c；上确界是e，下确界是c。
〔c〕的极大元为e，极小元为b；最大元是e，b是最小元；
上界是e，下界是b；上确界是e，下确界是b。
〔d〕的极大元为e，极小元为b,d；最大元是e，无最小元；
上界是e，下界是c；上确界是e，下确界是c。
设A={2，3，4}，B={2，4，7，10，12}从A到B的关系
，试给出的关系图和关系矩阵，并说明此关系及其逆关系是否为函数？为什么？
A
2
3
4
B
2
4
7
10
12
解：，那么的关系图为：
的关系矩阵为

关系不是到的函数，
因为元素2，4的象不唯一
逆关系也不是到的函数
因为元素7的象不存在．
以下函数是双射的为〔A〕。
A．f : Z®E , f (x) = 2x B．f : N®N´N, f (n) =<n
C．f : R®Z , f (x) = [x] D．f : Z
®N, f (x) = | x |
〔注：Z—整数集，E—偶数集， N—自然数集，R—实数集〕
设分别为整数集，自然数集，偶数集，那么以下函数是双射的为〔 A 〕
A． : , B． : ,
C．: , D． : ,
设，那么以下关系中能构成到函数的是〔 C 〕
A． B．
C． D．
设函数，都是单射，那么〔 A 〕
A．是单射 B．是满射 C．是双射 D．既非单射又非满射
设函数，都是满射，那么〔
B 〕
A．是单射 B．是满射 C．是双射 D．既非单射又非满射
设是自然数集上的函数,，
那么，．
关系F={<x1,y1>,<x2,y2>,<x3,y2>}是函数 〔　对 　〕
关系F={<x1,y1>,<x1,y2>}是函数 〔　错　 　〕
设图G的邻接矩阵为

那么G的边数为( B )．
A．6