《离散数学》复习资料 2023年12月。
一、单项选择题（每小题3分，本题共15分）
1．若集合a=，b=}，则下列表述正确的是( a )．
a． ab，且a∈b b．ba，且a∈b c．ab，且ab d．ab，且a∈b
2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( d )．
图一。a．（a）是强连通的b．（b）是强连通的。
c．（c）是强连通的d．（d）是强连通的。
3．设图g的邻接矩阵为。
则g的边数为( b )．
a．6 b．5 c．4 d．3
4．无向简单图g是棵树，当且仅当( a )．
a．g连通且边数比结点数少1 b．g连通且结点数比边数少1
c．g的边数比结点数少1d．g中没有回路．
5．下列公式 ( c )为重言式．
a．p∧qp∨qb．(q→(p∨q)) q∧(p∨q))
c．(p→(q→p))(p→(p→q)) d．(p∨(p∧q)) q
6．设a=，b=，r1，r2，r3是a到b的二元关系，且r1=，r2=，r3=，则（ b ）不是从a到b的函数．
a．r1和r2 b．r2
c．r3d．r1和r3
7．设a=，r是a上的整除关系，b=，则集合b的最大元、最小元、上界、下界依次为 ( b )．
ab．无、2、无、2
cd8．若集合a的元素个数为10，则其幂集的元素个数为（ a ）．
a．1024 b．10 c．100 d．1
9．设完全图k有n个结点(n≥2)，m条边，当（ c ）时，k中存在欧拉回路．
a．m为奇数 b．n为偶数
c．n为奇数 d．m为偶数。
10．已知图g的邻接矩阵为
则g有（ d ）．
a．5点，8边 b．6点，7边
c．6点，8边 d．5点，7边。
11.无向完全图k3的不同构的生成子图的个数为（ c ）
a) 6b) 5
(c) 4 (d) 3
12 n阶无向完全图kn中的边数为（ a ）
a) (b) (c) n (d)n(n+1)
13.在图g＝中，结点总度数与边数的关系是( c )
a deg(vi)=2∣eb) deg(vi)=∣e∣
c d二、填空题（每小题3分，本题共15分）
1．命题公式的真值是 1
2．若a=，r=，则r的自反闭包为 ，那么集合a的幂集是 ,,
6．如果r1和r2是a上的自反关系，则r1∪r2，r1∩r2，r1-r2中自反关系有 2 个．
7．设图g是有6个结点的连通图，结点的总度数为18，则可从g中删去 4 条边后使之变成树．
8．无向图g存在欧拉回路，当且仅当g所有结点的度数全为偶数且连通
9．设连通平面图g的结点数为5，边数为6，则面数为 3
10．设个体域d＝，则谓词公式(x)a(x)∧（x）b（x）消去量词后的等值式为 (a (a)∧a (b))∧b（a）∨b（b
三、逻辑公式翻译（每小题6分，本题共12分）
1．将语句“雪是黑色的．”翻译成命题公式．
设p：雪是黑色的2分）
则命题公式为：p．
2．将语句“他不去学校．”翻译成命题公式．
解：设p：他去学校。
则命题公式为： p．
3．将语句“小王是个学生，小李是个职员，而小张是个军人．”翻译成命题公式．
设p：小王是个学生，q：小李是个职员，r：小张是个军人2分）
则命题公式为：p∧q∧r．
4．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式．
解：设p：所有人今天都去参加活动，q：明天的会议取消，
则命题公式为： p→ q．
5．将语句“他去旅游，仅当他有时间．”翻译成命题公式．
解：设 p：他去旅游，q：他有时间。
则命题公式为： p →q．
6．将语句“41次列车下午五点开或者六点开．”翻译成命题公式．
解：设p：41次列车下午五点开，q：41次列车下午六点开2分）
命题公式为：（p∧q）∨（p∧q
7．将语句“小张学习努力，小王取得好成绩．”翻译成命题。
设p：小张学习努力，q：小王取得好成绩2分）
则命题公式为：p∧q．
8．将语句“有人去上课．” 翻译成谓词公式．
解：设p(x)：x是人，q(x)：x去上课1分）
x)(p(x) ∧q(x)
9．将语句“所有的人都学习努力．”翻译成命题公式．
解：设p(x)：x是人，q(x)：x学习努力。
x）(p(x)→q(x))．
四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．
1．设集合a=，b=，，判断下列关系f是否构成函数f：，并说明理由．
1) f=； 2)f=；
3) f=．
答：（1）不构成函数因为，但没有定义，所以不构成函数。
（2）不构成函数因为，但没有定义，所以不构成函数。
（3）满足。 因为任意，都有且结果唯一。
2．若集合a = 上的二元关系r=，则。
1) r是自反的关系2) r是对称的关系．
答：（1）错误因为，所以r不是自反的。
（2）错误因为，但是，所以r不是对称的。
3．如果r1和r2是a上的自反关系，判断结论：“r-11、r1∪r2、r1∩r2是自反的” 是否成立？并说明理由．
答：成立因为任意，有。
所以，， r-11、r1∪r2、r1∩r2是自反的。
4．若偏序集的哈斯图如图一所示，则集合a的最大元为a，最小元不存在．
答：错误，集合a没有最大元，也没有最小元。
其中a是极大元。
5．若偏序集的哈斯图如图一所示，则集合a的最大元为a，最小元不存在．
解：正确。对于集合a的任意元素x，均有∈r（或xra），所以a是集合a中的最大元．按照最小元的定义，在集合a中不存在最小元．
6．如果图g是无向图，且其结点度数均为偶数，则图g存在一条欧拉回路．．
答：错误如果图g是无向图，且图g是连通的，同时结点度数都是偶数。
7．设g是一个连通平面图，且有6个结点11条边，则g有7个面．
答案：正确。
定理，连通平面图g的结点数为v，边数是e，面数为r，则欧拉公式v-e+r=2成立。
所以r=2-v+e=2-6+11=7
则g存在一条欧拉回路。
8．设g是一个有6个结点14条边的连通图，则g为平面图．
解：错误，不满足“设g是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．” 9．命题公式p∧(p→q)∨p为永真式．
解：正确因为，由真值表。
可知，该命题公式为永真式．
离散数学复习指导
命题逻辑部分。一学习要求。1 理解命题 联结词的含义，掌握命题的符号化 2 理解命题公式的赋值，能求出公式的真值表，判断公式的类型 3.理解公式等值的定义，记住一些基本等值式，能进行等值演算 4.体会公式的主范式与公式赋值之间的关系，能利用等值演算求出范式 5.理解公式的蕴涵及推理的含义及联系，记住...
离散数学复习指导
例4.先将下列相关命题符号化，给出推理证明。如果4是偶数，则2不能整除5.或者7不是素数或者2整除5.7是素数。因此4不是偶数。解 设p 4是偶数 q 2能整除5 r 7是素数 s 2整除5,则。前提 结论 证明 1结论之否定 2t 1 等值式 3p 4t 2 3 假言推理 5p 6t 4 5 析取...
离散数学难点
联结词与复合命题。复合命题 p并且q 或 p与q 记作p q p并且q 的多种表述方式 既p又q.不仅p而且q.虽然p但qpq 的逻辑关系 q为p的必要条件，p为q的充分条件。如果p,则q 的多种表述方式 若p,就q只要p,就q p仅当q只有q 才p 除非q,才p 除非q,否则非p 假如没有q，就没...