离散数学作业4_集合与关系_关系的性质

专升本《离散数学》一、（共75题,共150分）1. 集合，则（）（2分）A.B.C.D.标准答案：B2. 集合，则下列哪个不是的元素（）（2分）A.B.C.D.标准答案：B3. 设，在条件且下与（）集合相等。

（2分）A.或B.或C.，或D.，或标准答案：C 4. 集合上的关系，则是（）（2分）A.自反的B.对称的C.传递且对称的D.反自反且传递的标准答案：B5. 集合,下列不是到的关系的是（）（2分）A.B.C.D.标准答案：A6. ，表示求两数的最小公倍数的运算（表示整数集合），对于运算的零元是（）（2分）A.B.C.D.不存在标准答案：D7. 下面各集合都是的子集，（）集合在普通加法运算下是封闭的。

（2分）A.B.C.D.标准答案：A8. 设集合，“”为整除关系，则代数系统（）（2分）A.是域B.是格，不是布尔代数C.是布尔代数D.不是代数系统标准答案：C9. 在（）中，补元是唯一的。

（2分）A.有界格B.有补格C.分配格D.有补分配格。

标准答案：D10. 下列语句中，真命题的是( ) （2分）A.请把门关上B.是素数C.D.太阳从西边升起标准答案：B11. 是自然数集，是小于等于关系，则是（）。

（2分）A.有界格B.有补格C.分配格D.有补分配格标准答案：C12. 下列函数中，（）是双射（2分）A.B.（除以的余数）C.D.标准答案：D13. 设为集合，，在上有（）种不同的关系。

（2分）A.B.C.D.标准答案：D14. 设是个结点、条边和个面的连通平面图，则等于（）。

（2分）A.B.C.D.标准答案：A15. 对于独异点，则下列说法正确的是（）（2分）A.不一定有单位元B.满足交换律C.一定是半群D.独异点就是群标准答案：C16. 群中，当（）时，该群一定是循环群。

（2分）A.B.C.D.标准答案：B17. 设，为普通乘法，则是（）（2分）A.代数系统B.半群C.群D.都不是标准答案：D18. 下列各图哪个一定是树（）（2分）A.有个结点，条边的连通图B.每对结点之间都有路的图C.有个结点，条边的图D.以上说法都不正确标准答案：A19. 在如下各图中是欧拉图的是（）（2分）A.B.C.D.标准答案：B20. 下列等价关系正确的是（）（2分）A.B.C.D.标准答案：B21. 下列哪些关系是对称关系（）（2分）A.B.C.D.标准答案：A,D22. 的合取范式为（）（2分）A.B.C.D.标准答案：B,D23. 关于复合运算，下列说法正确的是（）（2分）A.置换的复合不一定是置换B.置换在复合运算下是封闭的C.可数集的无限子集仍是可数集D.以上说法都正确标准答案：B,C24. 为命题，则下述公式中是重言式为（）（2分）A.B.C.D.标准答案：B,D25. 令我上街；我去书店看看；我很累则命题“如果我上街，我就去书店看看，除非我很累”可以符号化为（）（2分）A.B.C.D.标准答案：A,D26. 若集合，则（）（2分）A.且B.但C.但D.且标准答案：A27. 在（）下有。

