电大离散数学集合论部分期末复习辅导.pdf

《电大离散数学集合论部分期末复习辅导.pdf》由会员分享，可在线阅读，更多相关《电大离散数学集合论部分期末复习辅导.pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-离散数学集合论部分期末复习辅导离散数学集合论部分期末复习辅导一、单项选择题一、单项选择题1若集合 A a，a，1，2，则下列表述正确的是()Aa，aAB1，2解解 因为 aA，所以aAAC C a a A ADA2若集合1，2，1，2，1，2，则下列表述正确的是()A AA ACAB B，且，且 A AB，且 AB，2B，且 AB BBBBDAB，1，2BB，1，2A，且 AB，且 ABB解解 因为 1所以 A3若集合 A2，a，a，4，则下列表述正确的是()Aa，a ABAC2AD D a a A A解解 因为 aA，所以 a A4若集合 A a，a，则下列表述正确的是()A Aaa A

2、ABaACa，aADA解解 因为 aA，所以aAB B，且，且 A AB B 同时成立，怎么做？同时成立，怎么做？注：若请你判断是否存在两个集合注：若请你判断是否存在两个集合 A A，B B，使，使 A A答：答：存在。如 2 题中的集合 A、B。或，设a，a，a。注意注意：以上题型是重点，大家一定要掌握，还要灵活运用以上题型是重点，大家一定要掌握，还要灵活运用，譬如，将集合中的元素作一些调整，大家也应该会做例如，下题是 2011 年 1 月份考试试卷的第 1 题：若集合 A a，1，则下列表述正确的是()A A11 A AB1ACaADA解解 因为1是集合 A 的一个元素，所以15设集合a，

3、则 A 的幂集为()AaBa，aC C，aaD，aA-解解 A=a的所有子集为0 0 元子集元子集，即空集：；1 1 元子集元子集，即单元集单元集：a所以 P(A)=，a6设集合 A=1,a，则 P(A)=()A1,aB,1,aC C,1,a,1,a,1,a,1,a D1,a,1,a 解解 A=1,a的所有子集为0 0 元子集元子集，即空集：；1 1 元子集元子集，即单元集单元集：1，a；2 2 元子集元子集：1,a所以 P(A)=,1,a,1,a 注意注意：若集合 A 有一个或有三个元素，那么 P(A)怎么写呢？例如，2012 年 1 月份考试题的第 6 题：设集合 Aa，那么集合 A 的幂

4、集是,a,a若 A 是 n 元集，则幂集 P(A)有 2n个元素当当 8 8 或或 1010 时，时，A A 的幂集的幂集的元素有多少个有多少个？该是 256 或 1024 个）7若集合 A 的元素个数为 10，则其幂集的元素个数为（）A A10241024B10C100D1解解=10，所以(A)|=210=1024以下为 2012 年 1 月份考试题的第 1 题：若集合 A 的元素个数为 10，则其幂集的元素个数为（）A10B100C C10241024D18设 A、B 是两个任意集合，侧 AB ()AB BA AB BCABDB 解解 设 xA，则因为 AB ，所以 xAB，从而 xB，故

5、 AB9设集合1,2,3,4，R 是 A 上的二元关系，其关系矩阵为1001100000011000-（应-则 R 的关系表达式是()A A，B，C，D，10集合1,2,3,4,5,6,7,8上的关系10 且 x,，则 R 的性质为（）A自反的B B对称的对称的C传递且对称的D反自反且传递的解解 R=，易见，若答答 B另，因为 1因为 5A，但R，所以 R 不是自反的。R，则R，所以 R 是对称的A，但R，所以 R 不是反自反的。R，但R，所以 R 不是传递的。因为R 且要求要求大家能熟练地写出二元关系 R 的集合表达式，并能判别 R 具有的性质11集合1,2,3,4上的关系且 x,，则 R

6、的性质为（）A不是自反的B不是对称的C C传递的传递的D反自反解解 R=，是 A 上的恒等关系，是自反的、对称的、传递的。答答 C12如果 R1和 R2是 A 上的自反关系，则 R1R2，R1R2，R12中自反关系有（）个A0B B2 2C1D3解解 对于任意 aA，由于 R1和 R2是 A 上的自反关系，所以R2，从而R1R2，R1R2，(R12)R1，故 R1R2，R1R2是 A 上的自反关系，R12是 A 上的反自反关系答答 B13设集合1,2,3,4上的二元关系1,1，2,2，2,3，4,4，1,1，2,2，2,3，3,2，4,4，则 S 是 R 的（）闭包A自反B传递-C C对称对称

