离散数学 集合论

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

第二篇 集合与关系

集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。

随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。

现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科

第二篇 集合与关系

集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。

随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。

现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

第二篇 集合与关系

集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。

随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。

现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科

第二篇 集合与关系

集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。

随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。

现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学

集合论练习题

一、选择题

1．设B = { {2}, 3, 4, 2}，那么下列命题中错误的是（ ）．

A．{2}?B B．{2, {2}, 3, 4}?B C．{2}?B D．{2, {2}}?B 2．若集合A={a，b，{ 1，2 }}，B={ 1，2}，则（ ）． A．B ? A，且B?A B．B? A，但B?A C．B ? A，但B?A D．B? A，且B?A 3．设集合A = {1, a }，则P(A) = ( )．

A．{{1}, {a}} B．{?,{1}, {a}} C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 4.已知A?B={1,2,3}, A?C={2,3,4},若2? B,则（ ）

A． 1?C B．2?C C．3?C D．4?C

一．列式题。用谓词表示法表示如下集合： 1． 所有偶数组成的集合A

A={x| x∈Z ∧ x mod 2 =0}. 2． 所有奇数组成的集合B

B={x| x∈Z ∧ x mod 2 =1}. 3． 10的整倍数组成的集合A

A={x| x∈Z ∧x mod 10 =0}. 4． 5的整倍数组成的集合B

A={x| x∈Z ∧x mod 5 =0}.

5． 方程x2-1=0的所有实数解的集合B。

B={x|x∈R ∧x2-1=0}

6． 小于5的非负整数组成的集合A：A={x | x ∈ N ∧ x < 5 }.

二．判断题 1．（ F ）包含三个元素的集合A表示成：A=（1，2，3）。 2．（ F ）集合A ={1，2，3}与集合B ={2，3，1}是两个不同的集合。 3．（ T ）R=Φ是一个二元关系。 4．（ T ）设A= {1, 2, 3}，R= {<1, 1>, <2, 2>, <3, 3>, <1, 2>}，则R是A上自反的关系。 5．（ T ）设A= {1, 2, 3}，R= {<1, 1>, <1, 2>, <2, 1>}，则R是A上对称的关系。 6．（ T ）设A= {1, 2, 3}，R= {<1, 2>,<1, 3>}，则R是A上反对称的关系。 7．（ T ）设A= {1, 2, 3}，R= {<1, 1>,<2, 2>}，则R是A上

康托尔集合论 集合论是19世纪70-80年代由德国数学家康托尔创立，它建立在一种无限观——“实无限”的基础上。所谓“实无限”，即把“无限”作为一个已经完成了的观念实体来看待。例如，在集合论中用N={n：n是自然数}表示全体自然数的集合就是如此。需要指出的是，在此之前的几千年数学发展史中，占主导地位的是另一种无限观，即古希腊哲学家亚里士多德所主张的“潜无限”观念。所谓“潜无限”，是把“无限”作为一个不断发展着的、又永远无法完成的过程来看待。例如，把自然数看成一个不断延伸的无穷无尽的序列1，2，3，…，n，…就是如此。 集合论是数学观念和数学方法上的一次革命性变革，由于它在解释旧的数学理论和发展新的数学理论方面都极为方便，因而逐渐为许多数学家所接受。实数理论奠定在集合论的基础上，而且各种复杂的数学概念都可以用“集合”概念定义出来，而各种数学理论又都可以“嵌入”集合论之内。因此，集合论就成了全部数学的基础，而且有力地促进了各个数学分支的发展。现代数学几乎所有的分支都会用到集合这个概念。 康托尔集， 格奥尔格·康托尔在1883年引入，是位于一条线段上的一些点的集合，具有许多显著和深刻的性质。通过考虑这个集合，康托尔和其他数学家奠定了现代点集拓扑学的基

离散数学作业1_集合与关系

