第二次课(命题演算).ppt

《第二次课(命题演算).ppt》由会员分享，可在线阅读，更多相关《第二次课(命题演算).ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二次课第二次课(命题演算命题演算)Propositional EquivalencesPropositional 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 ).第一章第一章-数理

2、逻辑数理逻辑11/2/20222Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 原子命题或加上逻辑联结词组成的表达式成为复合命题原子命题或加上逻辑联结词组成的表达式成为复合命题（Compositional Proposition）。）。第一章第一章-数理逻辑数理逻辑P、Q、R 称为原子命题（称为原子命题（Atomic Proposition）。）。11/2/20223Hongzhi Qiao,Xidian Univ.Propositional Equiva

3、lencesPropositional Equivalences命题演算命题演算命题演算命题演算 第一章第一章-数理逻辑数理逻辑命题公式：命题公式：1、原子命题是命题公式；、原子命题是命题公式；2、设、设P是命题公式，则是命题公式，则 P 也是命题公式；也是命题公式；3、设、设P、Q是命题公式，则是命题公式，则 P、（、（P Q）、）、（P Q）、）、（P Q）、（）、（P Q）也是命题公式；）也是命题公式；4、有限次地使用、有限次地使用1、2、3所得到的也是命题公式。所得到的也是命题公式。11/2/20224Hongzhi Qiao,Xidian Univ.Propositional Equ

4、ivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 命题公式的运算规则：命题公式的运算规则：逻辑联接词的优先级：逻辑联接词的优先级：、命题公式的表达式的运算规律：命题公式的表达式的运算规律：同代数表达式同代数表达式命题公式的运算方法：命题公式的运算方法：所有公式中的命题变量用指定命题（真值）代入（或指派）所有公式中的命题变量用指定命题（真值）代入（或指派），得到一个公式对应的真值。，得到一个公式对应的真值。第一章第一章-数理逻辑数理逻辑11/2/20225Hongzhi Qiao,Xidian Univ.Propositional Equiv

5、alencesPropositional Equivalences命题演算命题演算命题演算命题演算 性质性质1 1：如果一个命题公式有如果一个命题公式有N个互异的命题变量，则个互异的命题变量，则命题公式对应的真值有命题公式对应的真值有2的的N次幂种可能分布。次幂种可能分布。第一章第一章-数理逻辑数理逻辑11/2/20226Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 永真命题公式（永真命题公式（Tautology）公式中的命题变量无论怎样代入，公式对应的

6、真值恒为公式中的命题变量无论怎样代入，公式对应的真值恒为T。第一章第一章-数理逻辑数理逻辑可满足命题公式（可满足命题公式（Satisfaction）公式中的命题变量无论怎样代入，公式对应的真值总有公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为一种情况为T。永假命题公式（永假命题公式（Contradiction)公式中的命题变量无论怎样代入，公式对应的真值恒为公式中的命题变量无论怎样代入，公式对应的真值恒为F。11/2/20227Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命

7、题演算命题演算命题演算命题演算 性质性质2 2：（1）设）设P是永真命题公式，则是永真命题公式，则P的否定公式是永假命题公式的否定公式是永假命题公式（2）设）设P是永假命题公式，则是永假命题公式，则P的否定公式是永真命题公式的否定公式是永真命题公式（3）设）设P、Q是永真命题公式，则（是永真命题公式，则（P Q）、）、（P Q）、（）、（P Q）、（）、（P Q）也是永真命题公式）也是永真命题公式 第一章第一章-数理逻辑数理逻辑11/2/20228Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalen

