复旦大学-赵一鸣-离散数学-二省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,每七天一交作业，作业成绩占总成绩10%；,平时不定时进行小测验，占总成绩,20%,；,期中考试成绩占总成绩,20%,；期终考试成绩占总成绩,50%,1/28,AB=AC,B=C,cancellation law,。,Example:A=1,2,3,B=3,4,5,C=4,5,B,C,But AB=AC=1,2,3,4,5,Example:A=1,2,3,B=3,4,5,C=3,B,C,But AB=AC=3,A-B=A-C,B=C,cancellation law,:,symmetric difference,2/28,The symmetric difference of A and B,write,A,B,is the set of all elements that are in A or B,but are not in both A and B,i.e.A,B=,(AB)-(AB),。,(AB)-(AB)=(A-B)(B-A),3/28,4/28,Theorem 1.4:if A,B=A,C,then B=C,Distributive laws,and,De Morgans laws:,B(A,1,A,2,A,n,)=(BA,1,)(BA,2,)(BA,n,),B(A,1,A,2,A,n,)=(BA,1,)(BA,2,)(BA,n,),5/28,Chapter 2 Relations,Definition 2.1:An order pair(a,b)is a listing of the objects a and b in a prescribed order,with a appearing first and b appearing second.Two order pairs(a,b)and(c,d)are equal if only if a=c and b=d,.,a,b=b,a，,order pairs:,(,a,b),(b,a)unless a=b.,(,a,a),6/28,Definition 2.2:The ordered n-tuple(a,1,a,2,a,n,)is the ordered collection that has a,1,as its first element,a,2,as its second element,and a,n,as its,n,th element.Two ordered n-tuples are equal is only if each corresponding pair of their elements ia equal,i.e.(a,1,a,2,a,n,)=(b,1,b,2,b,n,)if only if a,i,=b,i,for i=1,2,n.,7/28,Definition 2.3:Let A and B be two sets.The Cartesian product of A and B,denoted by AB,is the set of all ordered pairs(a,b)where a,A and b,B.Hence,A,B=(a,b)|a,A and b,B,Example:Let A=1,2,B=x,y,C=a,b,c.,AB=(1,x),(1,y),(2,x),(2,y);,BA=(x,1),(x,2),(y,1),(y,2);,BA,AB,commutative laws,8/28,AC=(1,a),(1,b),(1,c),(2,a),(2,b),(2,c);,AA=(1,1),(1,2),(2,1),(2,2)。,A,=,A=,Definition 2.4:Let A,1,A,2,A,n,be sets.The Cartesian product of A,1,A,2,A,n,denoted by A,1,A,2,A,n,is the set of all ordered n-tuples(a,1,a,2,a,n,)where a,i,A,i,for i=1,2,n.Hence,A,1,A,2,A,n,=,(,a,1,a,2,a,n,)|a,i,A,i,i=1,2,n.,9/28,Example:ABC=(1,x,a),(1,x,b),(1,x,c),(1,y,a),(1,y,b),(1,y,c),(2,x,a),(2,x,b),(2,x,c),(2,y,a),(2,y,b),(2,y,c)。,If A,i,=A for i=1,2,n,then A,1,A,2,A,n,by A,n,.,Example：Let A represent the set of all students at an university,and let B represent the set of all course at the university.What is the Cartesian product of AB?,The Cartesian product of AB consists of all the ordered pairs of the form(a,b),where a is a student at the university and b is a course offered at the university.The set AB can be used to represent all possible enrollments of students in courses at the university,10/28,students a,b,c,courses:x,y,z,w,(,a,y),(a,w),(b,x),(b,y),(b,w)，(c,w),R=(a,y),(a,w),(b,x),(b,y),(b,w),R,A,B,i.e.,R is a subset of A,B,relation,11/28,2.2,Binary relations,Definition 2.5:Let,A,and,B,be sets.A binary relation from,A,to,B,is a subset of,A,B,.A relation on,A,is a relation from,A,to,A,.If(,a,b,),R,we say that,a,is related to,b,by R,we also write,a,R,b,.If(a,b,),R,we say that,a,is not related to,b,by R,we also write,a,b,.we say that empty set is an empty relation.,12/28,Definition 2.6:Let R be a relation from A to B.The domain of Rdenoted by Dom(R),is the set of elements in A that are related to some element in B.The range of R,denoted by Ran(R),is the set of elements in B that are related to some element in A.,Dom R,A,Ran R,B。,13/28,Example:A=1,3,5,7,B=0,2,4,6,R=(a,b)|ab,where a,A and b,B,Hence R=(1,2),(1,4),(1,6),(3,4),(3,6),(5,6),Dom R=1,3,5,Ran R=2,4,6,(3,4),R,Because 43,so(4,3),R,Table,R=(1,2),(1,4),(1,6),(3,4),(3,6),(5,6),14/28,15/28,A=1,2,3,4,R=(a,b)|3|(a-b),where a and b,A,R=(1,1),(2,2),(3,3),(4,4),(1,4),(4,1),Dom R=Ran R=A。,congruence mod 3,congruence mod r,(a,b)|r|(a-b)where a and b,Z,and r,Z,+,16/28,Definition 2.7,：,Let A,1,A,2,A,n,be sets.An n-ary relation on these sets is a subset of A,1,A,2,A,n,.,17/28,2.3,Properties of relations,Definition 2.8:A relation R on a set A is reflexive if(a,a),R for all a,A.A relation R on a set A is irreflexive if(a,a),R for every a,A.,A=1,2,3,4,R,1,=(1,1),(2,2),(3,3)?,R,2,=(1,1),(1,2),(2,2),(3,3),(4,4)?,Let A be a nonempty set.The empty relation,AA is not reflexive since(a,a),for all a,A.However,is irreflexive,18/28,Definition 2.9:A relation R on a set A is symmetric if whenever a R b,then b R a.A relation R on a set A is asymmetric if whenever a R b,then b,a.A relation R on a set A is antisymmetric if whenever a R b,then b,a unless a=b.,If R is antisymmetric,then a,b or b,a when a,b.,A=1,2,3,4,S,1,=(1,2),(2,1),(1,3),(3,1)?,S,2,=(1,2),(2,1),(1,3)?,S,3,=(1,2),(2,1),(3,3),?,19/28,A relation is not,symmetric,and is also not antisymmetric,S,4,=(1,2),(1,3),(2,3)antisymmetric,asymmetric,S,5,=(1,1),(1,2),(1,3),(2,3),antisymmetric,is not,asymmetric,S,6,=(1,1),(2,2),antisymmetric,symmetric,is not,asymmetric,A relation is,symmetric,and is also antisymmetric,20/28,Definition 2.10:A relation R on set A is transitive if whenever a R b and b R c,then a R c.,A relation R on set A is not transitive if there exist a,b,and c in A so that a R b and b R c,but a,c.If such a,b,and c do not exist,then R is transitive,T,1,=(1,2),(1,3),transitive,T,2,=(1,1),transitive,T,3,=(1,2),(2,3),(1,3),transitive,T,4,=(1,2),(2,3),(1,3),(2,1),(1,1)?,21/28,Example：Let R be a nonempty relation on a set A.Suppose that R is symmetric and irreflexive.Show that R is not transitive.,Proof:Suppose R is,transitive.,Matrix or pictorial represented,22/28,Definition 2.11:Let R be a relation from A=a,1,a,2,a,m,to B=b,1,b,2,b,n,.The relation can be represented by the matrix M,R,=(m,i,j,),mn,where,m,i,j,=1?a,i,is related b,j,m,i,j,=0?a,i,is not related b,j,23/28,Example:A=1,2,3,4,R=(1,1),(2,2),(3,3),(4,4),(1,4),(4,1),Matrix:,Example：A=2,3,4,B=1,3,5,7,R=(2,3),(2,5),(2,7),(3,5),(3,7),(4,5),(4,7),Matrix:,Let R be a relation on set A.R is reflexive if all the elements on the main diagonal of M,R,are equal to 1,R is irreflexive if all the elements on the main diagonal of M,R,are equal to 0,R is symmetric if M,R,is a symmetric matrix.,R is antisymmetric if m,ij,=1 with i,j,then m,ji,=0,24/28,Directed graphs,or Digraphs。,Definition 2.12:Let R be a relation on A=a,1,a,2,a,n,.Draw a small circle(point)for each element of A and label the circle with the corresponding element of A.These circles are called vertices.Draw an arrow,called an edge,from vertex a,i,to vertex a,j,if only if a,i,R a,j,.An edge of the form(a,a)is represented using an arc from the vertex a back to itself.Such an edge is called a loop.,25/28,Example:LetA=1,2,3,4,5,R=(1,1),(2,2),(3,3),(4,4),(5,5),(1,4),(4,1),(2,5),(5,2),digraph,26/28,R,1,R,2,R,1,R,2,R,1,-,R,2,2.4,Operations on Relations,27/28,Exercise:P11 35,P114 17,35,P123 24,26,P135 20,31,33,28/28,