当前位置：文档之家 › 二序偶与笛卡儿积(精)

二序偶与笛卡儿积(精)

  • 格式：ppt
  • 大小：199.00 KB
  • 文档页数：9

下载文档原格式

  / 9

合集下载

离散数学-3-4序偶与笛卡儿积

离散数学-3-4序偶与笛卡儿积
笛卡儿积描述事件关系
通过笛卡儿积，可以描述两个或多个事件的独立性、相关性或条件性。例如，如果事件A和事件B相互独立，那么 事件A和事件B的笛卡儿积等于它们各自概率的乘积。
图论中的应用
序偶表示边
在图论中，序偶可以用来表示一条边，其中第一个元素表示起点，第二个元素表示终点。
笛卡儿积描述多重边
通过笛卡儿积，可以描述图中的多重边。如果存在一条从点i到点j的边和一条从点j到点 i的边，那么可以通过笛卡儿积来表示这两条边。
离散数学-3-4序偶与 笛卡儿积
目录
• 序偶的定义与性质 • 笛卡儿积的定义与性质 • 序偶与笛卡儿积的关系 • 序偶与笛卡儿积在离散数学中的应用
01
序偶的定义与性质
序偶的表示方法
01
02
ห้องสมุดไป่ตู้
03
序偶的表示
一个序偶可以表示为有序 对，通常用圆括号括起来， 如 (a, b)，其中a和b是元 素。
序偶的元素
THANKS
感谢观看
02
笛卡儿积的定义与性质
笛卡儿积的表示方法
定义
设 $A_1, A_2, ldots, A_n$ 是任意集合，则 $A_1 times A_2 times ldots times A_n$ 称为集合 $A_1, A_2, ldots, A_n$ 的笛卡儿积。
表示
笛卡儿积可以用大括号 {} 表示，即 $A_1 times A_2 times ldots times A_n = {(a_1, a_2, ldots, a_n) | a_i in A_i, i=1,2,ldots,n}$。
笛卡儿积的应用场景
组合数学
笛卡儿积常用于组合数学中，表示不同元素的排 列和组合。

集合论--第3讲笛卡尔积

集合论--第3讲笛卡尔积

离散数学笛卡尔积第3讲定义3.1有序对由两个元素x和y(允许x=y)按一定的顺序排列成的二元组叫做一个有序对(也称序偶)，记作<x,y>，其中x是它的第一元素，y是它的第二元素。

有序对：1.当x≠y时，<x,y>≠<y,x>。

2.两个有序对相等，即<x,y>＝<u,v>⇔是x＝u且y＝v。

注意：有序对<x,y>与2元集{x,y}的区别。

定义3.2笛卡尔积设A,B为集合，用A中元素为第一元素，B中元素为第二元素构成有序对。

所有这样的有序对组成的集合叫做A和B的笛卡儿积，记作A×B。

符号化表示为：A×B＝{<x,y>|x∈A∧y∈B}。

若<x,y>∈A ×B ，则有x∈A ∧y∈B 。

若<x,y>∉A ×B ，则有x ∉A ∨y ∉B 。

如果A 中有m 个元素,B 中有n 个元素，则A ×B 和B ×A 中都有多少个元素?mn 个1若A,B中有一个空集,则：∅⨯B＝A×∅＝∅2当A≠B且A,B都不是空集时,有：A×B≠B×A即笛卡儿积运算不适合交换律。

3当A,B,C都不是空集时,有：(A×B)×C≠A×(B×C)即笛卡儿积运算不适合结合律。

笛卡儿积运算对∪,∩或-运算满足分配律，即4①A×(B∪C)＝(A×B)∪(A×C)；②(B∪C)×A＝(B×A)∪(C×A)；③A×(B∩C)＝(A×B)∩(A×C)；④(B∩C)×A＝(B×A)∩(C×A)；⑤A×(B-C)＝(A×B)-(A×C)；⑥(B-C)×A＝(B×A)-(C×A)。

31序偶和笛卡儿积

