离散数学3.4-5.ppt

《离散数学3.4-5.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、3－4序偶与笛卡尔积一、序偶定义:由两个元素x,y按照一定的次序组成的二元组称为有序偶对(序偶),记作,其中x为第一个元素，y为第二个元素。常常表达两个客体之间的关系。序偶与笛卡尔积例：平面上点的坐标；中国地处亚洲<中国，亚洲>等都是序偶。序偶与集合的区别定义两个序偶相等＝当且仅当x=u且y=v序偶与笛卡尔积序偶的概念可以推广到三元组三元组是一个序偶，其第一元素本身也是序偶，可形式化表示为<,z>?>同理四元组被定义为一个序偶，其第一元素为三元组。定义由N个元素a1,a2,

2、a3,…,an按照一定的次序组成的N元组称为N重有序组，记作即：＝<,an>。序偶与笛卡尔积例：a年b月c日d时e分f秒可用下述六重有序组来描述：。性质:＝当且仅当　ai＝bi。(i＝1,2,3,...n)。序偶与笛卡尔积二、笛卡尔积定义设A，B是两个集合，若序偶的第一个成员是A的元素，第二个成员是B的元素，所有这样序偶的集合，称为A和B的笛卡尔积或直积。记作A×B：A×B＝{

3、>

4、(x∈A)∧(y∈B)}。序偶与笛卡尔积例题若A={a,b},B={1,2,3}，求AxB，BxA，AxA，BxB因此，一般情况下，对任何两个集合A、B，当A≠B时，有：A×B≠B×A，当A＝B时，有：A×B＝B×A＝A2。约定：如果A=Φ，或者B=Φ，则AxB=Φ笛卡尔积三条基本性质：1.A=且A=2.不满足交换律，即AB不一定等于BA。3.不满足结合律，即(AB)C不等于A(BC)。序偶与笛卡尔积笛卡尔积有如下性质(续)：4.笛卡尔积运算对并和交运算满足分配律，即：A(BC)=(AB)(AC)A(BC)=(AB)(A

5、C)(AB)C=(AC)(BC)(AB)C=(AC)(BC)5.若C非空，则ABACBCCACB序偶与笛卡尔积定理：设A,B,C,D为4个非空集合，则ABCD的充要条件是AC，BD序偶与笛卡尔积定义设A1，A2，…，An是N个集合，称下述集合：A1×A2×…×An＝{

6、(ai∈Ai)∧i∈{1,2,…,n}}为由A1，A2，A3，...，An构成的笛卡尔积。当A1＝A2＝…＝An时，A1×A2×…×An＝An。序偶与笛卡尔积世界上存在着各种各样的关系。在数学中，关系可以表达集合中元素间的联系。如：

7、”x>y”,”点a在b和c之间”。序偶可以表达两个客体或多个客体之间的联系，因此用序偶表达关系。3-5关系及其表示例如，电影票与座位之间有对号关系，设X表示电影票的集合，Y表示座位的集合，R表示“对号”关系，则对于任意的x∈X，y∈Y，必有x与y有对号关系和没有对号关系两种情况中的一种。上述问题可表达为xRy或xRy，也可记为∈R或R。由此可见对号关系R是一个序偶的集合。一、关系定义任一序偶的集合确定了一个二元关系R，R中任一序偶可记为∈R或xRy。不在R中任一序偶可记为R，或xRy。例如：在实数中关系

8、>可记为3-5、关系及其表示定义设R为二元关系，由∈R的所有x组成的集合称为R的前域，即domR={x

9、y(xRy)}使∈R的所有y组成的集合称为R的值域，即ranR={y

10、x(xRy)}R的前域和值域一起称为R的域，记作FLDR，即FLDR=domR∪ranR例：设A={1,2,3,5},B={1,2,4},H={<1,2>,<1,4>,<2,4>,<3,4>}，求domH,ranH,FLDH关系及其表示解：关系及其表示定义设A，B为两个集合，直积AxB的任何一个子集R称为从A到B的关系，简称关系(Relation)。特殊的，当A=B时，关系

11、R是AxA的子集，这时称R为A上的二元关系。关系及其表示关系及其表示例题设X={1,2,3,4}，求X上的关系<及dom<和ran<关系及其表示关系的数目：由于任何A×B的子集都是一个二元关系，按照子集的定义，知A×B共有个不同的子集。因此，从A到B不同的关系共有个。全域关系：A×B的平凡子集A×B称为A到B的全域关系空关系：A×B的平凡子集称为A到B的空关系恒等关系：设IA是A的二元关系且满足IA={

12、xA},则称IA是A上的恒等关系二、关系运算因为关系是序偶的集合，同一域上的关系，可以进行集合的所有运算。设R，S都是集合A到B的两个