1. 设A、B、C为任意三个集合，判断下列命题的真与假。如命题为真，则证明之；否则，举反例说明。 （1）若A?C=B?C，则A=B(假命题) （2）若A?C=B?C ，则A=B(假命题) （3）若A?C=B?C 且A?C=B?C ，则A=B (真命题,参考ppt 1.2节例8) 2.证明A-B=A∩~B.

证明思路：任取x∈A-B?……? x∈A∩~B

证明：任取x∈A-B?x∈A且x/∈B（根据相对补的定义）

? x∈A且x∈~B(根据绝对补的定义) ? x∈A∩~B

3. 设A={1，2，3，4，5，6},下面各式定义的R都是A上的二元关系。试分别以序偶、关系矩阵、关系图三种形式分别写出R。 (1) R={|x整除y}；(2) R={|x是y的倍数}； (3) R={|(x-y)2?A}；(4) R={|x/ y是素数}。 解： (1)

R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,2>,<2,4.>,<2,6>,<3,3>,<3,6>,<4,4>,<5,5>,<6,6>} (2)

R={<1,1>,<2,1>,<2,2>,<3,1>,<3,3>,<4,1>,<4,2>,<4,4>,<5,1>,

>,<6,1>,<6,2>,<6,3>,<6,6>} (3)

R={<1,2>,<1,3>,<2,1>,<2,3>,<2,4>,<3,2>,<3,4>,<3,1>,<3,5>,<4,3>,<4,5>,<4,2>,<4,6>,<5,4>,<5,6>,<5,3>,<6,5>,<6,4>}

(4) 质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。

100以内的质数有2，3，5，7，11，13

例：

1、设A,B是两个集合,B≠￠,试证:若A×B=B×B, 则A=B。

2、设A,B,C,D是任意四个集合，证明： （A∩B)×(C∩D)=(A×C)∩(B×D)

3、某班30名学生中学英语有7人，学日语有5人，这两科都选有3人，问两科都不选的有多少人？

(|AC∩BC|+|A∪B|=30, |AC∩BC|=21人)

4、令N={1,2,3,…}，S:N→N，则

(1)?n?N,S(n)=n+1,Ｓ称为自然数集N上的后继函数。

(2)S(1)=1,?n?N,S(n)=n-1,n≥2,Ｓ称为自然数集N 上的前仆函数。

5、设f:N×N ?N,f((x,y))=xy。则 （1）说明f是否是单射、满射或双射？ （2）求f(N×{1}),f-1({0})。

(1,4)≠(2,2),f((1,4))=f((2,2))=4；

?y?N,f((1,y))=1·y=y,任一元都有原象； [f不是单射,f是满射]

f(N×{1})={n·1|n ?N}=N；

f-1({0})={(x,y)|xy=0}={N×{0}}?{{0}×N}。

6、设R、I、N是实数、整数、自然数集合，下面定义映射f1,f2,f

例：

1、设A,B是两个集合,B≠￠,试证:若A×B=B×B, 则A=B。

2、设A,B,C,D是任意四个集合，证明： （A∩B)×(C∩D)=(A×C)∩(B×D)

3、某班30名学生中学英语有7人，学日语有5人，这两科都选有3人，问两科都不选的有多少人？

(|AC∩BC|+|A∪B|=30, |AC∩BC|=21人)

4、令N={1,2,3,…}，S:N→N，则

(1)?n?N,S(n)=n+1,Ｓ称为自然数集N上的后继函数。

(2)S(1)=1,?n?N,S(n)=n-1,n≥2,Ｓ称为自然数集N 上的前仆函数。

5、设f:N×N ?N,f((x,y))=xy。则 （1）说明f是否是单射、满射或双射？ （2）求f(N×{1}),f-1({0})。

(1,4)≠(2,2),f((1,4))=f((2,2))=4；

?y?N,f((1,y))=1·y=y,任一元都有原象； [f不是单射,f是满射]

f(N×{1})={n·1|n ?N}=N；

f-1({0})={(x,y)|xy=0}={N×{0}}?{{0}×N}。

6、设R、I、N是实数、整数、自然数集合，下面定义映射f1,f2,f