广东技术师范学院
模拟试题
科 目：离散数学
考试形式：闭卷 考试时间: 120 分钟 系别、班级： 姓名： 学号：
一．填空题（每小题2分，共10分） 1. 谓词公式∀xP (x ) →
P(x)∨Q(y) __________。 ∃xQ (x ) 的前束范式是__ ∃x ∃y¬
2. 设全集E ={1, 2, 3, 4, 5}, A ={1, 2, 3}, B ={2, 5}, 则A ∩A =_{4,5}____，
A B =3. 设A ={a , b , c }, B ={a , b }，则
ρ(B ) -ρ(A ) =_____Φ_______。
ρ(A ) -ρ(B ) =
__ {{c},{a,c},{b,c},{a,b,c}} __________，
4. 在代数系统（N ，+）中，其单位元是0，仅有 5．如果连通平面图G 有n 个顶点，e 条边，则G 有___e+2-n____个面。 二．选择题（每小题2分，共10分）
1. 与命题公式P →(Q →R ) 等价的公式是（ ） （A ）(P ∨Q ) →
R
（B ）(P
∧Q ) →R
（C ）P →(Q ∧R ) （D ）P →(Q ∨R )
2. 设集合A ={a , b , c },A 上的二元关系R ={, }不具备关系( ) 性质 （A ） (A)传递性 (B)反对称性 (C)对称性 (D)自反性 3. 在图G =中, 结点总度数与边数的关系是( ) (A)deg(v i ) =2E (B) deg(v i ) =E (C)∑deg(v i ) =2E (D)
v ∈V
∑deg(
v ∈V
v i ) =E
4. 设D 是有n 个结点的有向完全图, 则图D 的边数为( ) (A)n (n -1) (B)n (n +1) (C)n (n +1) /2 (D)n (n -1) /2 5. 无向图G 是欧拉图, 当且仅当( )
(A) G 的所有结点的度数都是偶数 (B)G的所有结点的度数都是奇数
(C)G 连通且所有结点的度数都是偶数 (D) G连通且G 的所有结点度数都是奇数。 三．计算题（共43分）
1. 求命题公式p ∧q ∨r 的主合取范式与主析取范式。（6分）
解：主合取方式：p ∧q ∨r ⇔(p∨q ∨r) ∧(p∨¬q ∨r) ∧(¬p ∨q ∨r)= ∏0.2.4
主析取范式：p ∧q ∨r ⇔(p∧q ∧r) ∨(p∧q ∧¬r) ∨(¬p∧q ∧r) ∨(¬p∧¬q∧r) ∨(p∧¬q∧r)= ∑1.3.5.6.7
⎛1
1=
0 0⎝
0000
0100
0⎫⎪1⎪
, 求⎪0⎪1⎪⎭
2. 设集合A ={a , b , c , d }上的二元关系R 的关系矩阵为M
R
r (R ), s (R ), t (R ) 的关系矩阵，并画出R ，r (R ), s (R ), t (R ) 的关系图。（10分）
3 无向图G 有12条边，G 中有6个3度结点，其余结点的度数均小于3，问G 中至少有多少个结点？（10分）
解：∵G （V ,E ），| E |=V，d （Vi ）8 故G 中至少有9个节点。
4 求下面两个图的最小生成树。（12分）
5. 试判断(z , ) 是否为格？说明理由。（5分）
解：（Z, ≤）是格，理由如下：
对于任意a ∈Z ，a ≤a 成立，满足自反性；
对于任意a ∈Z ，b ∈Z ，若a ≤b 且b ≤a ，则a=b，满足反对称性； 对于任意a ，b ，c ∈Z ，若a ≤b ，b ≤c ，则a ≤c ，满足传递性；
而对于任意a ，b ∈Z ，a ≤b ，b 为最小上界，a 为最大下界，故（Z ，≤）是格。
（注：什么是格？
）
四．证明题（共37分）
1. 用推理规则证明A →B , (⌝B ∨C ) ∧⌝C , ⌝(⌝A ∧D ) ⇒⌝D 。（10分）
证明： 编号 （1） （2） （3） （4） （5） （6） （7） （8）
公式 （¬B∨C ）∧¬C ¬B∨C ，¬C ¬B A →B ¬A ¬（¬A∧D ） A ∨¬D ¬D 依据 前提 （1） （2） （3） （3）（4） 前提 （6） （5）（6）
2. 设R 是实数集，f :R ⨯R →R , f (a , b ) =a +b ，g :R ⨯R →R , g (a , b ) =ab 。求证：f 和g 都是满射，但不是单射。（10分）
证明：要证f 是满射，即∀y ∈R, 都存在（x1，x2）∈R ×R ，使f （x1，x2）=y，而f （x1，x2）=x1+x2，可取x1=0，x2=y，即证得；
再证g 是满射，即∀y ∈R ，, 都存在（x1，x2）∈R ×R ，使g （x1，x2）=y，而g （x1，x2）=x1x2，可取x1=1，x2=y，即证得；
最后证f 不是单射，f （x1，x2）=f（x2，x1）取x1≠x2，即证得，同理：g （x1，x2）=g（x2，x1），取x1≠x2，即证得。
3. 无向图G 有9个结点，每个结点的度数不是5就是6，求证：G 中至少有5个6度结点或6个5度结点。（10分）
证明：设G 中至多有4个6度结点且5个5度结点， ∴d （Vi ）=49不是偶数， 故它不是一个图，矛盾。 （下面只供参考，个人答案）
4. 设平面上有100个点，期中任意两点间的距离至少是1，则最多有300对点距离恰好为1。（7分）
证明：设任意两点间的读书和恰好为1，则满足： ∑d （Vi ）=2e d （Vi ）≤6 ∴6×100≥2e e ≤300
故最多只有300条边，即300对点距离恰好为
1.
广东技术师范学院
模拟试题
科 目：离散数学
考试形式：闭卷 考试时间: 120 分钟 系别、班级： 姓名： 学号：
一．填空题（每小题2分，共10分） 1. 谓词公式∀xP (x ) →
P(x)∨Q(y) __________。 ∃xQ (x ) 的前束范式是__ ∃x ∃y¬
2. 设全集E ={1, 2, 3, 4, 5}, A ={1, 2, 3}, B ={2, 5}, 则A ∩A =_{4,5}____，
A B =3. 设A ={a , b , c }, B ={a , b }，则
ρ(B ) -ρ(A ) =_____Φ_______。
ρ(A ) -ρ(B ) =
__ {{c},{a,c},{b,c},{a,b,c}} __________，
4. 在代数系统（N ，+）中，其单位元是0，仅有 5．如果连通平面图G 有n 个顶点，e 条边，则G 有___e+2-n____个面。 二．选择题（每小题2分，共10分）
1. 与命题公式P →(Q →R ) 等价的公式是（ ） （A ）(P ∨Q ) →
R
（B ）(P
∧Q ) →R
（C ）P →(Q ∧R ) （D ）P →(Q ∨R )
2. 设集合A ={a , b , c },A 上的二元关系R ={, }不具备关系( ) 性质 （A ） (A)传递性 (B)反对称性 (C)对称性 (D)自反性 3. 在图G =中, 结点总度数与边数的关系是( ) (A)deg(v i ) =2E (B) deg(v i ) =E (C)∑deg(v i ) =2E (D)
v ∈V
∑deg(
v ∈V
v i ) =E
4. 设D 是有n 个结点的有向完全图, 则图D 的边数为( ) (A)n (n -1) (B)n (n +1) (C)n (n +1) /2 (D)n (n -1) /2 5. 无向图G 是欧拉图, 当且仅当( )
(A) G 的所有结点的度数都是偶数 (B)G的所有结点的度数都是奇数
(C)G 连通且所有结点的度数都是偶数 (D) G连通且G 的所有结点度数都是奇数。 三．计算题（共43分）
1. 求命题公式p ∧q ∨r 的主合取范式与主析取范式。（6分）
解：主合取方式：p ∧q ∨r ⇔(p∨q ∨r) ∧(p∨¬q ∨r) ∧(¬p ∨q ∨r)= ∏0.2.4
主析取范式：p ∧q ∨r ⇔(p∧q ∧r) ∨(p∧q ∧¬r) ∨(¬p∧q ∧r) ∨(¬p∧¬q∧r) ∨(p∧¬q∧r)= ∑1.3.5.6.7
⎛1
1=
0 0⎝
0000
0100
0⎫⎪1⎪
, 求⎪0⎪1⎪⎭
2. 设集合A ={a , b , c , d }上的二元关系R 的关系矩阵为M
R
r (R ), s (R ), t (R ) 的关系矩阵，并画出R ，r (R ), s (R ), t (R ) 的关系图。（10分）
3 无向图G 有12条边，G 中有6个3度结点，其余结点的度数均小于3，问G 中至少有多少个结点？（10分）
解：∵G （V ,E ），| E |=V，d （Vi ）8 故G 中至少有9个节点。
4 求下面两个图的最小生成树。（12分）
5. 试判断(z , ) 是否为格？说明理由。（5分）
解：（Z, ≤）是格，理由如下：
对于任意a ∈Z ，a ≤a 成立，满足自反性；
对于任意a ∈Z ，b ∈Z ，若a ≤b 且b ≤a ，则a=b，满足反对称性； 对于任意a ，b ，c ∈Z ，若a ≤b ，b ≤c ，则a ≤c ，满足传递性；
而对于任意a ，b ∈Z ，a ≤b ，b 为最小上界，a 为最大下界，故（Z ，≤）是格。
（注：什么是格？
）
四．证明题（共37分）
1. 用推理规则证明A →B , (⌝B ∨C ) ∧⌝C , ⌝(⌝A ∧D ) ⇒⌝D 。（10分）
证明： 编号 （1） （2） （3） （4） （5） （6） （7） （8）
公式 （¬B∨C ）∧¬C ¬B∨C ，¬C ¬B A →B ¬A ¬（¬A∧D ） A ∨¬D ¬D 依据 前提 （1） （2） （3） （3）（4） 前提 （6） （5）（6）
2. 设R 是实数集，f :R ⨯R →R , f (a , b ) =a +b ，g :R ⨯R →R , g (a , b ) =ab 。求证：f 和g 都是满射，但不是单射。（10分）
证明：要证f 是满射，即∀y ∈R, 都存在（x1，x2）∈R ×R ，使f （x1，x2）=y，而f （x1，x2）=x1+x2，可取x1=0，x2=y，即证得；
再证g 是满射，即∀y ∈R ，, 都存在（x1，x2）∈R ×R ，使g （x1，x2）=y，而g （x1，x2）=x1x2，可取x1=1，x2=y，即证得；
最后证f 不是单射，f （x1，x2）=f（x2，x1）取x1≠x2，即证得，同理：g （x1，x2）=g（x2，x1），取x1≠x2，即证得。
3. 无向图G 有9个结点，每个结点的度数不是5就是6，求证：G 中至少有5个6度结点或6个5度结点。（10分）
证明：设G 中至多有4个6度结点且5个5度结点， ∴d （Vi ）=49不是偶数， 故它不是一个图，矛盾。 （下面只供参考，个人答案）
4. 设平面上有100个点，期中任意两点间的距离至少是1，则最多有300对点距离恰好为1。（7分）
证明：设任意两点间的读书和恰好为1，则满足： ∑d （Vi ）=2e d （Vi ）≤6 ∴6×100≥2e e ≤300
故最多只有300条边，即300对点距离恰好为
1.