离散数学作业册第一章命题逻辑1.1 命题与逻辑联结词1.判断下列语句是否是命题，不是划“×”，是划“√”，且指出它的真值.(1)所有的素数都是奇数. ( ) 其真值( )(2)明天有离散数学课吗？ ( ) 其真值( )(3)326+>． ( ) 其真值( )(4)实践出真知. ( ) 其真值( )(5)这朵花真好看呀！ ( ) 其真值( )(6)5x=． ( ) 其真值( )(7)太阳系外有宇宙人． ( ) 其真值( )2.将下列命题符号化．(1)如果天下雨，那么我不去图书馆.(2)若地球上没有水和空气，则人类无法生存.(3)我们不能既划船又跑步．(4)大雁北回，春天来了.3.将下列复合命题分解成若干个原子命题，并找出适当的联结词.(1)天下雨，那么我不去图书馆.(2)若地球上没有水和空气，则人类无法生存.1.2 命题公式1. 判断下列各式是否是命题公式，不是的划“×”，是的划“√”．(1)(Q→R∧S). ( )(2)((R→(Q→R)→(P→Q)). ( )(3) (P∨QR)→S. ( )(4)((?P→Q)→(Q→P)). ( )2．写出五个常用命题联结词的真值表.1.3 真值表与等价公式1.指出下列命题的成真赋值与成假赋值．(1)?(P∨?Q).(2)?P→(Q→P).2.构造真值表，判断下列公式的类型．(1)(P∧Q)∧?(P∨Q).(2) P→(P∧┑Q))∨R.3.用等值演算法验证下列各等价式．(1) ((P→Q)∧(Q→R))→(P→R)?T.(2)P→(Q∧R)?(P→Q)∧(P→R).(3)?(P∨Q)∨(?P∧Q)??P．1.4 蕴涵式及其他联结词1.试证明下列各式为重言式．(1)(P→Q)∧(Q→R)?(P→R)．(2) (P→Q)→Q?P∨Q．(3)?(P↓Q)??P↑?Q．2.将下列公式化成与之等价且仅含{┑，∨}中联结词的公式．(1) (P∨Q)∧┑P(2) (P→(Q∨┑R))∧(┑P∧Q)3.证明{?，∧}是最小全功能联结词组.4.设A、B、C为任意的三个命题公式，试问下面的结论是否正确？(1)若A∧C?B∧C，则A?B．(2)若?A??B，则A?B．(3)若A→C?B→C，则A?B．1.6 对偶与范式1.试给出下列命题公式的对偶式．(1)T∨(P∧Q)．(2)?(P∧Q)∧(?P∨Q)．2.试求下列各公式的主析取范式和主合取范式．(1) (P→(Q∧R))∧(┑P→(┑Q→R))．(2)(?(P→Q)∧Q)∨R．(3)(P→(Q∨R))∧(?P∨(Q?R)).3.试用将公式化为主范式的方法，证明下列各等价式．(1) (┑P∨Q)∧(P→R)?P→(Q∧R)(2) ┑(P?Q)?(P∧┑Q)∨(┑P∧Q)1.7 推理理论1.试用推理规则，论证下列各式．(1) ┑(P∧┑Q),┑Q∨R,┑R?┑P(2) P∨Q,Q→R,P→S,┑S?R∧(P∨Q)(3) ┑P∨Q,┑Q∨R,R→S?P→S(4) P∨Q,P→R,Q→S?R∨S第二章谓词逻辑2.1 词的概念与表示1.用谓词表达写出下列命题．(1)高斯是数学家，但不是文学家.(2)小王既是运动员也是大学生.(3)张宁和李强都是三好学生.(4)若是x奇数，则2x不是奇数.2.2 命题函数与量词1.用谓词表达式写出下列命题．(1)每个计算机系的学生都学离散数学.(2)直线A平行于直线B当且仅当直线A不相交于直线B.(3)不存在既是奇数又是偶数的自然数.(4)没有运动员不是强壮的.(5)有些有理数是实数但不是整数.(6)所有学生都钦佩某些教师.2.3 谓词公式与变元的约束1.利用谓词公式翻译下列命题． (1)没有一个奇数是偶数.(2)一个整数是奇数，如果它的平方是奇数.2. 设个体域为自然数集N ，令P(x)：x 是素数；E(x)：x 是偶数；O(x)：x 是奇数；D(x ，y)：x 整除y ．将下列各式译成汉语．(1)?x(E(x)∧D(x ，6))．(2)?x(O(x)→?y(P(x)→?D(x ，y)))．3.指出下列表达示中的自由变元和约束变元，并指明量词的辖域．(1)()()(,)()()x F x Q x y xP x R x ?∧→?∨．(2)?x(P(x ，y)∨Q(z))∧?y(R(x ，y)→ ?zQ(z))．4.设个体域为A ＝{a ，b ，c}，消去公式?xP(x)∧?xQ(x)中的量词．2.4 谓词演算的等价式与蕴含式1.试证下列等价式或蕴涵式,其中A(x),B(x)表示含x自由变量的公式,A,B 表示不含变量x（不论是自由的还是约束的）的公式.(1)（?x A(x)→B）?(?x(A(x)→B))．(2)（?x A(x)→B）??x(A(x)→B)．2.试将下列公式化成等价的前束范式．(1)?x（（┑?yP(x,y)）→(?zQ(z)→R(x))）．(2)?x(F(x)→G(x))→(?xF(x)→?xG(x))．2.5 谓词演算的推理理论1.证明下列推理．(1)所有有理数都是实数，某些有理数是整数。

一、请给出一个集合A ，并给出A 上既具有对称性，又具有反对称性的关系。

（10分） A:(A ∩B)∪A=A,(A ∪B)∩A=A.二、请给出一个集合A ，并给出A 上既不具有对称性，又不具有反对称性的关系。

（10分） A:(A ∩B)∪A=A,(A ∪B)∩A=A.三、设A={1，2}，请给出A 上的所有关系。

（10分）{1,2} {2,1}四、设A={1，2，3}，问A 上一共有多少个不同的关系。

（10分）集合中有三个元素,3个元素对,可定义二元关系2^3=8种（3个元素对分别满足或者不满足关系R ）五、证明： 命题公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。

