集合论练习题
一、选择题
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
5、 下列选项中错误的就是( )
A. ???
B. ?∈?
C. {}???
D.{}?∈?
6、 下列命题中不正确的就是( )
A. x ∈{x }-{{x }}
B.{}{}{{}}x x x ?-
C.{}A x x =?,则x ∈A 且x A ?
D. A B A B -=??=
7、 A , B 就是集合,P (A ),P (B )为其幂集,且A B ?=?,则()()P A P B ?=( )
A. ?
B. {}?
C. {{}}?
D.{,{}}??
8、 空集?的幂集()P ?的基数就是( )
A. 0
B.1
C.3
D.4
9.设集合A = {1,2,3,4,5,6 }上的二元关系R ={?a , b ∈A , 且a +b = 8},则R 具有的性质为( ).
A.自反的
B.对称的
C.对称与传递的
D.反自反与传递的
10、 设集合A ={1 , 2 , 3 , 4}上的二元关系
R = {<1 , 1>,<2 , 2>,<2 , 3>,<4 , 4>},
S = {<1 , 1>,<2 , 2>,<2 , 3>,<3 , 2>,<4 , 4>},
则S就是R的( )闭包.
A.自反
B.传递
C.对称
D.以上都不对
11、设A={1,2,3,4},下列关系中为等价关系。
A.R
={<1,1>,<1,2>,<2,1>, <2,2>,<3,3>}
1
={<1,1>,<1,3>,<2,2>,<3,3>,<4,4>}
B.R
2
={<1,1>,<1,3>,<2,2>,<3,1>,<3,3>,<4,4>}
C.R
3
={<1,1>,<1,3>,<2,2>,<3,2>,<4,4>}
D.R
4
12.非空集合A上的二元关系R,满足( ),则称R就是等价关系.
A.自反性,对称性与传递性
B.反自反性,对称性与传递性
C.反自反性,反对称性与传递性
D.自反性,反对称性与传递性
13.设集合A={a, b},则A上的二元关系R={
A.就是等价关系但不就是偏序关系
B.就是偏序关系但不就是等价关系
C.既就是等价关系又就是偏序关系
D.不就是等价关系也不就是偏序关系
14、设R与S就是集合A上的等价关系,则R∪S的对称性( )
A.一定成立
B.不一定成立
C.一定不成立
D.不可能成立
15、整数集合Z上“＜”关系的自反闭包就是( ) 关系
A.＝
B.≠
C.＞
D.≤
16、关系R的传递闭包t(R)可由( )来定义
A.t(R)就是包含R的二元关系
B.t(R)就是包含R的最小的传递关系
C.t(R)就是包含R的一个传递关系
D.t(R)就是任何包含R的传递关系
17、设R就是集合A上的偏序关系,R c就是R的逆关系,则R∪R c就是( )
A.偏序关系
B.等价关系
C.相容关系
D.都不就是
18、设偏序集(A,≤)关系≤的哈斯图如下所示,若A的子集B = {2,3,4,5},则元素6为B的( )。
(A)下界(B)上界
(C)最小上界(D)以上答案都不对
二、填空题
1.设集合A 有n 个元素,那么A 的幂集合P (A )的元素个数为 .
2、 集合{{}}???的幂集为
3.设集合A = {1,2,3,4,5 },B = {1,2,3},R 从A 到B 的二元关系,
则R 的集合表示式为 .
4.设集合A ={0, 1, 2},B ={0, 2, 4},R 就是A 到B 的二元关系,
},,{B A y x B y A x y x R ?∈∈∈><=且且
则R 的关系矩阵M R ＝
5、 设集合A ={a ,b ,c },A 上的二元关系
则(R ?S )－
1= ; domR= ;ran(R ?S )=
6、 设集合A =｛a ,b ,c ,d ｝,A 上的二元关系R ={, , ,
7、 设R 就是集合A = {1 , 2 ,… , 10}上的模7同余关系则[2]R = .
8、 A ={ 1, 2,3,4,5,6,8,10,24,36},RA 就是上的整除关系,子集B={1,2,3,4},则
的最大元 ,最小元 ,极大元 ,极小元 , 上界 ,下界 ,上确界 ,下确界 。
三、计算题
1.设集合{{},{,1},{1,1,}},{{,1},{1}}A B =???=?,求
(1)B ?A ; (2)A ?B ; (3)A －B ; (4)A ⊕B ;(5)P (A )
2、 设{{0},0}A =,计算(){0},()P A P A A -⊕、
3、 设A ={1,2,3},写出下列图示关系的关系矩阵,并讨论它们的性质: 1 1 1
2 3 2 3 2 3
4、设A={1,2,…,10}。下列哪个就是A 的划分？若就是划分,则它们诱导的等价关系就是什么？
(1)B={{1,3,6},{2,8,10},{4,5,7}};
第三章集合论基础 1、设A={a,{a},{a,b},{{a,b},c}}判断下面命题的真值。 ⑴{a}∈A T ⑵?({a}? A) F ⑶c∈A F ⑷{a}?{{a,b},c} F ⑸{{a}}?A T ⑹{a,b}∈{{a,b},c} T ⑺{{a,b}}?A T ⑻{a,b}?{{a,b},c} F ⑼{c}?{{a,b},c} T ⑽({c}?A)→(a∈Φ) T 2、证明空集是唯一的。（性质1：对于任何集合A，都有Φ?A。） 证明：假设有两个空集Φ1 、Φ2 ，则 因为Φ1是空集，则由性质1得Φ1 ?Φ2 。 因为Φ2是空集，则由性质1得Φ2 ?Φ1 。 所以Φ1=Φ2 。 3、设A={Φ},B=P(P(A)).问：(这道题要求知道幂集合的概念) a)是否Φ∈B?是否Φ?B? b)是否{Φ}∈B? 是否{Φ}?B? c)是否{{Φ}}∈B? 是否{{Φ}}?B? 解：设A={Φ}，B=P(P(A)) P(A)= {Φ,{Φ}} 在求P(P(A))时，一些同学对集合{Φ,{Φ}}难理解，实际上你就将{Φ,{Φ}}中的元素分别看成Φ=a ,{Φ}=b, 于是{Φ,{Φ}}={a,b} B=P(P(A))=P({a,b}) ={B0, B1 , B2 , B3 }={B00, B01,B10 ,B11}={Φ, {b}, {a}, {a,b}} 然后再将a,b代回即可B=P(P(A))=P({Φ,{Φ}})={Φ,{Φ} ,{{Φ}}, {Φ,{Φ}}} 以后熟悉后就可以直接写出。 a) Φ∈B Φ?B b) {Φ}∈B {Φ} ? B c) {{Φ}}∈B {{Φ}}?B a)、b)、c)中命题均为真。 4、证明A?B ? A∩B=A成立。 证明：A∩B=A ??x(x∈A∩B ?x∈A) ??x((x∈A∩B → x∈A)∧(x∈A→ x∈A∩B)) ??x((x?A∩B∨x∈A)∧(x?A∨x∈A∩B)) ??x((?(x∈A∧x∈B)∨x∈A)∧(x?A∨(x∈A∧x∈B)) ??x(((x?A∨x?B)∨x∈A)∧(x?A∨(x∈A∧x∈B))) ??x(T∧(T∧( x?A∨x∈B))) ??x( x?A∨x∈B)??x(x∈A→x∈B)? A?B 5、(A-B)-C=(A-C)-(B-C) 证明：任取x∈(A-C)-(B-C) ?x∈(A-C)∧x?(B-C) ?(x∈A∧x?C)∧?(x∈B∧x?C) ?(x∈A∧x?C)∧(x?B∨x∈C) ?(x∈A∧x?C∧x?B)∨(x∈A∧x?C∧x∈C) ?x∈A∧x?C∧x?B?x∈A∧x?B∧x?C ?(x∈A∧x?B)∧x?C ?x∈A-B∧x?C?x∈(A-B)-C 所以(A-B)-C=(A-C)-(B-C)
离散数学试题库——填空题 （每空2分） 1 命题: ? ? {{a }} ? {{a },3,4,1} 的真值 = __ __ . 2. 设A= {a,b}, B = {x | x 2－(a+b) x+ab = 0}, 则两个集合的关系为: __ __. 3. 设集合A ＝{a ,b ,c },B ={a ,b }, 那么 P(B )－P(A )=__ __ . 4. 无孤立点的有限有向图有欧拉路的充分必要条件为: 5.公式))(),(()),()((x S z y R z y x Q x P x →?∨→?的自由变元是 , 约束变元是 . 6.)))()()(()),()(()((x R z Q z y x P y x →?→???的前束范式是 . 7．设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且（N ：自然数集，E + 正偶 数） 则 =?B A 。 8．A ，B ，C 。 9．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 10．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 11．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 12．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 13．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为
则 R= 。 14．图的补图为。15．设A={a，b，c，d} ，A上二元运算如下： 那么代数系统
离散数学常考题型梳理 第2章关系与函数 一、题型分析 本章主要介绍关系的概念及运算、关系的性质与闭包运算、等价关系、相容关系和偏序关系三个重要关系、函数以及函数相关知识等内容。常涉及到的题型主要包括： 2-1关系的概念理解以及关系的并、交、补、差以及复合和逆关系等运算2-2关系自反和反自反、对称和反对称等性质的概念理解与判定；自反、对称和传递闭包运算。 2-3等价关系 2-4偏序关系和哈斯图 2-5 函数的概念和性质 因此，在本章学习过程中希望大家要清楚地知道： 1．有序对和笛卡尔积 （1）有序对：所谓有序对就是指一个有顺序的数组，如< x , y >，x , y的位置是确定的，且< a , b >< b , a >。 （2）笛卡尔积：把集合A，B合成集合A×B，规定： {,|} ?=<>∈∈ 且 A B x y x A y B 由于有序对< x , y >中x，y 的位置是确定的，因此A×B 的记法也是确定的，不能写成B×A 。 笛卡儿积的运算一般不满足交换律。 2．二元关系的概念和表示、几种特殊的关系和关系的运算 （1）二元关系的概念：二元关系是一个有序对集合，设集合A，B ，从集合A 到B的二元关系 R∈ x ∈ < y =且 > } , x {B | y A 记作xRy。 二元关系的定义域：A Ram? R ) (。 ) R Dom? (；二元关系的值域：B 二元关系R 是一个有序对组成的集合．因此，一个二元关系是一个集合，可以用集合形式表示；反过来说，一个集合未必是一个二元关系，仅当集合是由有序对元素组成的，才能当做二元关系。 常用关系的表示法包括了集合表示法、列举法、描述法、关系矩阵法和关系图法。关系矩阵和关系图是有限集合上的二元关系的表示方法。
《离散数学》单元测试（集合论） 3.1集合的基本概念 1.设Ａ、Ｂ、Ｃ是集合，确定下列命题是否正确，说明理由。 （1）Ф?Ф （2）Ф∈Ф （3）Ф?{Ф} （4）Ф∈{Ф} （5）如果A∈B与B?C,则A?C （6）如果A∈B与B?C,则A∈C （7）如果A?B与B∈C,则A∈C （8）如果A?B与B∈C,则A?C 2.有n个元素的集合Ａ的幂集ρ(A)的元素个数为多少？求下列集合的幂集合。 （1）Ф （2）{Ф} （3）{Ф,{Ф}} （4）{a,b} （5）{a,b,{a,b}} （6）{1，{1}，2，{2}} 3.2 集合的运算 1.设A，B是两个集合，A={1，2，3}，B={2，3，4}，则B－A= ，ρ（B）－ ρ（A）= 。 2.全集E={a，b，c，d，e}，A={a，d}，B={a，b，e}，C={b，d}，求 ，ρ（A）∩ρ（B） A B C= () = 。 3.下列命题正确的是（）。 A．φ∩{φ}=φB．φ∪{φ}=φC．{a}∈{a，b，c} D．φ∈{a，b，c} 4.确定下列各式的值： Ф∩{Ф}＝ {Ф,{Ф}}－Ф＝ {Ф,{Ф}}－{Ф}＝ 6.证明下列各等式： A∩(B－A)＝Ф A∪(A∩B)＝A 3.3 有穷集合的计数问题 掌握文氏图和容斥原理求解有穷集合的计数问题的方法，并会简单应用。以教材的示例为基础。
第4章 二元关系 4.1二元关系的定义、表示方法与特性 1. A 和B 是任意两个集合，若序偶的第一个元素是A 的一个元素，第二个元素是B 的一个 元素，则所有这样的序偶集合称为集合A 和B 的 ， 记作A ?B ，即A ?B= 。A ?B 的子集R 称为A 到B 的一个 。若|A|=m ， B|=n ，则A 到B 共有 个不同的二元关系。 2. 设集合A ＝{a,b},B ＝{x,y},求笛卡尔乘积A ×B,B ×A,,A ×ρ(B)。 3. 证明： (1) (A ∩B)×C=(A ×C)∩(B ×C) (2) (A ∪B)×C=(A ×C)∪(B ×C) 4. 设A={a,b},B={x,y},则从A 到B 的二元关系共有多少个？请分别列出。 5. 设集合A={a,b,c,d},B={1,2,3},R 是A 到B 的二元关系，R={
离散数学集合论部分测试题
离散数学集合论部分综合练习 本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是集合论部分的综合练习。 一、单项选择题 1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）． A．A?B，且A∈B B．A∈B，但A?B C．A?B，但A?B D．A?B，且A?B 2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )． A．{a，{ a }}∈A B．{ a }?A C．{2}∈A D．?∈A 3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}∈A B．{2}?A C．{a}?A D．?∈A 4．若集合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 5．设集合A = {1, a }，则P(A) = ( )． A．{{1}, {a}} B．{?,{1}, {a}} C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 6．若集合A的元素个数为10，则其幂集的元素个数为（）． A．1024 B．10 C．100 D．1 7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={
第二篇集合与关系 集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。 随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。 现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。 本篇介绍集合论的基础知识，主要内容包括集合及其运算、性质、序偶、关系、映射、函数、基数等。 第2-1章集合及其运算 §2-1-1 集合的概念及其表示 一、集合的概念 “集合”是集合论中的一个原始的概念，因此它不能被精确地定义出来。一般地说，把具有某种共同性质的许多事物，汇集成一个整体，就形成一个集合。构成这个集合的每一个事物称为这个集合的一个成员（或一个元素），构成集合的这些成员可以是具体东西，也可以是抽象东西。例如：教室内的桌椅；图书馆的藏书；全国的高等学校；自然数的全体；程序设计语言C的基本字符的全体等均分别构成一个集合。通常用大写的英文字母表示集合的名称；用小写的英文字母表示元素。若元素a属于集合A记作
离散数学集合论部分综合练习 本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是集合论部分的综合练习。 一、单项选择题 1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）． A．A?B，且A∈B B．A∈B，但A?B C．A?B，但A?B D．A?B，且A?B 2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )． A．{a，{ a }}∈A B．{ a }?A C．{2}∈A D．?∈A 3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}∈A B．{2}?A C．{a}?A D．?∈A 4．若集合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 5．设集合A = {1, a }，则P(A) = ( )． A．{{1}, {a}} B．{?,{1}, {a}} C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 6．若集合A的元素个数为10，则其幂集的元素个数为（）． A．1024 B．10 C．100 D．1 7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={
离散数学复习注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1．下列句子中，（）是命题。 A．2是常数。B．这朵花多好看呀！ C．请把门关上！D．下午有会吗？ 2．令p: 今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（）。 A. p q r ∨→ ∧→ B. p q r C. p q r ∨? ∧∧ D. p q r 3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。 A.p q ∧ ∧? B.p q C.p q →? ∨? D. p q 4．设() Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。 P x:x是鸟，() A. ()(()()) Q x ??∧()) x P x Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y：x大于等于y；命题“所有整数 f x:x的绝对值，(,) P x:x是整数，() 的绝对值大于等于0”可符号化为（）。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人，() G x:x犯错误，命题“没有不犯错误的人”符号化为（）。 A．(()()) ??→? x F x G x ?∧B．(()()) x F x G x C．(()()) ??∧? x F x G x ??∧D．(()()) x F x G x 7.下列命题公式不是永真式的是（）。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8．设() R x:x为有理数；() Q x:x为实数。命题“任何有理数都是实数”的符号化为（）
9.给定算式: {[(a ＋b)＊c]＊(d ＋e)}＋[f －(g ＊h)] 此算式的波兰符号表示式为( ), 逆波兰符号表示式为( ). A 、＋＊＊a ＋bc ＋def －g ＊h B 、＋＊＊＋abc ＋de －f ＊gh C 、＊－＊＋abc ＋de －fgh ＋ D 、ab ＋c ＊de ＋＊fgh ＊－＋ 10．设R,Z,N 分别为实数,整数和自然数集，函数f ：R →R ，f(x)＝x ，f 是（ ）; g: Z →N, g(x)＝|x|, g 是( ); h: N →N ×N. h(n)＝﹤n,n ＋1﹥,h({5})＝( ) A ．满射函数 B ．单射函数 C ．双射函数 D ．非单射非满射 E. 满射非单射 F.单射非满射 G ,<5,6> H,{<5,6>} J,以上答案都不对. 11. 75个学生去书店买语文,数学,英语书,每种书每个学生至多买1本.已知20个学生每人 买3本书,55个学生每人至少买2本书.每本书的价格都是1元,所有学生总共花费 140元,恰好买2本书的有( )多少个学生.至少买2本书的学生花费( )元.买 1本书的有( )个学生.至少买1本书的有( )个学生.没买书的有( )个学生. A.55 B.40 C.35 D.15 E.30 F.130 G.65 H.140 J.60 K.10 12. 为每个逻辑断言选择正确的解释。T(x)：x 今天来上课，S(x)：x 学计算机专业的学生， P(x)：x 编程序，G(x)：x 玩游戏。个体域是殷都大学。 ?x T(x)表示（ ），??x T(x)表示（ ），?x ? T(x)表示（ ），?x(S(x)→P(x))表示（ ），?x(S(x)∧G(x))表示（ ），?x(S(x)∧P(x))表示（ ），?x(S(x)→G(x))表示（ ）。 A 学计算机专业的学生会编程序， B 殷都大学的学生都是计算机专业且会编程序。 C 有些计算机专业的学生玩游戏， D 所有同学今天都来上课了， E 今天有同学没来上课。 F 计算机专业的学生玩游戏， G 今天没有同学来上课。 二、计算与应用题（共40分） 1. S={ 1，2，…，10 }，定义S 上的关系R={
【半群】G非空，·为G上的二元代数运算，满足结合律。 【群】（非空，封闭，结合律，单位元，逆元）恰有一个元素1适合1·a=a·1=a,恰有一个元素a-1适合a·a-1=a-1·a=1。 【Abel群/交换群】·适合交换律。可能不只有两个元素适合x2=1 【置换】n元置换的全体作成的集合Sn对置换的乘法作成n 次对称群。 【子群】按照G中的乘法运算·,子集H仍是一个群。单位子群{1}和G称为平凡子群。 【循环群】G可以由它的某元素a生成,即G=（a）。a所有幂的集合an，n=0，±1，±2，…做成G的一个子群，由a生成的子群。若G的元数是一个质数，则G必是循环群。 n元循环群（a）中,元素ak是（a）的生成元的充要条件是（n，k）=1。共有?（n）个。【三次对称群】{I（12）（13）（23）（123）（132）} 【陪集】a，b∈G，若有h∈H，使得a =bh，则称a合同于b（右模H），a≡b（右mod H）。H有限，则H的任意右陪集aH的元数皆等于H的元数。任意两个右陪集aH和bH或者相等或者不相交。 求右陪集：H本身是一个；任取a?H而求aH又得到一个；任取b?H∪aH而求bH又一个。G=H∪aH∪bH∪… 【正规子群】G中任意g，gH=Hg。（H=gHg-1对任意g∈G都成立） Lagrange定理G为有限群，则任意子群H的元数整除群G的元数。 1有限群G的元数除以H的元数所得的商，记为（G：H），叫做H在G中的指数，H的指数也就是H的右（左）陪集的个数。 2设G为有限群,元数为n,对任意a∈G，有an=1。 3若H在G中的指数是2，则H必然是G的正规子群。证明：此时对H的左陪集aH，右陪集Ha，都是G中元去掉H的所余部分。故Ha=aH。 4G的任意多个子群的交集是G的子群。并且，G的任意多个正规子群的交集仍是G的正规子群。 5 H是G的子群。N是G的正规子群。命HN为H的元素乘N的元素所得的所有元素的集合，则HN是G的子群。 【同态映射】K是乘法系统，G到K的一个映射σ（ab）=σ（a）σ（b）。 设（G，*），（K，+）是两个群，令σ：x→e，?x∈G，其中e是K的单位元。则σ是G到K 内的映射，且对a，b∈G，有σ（a*b）=e=σ（a）+ σ（b）。即，σ是G到K的同态映射，G～σ（G）。σ（G）={e}是K的一个子群。这个同态映射是任意两个群之间都有的。 【同构映射】K是乘法系统，σ是G到σ（G）上的1-1映射。称G与σ（G）同构，G?G′。同构的群或代数系统，抽象地来看可以说毫无差别。G和G′同态，则可以说G′是G的一个缩影。 【同态核】σ是G到G′上的同态映射，核N为G中所有变成G′中1′的元素g的集合，即N=σ-1（1′）={g∈G∣σ（g）=1′}。 N是G的一个正规子群。对于Gˊ的任意元素aˊ，σ-1(aˊ)={x|x∈G ,σ(x)= aˊ}是N在G 中的一个陪集。Gˊ的元素和N在G中的陪集一一对应。 设N是G的正规子群。若A，B是N的陪集，则AB也是N的陪集。 【环】R非空，有加、乘两种运算 a+b=b+a2）a+（b+c）=（a+b）+c， 3）R中有一个元素0，适合a+0=a， 4）对于R中任意a,有-a,适合a+(-a)=0， 5）a（bc）=（ab）c，
集合论期末复习题 1. 求(())P P φ 答：(()){,{}}P P φφφ= 2. 设||A n =，求|()|P A 答：|()|2n P A = 3. {,{}}________φφφ-=，{,{}}{}________φφφ-= 答：{,{}}φφ，{{}}φ 4. 证明：()()()A B C A B A C ?⊕=?⊕? 证明： () [()()] (~)(~) (~)(~) (~)(~)(~)(~)[()(~~)][()(~~)] [()~()][()~()] [()()][()()] ()() A B C A B C C B A B C C B A B C A C B A B A A B C A C B A C A A B A C A C B A A B A C A C A B A B A C A C A B A B A C ?⊕=?-?-=????=?????=???????????=???????=???????=?-???-?=?⊕? 5. 200人中，有67人学数学，47人学物理，95人学生物，26人学数学和生物，28人学数学和物理，27人学生物和物理，50人三门都不学，问：三门都学的人数和单学一门的人数？ 解：设三门都学的人数和单学数学、物理、生物的人数分别为x ，y1,y2,y3，则如下图： (26)(28)167(27)(28)247(26)(27)395 (26)(27)(28)12350200 x x x y x x x y x x x y x x x x y y y +-+-+=??+-+-+=??+-+-+=??-+-+-+++++=? 求解得到：1132228135342214123269364 y x x y x y y x y y y y x y -==????-=-=?????-==????++-==?? 6. 集合S={0,1,2,3,4,5,6}，R 为S 上的关系。R={ 《离散数学》练习题和参考答案 一、选择或填空（数理逻辑部分） 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：（1），（4） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2），（3），（4），（5），（6） 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。(5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是 （4）是，T （5）不是（6）不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） P Q→ ?（2）Q P? →（3）Q P? ?（4）Q P→ ? 8、设个体域为整数集，则下列公式的意义是( )。 (1) ?x?y(x+y=0) (2) ?y?x(x+y=0) 答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值： (1) ?x?y (xy=y) ( ) (2) ?x?y(x+y=y) ( ) (3) ?x?y(x+y=x) ( ) (4) ?x?y(y=2x) ( )答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式?x(P(x)∨Q(x))在哪个个体域中为真?( ) (1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1） 11、命题“2是偶数或-3是负数”的否定是（）。答：2不是偶数且-3不是负数。 12、永真式的否定是（） (1) 永真式(2) 永假式(3) 可满足式(4) (1)--(3)均有可能答：（2） 13、公式(?P∧Q)∨(?P∧?Q)化简为（），公式 Q→(P∨(P∧Q))可化简为（）。答：?P ，Q→P 14、谓词公式?x(P(x)∨?yR(y))→Q(x)中量词?x的辖域是（）。答：P(x)∨?yR(y) 15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。 作业答案：集合论部分 P90:习题六 5、确定下列命题是否为真。 （2）?∈? （4）{}?∈? （6）{,}{,,,{,}}a b a b c a b ∈ 解答：（2）假（4）真（6）真 8、求下列集合的幂集。 （5）{{1,2},{2,1,1},{2,1,1,2}} （6）{{,2},{2}}? 解答： （5）集合的元素彼此互不相同，所以{2,1,1,2}{1,2}=，所以该题的结论应该为 {,{{1,2}},{{2,1,1}},{{1,2},{2,1,1}}}? （6）{,{{,2}},{{2}},{{,2},{2}}}??? 9、设{1,2,3,4,5,6}E =，{1,4}A =，{1,2,5}B =,{2,4}C =,求下列集合。 （1）A B （2）()A B 解答： （1）{1,4}{3,4,6}{4}A B == （2）(){1}{2,3,4,5,6}A B == 31、设A,B,C 为任意集合，证明 () ()()()A B B A A B A B --=- 证明： ()() {|}{|()()}{|()()()()} {|()()}{|()()}{|()()} {|()()}{|()(A B B A x x A B x B A x x A x B x B x A x x A x B x B x B x A x A x B x A x x A x B x B x A x x A B x A x B x x A B x A x B x x A B x B x x A B x A --=∈-∨∈-=∈∧?∨∈∧?=∈∨∈∧?∨∈∧∈∨?∧?∨?=∈∨∈∧?∨?=∈∧?∨?=∈∧∈∨∈=∈∧∈=∈∧∈)} B A B A B =- 离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外） 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出 掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有 解答过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在 03任务界面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)-P(B )= {{3}，{1,3}，{2,3}， A B {1,2,3}} ，A?B= {<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3.2>} ．2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ．3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为 {<2, 2>，<2, 3>，<3, 2>}，<3,3> ．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝ {<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={ 集合论练习题 一、选择题 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 ，且BA B ．B A ，但BA C ．B A ，但BA D ．B A ，且BA 3．设集合A = {1, a }，则P (A ) = ( )． A ．{{1}, {a }} B ．{?,{1}, {a }} C ．{?,{1}, {a }, {1, a }} D ．{{1}, {a }, {1, a }} 4.已知AB ={1,2,3}, AC ={2,3,4},若2 B,则（ ） A ． 1?C B ．2? C C ．3?C D ．4?C 5. 下列选项中错误的是( ) A ． ??? B ． ?∈? C ． {}??? D ．{}?∈? 6. 下列命题中不正确的是（ ） A ． x {x }-{{x }} B ．{}{}{{}}x x x ?- C ．{}A x x =?,则xA 且x A ? D ． A B A B -=??= 7. A , B 是集合，P (A ),P (B )为其幂集，且A B ?=?，则()()P A P B ?=( ) A ． ? B ． {}? C ． {{}}? D ．{,{}}?? 8. 空集?的幂集()P ?的基数是( ) A ． 0 B ．1 C ．3 D ．4 9．设集合A = {1，2，3，4，5，6 }上的二元关系R ={a , b ∈A , 且a +b = 8}，则R 具有的性质为（ ）． A ．自反的 B ．对称的 C ．对称和传递的 D ．反自反和传递的 试卷二试题与参考答案 一、填空 1、 P ：你努力，Q ：你失败。 2、 “除非你努力，否则你将失败”符号化为 ； “虽然你努力了，但还是失败了”符号化为 。 2、论域D={1，2}，指定谓词P 则公式x ??真值为 。 3设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则 R= （列举法）。 R 的关系矩阵M R = 。 4、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系 R= ；A 上既是对称的又是反对称的关系R= 。 5、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 6、4阶群必是 群或 群。 7、下面偏序格是分配格的是 。 8、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 二、选择 1、在下述公式中是重言式为（ ） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（ ）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生 的S S ?上一个划分共有（ ）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为 则R 具有（ ）性质。 A ．自反性、对称性、传递性； B ．反自反性、反对称性； C ．反自反性、反对称性、传递性； D ．自反性 。 第 1 页 共 4 页 2015 - 2016学年第一学期 《离散数学》（集合论部分）自测试题 一、单项选择题(本大题共8小题，每小题2分，共16分) 在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或漏选均不得分。 1）等价关系一定不是．．【 】 A. 对称的 B. 自反的 C. 可传递的 D. 反自反的 2）设{,{1}}A a =，则下列描述中正确．．的是【 】 A. {1}A ∈ B. {1}A ? C. {a}A ∈ D. A ?∈ 3）设A 、B 是两个任意集合，则A B -=??【 】 A. A B = B. A B ? C. A B ? D. B =? 4）设{{},{},{}}X a b =?，则其幂集()P X 的元素总个数为【 】 A. 4 B. 8 C. 16 D. 32 5）设R 是实数集合，:f R R →,()21f x x =+，则f 【 】 A. 是关系，但不是函数 B. 仅是满射函数 C. 仅是单射函数 D. 是双射函数 6）设R 是A 上的二元关系，r 、s 、t 分别指关系的自反闭包、对称闭包、传递闭包、则下列描述不正确．．．的是【 】 A. ()A r R R I = B. 2()t R R R = C. 1 ()s R R R -= D. -1-1 R R =（） 7）如果R 1和R 2是集合A 上的自反关系，则R 1∪R 2, R 1∩R 2, R 1―R 2中自反关系有【 】个 A. 0 B. 1 C. 2 D. 3 8）设集合A=｛a,b,c ｝，B=｛1,2,3,4｝，作f ：A →B ，则不同的函数个数为【 】个 A. 12 B. 81 C. 64 D. 以上均不正确 二、填空题(本大题共12空，每空2分，共24分) 请在每小题的空格中填上正确答案。错填、漏填均不得分。 7）设集合A={1,2,3,4}，则A 中的划分有_____________个. 8）设=<1,2>,<1,3>,<2,4>,<4,3>R ｛｝，那么fld R =_____________. 9）设集合A =｛1，2，3，4｝，则A A ⊕= _____________. 10）设关系F ={<3,3>,<6,2>},G ={<2,3>}，则F G = _____________. ----------------------------------------第-------------------1---------------------装--------------------------------线--------------------------------------- 离散数学疑难解析——集合论部分 第一章 集合 [集合的知识点] 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集 2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan 律等），文氏（Venn ）图 3、序偶与迪卡尔积 [集合的疑难解析] 1．集合的概念 因为集合的概念大家在中学阶段已经学过，这里只多介绍了一个幂集的概念，所重点要对幂集加以掌握，一是掌握幂集的构成，一个集合A 的幂集是由A 的所有子集组成的集合。二是掌握幂集元数为2n ，其中n 是集合A 的元素个数。 2．集合恒等式的证明 通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在B A B A ~?=-证明中的特殊作用。 第二章 关系与映射 [二元关系的知识点] 1、关系、关系矩阵与关系图 2、复合关系与逆关系 3、关系的性质（自反性、对称性、反对称性、传递性） 4、关系的闭包（自反闭包、对称闭包、传递闭包） 5、等价关系与等价类 6、偏序关系与哈斯图（Hasse ）、极大/小元、最大/小元、上/下界、最小上界、最大下界 7、函数及其性质（单射、满射、双射） 8、复合函数与反函数 [二元关系疑难解析] 1．关系的概念 关系的概念是第二章全章的基础，又是第一章集合概念的应用。因此，大家应该真正理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。 2．关系的性质及其判定 关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、半序关系的基础。对于四种性质的判定，可以依据教材中P49上总结的规律。这其中对传递性的判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。另一点是介绍一种判定传递性的“跟踪法”，即若()()()R a a R a a R a a i i ∈∈∈-,, ,,,,13221 ，则()R a a i ∈,1。如若()()R a b R b a ∈∈,,,，则有()R a a ∈,，且()R b b ∈,。 3．关系的闭包《离散数学》练习题和参考答案
离散数学及其应用集合论部分课后习题答案
离散数学作业答案
离散数学集合论练习题
离散数学试题与答案
《离散数学》(集合论部分)自测试题
离散数学疑难解析——集合论部分
相关主题
文本预览