关于【离散数学第二版集合知识梳理】，今天涌涌小编给您分享一下，如果对您有所帮助别忘了关注本站哦。

1、离散数学第二版集合知识梳理：离散数学部分概念和公式总结(考试专用)

命题：称能判断真假的陈述句为命题。

命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。

命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。若指定的一组值使A的值为真，则称成真赋值。

真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。

命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。

（2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。

（3）若A至少存在一组赋值是成真赋值，则A是可满足式。

主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。

主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。

命题的等值式：设A、B为两命题公式，若等价式A↔B是重言式，则称A与B是等值的，记作A<=>B。

约束变元和自由变元：在合式公式"xA和 $xA中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。

一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A↔B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。

前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Qk…xkB，称A为前束范式。

集合的基本运算：并、 交、差、相对补和对称差运算。

笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。

二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。

特殊关系：（1）、空关系：Φ（2）全域关系：EA={<x, y> | x∈A ∧ y∈A }= A×A

（3）恒等关系：IA={<x, x> | x∈A}

（4）小于等于关系：LA={<x, y>| x, y∈A∧x≤y∈A },A Í R

（5）整除关系： RÍ ={<x, y>| x，y∈ψ ∧ x Í y} ,ψ是集合族

二元关系的运算：设R是二元关系，

（1）R中所有有序对的第一元素构成的集合称为R的定义域domR= { x |$y（<x , y>∈R）}

（2）R中所有有序对的第二元素构成的集合称为R的值域ranR= {y|$x（<x,y>∈R）}

（3）R的定义域和值域的并集称为R的域fldR= domR∪ranR

二元关系的性质：自反性，反自反性，对称性，反对称性，传递性。

等价关系：如果集合A上的二元关系R是自反的，对称的和传递的，那么称R是等价关系。设R是A上的等价关系，x , y是A的任意元素，记作x～y。

等价类：设R是A上的等价关系，对任意的"x∈A，令[x]R={y|y∈A∧x R y }，称[x]R为x关于R的等价类。

偏序关系：设R是集合A上的二元关系，如果R是自反的，反对称的和传递的，那么称R为A上的偏序，记作≤；称序偶<A ,R >为偏序集合。

函数的性质：设f:A®B，

（1）若ranf= B，则称f是满射（到上）的。

（2）若 "yÎ ranf都存在唯一的xÎA使得f(x)=y,则称f是单射（— —）的。

（3）若f既是满射又是单射的，则称f是双射（— —到上）的。

无向图：是一个有序的二元组<V,E>，记作G，其中：

(1)V¹Ф称为顶点集，其元素称为顶点或结点。

(2)E为边集，它是无序积V&V的多重子集，其元素称为无向边，简称边。

有向图：是一个有序的二元组<V,E>,记作D,其中

(1)V同无向图。 (2) E为边集，它是笛卡尔积V´V的多重子集，其元素称为有向边。

设G=<V,E>是一个无向图或有向图。

有限图：若V,E是有限集，则称G为有限图。

n阶图：若|V|=n，称G为n阶图。

零图：若|E|=0，称G为零图,当|V|=1时，称G为平凡图。

基图：将有向图变为无向图得到的新图，称为有向图的基图。

图的同构：在用图形表示图时，由于顶点的位置不同，边的形状不同，同一个事物之间的关系可以用不同的图表示，这样的图称为图同构。

带权图：在处理有关图的实际问题时，往往有值的存在，一般这个值成为权值，带权值的图称为带权图或赋权图。

连通图：若无向图是平凡图，或图中任意两个顶点都是连通的，则称G是连通图。否则称为非连通图。设D是一个有向图，如果D的基图是连通图，则称D是弱连通图，若D中任意两个顶点至少一个可达另一个，则称D是单向连通图。若D中任意两个顶点是相互可达的，则称D是强连通图。

欧拉图：通过图中所有边一次且仅一次并且通过所有定点的通路（回路），称为欧拉通路（回路）。存在欧拉回路的图称为欧拉图。

哈密顿图：经过图中每个顶点一次且仅一次的通路（回路），称为哈密顿通路（回路），存在哈密顿回路的图称为哈密顿图。