8、ces命题演算命题演算命题演算命题演算 如果一个公式，对于它的任一解释如果一个公式，对于它的任一解释I I下其下其真值都为真，就称为重言式（永真式）。如真值都为真，就称为重言式（永真式）。如p pp p是一个重言式。是一个重言式。显然由显然由 、和和 联结的联结的重言式仍是重言式。重言式仍是重言式。第一章第一章-数理逻辑数理逻辑11/2/20229Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 举例：证明举例：证明P(Q(PQ)是重言式是重言式第一章第一章

9、-数理逻辑数理逻辑P Q (PQ)(Q(PQ)P(Q(PQ)F F F T T T F F T T F T F F T T T T T T故故P(Q(PQ)是一个重言式。是一个重言式。证明：构造它的真值表，用来看是否在它的任一解释证明：构造它的真值表，用来看是否在它的任一解释I下其真下其真值都为真。值都为真。11/2/202210Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 The propositions p and q are called logi

10、cally equivalent if p q is a tautotogy(重言式重言式).The notation p q denotes that p and q are logically equivalent.逻辑等值，或逻辑等价逻辑等值，或逻辑等价第一章第一章-数理逻辑数理逻辑11/2/202211Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 Show that (p q)and p q are logically equivalent.Th

11、is equivalence is one of De Morgans laws 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

12、all possible combinations of the truth values of p and q,it follows that these propositions are logically equivalent.11/2/202212Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 第一章第一章-数理逻辑数理逻辑11/2/202213Hongzhi Qiao,Xidian Univ.Propositional EquivalencesP

13、ropositional Equivalences命题演算命题演算命题演算命题演算 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.第一章第一章-数理逻辑数理逻辑11/2/202214Hongzhi Qi

14、ao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 第一章第一章-数理逻辑数理逻辑11/2/202215Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 基本逻辑等价定理：基本逻辑等价定理：对于任意的命题公式对于任意的命题公式p、q、r，下面的命题公，下面的命题公式是等价的。式是等价的。（参看课本（参看课本P8 表表1.2-1 逻辑恒等式）逻辑

15、恒等式）第一章第一章-数理逻辑数理逻辑11/2/202216Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 永真蕴含式永真蕴含式AB 是永真式，是永真式，A永真蕴含永真蕴含B。永真蕴含式的证明：永真蕴含式的证明：1）真值表）真值表2）假定前件是真，若能推出后件是真，则此蕴含式是真。）假定前件是真，若能推出后件是真，则此蕴含式是真。假定后件是假，若能推出前件是假，则此蕴含式是真。假定后件是假，若能推出前件是假，则此蕴含式是真。第一章第一章-数理逻辑数理逻辑1

16、1/2/202217Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 两个性质：两个性质：1）逻辑恒等和永真蕴含都是传递的。）逻辑恒等和永真蕴含都是传递的。2）若）若A永真蕴含永真蕴含B，A永真蕴含永真蕴含C，则，则A永真蕴含永真蕴含B合取合取C 第一章第一章-数理逻辑数理逻辑11/2/202218Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算

17、命题演算命题演算命题演算 代入规则代入规则 A是一个公式是一个公式,对对A使用代入规则得公式使用代入规则得公式B,若若A是重言式是重言式,则则B也是重言式。也是重言式。为保证重言式经代入规则仍得到保持为保证重言式经代入规则仍得到保持,要求要求:1.公式中被代换的只能是命题变元（原子命题）公式中被代换的只能是命题变元（原子命题）,而不能是复合命题。而不能是复合命题。2.对公式中某命题变项施以代入，必须对该公式中出现的所有同一命对公式中某命题变项施以代入，必须对该公式中出现的所有同一命题变项代换同一公式。题变项代换同一公式。常元（常元（T、F）变元（变元（A、B、C、。）、。）（重言式之值不依赖于

18、（重言式之值不依赖于变元变元的值。）的值。）第一章第一章-数理逻辑数理逻辑11/2/202219Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 举例：使用代入规则证明重言式。举例：使用代入规则证明重言式。例例1:判断判断(RS)(RS)为重言式。为重言式。因因 P P为重言式为重言式,作代入作代入 便得便得(RS)(RS)。依据代入规则依据代入规则,这公式必是重言式。这公式必是重言式。第一章第一章-数理逻辑数理逻辑11/2/202220Hongzhi Qi

19、ao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 例例2：判断判断(RS)(RS)(PQ)(PQ)为重言式为重言式.证：不难验证证：不难验证(A(AB)B是重言式是重言式,作代入作代入 便知便知(RS)(RS)(PQ)(PQ)是重言式。是重言式。第一章第一章-数理逻辑数理逻辑11/2/202221Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演

20、算 替换规则：替换规则：A恒等于恒等于B，如在公式，如在公式C中出现中出现A的地方，替换以的地方，替换以B（不必（不必每处必换）得到公式每处必换）得到公式D，则，则C恒等于恒等于D第一章第一章-数理逻辑数理逻辑11/2/202222Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 Show that (p(p q)and p q are logically equivalent.第一章第一章-数理逻辑数理逻辑11/2/202223Hongzhi Qiao,X

21、idian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 Show that(p q)(p q)is a tautology.第一章第一章-数理逻辑数理逻辑11/2/202224Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 命题公式命题公式P的的对偶公式（对偶公式（Dual）：将：将P中的中的 析取联结词换成合取联结词，析取联结词换成合取联结词，合取联结

22、词换成析取联结词，合取联结词换成析取联结词，T换成换成F，F换成换成T（如果存在的话）。（如果存在的话）。记为记为P*第一章第一章-数理逻辑数理逻辑11/2/202225Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 对偶式：对偶式：将将A中出现的中出现的、T、F分别以分别以、F、T代换代换,得得到公式到公式A*,则称则称A*是是A的对偶式的对偶式,或说或说A和和A*互为对偶式。互为对偶式。(PQ)R 的对偶式为的对偶式为(PQ)RPF 的对偶式为的对偶式为PT第一章第一章-数理逻辑数理逻辑11/2/202226Hongzhi Qiao,Xidian Univ.Propositional EquivalencesPropositional Equivalences命题演算命题演算命题演算命题演算 对偶原理（对偶原理（Duality Principle)设设P、Q是命题公式。如果是命题公式。如果 P Q 则则 P*Q*第一章第一章-数理逻辑数理逻辑11/2/202227Hongzhi Qiao,Xidian Univ.