7、D自反和传递解解 RS，S 是对称关系，且S 去掉任意一个元素就不包含 R 或没有对称性，即S 是包含 R 的具有对称性的最小的关系，从而 S 是 R 的对称闭包答答 C14设1,2,3,4,5,6,7,8，R 是 A 上的整除关系，2,4,6，则集合B 的最大元、最小元、上界、下界依次为()A8、2、8、2B8、1、6、1C6、2、6、2D D无、无、2 2、无、无、2 2解解R 1,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8,2,2,2,4,2,6,2,8,3,3,3,6,4,4,4,8,5,5,6,6,7,7,8,8 关系 R 的哈斯图如下：由图可见，集合2,4,6无最大

8、元，其最小元是 2无上界，下界是 2 和 1答答 D15设集合1，2，3，4，5，偏序关系是 A 上的整除关系，则偏序集上的元素 5 是集-16设集合A=1,2,3,4,5上的偏序关系的哈斯图如右图所示，若 A 的子集 B=3,4,5，则元素 3 为 B 的（）A下界B B最小上界最小上界C最大下界D最小元答答 B17设a,b，1,2，R1，R2，R3是 A 到 B 的二元关系，且 R1=,，R2=,，R3=,，则（）不是从 A 到 B 的函数AR1B BR2R2C R3DR1和 R3解解 R2，R2，即 R2不满足函数定义的单值性，因而不是函数答答 B注意注意：函数 R1，R3的定义域、值域

9、是什么？两个函数 R1，R3是否能复合？解解(R1)=a,b，(R1)=2；(R3)=a,b，(R3)=1,2因为(R1)(R3)，所以函数 R1和 R3不能复合。18设a，b，c，1，2，作 f：AB，则不同的函数个数为A2B3C6D D8 8解解 AB ，AB 的任一子集即为从 A 到 B 的二元关系，在这些关系中满足函数定义的两个条件（单值性；定义域是 A）的关系只能是，其中每个有序对的第二元素可取 1或 2，于是可知有 222 8 个不同的函数答答 D事实上，8 个不同的函数为：f1=a,1，b,1，c,1，f2=a,1，b,1，c,2，f3=a,1，b,2，c,1，f4=a,2，b,

10、1，c,1，f5=a,1，b,2，c,2，f6=a,2，b,1，c,2，f7=a,2，b,2，c,1，f8=a,2，b,2，c,2-24135-19设集合 A=1,2,3上的函数分别为：f=1,2，2,1，3,3，g=1,3，2,2，3,2，h=1,3，2,1，3,1，则 h=（）A AfgfgBgfCffDgg解解 fg 1,3，2,1，3,1 hgf 1,2，2,3，3,2ff 1,1，2,2，3,3gg 1,2，2,2，3,2答答 A20设函数 f：NN，f(n)1，下列表述正确的是（）Af 存在反函数Bf 是双射的Cf 是满射的D Df f 是单射函数是单射函数解解 因为任意n1,n2

11、 N，n1 n2，则f(n1)n11 n21 f(n2)，所以 f 是单射对于0N，不存在nN，使f(n)n 1 0，所以 f 不是满射从而 f 不是双射，也不存在反函数答答 D二、填空题二、填空题1设集合A 1,2,3,B 1,2，则P(A)(B)=，A解解P(A),1,2,3,1,2,1,3,2,3,1,2,3P(B),1,2,1,2答答 3,1,3,2,3,1,2,33,1,3,2,3,1,2,3,2设集合 A 有 10 个元素，那么 A 的幂集合 P(A)的元素个数为答答 2102103设集合0,1,2,3，2,3,4,5，R 是 A 到 B 的二元关系，R x,y x A且yB且x,

12、y AB-则 R 的有序对集合为答答 R R，注意：如果将二元关系 R 改为R x,y x A且yB且x2 y或R x,y x A且yB且x1 y则 R 的有序对集合是什么呢？答答 R或 R，4设集合1,2,3,4，6,8,12，A 到 B 的二元关系R x,y y 2x,x A,yB那么R1 6,3,8,4 5设集合a,b,c,d，A 上的二元关系,，则 R 具有的性质是因为任意 x答答 反自反的反自反的6设集合a,b,c,d，A 上的二元关系,，若在 R 中再增加两个元素，则新得到的关系就具有对称性答答，注意注意：第 5，6 题是重点，我们要熟练掌握，尤其是 A 和 R 的元素都减少的情况