平面图：一个图G如果能以这样的方式画在平面上：出定点处外没有变交叉出现，则称G为平面图。画出的没有边交叉出现的图称为G的一个平面嵌入。

二部图：若无向图G=〈V,E〉的顶点集合V可以划分成两个子集V1和V2（V1∩V2 =f），使G中的任何一条边的两个端点分别属于V1和V2，则称G为二部图（偶图）。二部图可记为G= < V1,V2 , E>,V1和V2称为互补顶点子集。

树的定义：连通无回路的无向图称为无向树，简称树，常用T表示树。平凡图称为平凡树。若无向图G至少有两个连通分支，每个连通都是树，则称G为森林。在无向图中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支点。

树的性质：性质1、设G=<V,E>是n阶m条边的无向图，则下面各命题是等价的：

（1）G是树（2）G中任意两个顶点之间存在唯一的路径（3）G中无回路且m=n-1.

（4）G是连通的且m=n-1.（5）G是连通的且G中任何边均为桥。（6）G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。

性质2、设T是n阶非平凡的无向树，则T中至少有两片树叶。

证：设T有x片树叶，由握手定理及性质1可知，2(n-1)=∑d(vi)≥x+2(n-x)由上式解出x≥2.

最小生成树：设T是无向图G的子图并且为树，则称T为G的树。若T是G的树且为生成子图，则称T是G的生成树。设T是G的生成树。e∈E(G)，若e∈E(T)，则称e为T的树枝，否则称e为T的弦。并称导出子图G[E(G)-E(T)]为T的余树，记作T。

最优二元树：设2叉树T有t片树叶v1,v2,…,vt，权分别为w1,w2,…,wt，称W(t)=wil(vi)为T的权，其中l(vi)是vi的层数。在所有有t片树叶，带权w1,w2,…,wt的2叉树中，权最小的2叉树称为最优2叉树。

最佳前缀码：利用Huffman算法求最优2叉树，由最优2叉树产生的前缀码称为最佳前缀码，用最佳前缀码传输对应的各符号能使传输的二进制数位最省。

蕴含式推理

等值公式表

集合恒等式：P61

幂等律：A∪A=A ；A∩A=A

结合律：(A∪B)∪C=A∪(B∪C) ；(A∩B)∩C=A∩(B∩C)

交换律：A∪B=B∪A ；A∩B=B∩A

分配律：A∪(B∩C)=(A∪B)∩(A∪C) ；A∩(B∪C)=(A∩B)∪(A∩C)

同一律：A∪f =A ；A∩E=A

零 律：A∪E =A ；A∩f=f

排中律：A∪~A=E

矛盾律：A∩~A =ff

吸收律：A∩(A∪B)=A；A∪ (A∩B)=A

德摩根定律：A-(B∪C)=(A-B)∩(A-C)；A-(B∩C)=(A-B)∪(A-C)

~(B∪C)= ~B∩~C；~(B∩C)= ~B∪~C；~f=E；~E=f

双重否定律：~（~A)=A

二元关系的运算：

设F,G,H是任意的关系，

（1）（F-¹) -¹= F（2）dom(F-¹)=ranF；ran (F-¹)=domF

（3）（ F ◦ G ) ◦ H =　F ◦(G ◦ H ) （4）（ F ◦ G ) - ¹ =G -¹ ◦ F -¹

设R是A上的关系（幂运算）

（1）Rº= {<x，x>| x∈A} （2）R^n = R^(n-1) ◦ R，n≥1 （3）R◦ Rº = Rº ◦R = R

图的矩阵表示：

（1）无向图的关联矩阵：设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}，令mij为顶点vi与边的关联次数，则称（mij ）n´ m为G的关联矩阵。记为M(G)。

（2）有向图的关联矩阵：设无向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}，

1,vi是ej的始点

mij=0,vi与ej不关联

-1，vi是ej的终点

则称（mij ）n´ m为D的关联矩阵。记为M(D) 。

2、离散数学第二版集合知识梳理，离散数学1.21.3集合与元素

【离散数学】第一章（集合论基础）的小节主要有：

• 1.1集合的定义和表示
• 1.2集合与元素的关系
• 1.3集合与集合之间的关系
• 1.4一些特殊的集合
• 1.5集合的运算

