离散-2-1-命题逻辑(1).ppt

《离散-2-1-命题逻辑(1).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主要内容：永真蕴涵关系(§1.3)证明方法基本永真蕴涵式永真蕴涵关系的性质联接词的全功能集(§1.6)1.-吴扬扬制-§1.3永真式5.永真蕴涵关系(1)定义：若A→B是永真式，则称A永真蕴涵B，记作AB证明方法:真值表、等价推导、前真导后真、后假导前假例1：证明P∧(P→Q)Q证明：若P∧(P→Q)为T,则P为T且(P→Q)为T。∴Q也为T。因此，P∧(P→Q)→Q是永真式，故P∧(P→Q)Q。例2：证明(P→Q)∧(Q→R)P→R证明：若P→R为F,则P为T，R为F若Q为T，则Q→R为F∴(

2、P→Q)∧(Q→R)为F若Q为F，则P→Q为F∴(P→Q)∧(Q→R)为F∴((P→Q)∧(Q→R))→P→R永真，因此，(P→Q)∧(Q→R)P→R2.-吴扬扬制-基本永真蕴涵式永真蕴涵关系的性质：自反性：对任意公式A,有AA传递性：若AB,BC,则AC反对称性：AB当且仅当AB且BA如何证明反对称性?若AB,则┐B┐A证明：若┐B为T,§1.3永真式5.永真蕴涵关系(2)则B为F,∵AB,∴A为F∴┐A为T，因此，┐B┐A定理1.3.5:设A,B为仅含┐,∧,∨的公式，若A

3、B，则B*A*3.-吴扬扬制-定理:设A,B为仅含┐,∧,∨的公式，若AB，则B*A*证明：设P1,…,Pn为出现在A和B的所有变元，AB，则有┐B┐A∴┐B→┐A是永真式∵┐B→┐AB*(┐P1,…,┐Pn)→A*(┐P1,…,┐Pn)∴B*(┐P1,…,┐Pn)→A*(┐P1,…,┐Pn)永真。现用┐Pi取代Pi(1≤i≤n),得到上式的一个代入实例:B*(P1,…,Pn)→A*(P1,…,Pn)即B*→A*仍为永真式∴B*A*4.-吴扬扬制-§1.6联接词的全功能集(1)定义符号系

4、统的重要问题：“完备性”论证。{┐,∧,∨,→,}是否能表达所有公式？含一个变元公式的真值表A000A101A210A311P01含两个变元公式的真值表PQ00011011B00000B10001B20010B30011……B151111A0P∧┐PA1PA2┐PA3P∨┐P5.-吴扬扬制-联接词全功能集:设C是联接词集合，若任何公式均可用仅含C中联接词的公式等价地表示，则称C是联接词全功能集；设C是联接词全功能集，如果从C中删去任意一个联接词，C就不是全功能集，则称C是联接词的极小全功能集。

5、{┐,∧,∨,→,}是联接词全功能集，但不是极小的。{┐,∧}，{┐,∨}都是极小全功能集。(证明方法P33)与非↑，或非↓定义：P↑Q┐(P∧Q)P↓Q┐(P∨Q)§1.6联接词的全功能集(2)»基本恒等式»{↑}是全功能集6.-吴扬扬制-§1.6联接词的全功能集(3){↑},{↓}是极小全功能集.如何证明?证明:∵┐P┐(P∧P)(等幂律)P↑P(↑的定义)又∵P∧Q┐┐(P∧Q)(双重否定律)┐(P↑Q)(↑的定义)(P↑Q)↑(P↑Q)∴含{┐,∧}的公式均可用仅含联接词↑的公式

6、等价地表示,∵{┐,∧}是极小全功能集,∴{↑}也是极小全功能集.7.-吴扬扬制-作业：P175(1)(3)，8(2)(3)，P333(1)补充题：证明{↓}是极小全功能集。8.-吴扬扬制-基本永真蕴涵式：附加式：PP∨Q化简式：P∧QP假言推论：P∧(P→Q)Q假言三段论:(P→Q)∧(Q→R)P→R析取三段论:┐P∧(P∨Q)Q拒取式：┐Q∧(P→Q)┐P«蕴涵关系9.-吴扬扬制-基本逻辑恒等式（P9）双重否定律：┐┐PP补余律：┐P∨PT┐P∧PF等幂律：P∨PPP∧PP交换

7、律：P∨QQ∨PP∧QQ∧P结合律:(P∨Q)∨RP∨(Q∨R)(P∧Q)∧RP∧(Q∧R)分配律:P∧(Q∨R)(P∧Q)∨(P∧R)P∨(Q∧R)(P∨Q)∧(P∨R)德·摩根律:┐(P∨Q)┐P∧┐Q┐(P∧Q)┐P∨┐Q蕴涵等值式:P→Q┐P∨Q等价等值式:PQ(P→Q)∧(Q→P)零律：P∨TTP∧FF同一律：P∨FPP∧TP«全功能集10