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

1、大一上离散数学重要公式定理汇总2022-7-12 基本的等价公式基本的等价公式 对合律对合律 P PP P 幂等律幂等律 P PP PP PP PP PP P 结合律结合律 P P(QQR)R)( (P PQ)Q)R R P P(QQR)R)( (P PQ)Q)R R 交换律交换律 P PQQQQP PP PQQQQP P 分配律分配律 P P(QQR)R)( (P PQ)Q)(P PR) R) P P(QQR)R)( (P PQ)Q)(P PR)R) 吸收律吸收律 P P(P PQ)Q)P PP P(P PQ)Q)P P 德摩根定律德摩根定律 ( (P PQ)Q)P P Q Q ( (P P

2、Q)Q)P P QQFormula2022-7-13 同一律同一律 P PF FP PP PT TP P 零律零律 P PT TT PT PF FF F 互补律互补律 P P P PT T P P P PF F 附加：附加： P PQQP PQ Q P PQQQQP P P PQ Q ( (P PQ)Q)(Q(QP)P) P PQ Q ( ( P PQ)Q)(P(P Q) Q) P PQ Q ( (P PQ)Q)( ( P P Q )Q )Formula2022-7-14 等价公式等价公式( (前前1010个个) )与集合论的公式比较与集合论的公式比较： 对合律对合律 AAA AA A表示表示

3、A A的绝对补集的绝对补集 幂等律幂等律 A AA AA AA AA AA A 结合律结合律 A A(B BC)C)( (A AB)B)C C； A A(B BC)C)( (A AB)B)C C 交换律交换律 A AB BB BA AA AB BB BA A 分配律分配律 A A(B BC)C)( (A AB)B)(A AC) C) A A(B BC)C)( (A AB)B)(A AC)C) 吸收律吸收律 A A(A AB)B)A AA A(A AB)B)A A Formula2022-7-15德摩根定律德摩根定律 ( (A AB)B)A AB B ( (A AB)B)A AB B 同一律同一

4、律 A AA; AA; AE EA EA E表示全集表示全集 零律零律 A AE EE AE A 否定律否定律 A AA AE E A AA AFormula2022-7-16Definition永真永真( (重言重言) )式（式（TautologyTautology）公式中的命题变量元论公式中的命题变量元论怎样指派，公式对应的真值恒为怎样指派，公式对应的真值恒为T T。 永假（矛盾）式（永假（矛盾）式（Contradiction)Contradiction)公式中的命题变公式中的命题变量无论怎样代入，公式对应的真值恒为量无论怎样代入，公式对应的真值恒为F F。 可满足公式（可满足公式（Sat

5、isfactionSatisfaction）公式中的命题变量无公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为论怎样代入，公式对应的真值总有一种情况为T T。一般命题公式（一般命题公式（ContingencyContingency）既不是永真公式也不既不是永真公式也不是永假公式。是永假公式。2022-7-173.重要的重言蕴含式重要的重言蕴含式(如教材第如教材第43页所示页所示) I1.PQP , I2. PQQ I3. PPQ I4. QPQ I5. PPQ I6. QPQ I7. (PQ)P I8. (PQ)Q I9. P,Q PQ I10. P(PQ)Q I11. P(PQ)Q

6、 I12. Q(PQ)P I13. (PQ)(QR)PR I14. (PQ)(PR)(QR)R I15. AB (AC)(BC) I16. AB (AC)(BC)Formula2022-7-18 蕴含的性质蕴含的性质* *若若A AB B且且A A为重言式，则为重言式，则B B必为重言式必为重言式* *若若A AB B且且B BC C，则，则A AC C (传递性传递性)* *若若A AB B且且A AC C，则，则A A(B B C C) * *若若A AB B且且C C B B，则，则(A AC C) B B证明见书证明见书P22P22Formula2022-7-19conjunction

7、一、全功能真值表一、全功能真值表PQ C1 C2 C3 C4 C5 C6 C7 C8TTTFTTFFTFTFTFTFFTFTFTTFFTTFFTFFTFFFTTFTPQC9C10 C11 C12 C13 C14 C15 C16TTTFTFTFTFTFTFFTFTTFFTTFTFFTFTFFFTTFTFTFPQccQP2022-7-1103.3.析取范式与合取范式的化法析取范式与合取范式的化法 化成限定性公式化成限定性公式。 公式公式E E16 16 P PQQP PQ Q 公式公式E E2121 P PQ Q ( (P PQ)Q)( ( P P Q) Q) 公式公式E E20 20 P PQ