在这篇中我们讨论1.2集合与元素的关系和1.3集合与集合之间的关系。

本两小节包括4个知识点——1.元素的性质，2.集合与元素的关系，3.集合与集合的关系，4.外延性定理。

元素有三个性质，分别是：

• 确定性

一个元素与一个集合，只有两种关系，要么元素属于集合，要么元素不属于集合，没有第三种情况。

就像一个孩子和一位母亲，要么孩子是这位母亲生的，要么不是这位母亲生的，绝不可能两位母亲生出同一个孩子。

例如：对于元素a和集合A={1,2,b}，就是a不属于A，数学表达为a∉A。

对于元素b和集合C={7,9,b}，就是b属于C，数学表达为b∈C。

• 无序性

集合内元素的排列是任意的，怎么排都可以。

与数组内的元素刚好相反，(数组是元素有序的集合)但是一般而言，我们喜欢按规律来排列。

例如：{a,b,c,d}和{b,a,d,c}两个集合是相等的，但是我们一般更喜欢第一种。

• 互异性

同一个集合中有多个相同的元素只算1个，可以舍去多余，保留1个即可。即集合中的元素各不相同

例如：{1,2,2,3,a,a,b}和{1,2,3,a,b}两个集合是相等的，相同元素可以舍去。

集合与元素的关系

• 基数(cardinal number)

一个集合内所有元素的个数称为基数，即为|A|或者cardA，其中A是集合名称

例如：集合B={7,8,9,a,b,c}，那么|B|=6 (cardB=6)。

• 从属关系(∈，∉)

如果一个元素a在集合A内，那么我们称或者a属于A，数学表达为：a∈A

反之，一个元素a不在集合A内，我们称为a不属于A数学表达就是：a∉A

注意：

一个集合的元素可以是另外一个集合。

A={2,6,a}，B={1,3,{2,6,a},c}

此时集合A是集合B的一个元素。

集合与集合的关系

• 包含关系

集合A与集合B，如果集合B中的任一元素都能在集合A中找到，那么我们称为B被A包含，或者说A包含B，数学表示为：B⊆A。

• 子集(subset)

如果B包含A，那么称A是B的子集。

反之，集合A有元素不能在集合B中找到，那么称为A不被B包含，或者B不包含A，数学表示为：A￠B。

假设集合G表示“在广州的人”，集合D表示“在广东的人”，那么每一个“在广州的人”一定都能从“在广东的人”中找到，即为G中任一元素都能在D中找到，所以D包含G(G被D包含)。反之，“在广东的人”不一定在“在广州的人”中，可能去了广东其他地方，所以G不包含D(D不被G包含)。

• 真包含关系

如果集合A包含集合B，但是集合B不包含集合A，那么我们称B被A真包含，或者A真包含B，数学表示为B⊂A。

• 真子集(proper subset)

如果A真包含B，那么称B是A的真子集

还是用集合G表示“在广州的人”，集合D表示“在广东的人”，我们知道D包含G，G不包含D，所以D真包含G。

• 相等关系

如果集合A包含集合B，且集合B包含集合A，那么我们称集合A与集合B相等，数学表达为A=B。

外延性定理

通过集合间的相等关系，我们得到一个结论：两个集合相等的充分必要条件是两个集合相互包含。

外延性定理：两个集合相等，当且仅当他们有相同的元素。

• 证明集合相等

先证：A⊆B(∀x∈A,......,x∈B所以...)再证：B⊆A(∀x∈B,......,x∈A所以...)由上两式知：A=B。

以上便是1.2＆1.3小节集合与元素，集合与集合之间的关系的全部内容。如果对您有帮助的话，可以点一个赞。如有错误，感谢指出。

本小节内容较为简单且基础，下次我们继续介绍1.4＆1.5小节——特殊的集合和集合的计算。

本文关键词：离散数学第二版知识点，离散数学第二版屈婉玲版课后答案第六章集合代数，离散数学第二版集合知识梳理答案，离散数学集合答案，离散数学集合论试题及答案。这就是关于《离散数学第二版集合知识梳理，离散数学部分概念和公式总结》的所有内容，希望对您能有所帮助！更多的知识请继续关注《犇涌向乾》百科知识网站：http://www.029ztxx.com！