《命题演算》PPT课件

《《命题演算》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.2命题演算PropositionalEquivalences8/7/20211DerenChen,ZhejiangUniv.1、命题(Proposition)2、从简单命题(atomicproposition)到复合命题(compositionalproposition)3、从命题常量(propositionalconstant)到命题变量(propositionalvariable)4、从复合命题(compositionalproposition)到命题公式(propositionalformulas)

2、8/7/20212DerenChen,ZhejiangUniv.永真命题公式（Tautology）公式中的命题变量无论怎样代入，公式对应的真值恒为T。永假命题公式（Contradiction)公式中的命题变量无论怎样代入，公式对应的真值恒为F。可满足命题公式（Satisfaction）公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为T。一般命题公式（Contingency）既不是永真公式也不是永假公式。8/7/20213DerenChen,ZhejiangUniv.EXAMPLE1Wecancons

3、tructexamplesoftautologiesandcontradictionsusingjustoneproposition.Considerthetruthtablesofp∨pandp∧p,showninTable1.Sincep∨pisalwaystrue,itisatautology.Sincep∧pisalwaysfalse,itisacontradiction.8/7/20214DerenChen,ZhejiangUniv.Table18/7/20215DerenChen,Zhejiang

4、Univ.DEFINITION2Thepropositionspandqarecalledlogicallyequivalentifpqisatautotogy.Thenotationpqdenotesthatpandqarelogicallyequivalent.逻辑等值，或逻辑等价8/7/20216DerenChen,ZhejiangUniv.EXAMPLE2Showthat(p∨q)andp∧qarelogicallyequivalent.ThisequivalenceisoneofDeMorgan's

5、lawsforpropositions,namedaftertheEnglishmathematicianAugustusDeMorgan,ofthemid-nineteenthcentury.Solution:ThetruthtablesforthesepropositionsaredisplayedinTable2.Sincethetruthvaluesofthepropositions(p∨q)andp∧qagreeforallpossiblecombinationsofthetruthvaluesof

6、pandq,itfollowsthatthesepropositionsarelogicallyequivalent.8/7/20217DerenChen,ZhejiangUniv.Table28/7/20218DerenChen,ZhejiangUniv.EXAMPLE3Showthatthepropositionsp→qandp∨qarelogicallyequivalent.Solution:WeconstructthetruthtableforthesepropositionsinTable3.Sin

7、cethetruthvaluesofp∨qandp→qagree,thesepropositionsarelogicallyequivalent.8/7/20219DerenChen,ZhejiangUniv.Table38/7/202110DerenChen,ZhejiangUniv.EXAMPLE4Showthatthepropositionsp∨(q∧r)and(p∨q)∧(p∨r)arelogicallyequivalent.Thisisthedistributivelawofdisjunctiono

8、verconjunction.Solution:WeconstructthetruthtableforthesepropositionsinTable4.Sincethetruthvaluesofp∨(q∧r)and(p∨q)∧(p∨r)agree,thesepropositionsarelogicallyequivalent.8/7/202111DerenChen,ZhejiangUniv.Tab