离散数学相容关系

离散数学关系
基本要求和重难点:
• 基本要求
了解序偶与笛卡尔积,掌握关系得性质和运算,重 点掌握关系闭包运算得求法和偏序关系及哈斯图 得正确画法。
• 重难点
关系5种性质得判断,关系得闭包运算和偏序关系 得性质及特殊元素得判断。
引言
日常生活中,大家熟知一些常见关系, 例:家庭集合,有父子关系、夫妻关系等。 全校同学作为一个集合,有同班关系,同组关系。 在计算机科学中,在计算机逻辑设计中,应用了等 价关系,相容关系。 在编译原理、关系数据库、数据结构、数学中也有 关系。
例题
返回第5、3节目录
五、传递性例题
例: A={1,2,3,4} R={<1,4>,<4,3>,<1,3>,<3,1>,<1,2>,<3,2>,<2,3>, <4,2>,<1,1>,<3,3>} R不就是传递得
返回传递性
返回第5、3节目录
六、举 例
自反性 反自反性 对称性 反对称性 传递性
任何集合上得
返回总目录
一、自反性
自反性
定义: 若xA,均有xRx,那么称R就是自反得。
A上关系R就是自反得x(xA xRx)
在关系矩阵中,反映为主对角线元素均为1 在关系图中,反映为每结点都有自回路 例1: A＝{1,2,3},R={<1,1>,<2,2>,<3,3>,<1,2>}
1 23
例2:“＝”关系和“≤”关系就是自反得吗？
S={<4,2>,<2,5>,<3,1>,<1,3>}

2021/4/1
第4章 关系
定义4.7 A×B的任意子集R称为A到B的二元关系。特 别当A＝B时，称R为A上的二元关系。其中称为空关系， A×B称为全关系。
关系可以推广到n元关系，我们主要讨论二元关系。 在计算机领域中，关系的概念也是到处存在的。如数据 结构中的线性关系和非线性关系，数据库中的表关系等。 例如，若A＝{1，2，3，4，5}，B＝{a，b，c}，则R＝ {<1，a>，<1，b>，<2，b>，<3，a>}是A到B的关系，S＝{<a， 2>，<c，4>，<c，5>}是B到A的关系。
第4章 关系
4.2 关系及其表示
4.2.1 关系
世界上存在着各种各样的关系。人和人之间有“同志”关 系、“师生”关系、“上下级”关系；两个数之间有“大于” 关系、“等于”关系、“小于”关系；两个变量之间有“函数” 关系；程序之间有“调用”关系等。所以，对关系进行深刻的 研究，对数学和计算机都有很大的用处。
定义4.6 令R为二元关系，DR＝{x|y(xRy)}和RR＝ {y|x(xRy)}分别称为R的定义域(或前域)和值域。关系R的域记 为FR＝DR∪RR。
例如，设H＝{<1，2>，<1，4>，<2，4>，<3，4>}是一个 二元关系，则DH＝{1，2，3}，RH＝{2，4}，FR＝{1，2，3，4}。
2021/4/1
第4章 关系
定义4.8 若IA是A上的二元关系，且满足IA＝{<x， x>|x∈A}，则称IA为A上的恒等关系。
定理4.5 若R和S是集合A到B的两个二元关系，则： (1)DR∪S＝DR∪DS。 (2)DR∩SDR∩DS。 (3)DR－DSDR－S。 (4)RR∪S＝RR∪RS。 (5)RR∩SRR∩RS。 (6)RR－RSRR－S。

离散数学笔记第一章命题逻辑合取析取定义 1. 否定：当某个命题为真时.其否定为假.当某个命题为假时.其否定为真定义 1. 条件联结词.表示“如果……那么……”形式的语句定义 1. 双条件联结词.表示“当且仅当”形式的语句定义合式公式(1)单个命题变元、命题常元为合式公式.称为原子公式。

