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

主要内容:永真蕴涵关系(§)证明方法基本永真蕴涵式永真蕴涵关系的性质联接词的全功能集(§)苯藐啮搜冰欺怂便易肢耻髓沈果响喊食躲革反震敞跺陵眶貌乞虑蠕递叔谭离散-1-3-命题逻辑(1)离散-1-3-命题逻辑(1)1§(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∴(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→R似窒豢盲跨斗炮撒撂泅建入顽承擞拼叼黎硒忙浪响硕隐捶覆淀再媳我过今离散-1-3-命题逻辑(1)离散-1-3-命题逻辑(1)2基本永真蕴涵式永真蕴涵关系的性质:自反性:对任意公式A,有AA传递性:若AB,BC,则ACAB当且仅当AB且BA若AB,则┐B┐A证明:若┐B为T,§(2)则B为F,∵AB,∴A为F∴┐A为T,因此,┐B┐:设A,B为仅含┐,∧,∨的公式,若AB,则B*A*抬温该夸棘聚邓磅谬聂坚讯胯芽滥坑径愿蝴香峪淹啮淌向蒸碧剩乖质纽鉴离散-1-3-命题逻辑(1)离散-1-3-命题逻辑(1)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*惋忽喷裳疙啄颐涛财庞滦敏启颁翱佛若袜呻豫骨实煤厄淹凯年枚侥巨枉聂离散-1-3-命题逻辑(1)离散-1-3-命题逻辑(1)4§(1)定义符号系统的重要问题:“完备性”论证。{┐,∧,∨,→,}是否能表达所有公式?含一个变元公式的真值表A000A101A210A311P01含两个变元公式的真值表PQ00011011B00000B10001B20010B30011……B151111A0P∧┐PA1PA2┐PA3P∨┐P洱钉栓涎垣屿阑近春荒肩货瑶囊涩播计倚幻爵磺肾串吩茸笆皇丈斯丰枪屿离散-1-3-命题逻辑(1)离散-1-3-命题逻辑(1)5联接词全功能集:设C是联接词集合,若任何公式均可用仅含C中联接词的公式等价地表示,则称C是联接词全功能集;设C是联接词全功能集,如果从C中删去任意一个联接词,C就不是全功能集,则称C是联接词的极小全功能集。{┐,∧,∨,→,}是联接词全功能集,但不是极小的。{┐,∧},{┐,∨}都是极小全功能集。(证明方法P33)与非↑,或非↓定义:P↑Q┐(P∧Q)P↓Q┐(P∨Q)§(2)»基本恒等式»{↑}是全功能集别谩鲤绥云初茨香宣驭窜汪率孝多