离散数学教案 编号：C701 课时安排： 2学时教学课型：理论课√实验课口习题课口实践课口其它口 题目（教学章、节或主题）： Ch7二元关系 §7.1有序对与笛卡儿积 67.2一元关系 教学目的要求（分掌握、热悉、了解三个层次） 1)草握有序对与笛卡儿积的概念： 2)掌握二元关系的定义及其矩阵表示： 教学重占、难占 二元关系的定义及其矩阵表示 教学方法： 利用黑板，CAI课件等教学 教学用具： 黑板，CA课件及其辅助设备 教学内容（注明：*重点 #难点 ？疑点)： 一、回顾上堂课内容（约5分钟） *二、有序对与笛卡儿积(40分钟) 1.有序对（也彩 序偶，记作<>，其中x是它的第一元素y是它的第二元素。 有序对的特点：1.）当xy时，<x>+y,之。 2)两个有序对相等，即<xJ心=<，>的充分必要条件是x=u且y=v。 2.A和B的笛卡儿积，记作AXB。符号化表示为 AXB={x,yK∈AAy∈B. 例1，A={a,b},B={0,1,2,则AXB=(<a0>,<a,1>,a,2>,b,0>,b,1>,b2>: BXA={0,aP,<0,b>,<1,aP,<1,b>,<2,aP,<2,b> 笛卡儿积运算的性质： 1.)若A,B中有一个空集，则它们的笛卡儿积是空集，即②×B=B×⑦=⑦ 2.)当A≠B且A,B都不是空集时，有AXB≠BXA。所以，笛卡儿积运算不适合交换律。 3.)当A,B,C都不是空集时，有(AXB)XC≠A×(BXC).所以，笛卡儿积运算不适合结合律。 笛卡儿积运算对U或门运算满足分配律即 AX(BUC)=(AXB)U(AXC): (BUC)XA =(BXA)U(CXA): AX(BOC)=(AXB)0(AXC): (BOC)XA =(BXA)0(CXA). 设A=1,23求PXA 例3 设A,B,C,D为任意集合，判断以下等式是否成立。 (1)(AnB)X(CnD)=(AXC)n(BXD): (2)(AUB)X(CUD)=(AXC)U(BXD):
701 离 散 数 学 教 案 编号：C701 课时安排： 2 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch7 二元关系 §7.1 有序对与笛卡儿积 §7.2 二元关系 教学目的要求（分掌握、熟悉、了解三个层次）： 1） 掌握有序对与笛卡儿积的概念； 2） 掌握二元关系的定义及其矩阵表示； 教学重点、难点： 1） 重点：二元关系的定义及其矩阵表示， 2） 难点：笛卡儿积运算的性质，笛卡儿积运算对∪或∩运算满足分配律； 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： 一、回顾上堂课内容（约 5 分钟） *二、有序对与笛卡儿积（40 分钟） 1． 有序对 (也称序偶),记作<x,y >,其中 x 是它的第一元素,y 是它的第二元素。 有序对的特点：1.）当 xy 时,<x,y><y,x>。 2.）两个有序对相等,即 <x,y>＝<u, v> 的充分必要条件是 x＝u 且 y＝v。 2．A 和 B 的笛卡儿积,记作 A×B。符号化表示为 A×B＝{(x,y)|x∈A∧y∈B}. 例 1,A＝{a,b},B＝{0,1,2},则 A×B＝{<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>}； B×A＝{<0,a>,<0,b>, <1,a>,<1,b>,<2,a>,<2,b>}。 4．笛卡儿积运算的性质: 1.）若 A,B 中有一个空集,则它们的笛卡儿积是空集,即 B＝B×＝ 2.）当 A≠B 且 A,B 都不是空集时,有 A×B≠B×A。所以,笛卡儿积运算不适合交换律。 3.）当 A,B,C 都不是空集时,有 (A×B)×C≠A×(B×C).所以,笛卡儿积运算不适合结合律。 5．笛卡儿积运算对∪或∩运算满足分配律即 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)。 例2 设 A={1,2，3},求 P(A)×A 例 3 设 A,B,C,D 为任意集合,判断以下等式是否成立。 (1) (A∩B)×(C∩D)＝(A×C)∩(B×D)； (2) (A∪B)×(C∪D)＝(A×C)∪(B×D)；
(③)(A-B)×(C-D)=(AXC)-(B×D): (4)(AB)X(C⊕D)=(AXC)田(BXD). 三、二元关系(40分钟) 1,举例引入二元关系定义：就是在集合中两个元素之间的某种相关性 例如，甲、乙、丙三个人进行乒乓球比赛，如果任何两个人之间都要赛一场，那么共要赛三场。假设 场比赛的结果是乙胜甲、甲胜丙、乙胜丙，这个结果可以记作<乙，甲>，<甲，丙>，<乙，丙>，其中<xy>表示x 胜y。它表示了集合（甲，乙，丙}中元素之间的一种胜负关系 2.二元关系定义如果一个集合为空集或者它的元素都是有序对，则称这个集合是一个二元关系，一般 记作R。对于二元关系R如果<x心ER则记作x:如果心R,则记作？Ry 3.A到B的二元关系，特别当A=B时，则叫做A上的二元关系。 4.对于任何集合A都有3种特殊的关系：空集②称做空关系： 全域关系EA:恒等关系IA。 定义对任何集合A,EA={X,y>Ix∈AAy∈A}=AXA。 IA={X,X|x∈A}。 例2A=0,1,3,4,求E,。 5.常用的关系小于等于关系、整除关系 设A为实数集R的某个子集，则A上的小于等于关系定义为 LA={X,y>Ixy∈AAx≤y; 设B为正整数集Z+的某个子集，则B上的整除关系定义为 DB=<ky>lxy∈BAxly; 6.关系矩阵和关系图 设V是顶点的集合，E是有向边的集合，令V=A={x,x2,xn},如果xiR,则有向边<xi,x炉∈E 那么G=<VE>就是R的关系图。 设A={,x2,},R是A上的关系则R的关系矩阵可表示为： -6套 ,j=12,",a) 五、课堂小结（约5分钟）
702 (3) (A—B)×(C—D)＝(A×C)－(B×D)； (4) (AB) ×(CD) ＝(A×C) (B×D)。 三、 二元关系（40 分钟） 1． 举例引入二元关系定义：就是在集合中两个元素之间的某种相关性. 例如,甲、乙、丙三个人进行乒乓球比赛,如果任何两个人之间都要赛一场,那么共要赛三场。假设三 场比赛的结果是乙胜甲、甲胜丙、乙胜丙,这个结果可以记作{<乙,甲>,<甲,丙>,<乙,丙>},其中<x,y>表示 x 胜 y。它表示了集合{甲,乙,丙}中元素之间的一种胜负关系. 2．二元关系定义 如果一个集合为空集或者它的元素都是有序对, 则称这个集合是一个二元关系,一般 记作 R。对于二元关系 R,如果<x,y>∈R,则记作 xRy；如果<x,y>R,则记作 3． A 到 B 的二元关系,特别当 A＝B 时,则叫做 A 上的二元关系。 4．对于任何集合 A 都有 3 种特殊的关系: 空集 , 称做空关系； 全域关系 EA ； 恒等关系 IA。 定义 对任何集合 A, EA＝{<x,y>｜x∈A∧y∈A}＝A×A。 IA＝{<x,x>｜x∈A}。 例 2 A={0,1,3，4},求 EA ， IA。 5．常用的关系:小于等于关系、整除关系 设 A 为实数集 R 的某个子集,则 A 上的小于等于关系定义为 LA＝{<x,y>｜x,y∈A∧x≤y} 设 B 为正整数集 Z＋的某个子集,则 B 上的整除关系定义为 DB＝{<x,y>｜x,y∈B∧xy}. 6．关系矩阵和关系图 设 V 是顶点的集合,E 是有向边的集合,令 V＝A＝{ 1 x , 2 x ,., n x },如果 xiRxj,则有向边<xi,xj>∈E. 那么 G＝<V,E>就是 R 的关系图。 设 A＝{ 1 x , 2 x ,., n x },R 是 A 上的关系,则 R 的关系矩阵可表示为： 五、课堂小结（约 5 分钟）
离散数学教案 编号：C702 课时安排： 2学时教学课型：理论课√实验课口习题课口实践课口其它口 题目（教学章、节或主题）： Ch7二元关系 §7.3关系的运算 S7.4关系的性历 教学目的要求（分掌握、热悉、了解三个层次）： 1.掌握关系的运算 2.掌握关系的性质 教学重点、难点： 1)重点：掌握关系的运算、掌握关系的五种常见的性质（自反性、反自反性、对称性、反对称性、传递 性)的定义 2)难点：关系的基本运算的主要性质 教学方法： 利用黑板，CI课件等教学 教学用具： 黑板，CAI课件及其辅助设备 教学内容（注明：◆重点#难点 ?疑点)： 一、回顾上堂课内容（约5分钟） *二、关系的运算（约20分钟） l.定义关系R的定义域domR值域ranR和域dR分别是 domR={xy(<x.y>ER)) ranR={y3x(<Xy>∈R} fldR =domRranR domR就是R的所有有序对的第一个元素构成的集合，raR就是R的所有有序对的第二个元素构成的集合 例1.实数集R上的关系 {x,yky∈RAx+y=l,则有domS,ranS,f1ds。 2.定义设F,G为任意的关系，A为集合，则 ()F的逆记作F- F-=(<xy>lyFx). 2P与G的复合记作F。G F.G.=[<x.y>I3z(xGizAzFy) (3)F在A上的限制记作F「A A={x.y>xFyAx∈A. (4)A在F下的象记作FA, FA=ran(F「A) ·复合运算不是可交换的，即对任何关系F,G,一般说来FG≠GF 三、关系的基本运算的主要性质（约20钟） 1.定理设F,G,H是任意的关系，则有 (1)(F)=p 703
703 离 散 数 学 教 案 编号：C702 课时安排： 2 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch7 二元关系 §7.3 关系的运算 §7.4 关系的性质 教学目的要求（分掌握、熟悉、了解三个层次）： 1. 掌握关系的运算 2．掌握关系的性质 教学重点、难点： 1）重点：掌握关系的运算、掌握关系的五种常见的性质（自反性、反自反性、对称性、反对称性、传递 性）的定义 2) 难点：关系的基本运算的主要性质 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： 一、回顾上堂课内容（约 5 分钟） *二、关系的运算（约 20 分钟） 1．定义 关系 R 的定义域 domR,值域 ranR 和域 fldR 分别是 domR＝{xy(<x,y>∈R)} ranR＝{y| x(<x,y>∈R)} fldR＝domR∪ranR。 domR就是R的所有有序对的第一个元素构成的集合,ranR就是R的所有有序对的第二个元素构成的集合. 例 1．实数集 R 上的关系 S={<x,y>|x,y∈R∧x+y=1},则有 domS，ranS，fldS。 2．定义 设 F,G 为任意的关系,A 为集合,则 (1)F 的逆记作 −1 F ， −1 F ＝{<x,y>|yFx}. (2)F 与 G 的复合记作 F◦G, F◦G,＝{<x,y>｜z(xGz∧zFy)} (3)F 在 A 上的限制记作 F A F A＝{<x,y>|xFy∧x∈A}. (4)A 在 F 下的象记作 F[A], F[A]＝ran (F A) ⚫ 复合运算不是可交换的,即对任何关系 F,G,一般说来 F◦G≠G◦F. 三、关系的基本运算的主要性质 （约 20 钟） 1．定理 设 F,G,H 是任意的关系,则有 （1） 1 1 ( ) − − F =F
(2)dom F=ranF ;ran F-=domF (3)(FG)H=F。(GH 4(FoG)=G-1。F- 2. 定理设F,G,H为任意的关系则有 (I)F。(GUH=fGFH (2)(GUH)-F=G.FUH-F (3)F。(GOH)EF.GOF.H 3. 定义设R为A上的关系，n为自然数，则R的n次幂规定如下： (I)R0={x,Xx∈A}=IA (2)R=R-。Rn≥1 四、关系的性质主要有以下5种（约40钟） 有以下5种：自反性、反自反性、对称性、反对称、性传递性。 表41 自反性反自反性 对称性 反对称性 传递性 定YxEA,有Yx∈A,有若(x,y∈R,则若xy》∈R且x 若《x,w》∈R且 G)ER. 红z在R (y)ER. ≠头.则y,z年R 〈y,z)ER,则（红， :)ER. 主对角线元主对角线元矩阵为对称矩阵。 素全是1山. 素全是0. 点矩 阵 精 图中每个顶 国中每个顶 如果两个顶点之 如果两个重点之 如果顶点名到 点都有环 间有过，一定是 点环 有边，到有 对方向相反的边。 条有向边. 边，则从面到 有边， 例7.14（§7.4） 例3.判断下列关系的性质 集合A上的全域关系：恒等关系：整除关系：小于等于关系：幂集上的包含关系 五、课堂小结（约5分钟）
704 (2）dom −1 F =ranF ;ran −1 F =domF (3) (F◦G) ◦H＝F◦ (G◦H) (4) 1 ( ) − F G = −1 G 。 −1 F 2. 定理 设 F,G,H 为任意的关系,则有 (1)F◦ (GH)=F◦GF◦H (2) (GH)◦F=G◦F H◦F (3) F◦ (GH) F◦GF◦H (4) (GH)◦F G◦F H◦F 3. 定义 设 R 为 A 上的关系,n 为自然数,则 R 的 n 次幂规定如下： (1) 0 R ={<x , x>| x A} = I A （2） n R = n−1 R 。R n 1 四、关系的性质主要有以下 5 种（约 40 钟） 有以下 5 种：自反性、反自反性、对称性、反对称 、性传递性。 例 7.14 （§7.4） 例 3．判断下列关系的性质 集合 A 上的全域关系；恒等关系；整除关系；小于等于关系；幂集上的包含关系 五、课堂小结（约 5 分钟）
离散数学教案 编号：C703 课时安排： 2学时教学课型：理论课√实验课口习题课口实践课口其它口 题目（教学章、节或主题）： Ch7二元关系 s7.5关系的闭包 §7.6等价关系与划分 教学目的要求（分掌握、熟悉、了解三个层次）： )掌握关系的自反闭包、对称闭包、传递闭包的定义和求法： 2)掌据等价关系的定义、等价类及性质，掌握集合划分的定义，以及等价关系与划分之间的关系： 教学重点、难点： )重点：二元关系的常见的性质及闭包的定义和求法，等价关系的定义 2)难点：闭包的定义和求法 教学方法： 利用黑板，CAI课件等教学 教学用具 黑板，CAI课件及其辅助设备。 教学内容（注明：·重点 #难点 ?疑点)： 、回顾上堂课内容（约5分钟） *二、关系的闭包(40分钟) 1.定义设R是非空集合A上的关系，R的自反闭包（对称闭包或传递闭包）是A上的关系R,且R"满足 以下条件： (I)'是自反的（对称的或传递的）： 2RcR】 (3)对A上的任何包含R的自反关系（对称或传递关系）R"都有R'SR” 一般将R的自反reflexive闭包记作r(R),对称ymmetric闭包记作sR),传递transitive闭包记作t(R)。 例1设A={ab,cd,R={<ab>,<b,a>,<b.c>,<C,d,则R和R),sR),(R的关系图 2. 定理设R为非空集合A上的关系，则有 (1)r(R)=RURo: (2)R)=RUR-: 3)t(R)=RU R2UR'U (4)A是含有n个元素的集合tR)=RUR2UR3U.UR,k≤n 例2设A={ab,cd,R={ab>,<b,a>,b,ce心，c,d,则rR),sR),tR) 3.闭包的矩阵表示 705
705 离 散 数 学 教 案 编号：C703 课时安排： 2 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch7 二元关系 §7.5 关系的闭包 §7.6 等价关系与划分 教学目的要求（分掌握、熟悉、了解三个层次）： 1）掌握关系的自反闭包、对称闭包、传递闭包的定义和求法； 2） 掌握等价关系的定义、等价类及性质，掌握集合划分的定义，以及等价关系与划分之间的关系； 教学重点、难点： 1) 重点：二元关系的常见的性质及闭包的定义和求法，等价关系的定义 2) 难点：闭包的定义和求法 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： 一、回顾上堂课内容（约 5 分钟） *二、关系的闭包（40 分钟） 1．定义 设 R 是非空集合 A 上的关系,R 的自反闭包(对称闭包或传递闭包)是 A 上的关系 R’,且 R’满足 以下条件: (1)R’是自反的(对称的或传递的)； (2)RR’； (3)对 A 上的任何包含 R 的自反关系(对称或传递关系)R”都有 R’ R”. 一般将 R 的自反 reflexive 闭包记作 r(R),对称 symmetric 闭包记作 s(R),传递 transitive 闭包记作 t(R)。 例 1 设 A＝{a,b,c,d},R＝{<a,b>,<b,a>,<b,c>,<c,d>},则 R 和 r(R),s(R),t(R)的关系图 2．定理 设 R 为非空集合 A 上的关系,则有 (1)r(R)＝R∪R0； (2)s(R)＝R∪ −1 R ； (3)t(R)=R∪ 2 R ∪ 3 R ∪. (4)A 是含有 n 个元素的集合 t(R)= R∪ 2 R ∪ 3 R ∪.∪ k R , k≤n 例 2 设 A＝{a,b,c,d},R＝{<a,b>,<b,a>,<b,c>,<c,d>},则 r(R),s(R),t(R) 3．闭包的矩阵表示