离散数学关系完整PPT课件

在现实生活中，场景之间仍然有一些联系，比如同学和朋友。这些关系正是各学科研究的主要内容。离散数学从集合开始，主要研究集合之间的关系。本章主要研究二元关系。为了讨论关系的基本概念，首先引入了有序对和笛卡儿积的概念。在由两个元素a，b，a和b组成的集合a，b中，a和b是不符合顺序的。有时有必要按顺序考虑两个元素，因此有必要从这两个元素中形成新的东西，这两个元素是按顺序排列的。定义2.1两个元素a、b按顺序放在一起，称为有序对或有序对，表示为(a、b)。在有序对(a，b)中，a称为第一个元素，b称为第二个元素。以及(a1，b1)=(a2，b2)当且仅当a1=a2且b1=b2。设A和B是两个集合，集合(x，y)|xA和yB称为A和B的笛卡儿积，也称为笛卡儿积，表示为AB。归属关系表示为：(x，y)AB当且仅当xA和yB和(x，y) ab当且仅当xa或Yb。其中a称为第一集合，b称为第二集合。在案例2.1中，设置A=1，2，3，B=a，b，找到AB。根据笛卡儿积的定义，有一个=a=。根据有序对的性质，一般没有ABBA。AB也是一个集合，所以它可以是笛卡儿积(AB)C与另一个集合C，类似地也有一个(BC)。然而，通常没有(ab)c=a(BC ), ab中的元素既不是a中的元素也不是b中的元素。如果是B1A1、B2A2，那么是B1B2A1A2.8，证明了对于(x，y) b1b2，有xB1和yB2，并且因为B1A1，B2A2，那么xA1和yA2，所以(x，y)A1A2，也就是B1B2A1A2.9，定理2.2A，B，C是任意集合，那么：(1) A (B C)=(AB) AC，(B C) A=(BA) CA。(2)A(BC)=(AB)(AC)，(BC)A=(BA)(CA).(3)甲(乙-丙)=(乙)-(丙)，(乙-丙)甲=(丙)-(丙).10，证明(1)对于(x，y) a (b c)，有xA和yBC，所以xA和(yB或yC)，当yB，xA和yB得到(x，y)AB，当yC，xA和yC得到(x，y) b。因为aa，y因此，a(bc)=(abAC)成立。同样，也可以证明(b c) a=(ba) ca。(2)对于(x，y) ab有(x，y)AB和(x，y)AC，所以(xA和yB)和(xA和yC)。从yB和yC得到y b c，从xA和y b c得到(x，y) a (b c)。因此(ab)a(bc)。因为aa，bCB和bcc，a(bc)ab和a(bc)AC成立，所以a(bc)(ab)AC成立。所以a(bc)=(ab)AC。同样，可以证明(bc)a=(ba)ca。(3)对于(x，y) a (b-c)，有xA和yB-C，所以xA和yB和YC。从xA和yB，(x，y)AB，从YC，(x，y) ac，所以(x，y) ab)-(ac)。因此，a (b-c) (ab)-(ac)。对于(x，y)AB)-(AC)，有(x，y)AB和(x，y) AC，xA和yB是从(x，y)AB得到的，YC是从xA和(x，y) AC得到的，所以xA和yB和YC。从yB和yc，yB-C，所以(x，y)A(B-C)。因此(ab)-(ac) a (b-c)。因此，A(B-C)=(AB)-(AC)。同样，它也可以被证明。13，定义2.3到n2，n个元素a1，一个按顺序放在一起，称为n个元素的有序组，表示为(a1，an)。为了反映n元有序群的顺序，规定(a1、当且仅当任何给定的1 I n时，an)=(b1，bn)具有ai=bi。一个由n个元素组成的有序群可以形成一个集合，尤其是n个集合的笛卡儿积。14，定义2.4为n2，A1，安是n个集合，集合(x1，xn) |任何给定的1in，都有笛卡儿积Ai称为A1，an，表示为a1.一个。给定1in，Ai称为笛卡儿积的第I集。定义2.5如果一个集合满足以下条件之一：(1)该集合不是空的，并且其元素都是有序对；(2)集合为空。那么这个集合被称为二元关系，表示为r。二元关系也可以缩写为关系。对于二元关系R，如果(x，y)R，它可以记录为xRy；如果(x，y) r，它被记录为xRy.让a和b是集合，并且由AB的任何子集定义的二元关系被称为从a到b的二元关系，尤其是当A=B被称为a上的二元关系时。在示例2.2中，集合A=0，1，B=1，2，3，然后R1=(0，2)，R2=AB，R3=，R4=(0，1)，等等。是从a到b的二元关系，R3和R4同时是a上的二元关系。定义笛卡儿积A1A 2的任何子集r.在A1，A2，安。当A1=A2=An=A时，r称为A上的n元关系。在2.7空集合上定义一个二元关系，缩写为空关系；如果一个n元关系r本身是一个笛卡儿积A1A 2一个.那么r被称为完全关系，由符号UA表示，即UA=(ai，aj)|ai，ajA是A上的完全关系。18，例2.3集合A=1，2，3，4，下面定义的R是A上的关系，使用列元素方法表示R，(1) r=(x，y) | x是y的倍数 (2) r=(x，y) | (x-y) 2 a (3) r=(x，y) | x/y是素数(4)R=(x，y)|xy，19，解决方案：(1) r=(4，4)，(4，2)，4，1)，(3，3)，(3，1)，(2，1)，(1，1) (2) r=(2) (3，2)，(4，3)，(3，1)，(4，2)，(2，4)，(1，3)，(3，4)，(2，3)，(1，2)(3)R=(2，1)，(3，1)，(4，2)(4)R=UA-IA=(1，2)，(1，3)在2.8RAB，定义所有有序对的第一组元素被称为r的域，并被表示为domR。形式上表示为：domr=x | x a，y b，使(x，y)R。在RAB，所有有序对的第二个元素的集合被称为r的值域，它被称为ranR。形式上表示为ranr=y | y b，x a，使得(x，y)R。定义2.9将R设置为二元关系，R的逆关系，缩写为R的逆，表示为R-1，其中R-1=(y，x)|(x，y)R。例2.4可分关系设置为A=2，3，4，8，B=3，4，5，6，7，定义二元关系r: (a，b) ra可被B从A到B整除，然后r=(2，4)，(2，6)，(3，3)，(3，6)，(4，4)，DomR=2，3，4，RanR=3，4，6，r-1=(4，2)，(6，2)，(3，3)，(4，4)。22，这个关系在本质上仍然是一个集合，但是这个集合中的元素都以有序的对出现。因为关系是一个集合，所以集合的表示方法可以用来表示关系，并且因为关系是一个特殊的集合，所以其中的元素都以序数对的形式出现。除了集合的表示方法之外，还可以使用其他表示方法。本文主要介绍以下表达式。2.2关系的表达，23.1通过枚举的二进制关系的表达如果二进制关系中的序数对的数量是有限的，则二进制关系中包含的所有元素可以通过枚举一个接一个地被枚举。例2.5假设集合A=1，2，3，集合A上定义的关系小于或等于，LA=(a，b)|a，bA，ab，则la=(1，1)，(1，2)，(1，3)，(2，2)，(2，3)，(3，3)。一种通过描述来表示二元关系的方法，通过某些条件来表示某些序数对是否属于这种关系，并通过将这种条件写在括号中来表示这种关系。格式为：LR=(x，y)|xR和yR和xy。例2.6假设a=1，2，3，4，由以下两个公式定义的R1和R2是A上的关系，R1和R2的元素如下所示：(1)R1=(x，y)|x是y的倍数(2)R2=(x，y)|(x-y)2A，25，解决方案：(1) R1=(4，4)、(4，2)、(4，1)、(3，3)、(3，1)、(2，2)、(2，1)、(1，1) (2) R2=(2，1)、(1，2)、(3，1)、(1，3)、(2，3)、(3，2)、(4，2)、(2，4)、(3，4)、(4，3)。26，3。关系矩阵用于表示关系，2.10定义为两个有限集合A=A1，上午，B=B1，例2.7，例2.5中关系R的关系矩阵为：例2.8，例2.6中关系R1和R2的关系矩阵分别为：，使用关系图来表示二元关系，设置a=a1，a，an，r是a上的二元关系。a中的每个元素ai都由一个点表示，该点称为顶点ai。R的关系图是有向图。A中的每个元素分别由一个顶点表示。当且仅当(ai，aj)R，ai和aj由弧或线段连接；如果(ai，aj)R，在ai处画一条自闭弧，其中11，j n。在R中表示关系的图称为R的关系图，由GR表示在例2.9中，集合A=1，2，3，4，在集合A上定义关系R=(1，1)，(1，2)，(2，3)，(2，4)，(4，2)，则R的关系图如图2.1所示。30，关系r的集合表达式、关系矩阵MR和关系图gr都可以彼此唯一地确定。31，定义2.11，假设关系r和s是从a到b的两个二元关系，对于aa，bb，定义：(1) r s: (a，b) r s (a，b) r或(a，b)s(2)rs:(a，b)rs(a，b)r和(a，b )8745 ;(3)r-s:(a，b)，2.3关系操作，例2.10集合A=a，B，c，集合B=1，2，r和s是从A到B的两个二元关系，r=(a，1)，(B，2)，(c，1) s=(a，1)，(B，1)，(c，2)然后r s=(a，1)，(B，2)，(c，1)，(B，1)，(1)，(c，2) r 8745；s=(A，1) r-s=(A，1).33，因为这种关系可以用矩阵的形式表示。当我们用矩阵的形式来计算关系的并、交、补和对称差时，可以用以下的形式来表示：Mr s=mrms(矩阵的相应分量做逻辑析取运算)，Mr ; s=mrms(矩阵的相应分量做逻辑合取运算)，Mr-s=Mr ; s=MRM SMR=Mr(矩阵的相应分量做逻辑非运算)。例2.10中关系的运算以矩阵的形式表示如下：根据主题，关系R和关系S的关系矩阵分别表示为、35。定理2.3假设关系R和S是从集合A到集合B的二元关系，下列性质成立：(1) (R-1)-1=R，(R)=R(双负律)(2) (R)-1=(R-1)，-1=(可交换性)(3)(RS)-1=R-1S-1(分布律)(RS)-1=R-1S-1(R-S)-1=R-1-S-1(4)SRS-1R-1(1)，36，证明：这里只证明了(1)和(5)。(1)取(x，y)，反定义为(x，y)(r-1)-1(y，x)r-1(x，y) r，因此有(r-1)-1=r(5)取x，x domr-1y (x，y) r-1) y (y，x) r) x ranr so domR-1=ranR。类似地，ranR-1=domR可以被证明。37，合成关系，定义2.12假设R是从集合A到集合B的二元关系，S是从集合B到集合C的二元关系，那么R和S之间的合成关系(合成关系)RS是从A到C的关系，并且RS=(x，z)|xA和zC，并且存在yB，使得(x，y)R，(y，z)S，运算被称为合成运算或合成运算。假设二元关系r=(x，y) | x，ya，x是y的父亲，s=(x，y) | x，ya，x是y的母亲 (1)表示RR，r-1s1，r-1s的含义。(2)表示以下关系：(x，y) | x，ya，y是x的祖母 (x，y) | x，ya，x是y的祖母，39，解：(1) RR表示关系(x，y) | x，ya，x是Y的祖父 r-1s1表示关系(x，y) | x，ya，Y是x的祖母 ta (x，t) r-1 (t，Y) s-1) r-1s表示空关系(2) (x，y) | x，ya，Y是x的祖母表示s-1s1 (x，y) | x，ya，Y例2.13假设z是一个整数集，r，s是从z到z的两个关系：r=(x，3x)| xz ；S=(x，5x)|xZ .计算RS；斯洛伐