第一章
1. 假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A
和B表示ECNU不必学习离散数学的二年级的学生的集合。
试求： P(?) P(P(?)) P(P(P(?)))
2. (1) (2) (3)
3. 在1?200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？
能被5整除的有40个， 能被15整除的有13个，
∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。
第三章
1. (1) (2) (3) (4) (5)
下列语句是命题吗？ 2是正数吗？ x2+x+1=0。 我要上学。
明年2月1日下雨。
如果股票涨了，那么我就赚钱。
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两两不和。请给出表示这种情形的图模型。
2018华东师范大学离散数学作业