8、Q ( (P PQ)Q)(Q(QP) P) 公式公式E E16 16 P PQ Q ( ( P PQ)Q)(P(P Q) Q) 将否定联结词移到命题变量的前面。将否定联结词移到命题变量的前面。 A(PA(P1 1,P,P2 2, ,P,Pn n) )A A* *( ( P P1 1, , P P2 2, , , P Pn n) ) ( (P PQ)Q)P P Q Q 、 ( (P PQ)Q)P P QQ 用分配律、幂等律等公式进行整理，使之成为所用分配律、幂等律等公式进行整理，使之成为所要求的形式。要求的形式。 normal form2022-7-111v主析取范式定义主析取范式定义 析取范式

9、析取范式 A A1 1AA2 2.A.An, n, , , 其中每个其中每个A Ai i (i=1,2.n) (i=1,2.n)都是小项，称之为都是小项，称之为主析取范式主析取范式。思考：主析取范式与析取范式的区别是什么？思考：主析取范式与析取范式的区别是什么？v主析取范式的写法主析取范式的写法 方法方法：列真值表列真值表 列出给定公式的真值表。列出给定公式的真值表。 找出真值表中每个找出真值表中每个“T”T”对应的真值指派再对对应的真值指派再对应的小项。应的小项。用用“”联结上述小项，即可。联结上述小项，即可。normal form2022-7-112v主合取范式定义主合取范式定义 合合取范

10、式取范式 A A1 1AA2 2. A. An, n, , , 其中每个其中每个A Ai i (i=1,2.n) (i=1,2.n)都是大项，称之为都是大项，称之为主合取范式。主合取范式。v主合取范式的写法主合取范式的写法 方法方法：列真值表列真值表 列出给定公式的真值表。列出给定公式的真值表。 找出真值表中每个找出真值表中每个“F”F”对应的真值指派再对应对应的真值指派再对应的大项。的大项。 用用“”联结上述大项，即可。联结上述大项，即可。normal form2022-7-113Brief Summary第一章第一章 小结小结 命题命题原子命题原子命题复合命题复合命题联结词联结词命题公式命

