离散数学(3.6关系性质)

离散数学关系离散数学关系是一种在有限集上定义的函数，用来描述两个集合之间的关系。

它是抽象数学中最基本的元素，它描述由一列实例构成的集合之间的关系。

离散数学关系有三种：一对一映射(one-to-one mapping)、可枚举映射(enumerable mapping)和量级(order)关系。

1、一对一映射：一对一映射是每个元素都有唯一的映射关系，一个域元素只能映射到一个定义域元素，而且每个定义域元素也只被一个域元素映射。

2、可枚举映射：可枚举映射是指有多个域元素可以映射到一个定义域元素，反之亦然，定义域元素也可以映射到多个域元素，但不一定要求每一个域元素都被映射。

3、量级(order)关系：量级关系是一种非抽象的关系，它可以用来描述元素之间的关系，但不能用唯一的映射关系表示。

量级关系表示一组元素之间的大小或者其他特征的排列顺序，比如“比”，“等于”，“交换”等等，它们可以表示不止一种关系。

二、关系的性质1、可满足性：可满足性是指关系的存在与否与域元素具体的值之间的关系。

可满足关系的存在可以通过满足一定的条件来进行检查，不满足的情况下就会说明这个关系不存在。

2、唯一性：唯一性是指关系的定义域与域元素之间的唯一映射关系。

唯一性可以用来确定定义域元素与域元素之间的唯一映射关系，它不能够产生重复的映射关系。

3、可枚举性：可枚举性是一种可以将定义域与域元素之间的映射关系一一列出来的性质。

可枚举性允许定义域元素有多个域元素与之映射，但它不一定满足唯一性。

4、可组合性：可组合性是一种可以将两个定义域之间的关系组合起来的性质。

可组合性可以将多个关系组合为一个或多个新的关系，从而可以更好的表达更多更复杂的关系。

三、应用1、在离散数学中，离散数学关系经常用来描述中间结果或概念之间的关系。

2、在计算机科学中，离散数学关系常常作为数据结构的基础，用来表示复杂的逻辑结构。

3、在数据库系统中，离散数学关系的应用非常广泛，用来表示不同表之间的关系。

第一章命题逻辑1.1 命题及其表示方法1.2 联结词1.3 命题公式与翻译1.4 真值表与等价公式1.5 重言式与蕴含式1.6 其它联结词1.7 对偶与范式1.8 推理理论1.1 命题及其表示方法命题：具有确定真值的陈述句命题的类型（原子命题和复合命题）命题语句的形式（陈述句）命题的表示（一个命题标识符（比如P）表示确定的命题）1.2 联结词1. 否定⌝2.合取∧（TT T）3. 析取∨（FF F）4. 条件→(TF F)5. 双条件↔(同T异F)1.3 命题公式与翻译命题公式●所谓命题的符号化就是把一个用文字叙述的句子相应地写成由命题标识符、联结词和括号表示的合式公式。

●符号化应该注意下列事项:•①确定给定句子是否为命题。

•②句子中连词是否为命题联结词。

•③要正确地表示原子命题和适当选择命题联结词。

命题符号化的重要性●命题符号化是很重要的，一定要掌握好，在命题推理中最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。

1.4 真值表与等价公式真值表的构造方法1) 找出公式中所含的全体命题变元P1, P2, …, Pn, (若无下角标就按字典顺序排列), 列出2n个赋值. 赋值从00…0开始, 然后按二进制加法依次写出各赋值, 直到11…1为止.(2) 按从低到高的顺序写出公式的各个层次.(3) 对应各个赋值计算出各层次的真值, 直到最后计算出公式的真值.等价公式等价式的判别方法•真值表法•等价演算法基本等价式(1)对合律（双重否定）：⌝⌝P⇔P(2)幂等律：P∧P⇔P，P∨P⇔P(3)结合律：(P∧Q)∧R⇔P∧(Q∧R)，(P∨Q)∨R⇔P∨(Q∨R)(4)交换律：P∧Q⇔Q∧P，P∨Q⇔Q∨P(5)分配律：P∧(Q∨R)⇔(P∧Q)∨(P∧R)，P∨(Q∧R)⇔(P∨Q)∧(P∨R)(6)德·摩根律：⌝ (P∧Q) ⌝⇔P∨⌝Q，⌝ (P∨Q) ⌝⇔P∧⌝Q(7)吸收律：P∧(P∨Q)⇔P，P∨(P∧Q)⇔P(8)同一律：P∧T⇔P，P∨F⇔P(9)零律：P∧F⇔F，P∨T⇔T(10)否定律：P∧⌝P⇔F，P∨⌝P⇔T(11) 条件式转化律：P→Q⌝⇔P∨Q，P→Q⌝⇔Q→⌝P(12) 双条件式转化律：P↔Q ⇔(P→Q)∧(Q→P) ⇔(P∧Q)∨(⌝P∧⌝Q)⌝ (P↔Q) ⇔P⌝↔Q ⌝⇔P↔Q(13) 输出律(CP规则)：P→(Q→R) ⇔(P∧Q)→R1.5 重言式与蕴含式●定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为真，则称该命题公式为重言式或永真公式。

离散数学关系与函数的定义及性质离散数学是数学的一个分支，主要研究离散的对象和结构，与连续的对象和结构不同。

在离散数学中，关系和函数是两个基本的概念，它们在数学和计算机科学中具有广泛的应用。

本文将介绍关系和函数的定义以及它们的性质。

一、关系的定义与性质关系是一个数学概念，用于描述两个数或多个数之间的相互关系。

在离散数学中，关系可以用集合表示。

设A和B是两个集合，R是从A到B的关系，记作R：A→B。