13、。如果 6 题新得到的关系具有自反性自反性，那么应该增加哪两个元素呢？答答 应增加，两个元素7如果 R1和 R2是 A 上的自反关系，则 R1R2，R1R2，R12中自反关系有个答答 2 2（见：一、9 题）8 设 1,2 上 的 二 元 关 系 为 为因为 R，所以 R 的自反闭包 s(R),答答,注意注意：如果二元关系改为A，yA,10，则 R 的自反闭包是什么呢？A，yA,=10，则R 的 自 反 闭 包A，R，所以 R 是反自反的解解 R ,是 A 上的全关系，它的自反闭包是它自己。-答答 R 或,9设 R 是集合 A 上的等价关系，且 1,2,3 是 A 中的元素，则 R 中至少包含

14、等元素答答，因为等价关系一定是自反的、对称的、传递的，由二元关系 R 是自反的，所以它至少包含,等元素注：如果给定二元关系注：如果给定二元关系 R R，你能否判断，你能否判断 R R 是否是等价关系？是否是等价关系？10设集合 1,2，a,b，那么 集合 A 到 B 的双射 函数是f 1,a,2,b，g 1,b,2,a 想一想：想一想：集合 A 到 B 的不同函数的个数有几个？答答 有 4 个，除上述两个双射函数外，还有h 1,a,2,a，i 1,b,2,b（参考：一、14 题）三、判断说明题三、判断说明题（判断下列各题，并说明理由）1若集合 A=1，2，3上的二元关系，则(1)R 是自反的关

15、系；(2)R 是对称的关系解解（1 1）错误因为）错误因为 3 3（2 2）错误因为）错误因为A A，但，但R R，但，但R RR R2如果 R1和 R2是 A 上的自反关系，判断结论：“R11、R1R2、R1 R2是自反的”是否成立？并说明理由解解 成立成立因为因为 R1R1 和和 R2R2 是是 A A 上的自反关系，所以上的自反关系，所以任意任意a A，有，有从而有从而有 a,a R1,a,a R2，a,a R11（逆关系定义）（逆关系定义），R2 a,a R1R2，a,a R1故故R11、R1R1R2R2、R1R1R2R2 是自反的是自反的3若偏序集的哈斯图如图一所示，则集合 A 的最

16、大元为 a，最小元不存在解解 不正确。不正确。可见可见 a a 大于等于大于等于 A A 中的元素中的元素 b b、c c、d d、e e、f f，-但与元素但与元素 g g、h h 没有关系，所以没有关系，所以 a a 不是不是 A A 的最大元。没有一个元素小于等于的最大元。没有一个元素小于等于 A A 中的所有元素，所中的所有元素，所以以 A A 没有最小元。没有最小元。注：本题中，极大元为注：本题中，极大元为 a a、g g，极小元为，极小元为 e e、f f、h h注意注意：题目修改为：若偏序集的哈斯图如右图所示，则集合 A 的最大元为 a，极小元极小元不存在解解 结论不成立。A 的

17、最大元为 a，极小元极小元为 b、c问：是否存在一个元素问：是否存在一个元素 a a，它既是偏序集，它既是偏序集 的最大元，也是的最大元，也是 的最小元？的最小元？4设集合1,2,3,4，2,4,6,8，判断下列关系 f 是否构成函数 f：A B，并说明理由(1),；(2),；(3),解解（1 1）关系）关系 f f 不构成函数不构成函数因为因为(f)=1,2,4(f)=1,2,4A A，不满足函数定义的条件，不满足函数定义的条件（2 2）关系）关系 f f 不构成函数不构成函数因为因为(f)=1,2,3(f)=1,2,3A A，不满足函数定义的条件，不满足函数定义的条件（3 3）关系）关系

18、f f 构成函数构成函数因为因为 任意任意 a a(f)(f)即关系即关系 f f 满足函数定义的两个条件，所以关系满足函数定义的两个条件，所以关系 f f 构成函数构成函数四、计算题四、计算题1设E 1,2,3,4,5,A 1,4,B 1,2,5,C 2,4，求：(1)(AB)；(2)(AB)-(BA)；(3)P(A)P(C)；(4)ABC 11,3,51,3,5；解解（1 1）(AB)（2 2）(AB)(BA)1,2,4,5 12,4,5；（3 3）P(A)P(C),1,4,1,4,2,4,2,41,1,4；(f)(f)，都存在唯一的，都存在唯一的 b b(f)(f)，使，使f f；（4

19、4）A B (AB)(AB)(AB)(BA)2,4,52设1,2,1,2，1,2,1,2，试计算-（1）（A-B）；（2）（AB）；（3）AB解解（1 1）A B 1,2；（2 2）AB 1,2；（3 3）AB 1,1,1,2,1,1,2,2,1,2,2,2,1,2,1,1,1,2,1,1,2,2,1,2,2,2,1,23设1，2，3，4，5，A，yA 且4，A，yA 且0，试求 R，S，RS，SR，1，1，r(S)，s(R)解解R 1,1,1,2,1,3,2,1,2,2,3,1，S RS ，S R ，R11,1,1,2,1,3,2,1,2,2,3,1 R，S1，r(S)Ss(R)RIA IA