11、题公式永真式永真式永真蕴涵式永真蕴涵式等价公式等价公式范式范式命题逻辑推理命题逻辑推理直接推理直接推理间接推理间接推理条件论证条件论证反证法反证法析取析取合取合取主析取主析取主合取主合取知识网络：知识网络：2022-7-114 如果是个不含客体变元x的谓词公式，且不在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)x(BA(x) 6. BxA(x)x(BA(x) 7. xA(x)Bx(A(x)B) 8. xA(x)Bx(A(

12、x)B) 量词辖域的扩充公式2022-7-1151. 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)xA(x)xB(x)4. xA(x)xB(x)x(A(x)B(x)证明：设论域为a1,a2,.,an， x(A(x)B(x) (A(a1)B(a1)(A(a2)B(a2) (A(an)B(an) (A(a1)A(a2).A(an) (B(a1)B(a2).B(an) xA(x)xB(x) 量词分配公式量词分配公式2022-7-116 其它公式1. x(A(x)B(x)xA(x)xB(x) 2. xA(x)xB(x)x(A(x)B(

13、x) xA(x)xB(x)xA(x)xB(x) xA(x)xB(x)x(A(x)B(x)x(A(x)B(x) ： xA(x)xB(x) xA(x)xB(x) xA(x)xB(x) x(A(x)B(x) x(A(x)B(x)2022-7-117量词之间有如下公式：1. xyA(x,y)yxA(x,y)2. xyA(x,y)yxA(x,y)3. yxA(x,y)xyA(x,y)4. xyA(x,y)xyA(x,y)5. yxA(x,y)xyA(x,y)6. xyA(x,y)yxA(x,y)7. yxA(x,y)xyA(x,y)8. xyA(x,y)yxA(x,y)注意：下面式子不成立xyA(x,y

14、)yxA(x,y)2022-7-118 x x yA(x,y)yA(x,y) y y xA(x,y)xA(x,y) x x yA(x,y)yA(x,y) y y xA(x,y)xA(x,y) x x yA(x,y)yA(x,y) y y xA(x,y)xA(x,y) y y xA(x,y)xA(x,y) x x yA(x,y)yA(x,y)为了便于记忆，用图形表示上面八个公式。2022-7-119第二章 小结集合的性质集合的性质幂等律幂等律 对任何集合A，有AA=A。交换律交换律 对任何集合A、B，有AB=BA。结合律结合律 对任何集合A、B、C，有 (AB)C=A(BC)。同一律同一律 对任

15、何集合A，有AE=A。零律零律 对任何集合A，有A=。 AB AB=A。交、并的性质交、并的性质幂等律幂等律 对任何集合对任何集合A A，有，有AA=AAA=A。交换律交换律 对任何集合对任何集合A A、B B，有，有AB=BAAB=BA。 结合律结合律 对任何集合对任何集合A A、B B、C C，有，有 (AB)C=A(BC) (AB)C=A(BC)。同一律同一律 对任何集合对任何集合A A，有，有A=AA=A。零律零律 对任何集合对任何集合A A，有，有AE =E AE =E 。分配律分配律 对任何集合对任何集合A A、B B、C C，有，有 A(BC) =(AB)(AC) A(BC) =

16、(AB)(AC)。 A(BC) =(AB)(AC) A(BC) =(AB)(AC)。吸收律吸收律 对任何集合对任何集合A A、B B，有，有 A(AB)=A A(AB) A(AB)=A A(AB) =A =A证明证明: : A(AB) A(AB) = (AE)(AB) ( = (AE)(AB) (同一同一) ) = A(EB) ( = A(EB) (分配分配) ) = AE=A ( = AE=A (零律零律) () (同一同一) ) A A B B AB=BAB=B差集的性质差集的性质设设A A、B B、C C是任意集合，则是任意集合，则 A-=A A-=A -A= -A= A-A= A-A=

17、 A-B A-B A A A A B B A-B= A-B= (A-B)-C=(A-C)-(B-C) (A-B)-C=(A-C)-(B-C) A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C) A A(B-(B-C)=(AB)-(AC)C)=(AB)-(AC)注意：注意：对对- - 是不可分配的，如是不可分配的，如A(A-B)=A A(A-B)=A 而而(AA)-(AB)=(AA)-(AB)=有关绝对补集的性质有关绝对补集的性质设设A A、B B、C C是任意集合，则是任意集合，则 E= E= =E =

18、E (A)=A(A)=A AA= AA= AA=E AA=E A-B=ABA-B=AB(AB)=AB (AB)=AB (AB)=AB (AB)=ABA A B B B B AA A=B A=B 当且仅当当且仅当AB=EAB=E且且 AB= AB=有关对称差的性质有关对称差的性质 交换律交换律 对任何集合对任何集合A A、B B，有，有A A B=BB=B A A。 结合律结合律 对任何集合对任何集合A A、B B、C C，有，有 (A (A B)B) C=AC=A (B(B C)C)。教材里有证明。教材里有证明。 同一律同一律 对任何集合对任何集合A A，有，有A A =A=A。 对任何集合对

19、任何集合A A，有，有A A A A=。 对对 可分配可分配 A A(B(B C)=(AB)C)=(AB) (AC)(AC)一一. . 自反性自反性定义定义: :设设R R是集合是集合A A中的关系，如果对于任意中的关系，如果对于任意xAxA都都有有R (xRx)R (xRx)，则称，则称R R是是A A中自反关系。中自反关系。 即即 R R是是A A中自反的关系中自反的关系x(xx(x A AxRx)xRx)例如：例如：在实数集合中在实数集合中, ,“ ”是自反关系，因是自反关系，因为，对任意实数为，对任意实数x x，有，有x x x. x. 关系的性质关系的性质从关系有向图看自反性从关系有

20、向图看自反性: :每个结点都有环。每个结点都有环。从关系矩阵看自反性：主对角线都为从关系矩阵看自反性：主对角线都为1 1。二二. .反自反性反自反性定义：定义：设设R R是集合是集合A A中的关系，如果对于任意的中的关系，如果对于任意的xAxA都有都有 R R ，则称，则称R R为为A A中的反自反关系。中的反自反关系。 即即 R R是是A A中反自反的中反自反的x(xx(x A A R)R)v 从关系有向图看反自反性从关系有向图看反自反性: :每个结点都无环。每个结点都无环。v 从关系矩阵看反自反性：主对角线都为从关系矩阵看反自反性：主对角线都为0 0。如如 实数的大于关系实数的大于关系，父

21、子关系是反自反的。，父子关系是反自反的。注意：注意：一个不是自反的关系，不一定就是反自反一个不是自反的关系，不一定就是反自反 的。的。三三. .对称性对称性定义定义: :R R是集合是集合A A中关系中关系, ,若对任何若对任何x, x, yA,yA,如果有如果有xRy,xRy,必有必有yRx,yRx,则称则称R R为为A A中的对称关系。中的对称关系。 R R是是A A上对称的上对称的 x x y(xy(x A A y y A A xRy) xRy) yRx)yRx)v从关系有向图看对称性从关系有向图看对称性: :在两个不同的结在两个不同的结点之间，若有边的话，则有方向相反的点之间，若有边的

22、话，则有方向相反的两条边。两条边。v从关系矩阵看对称性：以主对角线为对从关系矩阵看对称性：以主对角线为对称的矩阵。称的矩阵。例例 邻居关系和朋友关系是对称关系。邻居关系和朋友关系是对称关系。四四. .反对称性反对称性定义定义: :设设R R为集合为集合A A中关系中关系, ,若对任何若对任何x, x, yA,yA,如果有如果有xRy,xRy,和和yRx,yRx,就有就有x=y,x=y,则称则称R R为为A A中反对称关系中反对称关系 。R R R是是A A上反对称的上反对称的 x x y(xy(x A A y y A A xRyxRy yRx)yRx) x=y)x=y) x x y(xy(x

23、A A y y A A x x y y xRy)xRy)y xy x) (P112) (P112)v 由由R R的关系图看反对称性：两个不同的结点之间的关系图看反对称性：两个不同的结点之间最多有一条边。最多有一条边。v 从关系矩阵看反对称性：以主对角线为对称的两从关系矩阵看反对称性：以主对角线为对称的两个元素中最多有一个个元素中最多有一个1 1。v另外对称与反对称不是完全对立的，有些关系它另外对称与反对称不是完全对立的，有些关系它既是对称也是反对称的，如空关系和恒等关系。既是对称也是反对称的，如空关系和恒等关系。五五. . 传递性传递性定义定义: :R R是是A A中关系，对任何中关系，对任何

24、x,x,y,zA,y,zA,如果有如果有xRy,xRy,和和yRz,yRz,就有就有xRz,xRz,则称则称R R为为A A中传递关系。中传递关系。 即即R R在在A A上传递上传递x x y y z(xz(x A A y y A A z z A A xRyxRy yRz)yRz)xRz)xRz)例例 实数集中的实数集中的、，集合、，集合 、 是传递的。是传递的。v 从关系关系图和关系矩阵中不易看清是否有传从关系关系图和关系矩阵中不易看清是否有传递性。必须直接根据传递的定义来检查。递性。必须直接根据传递的定义来检查。v 检查时要特别注意使得传递定义表达式的前件检查时要特别注意使得传递定义表达式

25、的前件为为F F的时候此表达式为的时候此表达式为T T，即是传递的。，即是传递的。 即若即若RR与与RR有一个是有一个是F F时时( (即定义即定义的前件为假的前件为假) )，R R是传递的。是传递的。 本节要求：本节要求： 1.1.准确掌握这五个性质的定义。准确掌握这五个性质的定义。 2. 2.熟练掌握五个性质的判断和证明。熟练掌握五个性质的判断和证明。R R是是A A中自反的中自反的x(xx(x A AxRx)xRx)R R是是A A中反自反的中反自反的x(xx(x A A R)R)R R是是A A上对称的上对称的x x y(xy(x A A y y A A xRy) xRy) yRx)y

26、Rx)R R是是A A上反对称的上反对称的x x y(xy(x A A y y A A xRyxRy yRx)yRx) x=y)x=y)x x y(xy(x A A y y A A x x y y xRy)xRy)y xy x) )R R在在A A上传递上传递x x y y z(xz(x A A y y A A z z A A xRyxRy yRz)yRz)xRz)xRz)v注意注意 性质性质表达式的前件为表达式的前件为F F时此表达式为时此表达式为T T，即，即R R是满足此性质的。是满足此性质的。 ( (自反和反自反性除外自反和反自反性除外) )自反性自反性反自反性反自反性对称性对称性传递

