四川大学计算机学院 离散数学(第12讲)

冯伟森mEalif:w36s5@sc.udu.enc2031年7月5星期五日

要内容主 1、 殊特合集 、关系2的定义 3关、的表系 示 4关系、的质性21307--5计算学机

院2

集合幂的和集笛尔集一、卡集幂 义定35 .由合A的集有所子集成组的合称集为 A幂的，集记为 (A或2)A 2。 A =(A=){|x一x A}切这以种集合的集子为素元构的成合，常集称 为合集集的或集合。对族族的研究在数 集方学面、知库识表和处语理以言及工智人能等方 都有十面重要的分义。意2013-7-5计算机院学3

:

1)例设A=a{,b},:则2={ ,A{a},b{}{,,b}}a 2) 于空对集， 有： ={ } 22 {}= {,{} }) 3({1,2{3,}}){=,{Φ},{{2,3}1,{}1{,23,}}} 理定.4:3 设和AB是个集合，两如BA ,2则B A2 。 理定.3:5若 合A集n个有素，元则合A共集有n2 子

集，个即| (:A)=| n 。2201-37- 计5机学算 院4

. 二卡尔积(直笛积 ) 义 3.6定:设 给 定n≥1个 集 合A1A2,,…An,,称 A1× 2A×…×An{<=a,12a,,an>…︱iaAi ,1i ≤n}≤为A1,A2 ,…An,的卡笛尔积 。 对所 的有iA,=iA,时A1×A2 …×A×n简写 成 n ,如A×AA=²A,A×A×A= ³ A 如果 所有集的合都有是集穷,合则n个集合 的卡尔积的笛基数为 :|A1(×2A…×A×)|=n|A |×|A2|1…×|×n|A20137-5- 算计学院 5机

第4章

二元关系在第三我们讨论了集合及章元素其本，章 论集讨中合素元之间关系。关系是的用表于征 事物结构及的内其在系联 。研事物结究,构要是研究主系。关系关 概念应用广泛,在的计算科机中起学着重的要 作用如数,结据构数,据库数,字逻,情辑检报索,算 法析分,编译人工智能等,域领它是都很要重 数学的工。

具01327-5

-算计机院学6

§4.1

二关系元及表示其关系是一基本的概念,个俗地说通,所谓关 系,是对象之指的相互间系联它表,征物的事结 构。自如然界的中引力关“系”人与人之 间的“父,关子系,”上下“关系“级”,志同关 系,”“同关学系,对”间象的位“关置系,两” 数个间的“于大”,等于”““整,关系除”两,个 变量之的“间函关系”,计数算机件间的部“联结系”关程,序间的调“用关”,系…023-715 计算-机学院7

元关二系义4定.1A设，B为两集个，合AB的×何一个子 集R所定任义的二元关系称从A为B的到元关二系简称关 系，如R是从A。到A的元二系，关称R为A上则的二元系关。 R当=Φ时则，R为空称系关 当R=;A×时B则，R称全为系。关 设一序有：偶x,<>∈Ry,常把这一实记为xRy事，读“作对x有关yR系。”如 x<y, R,

>记则x为yR,作读x对“y有关系R”没。023-7-51 算机计院学 8

于由何任×AB子集的是一都二元个系关按， 子照的集定义，知×AB有共|A2╳|||个B不的子同

集

。因此从，A到B不的同关共有系|2|A╳B||个

20。1-735-算计机院

学9

系的关示表 法.1合表示法集由于关系是一种也殊的集合特所，以集的两合基种本表示法也的可以到关用的系表中示即。可用枚举和叙法法来表述关系。示例-1.4 11) A设{2},=B{=},3系R关{=<23,>} 2)如定 义合N集上的小“等于”于关：系

R={<,x>y(|x,y )∧Nx≤(y)}。203-1-5 7计机学院 算01

.2关图系设A={a法,a21a3,..,.an,},=Bb1,b{,2b,3...bm,,R是} A到从B的个一元关二系，则对于关系R应关系图之有下如规 ：定 1 设a),a12,3,a...a, nb和,1b,2b,3...,m b别为分图中节 点的用“。”表，;

示2 )如<i,baj> R则,从ia到bj 可用一向有a边i<i,baj为>应图中的有对向。边bj相 。连2103--75算机学计院

1

1如是R定义A在=a<1a2,a3,.,.,a.>n上关的系，对则 于关系R有应如下规定： 1)设 a1a2,,...a,为n图节中，用“。”点表。 示2) 如<a,aij> R,则从iaaj 可到一用有向边a <ii,aaj>对为应中的图有边； 向3 )如<ia,i>aR,则从a 到aii用带一头箭的圆环小表示ia aj连相

20。317-5

计算-机院学12

例41.2-)1设 A= P<,P12P,3…,P,6是六个>程，考序它虑之间

的一种调们关用R,系如P可i用P调j则,<P有iPj, R>,现假 设 =R<P1{P,2,>P<,26>P<,P,P2>5,P4<,P>4, <P,31>PP<3,P><44,P5>} P则此系R的关关系如图：下

203-7-15计机算院

学13

3.关矩系阵A设={1,a2,aa3,..,.na}B=,b{1,b,b23,...,b},mR 是A到从B一个二的关元系 称，阵矩MR(=rijn)×m关为 系的关系矩R阵邻接矩阵，其或中:1, a i,b jR rij i( 1 2,3,.,.,.n; j1,2, ,3...m,) 0 ,a i , j b R显然 关系矩，阵是布尔阵。

注矩意在关系矩阵时写首先，对应合A和B中的元集

进素排行，不序同排的会序到不同得关的矩系阵当。集 合枚以举表法示，如果没有对集合时元素的排，序默则认举枚的次序为元的排素。序20137--5计 算机院学 41

例41-.3A设{2,=34,},B{=,12,}4。虑 从A到B考的“于等于”关系R和大小“等于于关” 系S: R={2,<1>,2,<2><3,1,,<3>2>,,4<1,, >4,<2,>4,<4}> S,=<2,2>,{<,42,>3,<>,44<,4}>。 出写R,S的系矩阵。关 解 ：12 4 0 1 1 211 0 M S 0 0 1 MR 3 11 0 41 1 1 0 01 20137-- 5计机学算院 15

4§2.关系的 性质、 自1反性与反反性自

定义4. 2设R是集合A的上二元关，系 1)对任意的 ∈Ax都,足满<,x>xR,则称R是自反∈的或， 称具有R反自，即性R在 上A自是反 (的 x()(∈xA→(<),xx>R∈))1

2)=对任 意的∈A,都满足x<xx>, ,则称R是R反反的，自或称 具R反自反有，即性在RA是反自上的反 ( x((x)∈)A→(<xx,>R) =1 )ro( x(()x∈)A→(x,x>∈R)<)=20103--57计算机学 院16