20、1,1,2,2,3,3,4,4,5,5 R1 R，1,1,1,2,1,3,2,1,2,2,3,14设1,2,3,4,5,6,7,8，R 是 A 上的整除关系，2,4,6(1)写出关系 R 的表示式；(2)画出关系 R 的哈斯图；(3)求出集合 B 的最大元、最小元解解（1 1）R 1,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8,2,2,2,4,2,6,2,8,3,3,3,6,4,4,4,8,5,5,6,6,7,7,8,8（2 2）关系）关系 R R 的哈斯图如下：的哈斯图如下：（3 3）集合）集合2,4,62,4,6无最大元，其最小元是无最大元，其最小元是 2 2五、证明题五、

21、证明题-1试证明集合等式：A(BC)=(AB)(AC)证明证明 任意任意x A(BC)，则，则x A，或，或xBC若若x A，则，则x AB,x AC，从而，从而x(AB)(AC)；若若xBC，则，则xB,xC，x A从而从而x(A所以所以A(BB)(AC)B)(AC)B,x AC，C)(A任意任意x(AB)(AC)，则，则x AB 且 x AC由由x AB知，知，x A或或xB若若x A，则，则x A(BC)；若若x A，则必有，则必有xB，由，由x AC知，也有知，也有xC，从而，从而xBC，进而，进而x A(BC)所以所以(A故故A(BB)(AC)A(BB)C)C)(A(AC)2试证明集

22、合等式 A(BC)=(AB)(AC)证明证明 任意任意x A(BC)，则，则x A且且xBC即即x A且（且（xB 或 xC）即即x A且且xB，从而，从而xAB，或或x A且且xC，从而，从而xAC于是有于是有x(AB)(AC)，所以所以A(BC)(AB)(AC)任意任意x(AB)(AC)，则，则x AB 或 x AC若若xAB，则，则x A 且 xB，从而，从而x A 且 xBC，x A(BC)；若若xAC，则，则x A 且 xC，从而，从而x A 且 xBC，x A(BC)所以所以(AB)(AC)A(BC)故故A(BC)(AB)(AC)注意注意：第 1、2 题是重点，这样的证明方法我们要

23、熟练掌握3对任意三个集合 A,B 和 C，试证明：若=，且 A，则证明证明 若若 B B若若 B B，则，则 A AC CA AB B，由于，由于 A A，所以，所以 C C，从而，从而 B BC C，则，则AB ，任意任意bB，存在存在a A，使使 a,b A B，由于由于=，所以所以 a,b AC，从而从而bC，故故B C-ACAB ，C 任意任意cC，存在存在a A，使使 a,c AC，由于由于=，所以所以 a,c AB，从而从而cB，故故C B所以所以B C注意：这个题 09 秋学期的复习时重点强调了，但 2010 年 1 月份考卷中的证明题：设 A，B 是任意集合，试证明：若 AB，

24、则许多同学不会做，是不应该的事实上这道题并不难：证明：若证明：若 A A若若 A A任意任意 x x因为因为 A A则有则有 x x任意设任意设 x x因为因为 A A则有则有 x x故得故得大家可以看到，这两个题的证明方法是不仅类似，而且 1 月份考题更容易4试证明：若 R 与 S 是集合 A 上的自反关系，则 RS 也是集合 A 上的自反关系证明证明 任意任意 a aaaA A，因，因 R R 与与 S S 是集合是集合 A A 上的自反关系，所以上的自反关系，所以S S，则，则 B BB BA AA AA A，B BB B，所以，所以 B B，从而，从而 A AB B，则，则 A AA

25、AB BB BA A，则，则xxB B，故，故xxB B，所以，所以 A AB BB BA AA AB B，则，则xxB B，故，故xxA A，所以，所以 B BB B，A A，A AR R，aaRSRS，从而从而aa故，故，RSRS 也是集合也是集合 A A 上的自反关系上的自反关系注意：如果把该题的“自反关系”改为“对称关系”注意：如果把该题的“自反关系”改为“对称关系”，应该怎么证明呢？，应该怎么证明呢？请大家想一想即试证明：若 R 与 S 是集合 A 上的对称关系，则 RS 也是集合 A 上的对称关系（本题是 11 年 7月试题）证明证明 任意任意 a a，b bA A，如果，如果abRSRS，则，则abR R，abS SS S因为因为 R R 与与 S S 是集合是集合 A A 上的对称关系，所以上的对称关系，所以ba从而从而baRSRSR R，ba故，故，RSRS 也是集合也是集合 A A 上的对称关系上的对称关系-