『离散数学』课程。
作业3： p64：3
某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人中有4人会打排球。求不会打球的人数。
解：直接使用容斥原理。我们做如下设定：
a：会打篮球的学生； b：会打排球的学生； c：会打网球的学生；
根据题意：|e|=25，|a|=14，|b|=12，|c|=6，|a∩b|=6，|a∩c|=5，|b∩c|=4，|a∩b∩c|=2
由容斥原理：
不会打球的人数=|e|-|a∪b∪c|=25-19=6
但相当一部分同学没有直接使用容斥原理，而是画了文氏图。
使用文氏图的方法，会发现此题存在问题：
-1，表示只会打网球的同学是-1人，此种情况与实际不符。
这可能是作者的疏忽，该教材第一版中，已知6个会打网球的人中有4人会打排球。”
一句是写作。
已知6个会打网球的人都会打篮球或排球。”
则用容斥原理或文氏图，都可以得到5的结果。
a：会打篮球的学生； b：会打排球的学生； c：会打网球的学生；
根据题意：|e|=25，|a|=14，|b|=12，|c|=6，|a∩b|=6，|a∩c|=5，|a∩b∩c|=2
因为“会打网球的人都会打篮球或排球。”
所以c =（a∩c）∪（b∩c）
由容斥原理：
c|=|a∩c）∪（b∩c）|
|（a∩c）|+b∩c）|-a∩c）∩（b∩c）|
可知|（b∩c）|=c|-|a∩c）|+a∩c）∩（b∩c）|
a∪b∪c|＝|a|＋|b|＋|c|－|a∩b|－|a∩c|－|b∩c|＋|a∩b∩c|
不会打球的人数=|e|-|a∪b∪c|=25-20=5
作业4：p70：2
当a=φ时， 若a×ba×c，bc不一定成立；
当a≠φ时，若a×ba×c，则bc一定成立，反证如下：
若bc不成立，则存在y∈b∧yc；又因为φ≠a，所以存在x∈a；可知序偶∈a×b∧ a×c ，与a×ba×c矛盾。
p76：5自反闭包r(r)= r∪{}
对称闭包s(r)= r∪
传递闭包t(r)= r∪{}
p80：2a中各元素关于r的等价类：
a]=[b]=
c]=[d]=
相应的划分，}
当堂测试：1、判断下程序段基本语句执行次数的o(f(n))。
int n=10,x=n,y=0;
while(x>=(y+1)*(y+1))
y++;解：
第(k+1)此循环没有执行，说明循环条件不满足。
取临界值，我们认为x=n≈(y+1)*(y+1)=(k+1)2
k≈n1/2-1 时间复杂度t(n)= o(n1/2)
2、利用容斥原理作答：某班有50 位同学参加期末考试，结果英语不及格的有15 人，数学不及格的有19 人，英语和数学都及格的有21 人，求英语和数学都不及格的有多少人？
解：a：英语及格的学生 b：数学及格的学生。
e|=50 |a|=50-15=35 |b|=50-19=31 |a∩b|=21
根据容斥原理：|a∪b|=|a|+|b|-|a∩b|=35+31-21=45
所求为=|e|-|a∪b|=50-45=5
3、 r和s都是a=上的二元关系，r=，s=，试用矩阵相乘的方法求rs。
解：本题是拷给大家的ppt课件原题。
rs=4、 设ａ=，r=，求r(r)，s(r)，t(r)。
5、判断给出的关系是否是上的等价关系。如果是，列出等价类。
不是等价关系，不满足传递性有<1,3>,<3,4>却无<1,4>
是等价关系，等价类为：
对应的划分，，}
离散数学作业答案
1 第7页第3题。1 解 逆命题 如果我去公园，则天不下雨 反命题 如果天下雨，则我不去公园 逆反命题 如果我不去公园，则天下雨了。2 解 此题注意 p仅当q翻译成 逆命题 如果你去，那么我逗留。反命题 如果我不逗留，那么你没去。逆反命题 如果你没去，那么我不逗留。3 解 逆命题 如果方程无整数解，...
离散数学作业答案
作业题与解答。第一章 19 2 4 6 21 1 2 3 解答 p p q 真值表如下 所以公式 p q q 为可满足式。解答 p q q p 真值表如下 所以公式 p q q p 为永真式。19 6 解答 p q q r p r 真值表如下 所以公式 p q q r p r 为永真式。21 1 解...
离散数学作业4答案
1.如图一所示，以下说法正确的是 d a.是割边 b.是边割集。c.是边割集 d.是边割集。2.设g是连通平面图，有v个结点，e条边，r个面，则r a a.e v 2 b.v e 2 c.e v 2 d.e v 2 3.若g是一个欧拉图，则g一定是 c a.平面图 b.汉密尔顿图 c.连通图 d.对...