31序偶和笛卡儿积
(A ×B)×C ≠ A × (B ×C) 算法3.1 计算笛卡儿积算法如图3.1所示。
图3.1 笛卡儿积计算算法流程
输入:两个集合 A 和B。 输 出 :2× (nm)矩 阵 C。 思路:对 A 中每一个元素,与 B 中所有元素组成序偶,直到 A 遍历完。C 中 第 一 行 为 序偶第一坐标(A 中元素),C 中第二行为序偶第二坐标(B 中元素)。 定理3.1 设 A、B 和C 为任意三个集合,则有: (1)A×(B∪C)=(A×B)∪(A×C)。 (2)A×(B∩C)=(A×B)∩(A×C)。 (3)(A∪B)×C=(A×C)∪(B×C)。 (4)(A∩B)×C=(A×C)∩(B×C)。 证明: (1)设<x,y>∈A×(B∪C)⇔x∈A∧y∈B∪C ⇔x∈A∧(y∈B∨y∈C)⇔(x∈A∧y∈B)∨(x∈A∧y∈C)
如果|A|表 示 集 合 A 的 个 数。 若|A|=2,则|A3|=23 =8。 一 般 地,若 |A|=m,则 |An|=mn。
习 题 3.1
1.设 A={1,2,3},B={a,b}求:
(1)A×B
(2)B×A (3)B×B (4)2B ×B
2.使 A⊆A×A 成立的集合A 存在吗? 请阐明理由。
H3 = {<f,s>,<f,d>,<m,s>,<m,d>} dom H3 = {f,m} ranH3 = {s,d}
3.恒 等 关 系
48
B ×A = {<a,1>,<a,2>,<b,1>,<b,2>,<c,1>,<c,2>} (A ×B)∩ (B ×A)= ⌀ 显 然 ,我 们 有 : (1)A×B≠B×A。 (2)如 果|A|=m,|B|=n,则|A×B|=|B×A|=|A||B|=mn。 我们约定:若 A=⌀或 B=⌀,则 A×B=⌀。 由笛卡儿积定义可知: (A ×B)×C = {<<x,y>,z>|<x,y>∈ A ×B ∧z ∈ C} {<x,y,z>|x ∈ A ∧y ∈ B ∧z ∈ C} A × (B ×C)= {<x,<y,z>>|x ∈ A ∧ <y,z>∈ B ×C} 由 于 <x,<y,z>>不 是 三 元 组 ,所 以 :

04_序偶及笛卡尔积(精)

04_序偶及笛卡尔积(精)

序偶)，记为<a,b>，称a为第一元素，b
为第二元素；若它们无次序区别，称为二 元无序组(无序偶)，记为(a,b)。
当ab时，有： <a,b> <b,a>
(a,b) = (b,a)
可用序偶表示两个元素之间的关系：
<老王,小王> 老王是小王的父亲
(小李,小张) 小李和小张是同学
定义： 给定两个有序偶<a,b>和<u,v>， 当且仅当a=u且b=v时，有序偶
记< x1 , x2 , x3 > 记< x1 , x2 , x3 , x4 >
注意： < < x1, x2 >, x3 > 是有序 3 元组 < x1, < x2, x3 > > 不是有序 3 元组 < x1 , x2 , x3 > 表示 < < x1, x2 >, x3 >
二、笛卡尔积
定义：给定集合A和B， AB = {<x,y>|xA∧yB}， 称 AB 为A和B的笛卡尔积。
(A∪B)C = (AC)∪(BC)
求证：A(B∩C) = (AB)∩(AC) 分析： 要证明 左式 和 右式 有相同的元素： <x,y>A(B∩C) <x,y>(AB)∩(AC)
证明：
∵ <x,y>A(B∩C)
xA ∧ yB∩C
xA∧(yB∧yC) (xA∧xA)∧(yB∧yC) (xA∧yB)∧(xA∧yC) <x,y>AB ∧ <x,y>AC <x,y>(AB)∩(AC) ∴ A(B∩C)=(AB)∩(AC)

离散数学第四章(第1讲)