（10分）证明：设公式G 的合取范式为：G ’=G 1∧G 2∧…∧G n若公式G 恒真，则G ’恒真，即子句G i ；i=1,2,…n 恒真为其充要条件。

G i 恒真则其必然有一个原子和它的否定同时出现在G i 中，也就是说无论一个解释I 使这个原子为1或0 ，G i 都取1值。

若不然，假设G i 恒真，但每个原子和其否定都不同时出现在G i 中。

则可以给定一个解释I ，使带否定号的原子为1，不带否定号的原子为0，那么G i 在解释I 下的取值为0。

这与G i 恒真矛盾。

因此，公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。

六、若G=(P ，L)是有限图，设P(G)，L(G)的元数分别为m ，n 。

证明：n ≤2m C ，其中2m C 表示m 中取2的组合数。

（10分）证明：如果G=(P,L)为完全图，即对于任意的两点u 、v （u ≠v ）,都有一条边uv ，则此时对于元数为m 的P(G)，L(G)的元数取值最大为C m 2。

因此，若G=(P,L)为一有限图，设P(G)的元数为m ，则有L(G)的元数n ≤C m 2 ，其中C m 2 表示m 中取2的组合数。

离散数学集合与关系离散数学是数学中一门独立的分支，它主要研究离散的数学结构和被限制在有限范围的对象。

集合论和关系理论是离散数学的重要组成部分，它们在计算机科学、信息科学等领域具有广泛的应用。

一、集合的概念与基本运算集合是离散数学中最基本的概念之一，它是由确定的元素所组成的整体。

集合的表示通常使用大写字母，元素用小写字母表示，并用花括号{}括起来。

例如，集合A={1,2,3,4}表示由元素1,2,3,4组成的集合A。

在集合论中，集合之间的关系可以通过特定的运算来描述。

常见的集合运算包括并集、交集、差集和补集。

并集是指所有属于被操作的集合的元素的集合。

交集是指同时属于所有被操作的集合的元素的集合。

差集是指属于一个集合而不属于另一个集合的元素的集合。

补集是指在全集中属于一个集合而不属于另一个集合的元素的集合。

二、关系的定义与性质关系是描述集合之间元素之间的某种联系或者规律的数学概念。

在离散数学中，关系可以用二元组的形式表示。

关系的性质包括自反性、对称性和传递性。

自反性是指元素与自身之间存在关系。

对称性是指如果两个元素之间存在关系，那么它们之间的关系是互逆的。

传递性是指如果两个元素之间存在关系，并且与另一元素之间也存在关系，那么这两个元素之间也存在关系。

三、集合的基数与幂集集合的基数是指集合中的元素个数。

若集合A中的元素个数为n，则记作|A|=n。

基数为有限值的集合称为有限集，基数为无限值的集合称为无限集。

幂集是指一个集合的所有子集所组成的集合。

例如，对于集合A={1,2}，它的幂集为{{},{1},{2},{1,2}}。

幂集的基数等于原集合的基数的2的幂次方。

四、关系的类型与性质在离散数学中，关系可以分为几种不同的类型。

常见的关系类型包括等价关系、序关系和函数关系。

等价关系是指满足自反性、对称性和传递性的关系。

序关系是指满足自反性、反对称性和传递性的关系。

函数关系是指每个定义域中的元素都有唯一对应的值域中的元素的关系。

数学下册综合算式专项练习题离散数学中的集合与关系的应用在离散数学中，集合与关系是非常重要的概念，它们在数学下册综合算式中也有着广泛的应用。

本文将通过综合算式专项练习题的方式，探讨离散数学中集合与关系的应用。

题目一：集合的运算与应用1.已知集合A={1,2,3,4,5}，B={3,4,5,6}，C={3,5}，求(A∪B)-(A∩C)的结果并列出其中的元素。

解析：首先求A∩C，即集合A与C的共有元素，根据给定的集合数据可以得到，A∩C={3,5}。

然后求出A∪B，即集合A与B的并集，根据给定的集合数据可以得到，A∪B={1,2,3,4,5,6}。

最后根据集合运算法则(A∪B)-(A∩C)，将A∪B中与A∩C相同的元素去掉，得到结果集合{1,2,4,6}。

题目二：关系的性质与应用2.已知集合A={0,1,2,3,4}，定义二元关系R为{(x,y)|x，y∈A,x<y}，求R的基数与R的逆关系。

