有序对与笛卡儿积ppt课件.ppt

《有序对与笛卡儿积ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、关系代数1关系代数所谓关系代数是指专门用于研究集合中元素之间关系的数学方法。关系代数与集合论、数理逻辑以及图论等等有着密切的联系。关系代数广泛地应用于计算机科学技术，如计算机程序设计和分析（如程序的输入、输出关系；递归关系）、关系数据库。2第七章二元关系7.1有序对与笛卡儿积3定义7.1（有序对）由两个元素x和y（允许x=y）按一定顺序排列成的二元组叫做一个有序对或序偶，记作，其中x是它的第一元素，y是它的第二元素。有序对的性质：1、当xy时，2、=的充分必要条件是x=u且y=v例如：平面直角坐标系

2、中点的坐标就是有序对4定义7.2(笛卡儿积)设A，B是任意两个集合，用A中元素作第一元素，B中元素作第二元素构成的所有有序对的全体组成的集合称为集合A和B的笛卡儿积，记作A×B。易见A×B={xA,yB}5例如：集合A={a，b，c}，B={0，1}，求A×B，B×A，A×A解：A×B={,,,,,}B×A={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>}A×A={,,,,,,,,<

3、c,c>}（1）假如A，B均是有限集，A=m，B=n，则必有AB=mn。（2）一般的AB与BA不相等，即集合的笛卡尔积运算，不满足交换律。6练习设A={1，2}，求P（A）×A解：P（A）={，{1}，{2}，{1，2}}P（A）×A={，{1}，{2}，{1，2}}×{1，2}={<，1>，<，2>，<{1}，1>，<{1}，2>，<{2}，1>，<{2}，2>，<{1，2}，1>，<{1，2}，2>}7笛尔儿积运算具有以下性质性质1：对于任意集合A，A=，A=。性质2：笛卡儿积运算不满足交换律，即当A∧B∧AB

4、时，ABBA。性质3：笛卡儿运算不满足结合律，即当A，B，C均非空时，(AB)CA(BC)。性质4：笛卡儿运算对并和交运算满足分配律，即（1）A（BC）=（AB）（AC）（2）（BC）A=（BA）（CA）（3）A（BC）=（AB）（AC）（4）（BC）A=（BA）（CA）8例：证明A（BC）=（AB）（AC）集合恒等式的证明方法：等值演算基本思想是：欲证P=Q，即证对任意的x，有xPxQ。即证对于任意的，A（BC）（AB）（AC）9例：证明A（

5、BC）=（AB）（AC）证明：对于任意的A（BC）xA∧y（BC）xA∧（yB∨yC）（xA∧yB）∨（xA∧yC）AB∨AC（AB）（AC）所以A（BC）=（AB）（AC）10性质5：AC∧BDABCD问：性质5的逆命题是否成立？取A=，B={1}，C={3}，D={4}注意：性质5的逆命题不一定成立。推论：对于任意四个非空集合A、B、C、D，ABCD的充分必要条件是AC∧BD。11练习设A，B，C，D为任意集合，判断

6、以下命题是否为真，并说明理由。（1）AB=ACB=C（2）A-（BC）=（A-B）（A-C）（3）A=B∧C=DAC=BD（4）存在集合A，使得AA×A（1）AB=ACB=C不一定为真，当A=，B={1}，C={2}时，AB=AC=，但BC（2）A-（BC）=（A-B）（A-C）不一定为真，当A=B={1}，C={2}时，A-（BC）={1}-{<1，2>}={1}（A-B）（A-C）={1}=（4）存在集合A，使得AA×A。命题为真。当A=时，AA×A成立。（3）A=B∧C=DAC=BD为真。由等量代

7、入原理可证。12笛卡儿积的推广形式定义（笛卡儿积）设A1，A2，…，An为n个集合，则集合A1…An={

8、xiAi}称为由A1，A2，…，An构成的笛卡儿积。A1…An的元素称为有序n元组。137.2二元关系147.2二元关系一、二元关系的定义15定义7.3（二元关系）如果一个集合为空集或者它的元素都是有序对，则称这个集合是一个二元关系（2-Relation），可简称为关系，记作R。特别地，当R=时，则R称为空关系。对于一个二元关系R，如果R，则记作xRy；如果R，则记作xRy。16

9、例：R1={<1，2>，