离散数学第四章(第1讲)
xy??a??bc?xy??xyx??a??y??bc?xy??xyx??a??y??b??y??c?xy??xyx??a??y??b??x??a??y??c?xy??a??ba??c即a??bca??ba??c例
第四章 二元关系
§1 序偶与笛卡尔积 §2 关系及其表示 §3 关系的性质 §4 关系的运算 §5 等价关系与划分 §6 相容关系与覆盖 §7 偏序关系
§1 序偶与笛卡尔乘积
1 序偶 《定义》由二个具有给定次序的客体所组成的序列
称为序偶。记作〈x，y〉 例：X—Y二维平面上的一个点的坐标〈x，y〉就
是一个序偶。
说明： (1)在序偶中二个元素要有确定的排列次序。 若ab时，则〈a，b〉〈b，a〉 若〈x，y〉=〈a，b〉（x=a y=b） (2) 多重序元： 三元组：〈〈x，y〉，z〉 =〈x，y，z〉 n元组： 〈〈〈〈x1，x2〉，x3〉…〉，xn〉= 〈x1,…,xn〉
ran R={a,b,c,d}
FLD R={1,2,3,4,a,b,c,d}
４．关系和笛卡尔乘积 笛卡尔乘积的任何子集都可以定义一种二元关系。 例：X={1,2,3,4}，Y={1,2}
X Y {1,1 ,1,2 , 2,1 , 2,2 , 3,1 , 3,2 , 4,1 , 4,2 }
S1={<x,y>|x X yYx ≤ y}={<1,1><1,2><2,2>}
2 笛卡尔乘积 《定义》设A，B为二个任意集合，若序偶的第 一个成员（左元素）是A的一个元素，序偶的 第二个成员（右元素）是B的一个元素，则所 有这样的序偶构成的集合称为A和B的笛卡尔乘 积。
记作：A B={〈x，y〉|（xA）（yB）}

4二元关系和函数详解

4二元关系和函数详解
a b 1 c 2 d e 3 f
a与1间存在关系R记aR1 b与1间存在关系R记bR1 c与2间存在关系R记cR2 d与2间存在关系R记dR2 e与3间存在关系R记eR3 e与3间存在关系R记eR3
10/11/2018 10:28 PM
liu qun, northeastern Univ.
10
4.2关系及运算——关系
定理 若 C≠Ø，则 A B （A C B C） （C A C B） 定理 设 A，B，C，D 为四个非空集合， 则 A B C D 的充要条件为 A C，B D。
10/11/2018 10:28 PM liu qun, northeastern Univ. 9
其中、
A 0,1
10/11/2018 10:28 PM
liu qun, northeastern Univ.
8
4.1笛卡儿积与二元关系——笛卡尔积
Sets
集合
定理 设A，B，C为任意三个集合，则有 a) A×（B∪C）=（A×B）∪（A×C）； b) A×（B∩C）=（A×B）∩（A×C）； c)（A∪B）×C=（A×C）∪（B×C）； d)（A∩B）×C=（A×C）∩（B×C）。
例设有六个程序，它们之间有一定的调用关系
R : PRP 1 2, P 3 RP 4, P 4 RP 5, P 5 RP 2, P 2 RP 6, P 3 RP 1
这个关系是集合 p P1 P2 ...P6 上的关系， 有 R P , P , P , P , P , P , P , P , P , P , P , P
A B C 1, a, , 1, a, , 1, b, , 1, b, , 2, a, , 2, a, , 2, b, , 2, b,

3_4_序偶与笛卡儿集[8页]


