第一章
1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A
和B表示ECNU不必学习离散数学的二年级的学生的集合。
2.试求：
(1)P(φ)
(2)P(P(φ))
(3)P(P(P(φ)))
3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？
能被5整除的有40个，
能被15整除的有13个，
∴能被3或5整除，但不能被15整除的正整数共有
66-13+40-13=80个。
第三章
1.下列语句是命题吗？
(1)2是正数吗？
(2)x2+x+1=0。
(3)我要上学。
(4)明年2月1日下雨。
(5)如果股票涨了，那么我就赚钱。
2.请用自然语言表达命题(p⌝→r)∨(q⌝→r)，其中p、q、r为如下命题：
p：你得流感了
q：你错过了最后的考试
r：这门课你通过了
3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。
4.给出p→(q→s),q,p∨⌝r⇒r→s的形式证明。
第四章
1.将∀x(C(x)∨∃y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同
班同学，个体域是学校全体学生的集合。
解：
学校的全体学生要么自己有电脑，要么其同班同学有电脑。
2.构造∀x(P(x)∨Q(x)),∀x(Q(x)→⌝R(x)),∀xR(x)⇒∀xP(x)的形式证明。
解：
①∀xR(x) 前提引入
②R(e) ①US规则
③∀x(Q(x)→⌝R(x)) 前提引入
④Q(e) →⌝R(e) ③US规则
⑤⌝Q (e) ②④析取三段论
⑥∀x(P(x)∨Q(x)) 前提引入
⑦P(e) ∨Q(e) ⑥US规则
⑧P(e) ⑤⑦析取三段论
⑨∀x (P(x)) ⑧EG规则
第五章
1.设R、S、T都是X上的关系。证明：R︒(S∩T)⊆(R︒S)∩(R︒T)，(R∩S)︒T⊆(R︒T)∩(S︒T)。
2.设X是所有人组成的集合，定义X上的关系R1和R2：aR1b当且仅当a比b高，aR2b
当且仅当a和b有共同的祖父母。问关系R1和R2是否是自反、反自反、对称、反对称、传递的？
3.设R1和R2是X上的关系。证明t(R1⋃R2)⊇t(R1)⋃t(R2)。
4.下列集合关于整除关系⎪构成偏序集。请分别画出它们的哈斯图，判断它们是否是全
序集，给出它们的极大元、极小元、最大元、最小元。
（2）{2,4,8,16}；
（4）{2,3,4,5,9,10,80}。
第六章
1.f：X→Y，下列命题是否成立？
（1）f是一对一的当且仅当对任意a,b∈X，当f(a)=f(b)时，必有a=b；
（2）f是一对一的当且仅当对任意a,b∈X，当f(a)≠f(b)时，必有a≠b。
2.下图展示了五个关系的关系图。问：这些关系中，哪些是函数？哪些是一对一的函数？
哪些是到上的函数？哪些是一一对应？
第七章
1.6个学生：Alice、Bob、Carol、Dean、Santos和tom，其中，Alice和Carol不和，Dean
和Carol不和，Santos、Tom和Alice两两不和。请给出表示这种情形的图模型。
2.设简单无向图G=(V,E)，若δ(G)≥k(k≥1)，则G有长度为k的基本通路。
解：证明：
我们假设存在k-1的基本通路，则存在k个顶点，通路最后一个顶点与通路上顶点相连的度数至多为k-1。因为δ(G)≥k(k≥1)，所以该顶点必定与其他顶点相连，那么存在长度为K的基本通路。得证。
3.一大学有5个专业委员会：物理、化学、数学、生物、计算机，6位院士：B、C、D、
G、S、W。专业委员会由院士组成，物理委员会有院士：C、S和W，化学委员会有院
士：C、D和W；数学委员会有院士：B、C、G和S；生物委员会有院士：B和G；计算机委员会有院士：D和G。每个专业委员会每周开一小时例会，所有成员都不能缺席。
如果某院士同时是两个专业委员会的成员，那么这两个专业委员会的例会就不能安排在同一个时间。现要为这些例会安排时间，希望它们的时间尽可能集中。问最少需要几个开会时间？请给出一种安排。
第八章
1.说明下图不是哈密顿图。
解：从图中删除所标记的6个顶点，所得到的图由7个孤立点组成，有7个连通分量。所以，该图不满足哈密顿图的必要条件，因而不是哈密顿图
2.证明连通图的割边一定是每棵生成树的边。
证明：删除割边后的图一定不连通，其中不存在生成树。所以，每课生成树都包含割边
第九章
1.股评家推荐了12个股票，一股民欲购买其中的3个。问在下列各种条件下，分别有多
少种不同的投资方式？
（1）每个股票各投资3000元；
（2）3个股票分别投资5000元、3000元和1000元。
2.16支互不同颜色的蜡笔平分给4个孩子，有多少种不同的分法？
解： C(16,4) C(12,4) C(8,4) C(4,4)
3. 某学校有2504个计算机科学专业的学生，其中1876人选修了C 语言，999人选修了
Fortran 语言，345人选修了JA V A ，876人选修了C 语言和Fortran 语言，231人选修了Fortran 和JA V A ，290人选修了C 和JA V A ，189个学生同时选了C 、Fortran 和JAV A 。问没有选这3门程序设计语言课中的任何一门的学生有多少个？
第十章
1. 求初值问题的通项公式：a n =10a n-1-25a n-2；a 0=-7，a 1=15。
解：
特征方程：r 2-10r+25=0，特征根：r 2=r 1=5
通解：a n =(α+βn)5n
由a 0=α50=α=-7和a 1= (-7+β)51 =15解得：α=-7，β=10
初值问题的解：a n =(-7+10n)2n
2. 计算广义二项式系数35-⎛⎫
⎪⎝⎭和 1.23⎛⎫ ⎪⎝⎭
的值。 解： ()()3331351215!5----⋯--+⎛⎫==- ⎪⎝⎭ 1.2 1.2(1.21)...(1.231)0.0323!3--+⎛⎫== ⎪⎝⎭
3. 某人有大量1角、2角和3角的邮票（面值相同的邮票看成是相同的），现要在信封上
贴邮票，邮票排成一行且邮票的总值为r 角。若不考虑贴邮票的次序，ar 表示贴邮票的方法数，求{ar}的生成函数。