解析：首先根据定义的关系R={(x,y)|x，y∈A,x<y}，我们可以得到R中的元素有{(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}，共有10个元素，即R的基数为10。

然后我们来求R的逆关系R^-1。

根据R的定义可以得知，若(x,y)∈R，则(y,x)∈R^-1。

因此，我们可以将R中的每个元素的x和y对调得到R^-1中的元素。

经过对调，R^-1中的元素为{(1,0),(2,0),(3,0),(4,0),(2,1),(3,1),(4,1),(3,2),(4,2),(4,3)}。

综上所述，集合与关系在数学下册综合算式中有着重要的应用。

通过对集合的运算和关系的性质进行练习，我们能够更好地理解和应用离散数学中的集合与关系的概念。

这些知识不仅在数学中有着应用价值，也能够帮助我们解决实际生活中的问题。

离散数学中的集合与关系理论离散数学是数学中的一门重要分支，主要研究离散的数值和结构。

在离散数学中，集合与关系理论是两个基础且关键的概念。

本文将对离散数学中的集合与关系理论进行探讨。

一、集合在离散数学中，集合是由元素组成的整体。

集合的表示可以使用不同的方式，如枚举法、描述法和扩展法。

其中，枚举法通过罗列元素的方式来表示集合。

例如，集合A = {1, 2, 3, 4}就是使用了枚举法表示的集合。

集合的运算是集合理论中的重要内容。

常见的集合运算有并集、交集、差集和补集。

并集表示两个集合中的所有元素的组合，交集表示两个集合中共有的元素，差集表示一个集合减去另一个集合中的元素，补集表示一个集合相对于全集中没有的元素。

集合的关系也是集合理论中的重要内容。

常见的集合关系有相等关系、包含关系和子集关系。

相等关系指的是两个集合具有相同的元素，包含关系指的是一个集合包含另一个集合中的所有元素，子集关系指的是一个集合包含于另一个集合。

二、关系关系是研究离散数学中元素之间联系的一种数学工具。

在离散数学中，关系可以用一个有序对的集合表示。

例如，关系R = {(1, 2), (2, 3),(3, 4)}表示了元素1与2之间、元素2与3之间、元素3与4之间的联系。

关系可以是自反的、对称的、传递的等。

自反关系指的是每个元素与自己之间有联系，对称关系指的是如果元素a与元素b之间有联系，则元素b与元素a之间也有联系，传递关系指的是如果元素a与元素b 之间有联系，元素b与元素c之间有联系，则元素a与元素c之间也有联系。

离散数学中的关系还可以进行合成和关系的闭包运算。

关系的合成指的是将两个关系进行组合，得到一个新的关系。

关系的闭包指的是将一个关系进行扩展，使得它满足某些性质。

集合和关系是离散数学中的两个重要概念，它们在离散数学中起着重要的作用。

集合可以用来整理和分类元素，关系可以用来描述元素之间的联系。

它们的研究对于理解和解决实际问题具有重要意义。

离散数学知识点归纳一、集合论。

1. 集合的基本概念。

- 集合是由一些确定的、彼此不同的对象组成的整体。

这些对象称为集合的元素。

例如，A = {1,2,3}，其中1、2、3是集合A的元素。

- 集合的表示方法有列举法（如上述A的表示）和描述法（如B={xx是偶数且x < 10}）。

2. 集合间的关系。

- 子集：如果集合A的所有元素都是集合B的元素，则称A是B的子集，记作A⊆ B。

例如，{1,2}⊆{1,2,3}。

- 相等：如果A⊆ B且B⊆ A，则A = B。

- 真子集：如果A⊆ B且A≠ B，则A是B的真子集，记作A⊂ B。

3. 集合的运算。

- 并集：A∪ B={xx∈ A或x∈ B}。

例如，A = {1,2}，B={2,3}，则A∪B={1,2,3}。

- 交集：A∩ B = {xx∈ A且x∈ B}。

对于上述A和B，A∩ B={2}。

- 补集：设全集为U，集合A相对于U的补集¯A=U - A={xx∈ U且x∉ A}。

二、关系。

1. 关系的定义。

- 设A、B是两个集合，A× B的子集R称为从A到B的关系。

当A = B时，R称为A上的关系。

例如，A={1,2}，B = {3,4}，R={(1,3),(2,4)}是从A到B的关系。

2. 关系的表示。

- 关系矩阵：设A={a_1,a_2,·s,a_m}，B={b_1,b_2,·s,b_n}，R是从A到B的关系，则R的关系矩阵M_R=(r_ij)，其中r_ij=<=ft{begin{matrix}1,(a_i,b_j)∈ R0,(a_i,b_j)∉ Rend{matrix}right.。

- 关系图：对于集合A上的关系R，用节点表示A中的元素，若(a,b)∈ R，则用有向边从a指向b。

3. 关系的性质。

- 自反性：对于集合A上的关系R，如果对任意a∈ A，都有(a,a)∈ R，则R 是自反的。

例如，A={1,2,3}，R = {(1,1),(2,2),(3,3)}是自反关系。