第四章-高级数理逻辑.pptx

第4章 二元关系与函数4.1 集合的笛卡儿积与二元关系4.2 关系的运算4.3 关系的性质4.4 关系的闭包4.5 等价关系和偏序关系4.6 函数的定义和性质4.7 函数的复合和反函数4.1 集合的笛卡儿积和二元关系 有序对 笛卡儿积及其性质 二元关系的定义 二元关系的表示有序对定义 由两个元素 x 和 y，按照一定的顺序组成的 二元组称为有序对(或序偶)，记作x,y或 ( x,y )实例：平面直角坐标系中点的坐标3,?4 有序对具有以下特点： (1) 当x? y时，x,y?y,x (2) 两个有序对相等的充分必要条件是x=u且y=v 即 x,y=u,v ? x=u ? y=v有序 n 元组定义 一个有序 n (n?3) 元组 x1, x2, …, xn 是一个有序对，其中第一个元素是一个有序 n-1元组，即 x1, x2, …, xn = x1, x2, …, xn-1, xn 当 n=1时, x 形式上可以看成有序 1 元组. 例 有序三元组：空间直角坐标系中点的坐标1,2,3 笛卡儿积定义 设A,B为集合，A与B 的笛卡儿积记作A?B， 即A?B ={ x,y | x?A ? y?B }若|A|=m, |B|=n, 则 |A?B|=mn 例 A={1,2,3}, B={a,b,c} A?B ={1,a,1,b,1,c,2,a,2,b,2,c, 3,a,3,b,3,c} B?A ={a,1,b,1,c,1,a,2,b,2,c,2, a,3, b,3,c,3}笛卡儿积的性质若A或B中有一个为空集，则A?B就是空集. A??=??B=?若A ?B且A和B都不是空集时： A?B?B?A (不适合交换律 )若A、B和C都不是空集时： (A?B)?C?A?(B?C)(不适合结合律 )笛卡儿积的性质对于并或交运算满足分配律 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)证 任取x,y ，则有 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).性质的证明(续)证明 (B?C) ? A=(B ? A)?(C ? A)证 任取x,y ，则有 x,y∈(B?C) ? Ax∈ (B?C) ∧y∈ A (x∈ B ∧ x∈ C) ∧ y∈ A(x∈ B ∧ y∈ A) ∧ (x∈ C ∧ y∈ A) x,y∈ B ? A ∨x,y∈ C ? A? x,y∈ (B ? A)?(C ? A)所以 (B?C) ? A=(B ? A)?(C ? A)证明 (A?B) ? (C?D) =(A ? C)?(B ? D)证 任取x,y ，则有 x,y∈ (A?B) ? (C?D) x∈ (A?B) ∧y∈ (C?D) (x∈ A ∧ x∈ B) ∧ (y∈ C ∧ y∈ D) (x∈ A ∧ y∈ C ) ∧ (x∈ B ∧ y∈ D) x,y∈ A ? C ∨x,y∈ B ? D? x,y∈(A ? C)?(B ? D)所以(A?B) ? (C?D) =(A ? C)?(B ? D)注： (A?B) ? (C?D) =(A ? D)?(B ? C)例 (1) 证明 A=B ? C=D ? A?C=B?D (2) A?C=B?D是否推出 A=B ? C=D ? 为什么？解 (1) 任取x,y x,y?A?C ? x?A ? y?C ? x?B ? y?D ? x,y?B?D (2) 不一定. 反例如下： A={1}，B={2}, C=D=?, 则 A?C=B?D 但是 A?B.n阶笛卡儿积定义 设A1, A2, ···, An 是集合，它们的n阶笛卡儿积记作A1 ? A2 ?··· ? An ， 即 A1 ? A2 ?··· ? An ={ x1, x2, ···, xn | x1? A1 ? x2? A2 ?··· ? xn? An }特别地，当 A1=A2= ···= An= A时，可简记为An例 A={0,1}时，A3={0,0,0, 0,0,1, 0,1,0, 0,1,1, 1,0,0, 1,0,1, 1,1,0, 1,1,1}定义 如果一个集合满足以下条件之一：（1）集合非空, 且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系, 简称为关系，记作R.如x,y∈R, 可记作 xRy；如果x,y?R, 则记作x y例：R={1,2,a,b}, S={1,2,a,b