3.4.2 笛卡儿集
(4) 笛卡儿积对交和并运算满足分配律，即 ① A×(B∪C) = (A×B)∪(A×C) ② (B∪C)×A = (B×A)∪(C×A) ③ A×(B∩C) = (A×B)∩(A×C) ④ (B∩C)×A = (B×A)∩(C×A)
[例3-16] 求证：(1) 若A、B、C、D非空，则A⊆C且B⊆D⇔ A×B⊆ C×D 。 (2) 若C≠ Ø，则A⊆B⇔ A×C⊆ B×C⇔ C×A⊆C×B 。
<x1, x2, ... , xn>= <<x1, x2, ... , xn-1>, xn> 一般情况下，<x1, x2, ... , xn>≠ <x1,< x2, ... , xn-1, xn> 。
沈阳工业大学 牛连强 陈欣 张胜男 niulq@
3.4.2 笛卡儿集
[定义：笛卡儿集] 若A、B是集合，它们构成的笛卡儿积是一个序偶集合，序偶 的第一元素取自于A，而第二个元素取自于B，记作A×B ，即
3.4.2 笛卡儿集
[离散直角坐标系] 对于有限的笛卡儿积，显然有 | A×B |= |A|×|B| 。如果A=B=R， 笛卡儿积R×R 就是平面直角坐标系。故一般的笛卡儿积等同于“离散的直角坐 标系”。 [笛卡儿积的证明方法] 与简单集合类似，笛卡儿积部分的主要问题还是证明集
合包含。不过，笛卡儿积的元素是序偶，故证明A×B⊆ C×D 仍是从定义出发，
沈阳工业大学 牛连强 陈欣 张胜男 niulq@
3.4.1 序偶与元组
[定义：序偶相等] 两个序偶相等：<x, y>=<a, b>，当且仅当x=a 且y=b 。 [例3-14] 若<2x+2, y>=<2y, x-y>，求x和y。 [n元组] n个元素组成的有序集合，记作<x1, x2, ... , xn>，其含义是：

二元关系


不具备任何性质；
8.3 关系的性质
自反性； 传递性； 对称性；
反自反性； 传递性； 反对称性；
8.3 关系的性质
反自反性； 反对称性；
反自反性； 传递性； 反对称性；
8.3 关系的性质
例 设 系， 判断它们的性质。 是定义在 是定义在 上的二元关 上的二元关系，试
自反性； 传递性； 对称性； 反对称性；
的子集中的元素都是序偶，因此，任何序偶的
集合均是一个二元关系。
8.1 二元关系及其表示法 四、二元关系
设有一序偶 对 有关系 有关系 。 ，如果 ，则把这一事实记为 ，则记为 ，读作 对 没 ，读作
8.1 二元关系及其表示法 四、二元关系
称 为
的前域， 为
的后域，
满足
称 为
的定义域， 为
的值域，记为
8.1 二元关系及其表示法 四、二元关系
通常情况下研究的关系是两个集之间元素与元素之间的关 系或者是一个集合内部两个元素之间的关系，称为二元关系， 定义如下： 定义 设 从 到 由于 为两个非空集合， 为 的任何一个子集 所 是 定义的二元关系称为 到 的二元关系，称 的二元关系，简称关系。如 上的二元关系。
（1）用集合方法求 （2）用关系图法求 （3）用关系矩阵求
8.2 关系的运算 二、关系的复合运算
R S A B C 1。 。1 。1 2。 。2 。2 3。 。3 。3 。4 4。 。4 关系矩阵求法为： R。S
A 1。 2。 3。 4。
C 。1 。2 。3 。4
8.2 关系的运算 二、关系的复合运算
定理 设 则
是有限集合，且
， 是
上的二元关系，
8.2 关系的运算 四、关系运算的性质

离散数学：第3讲 序偶与笛卡尔积

任一序偶<x,y>可记作<x,y>R或xR/ y
2020/12/29
序偶与笛卡尔积
25
二元关系举例
例1: R1={<1,2>,<,>,<a,b>} R1是二元关系.
例2: R2={<1,2>,<3,4>,<白菜,小猫>} R2是二元关系.
例3: A={<a,b>,<1,2,3>,a,,1} A不是关系. #
AB={<1,2>},
BA={<2,1>}.
2020/12/29
序偶与笛卡尔积
11
笛卡尔积非结合性
非结合: (AB)C A(BC) (除非 A= B= C=)
反例: A=B=C={1}. (AB)C={<<1,1>,1>}, A(BC)={<1,<1,1>>}.
AB= A=B=等
2020/12/29
2020/12/29
序偶与笛卡尔积
15
消去律
设A,B,C是任意集合, 若C, 则AC BC AB CA CB AB
2020/12/29
序偶与笛卡尔积
16
消去律(证明)
若 C, 则AC BC AB. 证明(续): ()若A=,则AC=BC.
设 A. <x,y>, <x,y>AC xAyC
2020/12/29
序偶与笛卡尔积
6
笛卡尔积(Cartesian product)
笛卡尔积 : 令A和B是任意两个集合，若 序偶的第一个成员是A中的元素，第二个 成员是B中的元素，所有这些序偶组成的 集合称为集合A和B的笛卡尔积或卡氏积， 记作A B。

