《离散数学》二元相关同函数-1.ppt

第四章 二元关系和函数 关系是在集合的基础上定义的，它是计算机科学中最基本的概念。它主要反映元素之间的联系和性质，在计算机科学中有重要的意义，如有限自动机和形式语言，编译程序设计，信息检索，数据结构以及算法分析和程序设计的描述中经常出现。 问题： 数学是我们描述世界的有力工具。现实世界的事物之间常有一定的联系，这些联系常表现出一定顺序，如： 34， 张华高于李明， A是B的父亲，C是B的儿子 ....... 数学是如何描述或表示这种联系呢？为此集合论引入有序n元组的概念。 定义2.1 由两个客体x和y，按照一定的顺序组成的二元组称为有序对，记作x,y，其中x是第一元素，y是第二元素。 实例：点的直角坐标(3,?4) 有序对性质 （1）有序性 x,y?y,x （当x? y时） （2）x,y 与 u,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 元组. 实例: n维向量是有序 n元组. n维空间中点的坐标。 注①：有序n元组与集合 有序n元组与n个元素的集合是两个不同的概念: 集合中的n个元素是无序的，而有序n元组中的n个元素具有一个的次序。对任意给定的n个个体，他们只能组成一个n元素的集合，但却可以组成n!个不同的有序n元组。 n元组中的两个元素可以相同也可以不同，但集合中的两个元素是不同的。 注②：两个有序n元组a1,a2,…,an和b1,b2,…,bn相等?ai=bii=1,2,…,n， 记为a1,a2,…,an=b1,b2,…,bn。 笛卡儿积 例2.1.2 设A=?，B={1,2,3}，求A?B，B?A。 解 A?B=??B=?， B?A=B??=? 笛卡尔运算的性质： 注①：若A或B中有一个为空集，则A?B就是空集，即 A??=??B=? 注②：A?B且A、B都不为空集时 A?B?B?A 即笛卡尔积一般不满足交换律 注③：当A、B、C都不是空集时，(A?B)?C?A?(B?C) 即笛卡尔积一般不满足结合律 注④：对于并或交运算满足分配律 1A?(B?C)=(A?B)?(A?C) 2(B?C)?A=(B?A)?(C?A) 3A?(B?C)=(A?B)?(A?C) 4(B?C)?A=(B?A)?(C?A) 5A?(B-C)=(A?B)-(A?C) 6(A-B)?C=(A?C)-(B?C) 证明： 对任意的x,y x,y?(A-B)?C ?x?(A-B)?y?C ?x?A?x?B?y?C ?x,y?(A?C)? x,y?(B?C） ?x，y?(A?C)-(B?C) 所以：(A-B)?C=(A?C)-(B?C) 证明 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). 例题 1、设A={1,2},求P(A) ? A 解：P(A)={?,{1},{2},{1,2}} ? {1,2} ={ ?,1, ?,2 , {1},1, {1},2 , {2},1 , {2},2 , {1,2},1 , {1,2},2 } 例2 设A,B,C和D是任意的集合，试问下列等式是否成立？为什么？ 1(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,y?A×C?x,y?B×D ?x,y?(A?C)∩(B?D) 2(A∪B)?(C∪D)=(A?C)∪(B?D) 解 不成立。举一反例如下：设A=D=?，B=C={1}，则(A∪B)?(C∪D)