27、性传递性反对称性反对称性每个结点都有环每个结点都有环 主对角线全是主对角线全是1 1每个结点都无环每个结点都无环 主对角线全是主对角线全是0 0不同结点间如果有不同结点间如果有边边, ,则有方向相反则有方向相反的两条边的两条边. .是以对角线为对是以对角线为对称的矩阵称的矩阵不同结点间不同结点间, ,最多有最多有一条边一条边. .以主对角线为对称以主对角线为对称的位置不会同时为的位置不会同时为1 1如果有边如果有边, , ,则也有边则也有边. . 或前件为假或前件为假 如果如果a aij ij=1,=1,且且a ajk jk=1,=1,则则a aik ik=1=1性质判定性质判定 从关系的有向

28、图从关系的有向图 从关系的矩阵从关系的矩阵若若R R A AB SB S B BC C T T B BC C 则有则有)()()()()()(TRSRTSRTRSRTSR证明证明 任取任取R R (ST) (ST) b(bBb(bBRRST)ST)b(bBb(bBRR(ST)ST)）b(bBb(bBRRS)S) (bB (bBRRT)T)b(bBb(bBRRS)S) b(bBb(bBRRT)T)RR SRSR T T(R(R S)(RS)(R T)T)所以所以R R (ST)=(R (ST)=(R S) S)(R(R T)T) R是从A到B的关系，则 RR II RAB2. R2. RC C的

29、有向图：是将的有向图：是将R R的有向图的所有边的方向颠的有向图的所有边的方向颠倒一下即可。倒一下即可。3. R3. RC C的矩阵的矩阵 M =(M M =(MR R) )T T 即为即为R R矩阵的转置。如矩阵的转置。如 1 0 1 00 0 0 11 0 1 1MR=34 0 0 0 1 0 1 0 1 143 1 0 1=MRc三三. .性质性质令令R R、S S都是从都是从X X到到Y Y的关系，则的关系，则 1. (R1. (RC C) )C C = R= R 2. (RS) 2. (RS)C C = R = RC CSSC C 。 3. (RS) 3. (RS)C C = R =

30、 RC CSSC C 。 4. (R 4. (RS) S)C C = R = RC CS SC C 。5. R5. R S S R RC C S SC C 。6.(R)6.(R)C C=R=RC C7.7.令令R R是从是从X X到到Y Y的关系，的关系，S S是是Y Y到到 Z Z的关系，则的关系，则 (R (R S)S)C C= S= SC C R RC C 。 ( (注意注意RRC C S SC C ) )8. R8. R是是A A上关系，则上关系，则 R R是对称的，当且仅当是对称的，当且仅当 R RC C =R =R R R是反对称的，当且仅当是反对称的，当且仅当 RRRRC C I

31、 IA A。四四. .性质性质定理定理5.5. R R是是A A上关系，则上关系，则 R R是自反的，当且仅当是自反的，当且仅当 r(R)=R. r(R)=R. R R是对称的，当且仅当是对称的，当且仅当 s(R)=R. s(R)=R. R R是传递的，当且仅当是传递的，当且仅当 t(R)=R. t(R)=R.定理定理6 6. . R R是是A A上关系，则上关系，则 R R是自反的，则是自反的，则s(R)s(R)和和t(R)t(R)也自反。也自反。 R R是对称的，则是对称的，则r(R)r(R)和和t(R)t(R)也对称。也对称。 R R是传递的，则是传递的，则r(R)r(R)也传递。也传递。定理定理7 7：设设R R1 1、R R2 2是是A A上关系，如果上关系，如果R R1 1 R R2 2 ，则，则 r(Rr(R1 1) ) r(Rr(R2 2) ) s(Rs(R1 1) ) s(Rs(R2 2) ) t(Rt(R1 1) ) t(Rt(R2 2) ) 证明证明 r(Rr(R1 1)=I)=IA ARR1 1 I IA ARR2 2= r(Rr(R2 2) ) ，类似可证。，类似可证