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

《离散数学重要公式定理汇总.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、大一上离散数学重要公式定理汇总2021/10/82基本的等价公式⑴对合律PP⑵幂等律P∨PPP∧PP⑶结合律P∨(Q∨R)(P∨Q)∨RP∧(Q∧R)(P∧Q)∧R⑷交换律P∨QQ∨PP∧QQ∧P⑸分配律P∨(Q∧R)(P∨Q)∧(P∨R)P∧(Q∨R)(P∧Q)∨(P∧R)⑹吸收律P∨(P∧Q)PP∧(P∨Q)P⑺德．摩根定律(P∨Q)P∧Q(P∧Q)P∨QFormula2021/10/83⑻同一律P∨FPP∧TP⑼零律P∨TTP∧FF⑽互补律P∨PTP∧PF附加：⑾P

2、QP∨Q⑿PQQP⒀PQ(PQ)∧(QP)⒁PQ(P∨Q)∧(P∨Q)⒂PQ(P∧Q)∨(P∧Q)Formula2021/10/84等价公式(前10个)与集合论的公式比较：⑴对合律~~AA~A表示A的绝对补集⑵幂等律A∪AAA∩AA⑶结合律A∪(B∪C)(A∪B)∪C；A∩(B∩C)(A∩B)∩C⑷交换律A∪BB∪AA∩BB∩A⑸分配律A∪(B∩C)(A∪B)∩(A∪C)A∩(B∪C)(A∩B)∪(A∩C)⑹吸收律A∪(A∩B)AA∩(A∪B)AFormula2021

3、/10/85⑺德．摩根定律~(A∪B)~A∩~B~(A∩B)~A∪~B⑻同一律A∪ΦA;A∩EAE表示全集⑼零律A∪EEA∩ΦΦ⑽否定律A∪~AEA∩~AΦFormula2021/10/86Definition永真(重言)式（Tautology）公式中的命题变量元论怎样指派，公式对应的真值恒为T。永假（矛盾）式（Contradiction)公式中的命题变量无论怎样代入，公式对应的真值恒为F。可满足公式（Satisfaction）公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为T。一般命题公式（Conti

4、ngency）既不是永真公式也不是永假公式。2021/10/873.重要的重言蕴含式(如教材第43页所示)I1.P∧QP,I2.P∧QQI3.PP∨QI4.QP∨QI5.PPQI6.QPQI7.(PQ)PI8.(PQ)QI9.P,QP∧QI10.P∧(P∨Q)QI11.P∧(PQ)QI12.Q∧(PQ)PI13.(PQ)∧(QR)PRI14.(P∨Q)∧(PR)∧(QR)RI15.AB(A∨C)(B∨C)I16.AB(A∧C)(B∧C)Formula20

5、21/10/88蕴含的性质*若AB且A为重言式，则B必为重言式*若AB且BC，则AC(传递性)*若AB且AC，则A(B∧C)*若AB且CB，则(A∨C)B证明见书P22Formula2021/10/89conjunction一、全功能真值表PQC1C2C3C4C5C6C7C8TTTFTTFFTFTFTFTFFTFTFTTFFTTFFTFFTFFFTTFTPQC9C10C11C12C13C14C15C16TTTFTFTFTFTFTFFTFTTFFTTFTFFTFTFFFTTFTFTF↓∨∧↑PQQP2021

6、/10/8103.析取范式与合取范式的化法化成限定性公式。公式E16PQP∨Q公式E21PQ(P∧Q)∨(P∧Q)公式E20PQ(PQ)∧(QP)公式E16PQ(P∨Q)∧(P∨Q)将否定联结词移到命题变量的前面。A(P1,P2,…,Pn)A*(P1,P2,…,Pn)(P∨Q)P∧Q、(P∧Q)P∨Q用分配律、幂等律等公式进行整理，使之成为所要求的形式。normalform2021/10/811主析取范式定义析取范式A1∨A2∨...∨An,,其中每个Ai(i=1,2..n

7、)都是小项，称之为主析取范式。思考：主析取范式与析取范式的区别是什么？主析取范式的写法方法Ⅰ：列真值表⑴列出给定公式的真值表。⑵找出真值表中每个“T”对应的真值指派再对应的小项。⑶用“∨”联结上述小项，即可。normalform2021/10/812主合取范式定义合取范式A1∧A2∧...∧An,,其中每个Ai(i=1,2..n)都是大项，称之为主合取范式。主合取范式的写法方法Ⅰ：列真值表⑴列出给定公式的真值表。⑵找出真值表中每个“F”对应的真值指派再对应的大项。⑶用“∧”联结上述大项，即可。normalform2021/10/

8、813BriefSummary第一章小结命题原子命题复合命题联结词命题公式永真式永真蕴涵式等价公式范式命题逻辑推理直接推理间接推理条件论证反证法析取合取主析取主合取知识网络：2021/10/814如果Ｂ是个不含客体变元x的谓词公式，且不在x和x的辖域内，可以