如果元素a∈A与元素b∈B满足某种规定的条件，则称a与b有该关系。

例如，若X表示所有学生的集合，Y表示所有课程的集合，而R表示学生与所选课程之间的关系，则若学生x选择了课程y，则(x, y)∈R。

在关系的定义中，我们可以根据关系的性质进一步划分不同类型的关系。

常见的关系类型包括：1. 自反性：对于集合中的每个元素a，(a, a)∈R，即a与自身相关。

2. 反自反性：对于集合中的每个元素a，(a, a)∉R，即a与自身无关。

3. 对称性：对于任意a和b，若(a, b)∈R，则(b, a)∈R，即a与b有关时，b与a也有关。

4. 反对称性：对于任意a和b，若(a, b)∈R且(b, a)∈R，则a=b，即a与b有关时，a=b。

5. 传递性：对于任意a、b和c，若(a, b)∈R且(b, c)∈R，则(a,c)∈R，即a与b有关，b与c有关时，a与c也有关。

关系的定义和性质在离散数学中有广泛的应用，例如在图论中，关系可以用于描述顶点之间的连接关系，而关系的性质可以帮助我们分析图的特定结构。

二、函数的定义与性质函数是一种特殊类型的关系，它在数学和计算机科学中扮演着重要的角色。

函数是一种将输入集合中的每个元素映射到输出集合中唯一元素的关系。

假设A和B是两个集合，函数f:A→B表示从A到B的函数，如果对于任意a∈A，存在唯一的b∈B使得(a, b)∈f，则称f为一个函数，记作f(a)=b。

函数的性质同样对于离散数学和计算机科学具有重要意义。

离散数学中关系性质的判定方法摘要：关系是离散数学中的基本概念，而关系的性质是关系的闭包、等价关系、半序关系的基础，本文给出了关系四种性质的判定方法。

关键词：离散数学关系性质判定关系的概念是离散数学中关系的基础，又是集合概念的应用，因此应该真正理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。

而关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、半序关系的基础。

对于四种性质（自反性、对称性、反对称性、传递性），有如下方法加以判定：一、依据其定义1.自反性：设R是集合A上的二元关系，如果对于每一个a∈A，若有（a，a）∈R，即aRa，则称R在集合A上具有自反性。

2.对称性：设R是集合A上的二元关系，对于任意的a、b∈A，若有（a，b）∈R，就有（b，a）∈R，则称R在集合A上具有对称性。

3.反对称性：设R是集合A上的二元关系，对于任意的a、b∈A，若（a，b）∈R且（b，a）∈R时，必有a=b，则称R在集合A上具有反对称性。

4.传递性：设R是集合A上的二元关系，对于任意的a、b、c∈R，若（a，b）∈R，且（b，c）∈R，就有（a，c）∈R，则称关系R在A上具有传递性。

二、依据关系矩阵和关系图的关系1.关系R具有自反性，当且仅当在关系矩阵中，主对角线上元素全为1；或者在关系图中每个结点上都有一条自回路。

2.若关系R具有对称性，当且仅当关系矩阵是对称矩阵；或者在关系图中，若两个结点间存在有向弧，必是成对的。

3.若关系R具有反对称性，当且仅当关系矩阵中以主对角线为对称轴的对称元素不能同时为1（可以同时为0），而主对角线上的元素是1或者是0；在关系图上，若两个结点间存在有向弧，不可能成对出现，结点可以有自回路。

4.若关系R具有传递性，关系矩阵没有明显特征。

关系图的特点是：任意两个结点a、b间若能通过一条以上的弧间接连结起来，则必有一条直接从a到b的弧。

作为它的一种特殊情况，若两点间各有一条直接从a到b和由b到a的弧连接时，则在这两个结点a、b上必然各有一条自回路。

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

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)}是自反关系。

离散数学关系离散数学中，关系是一个重要的概念。

关系是指一个元素集合之间的对应关系。

这个对应关系可以用图形表示。

让我们来一步步地探讨什么是关系和关系图。

首先，我们要了解什么是元素和元素集合。

元素是一组有意义的数据，它可以是数字、字母、单词等。

元素集合是由多个元素组成的集合，比如所有自然数可以形成一个元素集合。

接着，我们可以定义关系。

关系就是两个元素集合之间的对应关系。

这个对应关系可以用有序对(x,y)表示。

如果(x,y)属于一个关系，那么我们可以说x和y之间存在这个关系。

例如，我们可以定义一个关系R为{(1,2),(2,4),(3,6)}。

这个关系表示1对2，2对4，3对6。

我们可以从这个关系中得到很多信息，比如1对应2，2对应4，3对应6。

这告诉我们一些元素之间的关系。

然而，我们很难从一个关系里面得到全部元素的对应关系，因此我们需要使用关系图来更好地理解关系的意义。

关系图是一种用点和箭头表示关系的图形。

在关系图中，每个点代表一个元素，每个射线代表一个关系。

我们可以通过观察图形来更好地理解两个元素之间的关系。

例如，我们可以用以下图形表示关系R：在这个关系图中，我们可以看到每个点代表了一个元素，每个射线表示了一个关系。

箭头的方向表示了关系的方向。

这个关系图清晰地表达出了每个元素之间的对应关系，让我们更容易地理解这个关系。

除了上述的基本关系之外，离散数学还有很多其他类型的关系，比如等价关系、偏序关系、偏序关系等等。

这些关系的定义和性质都有所不同。

总之，在离散数学中，关系是一个非常重要的概念，它帮助我们理解元素之间的联系和关系，是学习离散数学的基础。

通过理解和掌握关系，我们可以更好地解决许多离散数学中的难题。