《离散数学》习题集(4)

___(b)

S?CS?S?CS。

15. 指出下列集合的幂集合： (a) {a,b,c}；(b) {{a,b},{c}}。 16. 证明下列各式： (a) A?A?B?B； (b) (A?B)?B?AB； (c) C(A?B)?(C

A)?(CB)。

2.1 归纳法和自然数

17. 对下列集合给出归纳定义：

(a) 十进制无符号整数集合，定义集合将包含6，235，0045等等；

(b) 十进制的以小数部分为结束的实数集合，定义的集合包含5.3，453.，01.2700，0.480； (c) 二进制形式的不以0开头的正偶数和0组成的集合，定义的集合包含0,110,1010等； (d) 把算术表达式中的运算符和运算对象全删去，所得的括号叫成形括号串。例如

[],[[]],[][],[[[]][]]等都是成形括号串（例中用[]代（）是为了明晰），试定义成形括号串集合。

18. 用{a}代替N的定义中的?，但仍用这一定义，可否生成自然数集合？有何不同？ 19. 证明成形括号串的左右括号个数相等。

20. 我们有3分和5分两种不同票值的邮票，试证明用这两种邮票就足以组成8分或者更多

的任意邮资。

21. 用归纳法证明：对一切n?I?，(1?2?22. 对所有n?N，证明下列每一关系式： (a) ?i2?n(n?1)(2n?1)/6；

i?0nn?n)2?13?23??n3。

(b) ?(2i?1)?(n?1)2；

i?0n(c) ?i(i!)?(n?1)!?1；

i?0第16页 共53页

n(n?1)??n2?i(d) ?ir??n?2n?1i?0?nr?(n?1)r?r?(r?1)2?r?1；

r?1(e) 1?2n?3n。

23. 如果每根直线连接多边形的两个点，且位于多边形上，那么这个多边形叫凸的，证明对

一切n?3，n边的凸多边形内角之和等于(n?2)180。（提示：多边形能用连结两个非邻接的顶角划分为两部分。）

24. 找出自然域上的两个谓词P和Q一证明归纳证明的基础步骤和归纳步骤是独立的，也

就是没有一个逻辑地蕴含另一个。特别，要找出一谓词P使P(0)是真而

?n(P(n)?P(n?1))是假，和一谓词Q，使Q(0)是假，而?n(Q(n)?Q(n?1))是真。

25. 我们意欲证明，对一切n和一切S，如果S是n个人的集合，那么在S中的所有人都有

同样的身材。下面“所有人都有同样的身材”的证明错在那里？

(a) （基础）设S是一空集合，那么对所有的x和y，如果x?S和y?S，那么x和y有

同样的身材。

(b) （归纳）假定对所有包含n个人的集合断言是真。我们证明对包含n?1个人的集合也

真。任何由n?1个人组成的集合包含两个n个人组成的不同的但交搭的子集合。用

S?和S??表示这两个子集合。那么根据归纳前提，在S?中的所有人有相同的身材，

在S??中的所有人有相同的身材，因为S?和S??是交搭的，所以，所有在S?S??S??中的人都有相同的身材。

26. 设{A1,A2,nn,An}是集合的非空搜集，对n作归纳证明下述推广的德摩根定律：

(a)

i?1nAi?i?1nAi； Ai。

i?1(b)

i?1Ai?27. 证明对所有大于1的整数n都能写成若干个质数之积。

28. 如果a?(b?c)?(a?b)?c，那么二元运算?称为可结合的。从它可推出更强的结果，即

在任何仅含运算?的表达式中，括号的位置不影响结果，就是，仅仅出现于表达式中的运算对象和次序是重要的。为了证明这个“推广的结合律”，我们定义“?表达式集合”如下：

(a) （基础）单个运算对象a1是?表达式；

(b) （归纳）设e1和e2是?表达式，那么(e1,e2)是?表达式；

第17页 共53页

(c) （极小性）只有有限次应用（a）和（b）构成的式子才是?表达式。 设e是一个表达式，它有a1,a2,,an个运算对象，且此次序出现于表达式中，那么

e?(a1?(a2?(a3?((an?1?an)))))

证明这个推广的结合律。（提示：用数学归纳法第二原理。）

2.5 集合的笛卡儿乘积

29. 如果A?{a,b}和B?{c}，试确定下列集合： (a) A?{0,1}?B； (b) B2?A； (c) (A?B)2。

