离散数学重要公式定理汇总ppt课件

1、大一新生，离散数学中重要公式和定理的总结，1，2020/7/18，2，基本等价公式等价于幂等定律幂等定律购买力平价关联定律P(QR)(PQ)R P(QR)(PQ)R交换定律PQQP PQQP分布定律P(QR)(PQ)(PR) P(QR)(PQ)(PR)吸收定律P(PQ)P(PQ)P(PQ)P(P)德摩根定律(2020/7/18，3，同PFP A(BC)(AB)C交换定律ABBA ABBA分布定律A(BC)(AB)(AC) A(BC)(AB)(AC)吸收定律A(AB)A(AB)A(AB)A，公式，4，2020/7/18，5，德摩根定律(AB) AEA E指出了如何在负定律aaea，公式，5，20

2、20/7/18，6，定义，重言式公式中分配命题变量元理论，并且对应于公式的真值总是t 与公式相对应的真值总是f。可满足公式(满意度)无论公式中的命题变量如何替换，总会有与公式相对应的真值是T的情况.一般命题公式既不是永久真公式，也不是永久假公式。6，2020/7/18，7，3。重要的同义反复(如教科书第43页所示)i1。pqp，I2。pqq3。ppqi4。qpqi5。ppqi6。qpqi7。(pq) pi8。(pq) qi9。p，Qpqi 10 . p(pq)qi 11 . p(pq)qi 12 . q(pq)pi13。(pq) (QR) pri14。(pq)(pr)(QR)ri15 . ab

3、(AC)(BC)i16 . ab()。那么B必须是同义反复*如果AB和BC，那么AC(传递性)*如果AB和AC，那么A(B C) *如果AB和C B，那么(AC) B在p22，公式，8，2020/7/18，9，结，1中被证明。全功能真值表、公式e16ppq公式E21 PQ (PQ)(PQ)公式E20 PQ (PQ)(QP)公式E16 PQ (PQ)(PQ)将否定连词移到命题变量的前面。A (P1，p2，pn) a * (P1，p2，pn) (PQ)PQ，(PQ)PQ按分布律、幂等律和其他公式排序，使它们成为所需的形式。范式，10，2020/7/18，11，主析取范式定义析取范式A1A2.其中每

4、个ai (I=1，2.n)是一个次要术语，称为主析取范式。思考：主析取范式和析取范式之间有什么区别？主析取范式的编写方法：列真值表列出给定公式的真值表。找出真值表中每个“t”对应的真值赋值。将上述事件与“”联系起来。范式，11，2020/7/18，12，主合取范式定义合取范式A1A2.其中每个ai (I=1，2.n)是一个主项，称为主合取范式。主合取范式的编写方法：列真值表列出给定公式的真值表。找出真值表中与每个“f”对应的真值赋值对应的主要项目。将上述项目与连接。范式，12，2020/7/18，13，简要概述，第1章概述，知识网络：13，2020/7/18，14，如果它是一个没有对象参数x的

5、谓词公式，并且它不在x和x的管辖范围内，它可以被放入x和x的管辖范围内得到以下公式：1 .xa (x) bx (a (x) b) 2。xa (x) bx (a (x) b) 3。xa (x) bx (a (x) b) 4。xa (x) bx (a (x) b) 5。bxa (x) B，量词范围的扩展公式，14，2020/7/18，15，1 . X(a(X)B(X)xa(X)XB(X)2 . X(a(X)B(X)xa(X)XB(X)3 X(a(X)B(X)(a(a1)B(a1)(a(a2)B(a2)(a(an)B(an)(B(a1)B(1)。x (a (x) b (x) xa (x) XB (x

6、) 2。xa (x) XB (x) x (a (x) b (x)，证明1: xa (x) XB (x) xa (x)证明2:xa(x)XB(x)xa(x)XB(x)xa(x)XB(x)x(a(x)b(x)，16，2020/7/18，17，量词Y) 4.xya (x，y) xya (x，y) 5.yxa (x，y) xya (x，Y) 对于任何集合A，集合的幂等律具有AA=A。对于任何集合A和b，交换律具有AB=BA。对于任何集合A、b和C，关联律具有(AB)C=A(BC) .任何一组的均匀性.零定律对任何集合都成立.20，交与并的性质幂等律对于任何集合A都有AA=A .交换律对于任何集合A和b

7、都有AB=BA .关联律对于任何集合A，b和C都有(AB)C=A(BC).任何集合a的恒等式都是a=a。零定律对任何集合a都是AE=E.对于任何集合A、b和C，分布定律都有A(BC)=(AB)(AC).A(BC)=(AB)(AC).21，对于任何集合A，B，有A(AB)=A(AB)=A证明： A(AB)=(AE)(AB)(同)=A(EB)(分布)=AE=A(零定律)(同)AB=B，22那么A-=A-A-A=A-ba A-B=(A-B)-c=(A-c)-(B-c)A-(BC)=(A-B)(A-c)A-(BC)=(A-B) 那么E=E(A)=aa=aa=ea-b=ab(AB)=AB(AB)=AB=

8、BA A=b当且仅当AB=E且AB=，24时，对称差的性质交换定律对任何集合A和b都具有AB。关联定律对任何集合A、b和C都具有(AB)C=A(BC) .教科书里有证据。对于任何集合a，都有一个=a。对于任何集合a，都有一个=a。对于可分配的A(BC)=(AB)(AC)，25，1。自反性定义3360，让R是集合A中的关系，如果对于任何xA都有R (xRx)，那么R是集合A中的自反关系。也就是说，R是集合A中的自反关系xAxRx)。例如，在实数集合中，“”是自反关系，因为对于任何实数x，都有x的性质，并且从关系的有向图来看，自反性3360每个节点都有一个环。关系矩阵的自反性：主对角线都是1。26

9、，二。反自反性的定义：设R是集合A中的关系，如果任意xA都有R，那么R就叫做集合A中的反自反关系，也就是说，R是集合A中的反自反x(xAR)，反自反性：是从关系有向图中看到的，每个节点都没有环。关系矩阵的反自反性：主对角线都是0。如果实数大于关系，父子关系是自反的。注意：非自反的关系不一定是自反的。27，3。对称定义：R是集合a中的一个关系。如果任何x和ya都有xRy和yRx，那么r在集合a中称为对称关系.r是a上的对称xy(xAyAxRy) yRx)，对称：是在两个不同的节点之间，如果有边，则有两个方向相反的边。关系矩阵的对称性：以主对角线为对称的矩阵。邻居关系和朋友关系是对称的。28，iv

10、 .反对称定义假设r是集合a中的关系，如果对于任何x，yA，如果有xRy和yRx，那么x=y，那么r在集合a中称为反对称关系。从r的图看反对称：在两个不同的节点之间最多有一条边。从关系矩阵的角度来看是反对称的：与主对角线对称的两个元素之一最多为1。另外，对称和反对称并不是完全对立的，有些关系是对称和反对称的，如空间关系和恒等式关系。传递性定义：R是a中的传递关系，对于任何x，y，zA，如果有xRy和yRz，就有xRz，所以r在a中称为传递关系.也就是说，r在xyz上是可传递的。在实数集中，是可传递的。从关系图和关系矩阵中很难看出是否存在传递性。必须直接对照传递的定义进行检查。检查时，要特别注意

11、这样一个事实，当转移定义表达式的先行词是f时，这个表达式是t，即转移。也就是说，如果R and R中的一个是F(即定义的先行词是假的)，则R是传递的。本节要求：1 .准确把握这五个属性的定义。2.掌握五个属性的判断和证明。R是自反x(xAxRx) R是自反x(XaRr)R是对称xy(xAyAxRy) yRx) R是反对称xy(XaYaxRyRx)x=y)xy(XaYaxRy)y x)R在a上转移XYZ(XaYaxRyRz)xRz)(除了自反性和反自反性)，31，32，如果RAB SBC TBC存在，证明R (ST) B (BBRST) B (BBRS) (BBRT) B例如，=，MR，c，34

12、，3。因为r和s是从x到y，那么1。(RC)C=R 2。(塞尔维亚)C=RCSC。3.(塞尔维亚)C=RCSC .4.(塞尔维亚)C=RCSC .35，5。斯普斯卡共和国军.6.(相对)C=RC，7。假设R是从X到Y的关系，S是从Y到Z的关系，那么(R S)C=SC RC。(注意RC sc)，如果8。R是a上的一个关系，那么R是对称的，当且仅当RC=R R是反对称的，当且仅当RRC IA。36，4。属性定理5。R是A上的关系，那么R是自反的，当且仅当R(R)=R。R是对称的，当且仅当s(R)=R。R是传递的，当且仅当t(R)=R。定理6。R是A上的关系，那么R是自反的，那么S R是对称的，r(

13、R)和t(R)也是对称的。R是传递的，那么r(R)也是传递的。37，定理7:设R1和R2是A上的一个关系，如果R1R2，那么r(R1) r(R2) s(R1) s(R2) t(R1)t(R2)证明r(R1)=IA1IAR 2=r(R2)，这是类似可证明的。定理8:设R是A上的一个关系，那么SR(R)=RS(R)TR(R)=RT(R)ST(R)TS(R)证明了SR(R)=R(R)(R)C=(RIA)(RIA)C=(RIA)，38，6。函数类型，一对一，一对一，外射，内反射，入射单射，双射一对一，39，函数组合的性质，1。定理5-2.1满足：XY，g:YZ，h :ZW是函数，2。定理5-2.2 f :XY，g:YZ是两个函数，那么如果F和G是满射的，那么g f也是满射的；如果F和G是事件，g f也是事件；如果f和g是双射的，那么g f就是双射的。定理5-2.3如果gf是满射的，那么G是满射的