资源描述：
《离散数学 作业 3~4 答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、『离散数学』课程作业3：P64：3某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人中有4人会打排球。求不会打球的人数。解：直接使用容斥原理。我们做如下设定：A：会打篮球的学生；B：会打排球的学生；C：会打网球的学生；根据题意：
2、E
3、=25，
4、A
5、=14，
6、B
7、=12，
8、C
9、=6，
10、A∩B
11、=6，
12、A∩C
13、=5，
14、B∩C
15、=4，
16、A∩B∩C
17、=2由容斥原理:
18、A∪B∪C
19、＝
20、A
21、＋
22、B
23、＋
24、C
25、－
26、A∩B
27、－
28、
29、A∩C
30、－
31、B∩C
32、＋
33、A∩B∩C
34、=14+12+6-6-5-4+2=19不会打球的人数=
35、E
36、-
37、A∪B∪C
38、=25-19=6——————————————————————————————————————但相当一部分同学没有直接使用容斥原理，而是画了文氏图。使用文氏图的方法，会发现此题存在问题：=-1，表示只会打网球的同学是-1人，此种情况与实际不符。这可能是作者的疏忽，该教材第一版中，“已知6个会打网球的人中有4人会打排球。”一句是写作“已知6个会打网球的人都会打篮球或排球。”则用容斥原理或文
39、氏图，都可以得到5的结果。A：会打篮球的学生；B：会打排球的学生；C：会打网球的学生；根据题意：
40、E
41、=25，
42、A
43、=14，
44、B
45、=12，
46、C
47、=6，
48、A∩B
49、=6，
50、A∩C
51、=5，
52、A∩B∩C
53、=2因为“会打网球的人都会打篮球或排球。”所以C=（A∩C）∪（B∩C）由容斥原理:
54、C
55、=
56、（A∩C）∪（B∩C）
57、=
58、（A∩C）
59、+
60、（B∩C）
61、-
62、（A∩C）∩（B∩C）
63、可知
64、（B∩C）
65、=
66、C
67、-
68、（A∩C）
69、+
70、（A∩C）∩（B∩C）
71、=6-5+2=3
72、A∪B∪C
73、＝
74、A
75、＋
76、B
77、＋
78、C
79、－
80、
81、A∩B
82、－
83、A∩C
84、－
85、B∩C
86、＋
87、A∩B∩C
88、=14+12+6-6-5-3+2=20不会打球的人数=
89、E
90、-
91、A∪B∪C
92、=25-20=5作业4：P70：2当A=φ时，若A×B⊆A×C，B⊆C不一定成立；当A≠φ时，若A×B⊆A×C，则B⊆C一定成立，反证如下：若B⊆C不成立，则存在y∈B∧y∉C；又因为φ≠A，所以存在x∈A；可知序偶∈A×B∧∉A×C，与A×B⊆A×C矛盾。P76：5自反闭包r(R)=R∪{}对称闭包s(R)=R∪{,}传
93、递闭包t(R)=R∪{}P80：2A中各元素关于R的等价类：[a]=[b]={a,b}[c]=[d]={c,d}相应的划分{{a,b}，{c,d}}当堂测试：1、判断下程序段基本语句执行次数的O(f(n))。intn=10,x=n,y=0;while(x>=(y+1)*(y+1))y++;解：循环次数123…ky的值123…k第(k+1)此循环没有执行，说明循环条件不满足。取临界值，我们认为x=n≈(y+1)*(y+1)=(k+1)2k≈n1/2-1时间复杂度T(n)=O(n1/2)2
94、、利用容斥原理作答：某班有50位同学参加期末考试，结果英语不及格的有15人，数学不及格的有19人，英语和数学都及格的有21人，求英语和数学都不及格的有多少人？解：A：英语及格的学生B：数学及格的学生
95、E
96、=50
97、A
98、=50-15=35
99、B
100、=50-19=31
101、A∩B
102、=21根据容斥原理：
103、A∪B
104、=
105、A
106、+
107、B
108、-
109、A∩B
110、=35+31-21=45所求为=
111、E
112、-
113、A∪B
114、=50-45=53、R和S都是A={1,2,3,4}上的二元关系，R={<1,1>,<1,2>,<1,3>,<2,3>,<2
115、,4>,<4,3>,<4,4>}，S={<1,2>,<1,3>,<2,3>,<2,4>,<3,1>,<4,3>}，试用矩阵相乘的方法求R°S。解：本题是拷给大家的PPT课件原题。R°S={<1,1>，<1,2>，<1,3>，<1,4>，<2,1>，<2,3>，<4,1>，<4,3>}3、设Ａ={a,b,c}，R={,,}，求r(R)，s(R)，t(R)。5、判断给出的关系是否是{1,2,3,4,5}上的等价关系。如果是，列出等价类。（1）{<1,1>,<2,2>,<
116、3,3>,<4,4>,<5,5>,<1,3>,<3,1>,<3,4>,<4,3>}不是等价关系，不满足传递性有<1,3>,<3,4>却无<1,4>（2）{<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<1,5>,<5,1>,<3,5>,<5,3>,<1,3>,<3,1>}是等价关系，等价类为：[1]=[3]=[5]={1,3,5}[2]={2}[4]={4}对应的划分{{1,3,5}，{2}，{4}}
