离散数学 二元关系与运算

13
Discrete Mathematics 2）反之，在非空集合A上给定一个划分π，则可将A 分割成若干个划分块。 根据以下条件定义A上的二元关系R，即对任何元 素x,y∈A，如果x和y在同一划分块中，则xRy。显 然，R是A上的等价关系，称为由划分π所诱导的 等价关系，并且该等价关系的商集就等于π 。 结论 的划分是一一对应的。 集合A上的等价关系与集合crete Mathematics 在非空集合A上给定一个划分 在非空集合 上给定一个划分π={A1,A2,…,Am}， 上给定一个划分 ， 找出由π所唯一确定的 所唯一确定的A上的等价关系的方法如 找出由 所唯一确定的 上的等价关系的方法如 下： 把划分π的每一块 都拿出来， 把划分 的每一块Ai都拿出来，并且作其笛卡 的每一块 尔积A 尔积 i× Ai(i=1,2,..,m) ，然后求这些笛卡尔积的 并集，即为所求， 并集，即为所求，即
1
Discrete Mathematics 例 设A={1,2,3,4,5,6,7,8}， ， R={<x,y>|x,y∈A∧x =y(mod3)}，其中 =y(mod3) ∈ ∧ ，其中x 的含义是x和 分别除以 后的余数相等， 分别除以3后的余数相等 的含义是 和y分别除以 后的余数相等，即x-y可以 整除。 上的等价关系， 被3整除。不难验证 为A上的等价关系，它的关系 整除 不难验证R为 上的等价关系 图如下图所示： 下图所示 图如下图所示：
Discrete Mathematics
Discrete Mathematics 3、商集 、 为非空集合A上的等价关系， 定义 设R为非空集合 上的等价关系，以R的不相 为非空集合 上的等价关系 的不相 交的等价类为元素的集合叫做A在 下的商集， 下的商集 交的等价类为元素的集合叫做 在R下的商集，记 作A/R，即 ， A/R={[a]R |a∈A} ∈ 显然， 显然，在例1中，A在R下的商集是 中 在 下的商集是 A/R ={{1,4,7},{2,5,8},{3,6}}。 。

离 散 数 学
9
关系图举例
• 例：设A={1,2,3,4,5} , R={<1,1>,<1,2>,<3,2>,<1,4>,<5,4>,<5,1>}, 则，R的关系图GR如下：
1
5 4 3
离 散 数 学
10
2
下面关系图有什么性质
a b c a b d c b a c
(a)
自反,反对称, 传递
(b)
离 散 数 学
15
逆关系
定义2.2.3 设R是A到B的二元关系，令： R–1={<y,x>|<x,y>∈R}，称为R的逆关系。 显然，(R–1)–1=R 。 定理2.2.3 设R是A到B的二元关系， S是B到C的 二元关系，则：(R • S) –1 = S–1 • R–1 证明：∵任意<x,z>∈(R • S) –1 <z,x>∈R • S 存在y∈B，使得<z, y>∈R且 <y, x>∈S <y,z>∈ R–1且<x,y>∈ S–1 <x,z>∈S–1 • R-1
离 散 数 学
8
关系的图的表示
• 一个在有穷集合A上的二元关系R可以用 一个有向图GR表示。令| A | = n ，〈 i, j 〉 表示A中第i个元素和第j个元素的序偶， GR=〈V，E〉， | V | = n ，V中的每个结 点分别表示A中的一个元素。ninj E， 即从结点i到结点j有一条有向边，当且仅 当〈 i，j 〉 R。
2
2
离 散 数 学
2
二元关系几个性质的定义
定义2.1.2 设R是定义在集合A上的二元关系：

离散数学部分概念和公式总结命题：称能判断真假的陈述句为命题。

命题公式：若在复合命题中，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是一个二元关系。

离散数学部分概念和公式总结命题：称能判断真假的陈述句为命题。

命题公式：若在复合命题中，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。

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

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

前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Q k…x k B，称A为前束范式。

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

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

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