《命题演算》PPT课件

5/15/202012:47AM,DerenChen,ZhejiangUniv.,1,1.2命题演算PropositionalEquivalences,5/15/202012:47AM,DerenChen,ZhejiangUniv.,2,1、命题(Proposition)2、从简单命题(atomicproposition)到复合命题(compositionalproposition)3、从命题常量(propositionalconstant)到命题变量(propositionalvariable)4、从复合命题(compositionalproposition)到命题公式(propositionalformulas),5/15/202012:47AM,DerenChen,ZhejiangUniv.,3,永真命题公式（Tautology）公式中的命题变量无论怎样代入，公式对应的真值恒为T。永假命题公式（Contradiction)公式中的命题变量无论怎样代入，公式对应的真值恒为F。可满足命题公式（Satisfaction）公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为T。一般命题公式（Contingency）既不是永真公式也不是永假公式。,5/15/202012:47AM,DerenChen,ZhejiangUniv.,4,EXAMPLE1,Wecanconstructexamplesoftautologiesandcontradictionsusingjustoneproposition.Considerthetruthtablesofppandpp,showninTable1.Sinceppisalwaystrue,itisatautology.Sinceppisalwaysfalse,itisacontradiction.,5/15/202012:47AM,DerenChen,ZhejiangUniv.,5,Table1,5/15/202012:47AM,DerenChen,ZhejiangUniv.,6,DEFINITION2,Thepropositionspandqarecalledlogicallyequivalentifpqisatautotogy.Thenotationpqdenotesthatpandqarelogicallyequivalent.,逻辑等值，或逻辑等价,5/15/202012:47AM,DerenChen,ZhejiangUniv.,7,EXAMPLE2,Showthat(pq)andpqarelogicallyequivalent.ThisequivalenceisoneofDeMorganslawsforpropositions,namedaftertheEnglishmathematicianAugustusDeMorgan,ofthemid-nineteenthcentury.,Solution:ThetruthtablesforthesepropositionsaredisplayedinTable2.Sincethetruthvaluesofthepropositions(pq)andpqagreeforallpossiblecombinationsofthetruthvaluesofpandq,itfollowsthatthesepropositionsarelogicallyequivalent.,5/15/202012:47AM,DerenChen,ZhejiangUniv.,8,Table2,5/15/202012:47AM,DerenChen,ZhejiangUniv.,9,EXAMPLE3,Showthatthepropositionspqandpqarelogicallyequivalent.,Solution:WeconstructthetruthtableforthesepropositionsinTable3.Sincethetruthvaluesofpqandpqagree,thesepropositionsarelogicallyequivalent.,5/15/202012:47AM,DerenChen,ZhejiangUniv.,10,Table3,5/15/202012:47AM,DerenChen,ZhejiangUniv.,11,EXAMPLE4,Showthatthepropositionsp(qr)and(pq)(pr)arelogicallyequivalent.Thisisthedistributivelawofdisjunctionoverconjunction.,Solution:WeconstructthetruthtableforthesepropositionsinTable4.Sincethetruthvaluesofp(qr)and(pq)(pr)agree,thesepropositionsarelogicallyequivalent.,5/15/202012:47AM,DerenChen,ZhejiangUniv.,12,Table4,5/15/202012:47AM,DerenChen,ZhejiangUniv.,13,基本逻辑等价定理：对于任意的命题公式p、q、r，下面的命题公式是等价的。,5/15/202012:47AM,DerenChen,ZhejiangUniv.,14,Table5,5/15/202012:47AM,DerenChen,ZhejiangUniv.,15,Table6,p(pq)pAbsorptionLaws/吸收律p(pq)ppqpqpq(pq)(qp),5/15/202012:47AM,DerenChen,ZhejiangUniv.,16,EXAMPLE5,Showthat(p(pq)andpqarelogicallyequivalent.,5/15/202012:47AM,DerenChen,ZhejiangUniv.,17,EXAMPLE6,Showthat(pq)(pq)isatautology.,5/15/202012:47AM,DerenChen,ZhejiangUniv.,18,判断命题公式逻辑等价的方法：1、真值表2、命题公式的演算基本等值定理；公式的代入不变性；等值关系的传递性。,5/15/202012:47AM,DerenChen,ZhejiangUniv.,19,命题公式逻辑等价关系的应用：1、判定是否逻辑等价；2、判断是否为永真公式或永假公式；3、命题公式的化简,5/15/202012:47AM,DerenChen,ZhejiangUniv.,20,Example7,什麽，如果她不来那么我也不去，没有那回事。,P：她来。Q：我去。,5/15/202012:47AM,DerenChen,ZhejiangUniv.,21,进一步的思考：一、命题公式的对偶性及其对偶处理。,5/15/202012:47AM,DerenChen,ZhejiangUniv.,22,限定性命题公式：最多仅含有否定、析取、合取逻辑联结词的命题公式。命题公式P的对偶公式（Dual）：将P中的析取联结词换成合取联结词，合取联结词换成析取联结词，T换成F，F换成T（如果存在的话）。记为P*,5/15/202012:47AM,DerenChen,ZhejiangUniv.,23,对偶原理（DualityPrinciple)设P、Q是限定性命题公式。如果PQ则P*Q*,例：A：（PQ）QB：PQ,5/15/202012:47AM,DerenChen,ZhejiangUniv.,24,进一步的思考：二、命题公式中的逻辑联接词的极小完备性。,5/15/202012:47AM,DerenChen,ZhejiangUniv.,25,逻辑联接词组是功能完备的（FunctionallyComplete）：任一个命题公式都能够等价于仅包含这些逻辑联接词联结起来的公式。逻辑联接词组是极小功能完备的：是功能完备的并且不能少一个。,5/15/202012:47AM,DerenChen,ZhejiangUniv.,26,例2：否定和合取组成的逻辑联结词组是极小功能完备的。例3：否定和析取组成的逻辑联结词组是极小功能完备的。,例1：否定、析取、合取组成的逻辑联结词组是功能完备的，但不是极小功能完备的。,5/15/202012:47AM,DerenChen,ZhejiangUniv.,27,进一步的思考：三、命题公式的进一步分类。,命题公式的标准化-范式,5/15/202012:47AM,DerenChen,ZhejiangUniv.,28,文字（literal）/符号（symbol）：原子命题或其否定小项（smallitem）/合取式（conjunctiveform）:若干个文字的合取。大项（largeitem）/析取式（disjunctiveform）:若干个文字的析取。,5/15/202012:47AM,DerenChen,ZhejiangUniv.,29,合取范式（conjunctivenormalform):若干个大项的合取。析取范式（disjunctivenormalform):若干个小项的析取。标准句(standardsentence)：合取范式或析取范式子句（clause）:合取范式中的大项或析取范式中的小项。,5/15/202012:47AM,DerenChen,ZhejiangUniv.,30,定理1：任意一个命题公式都存在与之等价的合取范式和析取范式。,定理的证明思路：1、化成限定性公式；2、将否定联结词移到命题变量的前面；3、消除多余的否定联结词；4、化成合取范式和析取范式。,5/15/202012:47AM,DerenChen,ZhejiangUniv.,31,定理1的作用与局限：1、标准化但仅仅是初步的#标准化的形式#不唯一性2、能够判定是否为永真或永假公式但不方便,5/15/202012:47AM,DerenChen,ZhejiangUniv.,32,定理2：一个命题公式是永真公式当且仅当与它等价的合取范式的每一个大项中包含了一个命题变量和它的否定；一个命题公式是永假公式当且仅当与它等价的析取范式的每一个小项中包含了一个命题变量和它的否定；,5/15/202012:47AM,DerenChen,ZhejiangUniv.,33,令A（a1、a2、an）包含有n个变量的公式，极小项(extremal):小项中恰包含n个变量或其否定。极大项(extremal):大项中恰包含n个变量或其否定。主合取范式（Uniqueconjunctivenormalform):若干个极大项的合取。主析取范式（Uniquedisjunctivenormalform):若干个极小项的析取。,5/15/202012:47AM,DerenChen,ZhejiangUniv.,34,定理3：令A（a1、a2、an）包含有n个变量的公式，则有：1、如果A存在与之等价的主析取范式，则必唯一；2、如果A存在与之等价的主合取范式，则必唯一；3、A是永真公式当且仅当与A等价的主析取范式恰有2n个极小项或没有主合取范式；4、A是永假公式当且仅当与A等价的主合取范式恰有2n个极大项或没有主析取范式；5、两个命题公式等价当且仅当它们有相同的主合取范式或相同的主析取范式。,5/15/202012:47AM,DerenChen,ZhejiangUniv.,35,例6张先生手中有代号为A、B、C、D、E的五种股票，根据当前股市情况及张先生本人的经济需求，需要有若干个股票抛出，但又必须满足如下复杂的要求：（1）若A