30. 设A?{0,1}，构成集合?(A)?A。 31. 设A,B,C和D是任意集合，试证明：

(AB)?(CD)?(A?C)(B?D)。

32. 试证明：A?B?B?A?A???B???A?B。 33. 指出下列各式是否成立：

(a) (AB)?(CD)?(A?C)(B?D)； (b) (A?B)?(C?D)?(A?C)?(B?D) (c) (A?B)?(C?D)?(A?C)?(B?D)； (d) (A?B)?C?(A?C)?(B?C)； (e) (A?B)?C?(A?C)?(B?C)。

补充习题：

1令A?{1,2}，B?{1,2,O}，C?{2,2,1}，D?{2,O,O,1}，E?{x|x?3x?2?0}。试指出哪些集合是相等的？哪些集合是不相等的？

2设S?{2,a,{3},4}，R?{{a},3,4,1}，判断下列各命题真或假：

（1）{a}?S； （2）{3}?S； （3）{O}?S； （4）O?{{3},4}； （5）O?{{a}}?R； （6）O?R； （7）O?R； （8）{{a},1,3,4}?R

3第18页 共53页

3试指出下列命题哪些为真？哪些为假？

（1）O?O； （2）O?{O}； （3）O?{{O}}； （4）O?{O,{O}}； （5）O?O； （6）O?{O}； （7）O?{{O}}； （8）O?{O,{O}} 4设A={a,b,c}，A是空集，试求P(A)，P(P(A))。 5 求下列集合的幂集：

（1）O； （2）{O}； （3）{O,{O}}； （4）{O,1,{2}}； （5）{{1},{O,1}}； （6）{{1,2},{1,1,2},{2,1,2}} 6设A,B,C是集合，试回答下列问题： （1）若A （2）若AB?AC，是否必须B?C？ B?AC，是否必须B?C？

（3）若A?B?A?C，是否必须B?C？ 7设A,B是任意的集合，求证: A-B= A∩(~B)。

8设A,B是任意的集合，求证: A?B=(A-B)∪(B-A)=(A∩~B)∪(B∩~A)。

9设集合E?{1,2,3,4,5}，A，B和C是E的子集，A?{1,3},B?{2,3,5}，C?{2,4}，试求： （1）A?~B （2）?A?B??~C （3）~?A?C? （4）??A????B? （5）C???C?

10设A，B，C是任意集合，证明：(A11设A，B是集合，证明： （1）若A?B，则 （2）(AB)C?A(BC)?C?A。

A?B

B)?(A)(B)

A

（3）若A?B且(?C)(C?A)，则B?第19页 共53页

（4）

A?A

12设A，B，C是任意集合，证明： A??B?C??A???B?A???A?C??

13某班有50名学生，第一次考试中26人成绩为优，第二次考试中21人成绩为优，已知两次考试中都不为优的共17人。问两次考试中都为优的有多少人？

14用命题定律中的吸收律A∨(A∧B)?A和A∧(A∨B)?A，证明集合恒等式：

⑴A∩(A∪B)=A ⑵A∪(A∩B)=A

15用命题定律中的德摩根律? (A∨B)??A∧?B，? (A∧B)??A∨?B，证明集合恒等式：

⑴ ~ (A∪B)= ~A∩~B ⑵ ~ (A∩B)= ~A∪~B

16设A，B是任意集合，用已知的集合恒等式证明：A-B=A-(A∩B)。 17设A={a,b,c}，以下是A的子集构成的集合：

S={{a,b},{b,c}} Q={{a},{a,b},{a,c}} D={{a},{b,c}} G={{a,b,c

E={{a},{b},{c}} F={{a},{a,c}}

试确定哪些集合是A的覆盖？哪些集合是A的划分？哪些集合既不是覆盖，也不是划分？ 18设A={1,2,3}，试确定A的所有划分。 19设A={a,b}，B={1,2,3}，

⑴试求A×B和B×A

⑵验证|A×B|=|A||B|和|B×A|=|B||A|

20设A={1,2}，B={a,b}，A={x,y}，求：A×B×C，A×(B×C)。 21设A?{a,b},B?{c}，求下列各集合： （1）A?{0,1}?B （2）B?A （3）(A?B)

第20页 共53页

22

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《离散数学》习题集(4)在线全文阅读。