《02 第二次课(命题演算).ppt》由会员分享,可在线阅读,更多相关《02 第二次课(命题演算).ppt(27页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 第一章第一章 -数理逻辑数理逻辑问题:问题:问题:问题:1.什么是命题?什么是命题?2.命题必须具备的两个条件是什么?命题必须具备的两个条件是什么?3.判断下面是不是命题:判断下面是不是命题:1)春蚕到死丝方尽。)春蚕到死丝方尽。2)考试一定要抄袭!)考试一定要抄袭!3)暮春三月,江南草长。暮春三月,江南草长。12/31/20221Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional
2、 Equivalences命题演算命题演算命题演算命题演算 How can the following English sentence be translated into a logical expression?You can access the Internet from campus only if you are a computer science major or you are not a freshman,Solution:a (c f ).第一章第一章 -数理逻辑数理逻辑12/31/20222Hongzhi Qiao,Xidian Univ.Propositional
3、EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 原子命题或加上逻辑联结词组成的表达式成为复合命题原子命题或加上逻辑联结词组成的表达式成为复合命题(Compositional Proposition)。)。第一章第一章 -数理逻辑数理逻辑P、Q、R 称为原子命题(称为原子命题(Atomic Proposition)。)。12/31/20223Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 第一章第
4、一章 -数理逻辑数理逻辑命题公式:命题公式:1、原子命题是命题公式;、原子命题是命题公式;2、设、设P是命题公式,则是命题公式,则 P 也是命题公式;也是命题公式;3、设、设P、Q是命题公式,则是命题公式,则 P、(、(P Q)、)、(P Q)、)、(P Q)、()、(P Q)也是命题公式;)也是命题公式;4、有限次地使用、有限次地使用1、2、3所得到的也是命题公式。所得到的也是命题公式。12/31/20224Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算
5、 命题公式的运算规则:命题公式的运算规则:逻辑联接词的优先级:逻辑联接词的优先级:、命题公式的表达式的运算规律:命题公式的表达式的运算规律:同代数表达式同代数表达式命题公式的运算方法:命题公式的运算方法:所有公式中的命题变量用指定命题(真值)代入(或指派)所有公式中的命题变量用指定命题(真值)代入(或指派),得到一个公式对应的真值。,得到一个公式对应的真值。第一章第一章 -数理逻辑数理逻辑12/31/20225Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算
6、 性质性质1 1:如果一个命题公式有如果一个命题公式有N个互异的命题变量,则个互异的命题变量,则命题公式对应的真值有命题公式对应的真值有2的的N次幂种可能分布。次幂种可能分布。第一章第一章 -数理逻辑数理逻辑12/31/20226Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 永真命题公式(永真命题公式(Tautology)公式中的命题变量无论怎样代入,公式对应的真值恒为公式中的命题变量无论怎样代入,公式对应的真值恒为T。第一章第一章 -数理逻辑数理逻辑可
7、满足命题公式(可满足命题公式(Satisfaction)公式中的命题变量无论怎样代入,公式对应的真值总有公式中的命题变量无论怎样代入,公式对应的真值总有一种情况为一种情况为T。永假命题公式(永假命题公式(Contradiction)公式中的命题变量无论怎样代入,公式对应的真值恒为公式中的命题变量无论怎样代入,公式对应的真值恒为F。12/31/20227Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 性质性质2 2:(1)设)设P是永真命题公式,则是永真命题
8、公式,则P的否定公式是永假命题公式的否定公式是永假命题公式(2)设)设P是永假命题公式,则是永假命题公式,则P的否定公式是永真命题公式的否定公式是永真命题公式(3)设)设P、Q是永真命题公式,则(是永真命题公式,则(P Q)、)、(P Q)、()、(P Q)、()、(P Q)也是永真命题公式也是永真命题公式 第一章第一章 -数理逻辑数理逻辑12/31/20228Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 如果一个公式,对于它的任一解释如果一个公式,对于
9、它的任一解释I I下其下其真值都为真,就称为重言式(永真式)。如真值都为真,就称为重言式(永真式)。如p pp p是一个重言式。是一个重言式。显然由显然由 、和和 联结的联结的重言式仍是重言式。重言式仍是重言式。第一章第一章 -数理逻辑数理逻辑12/31/20229Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 举例:证明举例:证明P(Q(PQ)是重言式是重言式第一章第一章 -数理逻辑数理逻辑P Q (PQ)(Q(PQ)P(Q(PQ)F F F T T T
10、 F F T T F T F F T T T T T T故故P(Q(PQ)是一个重言式。是一个重言式。证明:构造它的真值表,用来看是否在它的任一解释证明:构造它的真值表,用来看是否在它的任一解释I下其真下其真值都为真。值都为真。12/31/202210Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 The propositions p and q are called logically equivalent if p q is a tautotogy(重
11、言式重言式).The notation p q denotes that p and q are logically equivalent.逻辑等值,或逻辑等价逻辑等值,或逻辑等价第一章第一章 -数理逻辑数理逻辑12/31/202211Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 Show that (p q)and p q are logically equivalent.This equivalence is one of De Morgans la
12、ws for propositions,named after the English mathematician Augustus De Morgan,of the mid-nineteenth century.第一章第一章 -数理逻辑数理逻辑Solution:The truth tables for these propositions are displayed in Table 2.Since the truth values of the propositions (p q)and p q agree for all possible combinations of the trut
13、h values of p and q,it follows that these propositions are logically equivalent.12/31/202212Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 第一章第一章 -数理逻辑数理逻辑12/31/202213Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命
14、题演算命题演算 Show that the propositions pq and pq are logically equivalent.Solution:We construct the truth table for these propositions in Table 3.Since the truth values of p q and p q agree,these propositions are logically equivalent.第一章第一章 -数理逻辑数理逻辑12/31/202214Hongzhi Qiao,Xidian Univ.Propositional Equ
15、ivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 第一章第一章 -数理逻辑数理逻辑12/31/202215Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 基本逻辑等价定理:基本逻辑等价定理:对于任意的命题公式对于任意的命题公式p、q、r,下面的命题公下面的命题公式是等价的。式是等价的。(参看课本(参看课本P8 表表1.2-1 逻辑恒等式)逻辑恒等式)第一章第一章 -数理逻辑数理逻辑12/31/20221
16、6Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 永真蕴含式永真蕴含式AB 是永真式,是永真式,A永真蕴含永真蕴含B。永真蕴含式的证明:永真蕴含式的证明:1)真值表)真值表2)假定前件是真,若能推出后件是真,则此蕴含式是真。)假定前件是真,若能推出后件是真,则此蕴含式是真。假定后件是假,若能推出前件是假,则此蕴含式是真。假定后件是假,若能推出前件是假,则此蕴含式是真。第一章第一章 -数理逻辑数理逻辑12/31/202217Hongzhi Qiao,Xidi
17、an Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 两个性质:两个性质:1)逻辑恒等和永真蕴含都是传递的。)逻辑恒等和永真蕴含都是传递的。2)若)若A永真蕴含永真蕴含B,A永真蕴含永真蕴含C,则,则A永真蕴含永真蕴含B合取合取C 第一章第一章 -数理逻辑数理逻辑12/31/202218Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 代入规则代入规则 A是一
18、个公式是一个公式,对对A使用代入规则得公式使用代入规则得公式B,若若A是重言式是重言式,则则B也是重言式。也是重言式。为保证重言式经代入规则仍得到保持为保证重言式经代入规则仍得到保持,要求要求:1.公式中被代换的只能是命题变元(原子命题)公式中被代换的只能是命题变元(原子命题),而不能是复合命题。而不能是复合命题。2.对公式中某命题变项施以代入,必须对该公式中出现的所有同一命对公式中某命题变项施以代入,必须对该公式中出现的所有同一命题变项代换同一公式。题变项代换同一公式。常元(常元(T、F)变元(变元(A、B、C、。)、。)(重言式之值不依赖于(重言式之值不依赖于变元变元的值。)的值。)第一章
19、第一章 -数理逻辑数理逻辑12/31/202219Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 举例:使用代入规则证明重言式。举例:使用代入规则证明重言式。例例1:判断判断(RS)(RS)为重言式。为重言式。因因 P P为重言式为重言式,作代入作代入 便得便得(RS)(RS)。依据代入规则依据代入规则,这公式必是重言式。这公式必是重言式。第一章第一章 -数理逻辑数理逻辑12/31/202220Hongzhi Qiao,Xidian Univ.Propos
20、itional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 例例2:判断判断(RS)(RS)(PQ)(PQ)为重言为重言式式.证:不难验证证:不难验证(A(AB)B是重言式是重言式,作代入作代入 便知便知(RS)(RS)(PQ)(PQ)是重言式。是重言式。第一章第一章 -数理逻辑数理逻辑12/31/202221Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 替换规则:替换规则:A恒等于恒等于
21、B,如在公式,如在公式C中出现中出现A的地方,替换以的地方,替换以B(不必(不必每处必换)得到公式每处必换)得到公式D,则,则C恒等于恒等于D第一章第一章 -数理逻辑数理逻辑12/31/202222Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 Show that (p(p q)and p q are logically equivalent.第一章第一章 -数理逻辑数理逻辑12/31/202223Hongzhi Qiao,Xidian Univ.Prop
22、ositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 Show that(p q)(p q)is a tautology.第一章第一章 -数理逻辑数理逻辑12/31/202224Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 命题公式命题公式P的的对偶公式(对偶公式(Dual):将:将P中的中的 析取联结词换成合取联结词,析取联结词换成合取联结词,合取联结词换成析取联结词,合取联结
23、词换成析取联结词,T换成换成F,F换成换成T(如果存在的话)。如果存在的话)。记为记为P*第一章第一章 -数理逻辑数理逻辑12/31/202225Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 对偶式:对偶式:将将A中出现的中出现的、T、F分别以分别以、F、T代换代换,得得到公式到公式A*,则称则称A*是是A的对偶式的对偶式,或说或说A和和A*互为对偶式。互为对偶式。(PQ)R 的对偶式为的对偶式为(PQ)RPF 的对偶式为的对偶式为PT第一章第一章 -数理逻辑数理逻辑12/31/202226Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 对偶原理(对偶原理(Duality Principle)设设P、Q是命题公式。如果是命题公式。如果 P Q 则则 P*Q*第一章第一章 -数理逻辑数理逻辑12/31/202227Hongzhi Qiao,Xidian Univ.
限制150内