(2)若某个字符串 A 是合式公式.则⌝A、(A)也是合式公式。

(3)若 A、B 是合式公式.则 A ∧B、A∨B、A→ B、A↔B 是合式公式。

(4)有限次使用(2)~(3)形成的字符串均为合式公式。

等值式析取范式与合取范式将一个普通公式转换为范式的基本步骤推理定义 设 A 与 C 是两个命题公式. 若 A → C 为永真式、 重言式.则称 C 是 A 的有 效结论.或称 A 可以逻辑推出 C.记为 A => C 。

（用等值演算或真值表）第二章 谓词逻辑、基本概念∀：全称量词 ∃：存在量词一般情况下. 如果个体变元的取值范围不做任何限制即为全总个体域时. 带 “全称量词”的谓词公式形如"∀x(H(x)→B(x)).即量词的后面为条件式.带“存在量词”的谓词公式形如∃x(H(x)∨WL(x)).即量词的后面为合取式 例题R(x)表示对象 x 是兔子.T(x)表示对象 x 是乌龟. H(x,y)表示 x 比 y 跑得快.L(x,y)表示x 与 y 一样快.则兔子比乌龟跑得快表示为： ∀x ∀y(R(x)∧T(y)→H(x,y))有的兔子比所有的乌龟跑得快表示为：∃x ∀y(R(x)∧T(y)→H(x,y))、谓词公式及其解释定义 、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示22y x 的 f(x,y))、 谓词常元(如表示人类的 H(x))。

定义 、逻辑符号：个体变元、量词(∀∃)、联结词(﹁∨∧→↔)、逗号、括号。

定义 、项的定义：个体常元、变元及其函数式的表达式称为项(item)。

则r是相容关系
2004-11-15
离散数学-lecture15
1
3-11 相容关系
令x1=cat，x2=teacher， x3=cold， x4=desk， x5=knife， x6=by。 R的关系图及关系矩阵
2004-11-15
离散数学-lecture15
2
3-11 相容关系
• 由于相容关系是自反和对称的，因此其关系矩阵的对角线元素都 是1，且矩阵是对称的。为此可将矩阵用梯形表示。
2004相容关系
定理3-11.3 集合A上相容关系r与完全覆盖Cr(A)存在一一对应。 先证由集合A上的相容关系唯一确定完全覆盖Cr(A)。 反证法：假设集合A上的相容关系r对应两个不同的完全覆盖Cr和Cr’，设 Cr={C1,C2,…,Cm}，Cr’={C1’,C2’,…,Cn’}，假设有Ck∈Cr，因为Ck是最大相容 类，所以Ck对应相容关系图中的一个完全多边形的顶点或不是完全多边形 的两个结点的连线或是一个孤立点，又Cr’是最大相容类的集合，因此一 上三种情况对应的结点集合必定在Cr’中，所以Ck必在Cr’中。因此Cr=Cr’。 再证 已知完全覆盖Cr(A)能唯一确定相容关系r。 因为Cr(A)是A的覆盖，利用定理3-11.2可得到一个相容关系r，假设从Cr(A) 还可以得到另外一个不同于r的相容关系r’，那么就有<x,y>∈r’但 <x,y>r，即<y,x>r，反映在相容关系图上，就是r’与r的相容关系图不 同，即r’与r对应的完全覆盖也不同，与r’和r对应的同一完全覆盖相矛盾。
2004-11-15
离散数学-lecture15
18
3-12 序关系
对于给定偏序集<A, ≤>，它的盖住关系是唯一的，所以可用盖住的 性质画出偏序集合图，或称哈斯图，其作图规则为： (1) 用小圆圈代表元素 (2) 如果x≤y且x≠y，则将代表y的小圆圈画在代表x 的小圆圈之上。 (3) 如果<x,y>∈COV A，则在x与y之间用直线连接。 根据这个作图规则，例题3中偏序集的哈斯图如右 图所示。