CH4二元关系和函数1二元关系的基本概念.ppt
36页
离散数学离散数学CH4二元关系和函数二元关系和函数 回顾 用推理规则证明： |= Ø A 证明：明：设论域D={a , b , c}，求证： 第第4 4章二元关系和函数章二元关系和函数本章学本章学习1.1.集合的笛卡集合的笛卡尔积2.2.关系及其表示关系及其表示3.3.关系的运算关系的运算4.4.关系的性关系的性质5.5.关系的关系的闭包包6.6.等价关系和偏序关系等价关系和偏序关系7.7.函数的定函数的定义和性和性质8.8.函数的复合和反函数函数的复合和反函数 今日内容集合的笛卡集合的笛卡尔积关系及其表示关系及其表示关系的运算关系的运算 笛卡笛卡尔乘乘积定定义：由两个元素：由两个元素x x和和y y（允（允许x=yx=y）按）按一定的一定的顺序排列成的二元序排列成的二元组叫做一个叫做一个有序有序对（也称（也称序偶序偶），），记做做
系中不同的点 序偶的特点序偶的特点（与集合的不同之（与集合的不同之处））当当x≠yx≠y时，，
所有成序偶所有这样的序偶的序偶组成的集合叫做成的集合叫做A A和和B B的的笛卡儿笛卡儿积，，记作作A A×B B符号化表示符号化表示为 A A×B={
一般情况下一般情况下, <
它它们的的n n阶笛卡儿笛卡儿积 A A1 1 × A × A2 2 × ×…× A× An n={={〈〈x x1 1,x,x2 2, ,…,x,xn n〉〉|x|x1 1∈A∈A1 1∧x∧x2 2∈A∈A2 2∧∧…∧x∧xn n∈A∈An n} } 当当A A1 1 = A = A2 2 = =…= A= An n = A = A时，可将它，可将它们的的n n阶笛卡儿笛卡儿积 简记为A An n例如，例如，A={aA={a，，b}b}，，则 A A3 3={={〈〈a a，，a a，，a a〉〉，，〈〈a a，，a a，，b b〉〉，，〈〈a a，，b b，，a a〉〉，， 〈〈a a，，b b，，b b〉〉，，〈〈b b，，a a，，a a〉〉，，〈〈b b，，a a，，b b〉〉，， 〈〈b b，，b b，，a a〉〉，，〈〈b b，，b b，，b b〉〉} } 关系及其表示关系及其表示 l什么是关系什么是关系l关系的表示关系的表示 l所谓所谓二元关系二元关系就是在集合中两个元素之间的就是在集合中两个元素之间的某种相关性某种相关性l例如：甲、乙、丙三人进行乒乓球比赛，如例如：甲、乙、丙三人进行乒乓球比赛，如果任何两人之间都要赛一场，那么共要赛三场。
果任何两人之间都要赛一场，那么共要赛三场假设三场比赛的结果是乙胜甲，甲胜丙，乙胜假设三场比赛的结果是乙胜甲，甲胜丙，乙胜丙，这个结果可以记作丙，这个结果可以记作 {〈〈乙，甲乙，甲〉〉，，〈〈甲，丙甲，丙〉〉，，〈〈乙，丙乙，丙〉〉} 其中其中〈〈x，，y〉〉表示表示x胜胜y它表示了集合它表示了集合{甲、乙、丙甲、乙、丙}中元素之间的一种中元素之间的一种胜负关系胜负关系1、什么是关系 l再例如，有再例如，有甲，乙，丙甲，乙，丙三个人和四三个人和四项工作工作a a，，b b，，c c，，d d 已知甲可以从事已知甲可以从事工作工作a a和和b b，乙可以从事工作，乙可以从事工作c c，丙可以从事，丙可以从事工作工作a a和和d d 那么人和工作之那么人和工作之间的的对应关系可以关系可以记作作 R={
l除了二元关系以外除了二元关系以外还有有多元关系多元关系 本本书只只讨论二元关系以后凡是出二元关系以后凡是出现关系的地关系的地方均指二元关系方均指二元关系 下面下面给出二元关系的一般定出二元关系的一般定义l定定义（（二元关系二元关系）如果一个集合）如果一个集合为空集空集或它的或它的元素都是有序元素都是有序对，，则称称这个集合是一个个集合是一个二元关二元关系系，一般，一般记作作R R 对于二元关系于二元关系R R，如果，如果〈〈x x，，y y〉〉∊ ∊ R R，，则记作作xRyxRyl设A A，，B B为集合，集合，A A✕✕B B的任何子集所定的任何子集所定义的二元的二元关系称作从关系称作从A A到到B B的二元关系的二元关系，特，特别当当A=BA=B时，，则叫做叫做A A上的二元关系上的二元关系 例：集合例：集合A＝＝{0,1}，，B＝＝{2,3}A×B＝＝{<0，，2>，， <0，，3>，， <1，，2>，， <1，，3>}A×A的子集：的子集： R3={<0，，0>，， <0，，1>} R4={<0，，0>，， <1，，0>，， <1，，1>} 都是都是A上的二元关系上的二元关系A×A＝＝{<0，，0>，， <0，，1>，， <1，，0>，， <1，，1>}A×B的子集：的子集：R1= {<0，，2>，， <0，，3>} R2={<0，，2>，， <1，，2>，， <1，，3>} 都是都是A到到B上的二元关系上的二元关系 l|A|=n|A|=n，， A A✕✕A A的子集有的子集有2 2n n2 2个，每个子集代表一个个，每个子集代表一个A A上的上的关系，关系， 所以所以A A上有上有2 2n n2 2个不同的二元关系。
个不同的二元关系lA A上的上的3 3种特殊的关系种特殊的关系³空关系空关系：： 空集空集³全域关系全域关系:E:EA A= A= A✕✕A A³恒等关系恒等关系:I:IA A={={〈〈x x，，x x〉〉| x| x ∊ ∊ A} A} 例：集合例：集合A A＝＝{0,1}{0,1}为为A A上的上的空关系空关系E EA A ＝＝ {<0{<0，，0>0>，， <0<0，，1>1>，， <1<1，，0>0>，， <1<1，，1>}1>}为为A A上的全域关系上的全域关系I IA A ＝＝ {<0{<0，，0>0>，， <1<1，，1>}1>}为为A A上的恒等关系上的恒等关系A×AA×A＝＝{<0{<0，，0>0>，， <0<0，，1>1>，， <1<1，，0>0>，， <1<1，，1>}1>} 其它一些常其它一些常见关系关系: :l设A A为实数集数集R R的某个子集，的某个子集，则A A上上小于等小于等于于关系定关系定义为: : L LA A={={〈〈x x，，y y〉〉| x| x，，y y ∊ ∊ A∧x≤y} A∧x≤y}例如：例如： A={-1 A={-1 ，，3 3，， 4}4}，，则 A A上上小于等于小于等于关系关系 L LA A= = { {〈〈-1-1，，-1-1〉〉, ,〈〈-1-1，，3 3〉〉, ,〈〈-1-1，，4 4〉〉, , 〈〈3 3，，3 3〉〉, ,〈〈3 3，，4 4〉〉，，〈〈4 4，，4 4〉〉} } l设B B为实数集数集Z Z+ +的某个子集，的某个子集，则B B上上整除关整除关系系定定义为: : D DB B={={〈〈x x，，y y〉〉| x| x，，y y ∊ ∊ B∧ x|y} B∧ x|y}例：例：B={1B={1，，2 2，，3 3，，6}6}，，则B B上上整除关系整除关系D DB B= ={ {〈〈1,11,1〉〉, ,〈〈1,21,2〉〉, ,〈〈1,31,3〉〉, ,〈〈1,61,6〉〉, , 〈〈2,22,2〉〉, ,〈〈2,62,6〉〉, , 〈〈3,33,3〉〉, ,〈〈3,63,6〉〉, , 〈〈6,66,6〉〉} } 集合集合A A的的幂集集P(A)P(A)上的上的包含关系：包含关系： R={R={〈〈x x，，y y〉〉| x| x，，y y ∊ ∊ P(A) ∧x P(A) ∧x ⊆ ⊆ y} y} 例例: :设A={aA={a，，b}b}，，则有有: : P(A)={ P(A)={, , {a}{a}，，{b}{b}，，A}A} R={< R={<, ,>,<>,<,{a}>,<,{a}>,<,{b}>,,{b}>, < <,A>,<{a},{a}>,<{a},A>, ,A>,<{a},{a}>,<{a},A>, <{b},{b}>,<{b},A>,
上的关系 ①首先在平面上画上首先在平面上画上n n个个结点分点分别代表代表x x1 1，，…x xn n，， 再画上再画上m m个个结点分点分别代表代表y y1 1，，y y2 2，，…，，y ym m ②如果如果
这样得到的得到的图就是就是R R的关系的关系图 例如：例如：设 A={1A={1，，2 2，，3 3，，4}, A 4}, A 上的关系上的关系 R={R={〈〈1,11,1〉〉, ,〈〈1,21,2〉〉, ,〈〈2,32,3〉〉, ,〈〈2,42,4〉〉, , 〈〈4,24,2〉〉} } R R的关系的关系图: : 课堂练习：集合A={1，2，3}写出A上的恒等关系，全域关系，小于等于关系，整除关系，并画出关系图 Q & A36 。
