科目：离散数学考试形式：闭卷
广东技术师范学院模拟试题考试时间120分钟
系别、班级：
姓名：
学号：
一．填空题（每小题2分，共10分）1谓词公式xPxxQx的前束范式是__xyPx∨Qy__________。
2设全集E12345A123B25则A∩B__2__，A_45____，
AB__1345_____
3设AabcBab，则AB__cacbcabc__________，
BA_____Φ_______。4在代数系统（N，）中，其单位元是0，仅有_1___有逆元。
5．如果连通平面图G有
个顶点，e条边，则G有___e2
____个面。
二．选择题（每小题2分，共10分）
1与命题公式PQR等价的公式是（）
（A）PQR（B）PQR（C）PQR（D）PQR
2设集合AabcA上的二元关系Raabb不具备关系性质
（A）A传递性
B反对称性
C对称性
D自反性
3在图GVE中结点总度数与边数的关系是
Adegvi2EBdegviECdegvi2EDdegviE
vV
vV
4设D是有
个结点的有向完全图则图D的边数为
A
1B
1C
12D
12
5无向图G是欧拉图当且仅当AG的所有结点的度数都是偶数BG的所有结点的度数都是奇数
第1页共5页
fCG连通且所有结点的度数都是偶数DG连通且G的所有结点度数都是奇数。三．计算题（共43分）
1求命题公式pqr的主合取范式与主析取范式。（6分）
解：主合取方式：p∧q∨rp∨q∨r∧p∨q∨r∧p∨q∨r∏024主析取范式：p∧q∨rp∧q∧r∨p∧q∧r∨p∧q∧r∨p∧q∧r∨p∧q
∧r∑13567
1000


2
设集合Aabcd上的二元关系
R
的
关系
矩
阵
为
MR

1

00
000
100
110

求
rRsRtR的关系矩阵，并画出R，rRsRtR的关系图。（10分）
3无向图G有12条边，G中有6个3度结点，其余结点的度数均小于3，问G中至少有多少个
结点？（10分）
第2页共5页
f解：∵G（VE），EV，d（Vi）3设至少有x个节点，由握手定理得：2×12∑d（Vi）6×3x6×32x6＞x8故G中至少有9个节点。4求下面两个图的最小生成树。（12分）
5试判断z是否为格？说明理由。（5分）
解：（Z≤）是格，理由如下：对于任意a∈Z，a≤a成立，满足自反性；对于任意a∈Z，b∈Z，若a≤b且b≤a，则ab，满足反对称性；对于任意a，b，c∈Z，若a≤b，b≤c，则a≤c，满足传递性；而对于任意a，b∈Z，a≤b，b为最小上界，a为最大下界，故（Z，≤）是格。
（注：什么是格？
）
第3页共5页
f四．证明题（共37分）
1r