离散数学-命题逻辑.ppt

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

1、第一章数理逻辑一命题逻辑命题及其表示法联结词命题公式与翻译真值表与等价式等价式与蕴含式对偶与范式推理理论二谓词逻辑谓词的概念与表示命题函数与量词谓词公式与翻译变元的约束谓词演算的等价式与蕴含式前束范式谓词演算的推理理论本章作业真值表与等价公式定义1-4、1在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。例1构造┒P∨Q的真值表。例2给出(P∧Q)∧┒P的真值表。例3给出(P∧Q)∨(┒P∧┒Q)的真值表。例4给出┒(P∧Q)⇄(┒P∨┒Q)的真值表。等价式和蕴涵式一、几个定义与定理定义1-5、1给定

2、一命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称该命题公式为重言式或永真公式。定义1-5、2给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称该命题公式为矛盾式或永假公式。定理1-5、1任何两个重言式的合取或析取，仍然是一个重言式。证明：设A和B为两个重言式，则不论A和B的分量指派任何真值，总有A为T，B为T，故A∧B⇔T,A∨B⇔T。定理：一个重言式，对同一分量都用任何合式公式置换，其结果仍为一个重言式。证明：由于重言式的真值与分量的指派无关，故对同一分量以任何合式公式置换后，重言式的真值仍永为T。定义1-4、2给定两个命题公式A和B，

3、设P1，P2，…，Pn为所有出现于A和B中的原子变元，若给P1，P2，…，Pn任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等。记作A⇔B。例5证明P⇄Q⇔(P→Q)∧(Q→P)定理：设A、B为两个命题公式，A⇔B当且仅当A⇄B为一个重言式。等价式下表列出的命题定律，都可以用真值表予以验证。10否定律9零律8同一律7德·摩根律6吸收律5分配律4交换律3结合律2幂等律1רר对合律补充：其它常用等价公式(1)P→Q⇔┒P∨Q(2)P⇄Q⇔(P→Q)∧(Q→P)⇔┒P⇄┒Q(3)(P→Q)∧(P→┒Q)⇔┒P(归缪论)(4)P→Q⇔┒Q→┒P(逆反式)我们称

4、Q→P为逆换式，称┒P→┒Q为反换式定义1-4、3如果X是合式公式A的一部分，且X本身也是一个合式公式，则称X为公式A的子公式。定理1-4、1设X是合式公式A的子公式，若X⇔Y，如果将A中的X用Y来置换，所得到的公式B与公式A等价，即A⇔B。证明：因为在相应变元的任一种指派情况下，X与Y的真值相同，故以Y取代X后，公式B与公式A在相应的指派情况下，其真值亦必相同，故A⇔B。注：满足定理1-4、1条件的置换称为等价置换（等价代换）。例题7证明Q→(P∨(P∧Q))⇔Q→P例题8证明(P∧Q)∨(P∧┒Q)⇔P例题9证明P→(Q→R)⇔Q→(P→R)⇔┒R→(Q→┒P)例

5、题10证明((P∨Q)∧┒(┒P∧(┒Q∨┒R)))∨(┒P∧┒Q)∨(┒P∧┒R)⇔T下一节例7证明设A：因为故B：即例8证明例9证明又，例10证明原式左边例1解TTFFTTTFFFFTTFTT┒P∨Q┒PQP例2解TTFF┒PFFFFFFTFFFFTFTTT(P∧Q)∧┒PP∧QQP例3解TFFF┒P∧┒QFFFTP∧QTFTF┒QTTFFFTTFFFFTTFTT(P∧Q)∨(┒P∧┒Q)┒PQP例4解TTTF┒P∨┒QTFTF┒QTTFF┒PTTTF┒(P∧Q)TFFFTFTFTFFTTTTT┒(P∧Q)⇄(┒P∨┒Q)P∧QQP例5解:TFFTTFTTTTFF

6、FTTFFFFTTTTTQP定义：当且仅当P→Q是一个重言式时，我们称“P蕴含Q”，并记作P⇒Q。注意：区别条件与蕴含，同时，二者存在联系.定理：设P，Q为任意两个命题公式，P⇔Q的充分必要条件是P⇒Q且Q⇒P。证明：若P⇔Q，则P⇄Q为重言式，因为P⇄Q⇔(P→Q)∧(Q→P)故P→Q为T且Q→P为T，即P⇒Q，Q⇒P成立。反之，若P⇒Q且Q⇒P，则P→Q为T且Q→P为T，因此P⇄Q为T，P⇄Q是重言式，即P⇔Q。证毕。蕴含式二、蕴含有下面几个常用的性质：（1）设A、B、C为合式公式，若A⇒B且A是重言式，则B必是重言式。（2）若A⇒B，B⇒C，则A⇒C，即蕴含关系

7、是传递的。（3）若A⇒B且A⇒C，那么A⇒(B∧C)（4）若A⇒B且C⇒B，则A∨C⇒B三、下表所列各蕴含式都可推理证明。1413121110987654321重言式、等价式与蕴涵式的证明：例题1证明((P∨S)∧R)∨┒((P∨S)∧R)为重言式。例题2证明┒(P∧Q)⇔(┒P∨┒Q)例题3推证┒Q∧(P→Q)⇒┒PBACK例题1证明因为P∨┒P⇔T，如以((P∨S)∧R)置换P即得((P∨S)∧R)∨┒((P∨S)∧R)⇔T例题2证明由上节例题4表可知，┒(P∧Q)⇄(┒P∨┒Q)为重言式，故根据定理1-5、3：┒(P∧Q)⇔(┒P∨┒Q)例题3