(书后作业)集合论及图论.doc

集合论与图论习题册 软件基础教研室 刘 峰 2012.09.09 第一章 集合及其运算 习题 写出方程的根所构成的集合。 .下列命题中哪些是真的，哪些为假 a)对每个集A，；b)对每个集A，； c)对每个集A，；d)对每个集A，； e)对每个集A，；f)对每个集A，； g)对每个集A，；h)对每个集A，； i)对每个集A，；j)对每个集A，； k)对每个集A，；l)对每个集A，； m)对每个集A，；n) ； o)中没有任何元素p)若，则 q)对任何集A，；r)对任何集A，； s)对任何集A，； t)对任何集A，答案：.设有n个集合且试证。 4.设，试求？ .设S恰有n个元素，证明有个元素。 习题 6.设A、B是集合，证明。 7.设A、B是集合，试证. 设AB，C是集合，证明。 9.设AB，C为集合，证明。 10.设AB，C为集合，证明。 11.设AB，C为集合，证明：.设AB，C都是集合，若且，试证B=C。 ；(2)； (3)。 16．下列命题哪个为真？ a)对任何集合A,B,C，若，则A=C。 b)设A,B,C为任何集合，若，则B=C。 c)对任何集合A,B，。 d)对任何集合A,B，。 e)对任何集合A,B，。 f)对任何集合A,B，。 17．填空：设A,B是两个集合。 a)______________________； (b)______________________； (c)_______________________； (d)_______________________。 18．设AB，C为三个集合，下列集合表达式哪一个等于？ a）；（b） （c）；（d） （e） 答案： 习题 20．设A,B,C为集合，并且，则下列断言哪个成立？ ；(2)；(3)；(4)。 答案： 21．设A,B,C为任意集合，化简 习题 24．设。求。 25．设A,B为集合，试证：A×B＝B×A的充要条件是下列三个条件至少一个成立：（1）；（2）；（3）。 设A,B,C,D为任四个集合，证明： 设证明：设A,B为集合，下列命题哪些为真？且或； （4）若，则若，则。 31．设A有m个元素，B有n个元素，则A×B是多少个序对组成的？A×B有多少个不同的子集？ 设集合，，试证：若，则。 习题 33.某班学生中有45％正在学德文，65％正在学法文。问此班中至少有百分之几的学生正同时学德文和法文？ 35．设A,B是两个有限集，试求 第二章 映射习题 习题 1. 设A，B是有穷集，（1）计算（2）从A到A有多少个双射？ 习题 . 证明：从一个边长为1的等边三角形中任意选5个点，那么这5个点中必有2个点，它们之间的距离至多为1/2，而任意10个点中必有2个点其距离至多是1/3。 个整数，试证：存在两个整数，使得 能被整除。 5. 证明在52个整数中，必有两个整数，使这两个整数之和或差能被1整除。 为的任一排列，若n是奇数且 ， 则乘积为偶数。 习题 设，，证明 8. 设，，证明.设。以下四个小题中，每个小题均有四个命题，这四个命题有且仅有一个正确，请找出正确的那个。 （1）（a）若则必在A中（b）若则（c）若则（d）若则（2）（a） （b）（c） （d）（3）（a） （b）（c） （d）上面三个均不对（4）（a） （b）（c）若（d）若答案： ，证明： （1）f是单射； （2）f是满射。 习题 设，，，试求。习题 ，试构造两个映射和g：，使得 （1），但；（2），但。 18.设则 （1）若存在唯一的一个映射，使得，则是可逆的吗？ （2）若存在唯一的一个映射，使得，则是可逆的吗？ 19.设，则 （1）若是左可逆的，则有多少个左逆映射？ （2）若是右可逆的，则有多少个右逆映射？ 20. 是否有一个从到的一一对应，使得，但？ 习题 设求。 2.将置换分解成对换的乘积。 3.设是任一n次置换，试证：与的奇偶性相同。 习题 1.给出一个既不是自反的又不是反自反的二元关系？ 2.是否存在一个同时不满足自反性，对称性，反对称性，传递性和反自反性的二元关系？ 3.设R，S是X上的二元关系，下列命题哪些成立： a)若R与S是自反的，则分别也是自的b) 若R与S是对称的，则分别对称的c) 若R与S是传递的，则也是传递的d) 若R与S不是自反的，则也不是自反的e) 若R与S是反自反的，则也是反自反的f) 若R是自反的，则也是反自反的g) 若R与S是传递的，则R\S是传递的答案：是否是反自反的？集合X的幂集上的“真包含”关系是否是反自反的？为什么？ 5.设R、S是X上的二元关系。证明：