二、序偶与笛卡儿积


例题2
例题 设A,B为两个集合，若A∩B≠ ，则 (A∩B)×(A∪B)⊆(A×A)∪(B×B) 证明 x,y, <x,y>(A∩B)×(A∪B) x(A∩B)∧y(A∪B) (xA∧xB)∧(yA∨yB) (xA∧xB∧yA)∨(xA∧xB∧yB) (xA∧yA)∨(xB∧yB) (<x,y>A×A)∨(<x,y>B×B) <x,y>(A×A)∪(B×B)
×对∩、∪的分配律
定理3-4.1 笛卡儿积在并与交上可分配律 设A，B，C是任意三个集合，则有 (1)A×（B∪C）＝（A×B）∪（A×C） (2)A×（B∩C）＝（A×B）∩（A×C） (3)(A∪B）×C＝（A×C）∪（B×C） (4)(A∩B）×C＝（A×C）∩（B×C） <x,y>∈A×B x∈A∧y∈B 运用×的定义和 数理逻辑中的等 价式进行证明
方法总结
方法总结
1. 等价的证明 A⊆ B （ A × C ⊆ B × C ） （ A × C ⊆ B × C ） A⊆ B 2. “包含”的证明 区分是什么样的集合之间的包含，以待证明的结论来定。 3. 定义出发，数理逻辑中的方法
例题
例题：设A、B、C、D为四个任意集合， 则判断下列命题真假： • 若A⊆C，B⊆D ，则A×B⊆C×D
∴A×（B∪C）＝（A×B）∪（A×C）
定理证明
定理3-4.2 若C≠ ， 则 A⊆ B ⇔ A × C ⊆ B × C ⇔ C × A ⊆ C × B 证A⊆B⇔ C×A ⊆ C×B 证明：当A⊆B，对任意<x,y>设 <x,y>∈C×A ⇔(x∈C ∧y∈A) (x∈C ∧y∈B) <x,y>∈C×B ∴ A⊆ B C × A ⊆ C × B 反之，当C×A⊆C×B，因为C≠ ，设y ∈C，则当 x∈A (y∈C ∧x∈A) ⇔ <y,x>∈C×A <y,x>∈C×B ⇔(y∈C∧x∈B) x∈B ∴ C × A ⊆ C × B A⊆ B 故 A⊆ B⇔ C× A ⊆ C× B
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2. 笛卡儿积（直积） 定义3 笛卡尔积（Cartesian Products） 令A、B是任意两个 集合，若序偶的第一成员是A的元素，第二成员是B的元素， 所有这样的序偶组成的集合， 称为集合A和B的笛卡尔乘积或直积。记作A×B。 A×B＝｛<x，y>| (x∈A)∧(y∈B) ｝ 笛卡尔积是 集合，以序 偶为元素！
因为，对x, xA，y, yB,有 (xA) ∧(y∈B) ⇔ <x,y>∈A×B <x,y>∈C×D ⇔(xC) ∧(y∈D) 故， A⊆C，B⊆D
例题2
例题 设A,B为两个集合，若A∩B≠ ，则 (A∩B)×(A∪B)⊆(A×A)∪(B×B)
证明 x,y, <x,y>(A∩B)×(A∪B) x(A∩B)∧y(A∪B) (xA∧xB)∧(yA∨yB) (xA∧xB∧yA)∨(xA∧xB∧yB) (xA∧yA)∨(xB∧yB) (<x,y>A×A)∨(<x,y>B×B) <x,y>(A×A)∪(B×B)
笛卡尔积举例
例: A＝｛a，b｝，B＝｛1，2，3｝， 求A×B，B×A和（A×B）∩（B×A）。
解： A×B＝｛<a，1>，<a，2>，<a，3>，<b，1>，<b，2>，<b，3>｝ B×A＝｛<1，a>，<1，b>，<2，a>，<2，b>，<3，a>，<3笛卡尔积不 ，b>｝
？
（A×B）∩（B×A）＝
定义2： 两个序偶相等，<x,y>=<u,v>, 当且仅当 x=u, y=v。
n元组
三元组 <x, y, z> = <<x, y>，z >， 第一元素是一个序偶。
<x,y,z>≠<x,<y,z>>
n元组 <x1,…, xn> = <<x1 ,…, xn－1>，xn>是一个序偶。
第一元素是(n1)元序偶
3-4 序偶与笛卡儿积
{a,b}={b,a} <a,b>≠<b,a>
1. 序偶 定义1： 序偶（Ordered Pair） 两个具有固定次序的客体组 成的集合，记作 <x,y>。(x称为第一元素，y称为第二元素) 例如： <上,下>、<父,子>、<F,0>、二维平面上点的坐标等。
注意： （1）序偶与集合不同，其元素具有次序。 （2）序偶<x,y>的两个元素可以来自同一集合，也可来自不同 集合。
满足交换律
满足结合律吗？（A×B）×C ≠ A×（B×C） A=B=C＝呢 A=B=C≠呢
(A×B)×C={<<a,b>,c>|<a,b>∈A×B∧c∈C} ={<a,b,c>|a∈A∧b∈B∧c∈C} A×(B×C)={<a,<b,c>>|a∈A∧<b,c>∈B×C} 非三元组
注意：|A×B×…×An ＝（A1×A2×…×An-1）×An ＝｛<x1,x2,…,xn>|(x1∈A1)∧(x2∈A2)∧…∧(xn∈An)｝
分配率证明
证明
(1) A×（B∪C）＝（A×B）∪（A×C）
<x,y>∈A×（B∪C）
证明：设任一序偶<x,y>∈A×（B∪C），则
⇔(x∈A) ∧ (y∈B∪C) ⇔(x∈A)∧（y∈B∨y∈C） ⇔(x∈A ∧y∈B)∨(x∈A∧y∈C) ⇔ <x,y>∈A×B∨<x,y>∈A×C ⇔ <x,y>∈（A×B）∪（A×C）
∴A×（B∪C）＝（A×B）∪（A×C）
定理证明
定理3-4.2 若C≠ ， 则 A⊆B⇔ A×C⊆B×C ⇔ C×A⊆C×B 证A⊆B⇔ C×A ⊆ C×B 证明：当A⊆B，对任意<x,y>设 <x,y>∈C×A ⇔(x∈C ∧y∈A) (x∈C ∧y∈B) <x,y>∈C×B ∴A⊆B C × A ⊆ C × B 反之，当C×A⊆C×B，因为C≠ ，设y ∈C，则当 x∈A (y∈C ∧x∈A) ⇔ <y,x>∈C×A <y,x>∈C×B ⇔(y∈C∧x∈B) x∈B ∴ C×A ⊆ C×B A⊆B 故 A⊆B⇔ C×A ⊆ C×B
方法总结
方法总结
1. 等价的证明 A⊆B （A×C⊆B×C） （A×C⊆B×C） A⊆B 2. “包含”的证 明 区分是什么样的集合之间的包含，以待证明的结论来定。 3. 定义出发，数理逻辑中的方法
例题
例题：设A、B、C、D为四个任意集合， 则判断下列命题真假： • 若A⊆C，B⊆D ，则A×B⊆C×D
为真，P104 定理3-4.3
• 若A×B⊆C×D，则A⊆C，B⊆D。 为假，若A或B为空集 证明 若A⊆C，B⊆D ，对x, y,设 <x,y>∈A×B ⇔(x∈A ∧y∈B) (x∈C ∧y∈D) ⇔ <x,y>∈C×D 故， A×B⊆C×D
若A、B、C、D为四个非空集合，则A×B⊆C×D A⊆C，B⊆D
故， (A∩B)×(A∪B)⊆(A×A)∪(B×B) 作业： P105 (2),
(3)a, d, (5)
×对∩、∪的分配律
定理3-4.1 笛卡儿积在并与交上可分配律 设A，B，C是任意三个集合，则有 (1)A×（B∪C）＝（A×B）∪（A×C）
(2)A×（B∩C）＝（A×B）∩（A×C）
(3)(A∪B）×C＝（A×C）∪（B×C）
(4)(A∩B）×C＝（A×C）∩（B×C）
<x,y>∈A×B x∈A∧y∈B 运用×的定义和 数理逻辑中的等 价式进行证明