离散数学 命题逻辑2.ppt

《离散数学 命题逻辑2.ppt》由会员分享，可在线阅读，更多相关《离散数学 命题逻辑2.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1真值表真值表真值表真值表逻辑等价逻辑等价逻辑等价逻辑等价永真蕴涵永真蕴涵永真蕴涵永真蕴涵2命题公式的真值表命题公式的真值表对命题公式中各分量（命题变元）对命题公式中各分量（命题变元）指派所有可能的真值，以及由此而指派所有可能的真值，以及由此而确定的命题公式的真值汇列而成的确定的命题公式的真值汇列而成的表称为真值表。表称为真值表。3真值表示例真值表示例1P Q的真值表的真值表PQPP Q00110111100011014真值表示例真值表示例2(P Q)P的真值表的真值表PQP Q(P Q)PFFFTFTFTTFFTTTTT5真值表示例真值表示例3构成构成(P Q)R的真值表的真值表PQRP Q

2、(P Q)R00001001010100101101100011010111010111116真值表结论真值表结论含有含有n个命题变元的命题公式中，个命题变元的命题公式中，n个变元共有？组不同的取值？个变元共有？组不同的取值？回答：回答：2n组组7永真式和永假式永真式和永假式永真式永真式(重言式重言式)在命题变元的不同指派下，真值总是在命题变元的不同指派下，真值总是真的命题公式，记为真的命题公式，记为1或或T永假式永假式(矛盾式矛盾式)在命题变元的不同指派下，真值总是在命题变元的不同指派下，真值总是假的命题公式，记为假的命题公式，记为0或或F8永真式举例永真式举例(P Q)P的真值表的真值表P

3、QP Q(P Q)P1001010110011111(P Q)P是永真式是永真式9永假式举例永假式举例(P Q)P)的真值表的真值表PQP Q(P Q)P)0000010010001110(P Q)P)是永假式是永假式10逻辑等价逻辑等价在真值表中，两个命题公式在真值表中，两个命题公式A和和B 在分量的不同指派下，其在分量的不同指派下，其真值总是真值总是相同相同的，则称这两个命题公式的，则称这两个命题公式A和和B是是逻辑等价逻辑等价的的记做记做AB11逻辑等价例逻辑等价例1证明证明P Q PQPQP QPQ001101111000111112逻辑等价例逻辑等价例2证明证明 PQ(P Q)(Q

4、P)PQ(P Q)(Q P)PQ000001111011110013常用的逻辑等价公式常用的逻辑等价公式(1)PQ P QPQ(PQ)(QP)(P Q)(P Q)PQ(P Q)(Q P)14常用的逻辑等价公式常用的逻辑等价公式(2)P P (对合律对合律)(P Q)R P(Q R)(结合律结合律)(P Q)R P(Q R)P Q Q P (交换律交换律)P Q Q PP(Q R)(P Q)(P R)(分配律分配律)P(Q R)(P Q)(P R)P(P Q)P (吸收律吸收律)P(P Q)P15常用的逻辑等价公式常用的逻辑等价公式(3)(P Q)P Q (摩根律摩根律)(P Q)P Q P P

5、 P (等幂律等幂律)P P P P 0 P (同一律同一律)P 1 P P 1 1 (零律零律)P 0 0 P P 1 (否定律否定律)P P 016代换规则代换规则设命题公式设命题公式A和和B逻辑等价，即逻辑等价，即AB，如果在命题公式如果在命题公式C中出现中出现A的地方用的地方用B替换后替换后(不一定是每一处不一定是每一处)得到命题得到命题公式公式D则则CD。17代换规则示例代换规则示例1证明证明P(PQ)P Q 证明证明:因为因为PQ P Q，利用代换规则得利用代换规则得 P(PQ)P(P Q)(P P)(P Q)0(P Q)P Q 18命题的演算命题的演算利用代换规则从一个命题得到另

6、一利用代换规则从一个命题得到另一个逻辑等价的命题称为命题的演算。个逻辑等价的命题称为命题的演算。19证明逻辑等价、永真（假）证明逻辑等价、永真（假）式的方法（式的方法（1）方法一：真值表法方法一：真值表法 设设P1,Pn为命题为命题A和和B包含的所有命题变元。包含的所有命题变元。P1 PnA Bv1v1v2v2v3v3 A BP1 PnA000P1 PnA111A为永真式为永真式A为永假式为永假式20证明逻辑等价、永真（假）式的证明逻辑等价、永真（假）式的方法（方法（2）方法二：命题演算方法二：命题演算 AB:AB A为永真式为永真式:A11 A为永假式为永假式:A0021证明逻辑等价例证明逻

7、辑等价例证明证明(PQ)PQ 证明证明:因为因为PQ (PQ)(QP)(PQ)(PQ)(QP)(PQ)(QP)(P Q)(Q P)(P Q)(Q P)(P Q)(Q P)PQ22证明逻辑等价例证明逻辑等价例2证明证明(P Q)P 1 证明证明:(P Q)P (P Q)P (P Q)P (P P)Q 1 Q 1 23对偶式对偶式设设A是命题公式，且是命题公式，且A中仅有联结词中仅有联结词，在在A中将中将，1，0分别换成分别换成，0，1后所得的命题公式称为后所得的命题公式称为A的的对偶式对偶式，记为，记为A*24对偶式示例对偶式示例命题公式命题公式P(Q R)的对偶式为的对偶式为?P(Q R)命题

8、公式命题公式(P 0)Q的对偶式为的对偶式为?(P 1)Q25对偶原理对偶原理设设A、B为仅有命题变元和联结词为仅有命题变元和联结词，构成的命题公式，构成的命题公式，A*为为A的的对偶式，对偶式，B*为为B的对偶式的对偶式如果如果AB，则，则A*B*26永真蕴含式永真蕴含式设设A、B是命题公式，如果是命题公式，如果AB是是永真式永真式则称则称A永真蕴含永真蕴含B记为：记为：AB27永真蕴涵的证明方法（永真蕴涵的证明方法（1）欲证：欲证：AB方法一：方法一：构造构造AB的的真值表真值表方法二：利用等价演算证明方法二：利用等价演算证明 AB1方法三：证明当方法三：证明当A为真时，为真时，B必为真。

9、必为真。方法四：利用常用的等价公式和永真蕴涵方法四：利用常用的等价公式和永真蕴涵 公式证明。公式证明。方法五：范式方法五：范式28永真蕴含式例永真蕴含式例1（1）证明证明P QP 证明证明：方法一方法一 等价于证明等价于证明P QP为永真式。为永真式。P QP的真值表的真值表如下如下:PQP QP001011101111由真值表可知：由真值表可知：P QP为永真公式，故为永真公式，故P Q P。29永真蕴含式例永真蕴含式例1（2）证明证明P QP 证明证明：方法二：等价演算方法二：等价演算 等价于证明等价于证明(P Q)P 1 (P Q)P (P Q)P P Q P 1 故故P Q P 30永

10、真蕴含式例永真蕴含式例1（2）证明证明P QP 方法三方法三：证明：证明P QP为永真式等价为永真式等价于证明当于证明当P Q为真时，为真时，P必为真。必为真。若若P Q为真，则为真，则P为真且为真且Q为真，因为真，因此此P必为真。必为真。31永真蕴含式例永真蕴含式例2证明证明(PQ)(QR)PR 证明：等价于证明：当证明：等价于证明：当(PQ)(QR)为为T时，时，PR必为必为T。若若(PQ)(QR)为为T时，有：时，有：(PQ)为为T且且(QR)为为T。下面根据下面根据R的取值分两种情况讨论的取值分两种情况讨论PR 的取值：的取值：(1)当当R取值为取值为T时，显然，时，显然，PR为为T。

11、(2)当当R取值为取值为F时，由时，由(QR)为为T可知：可知：Q必为必为F，进而，由，进而，由(PQ)为为T可知：可知：P必为必为F。因此，因此，当当R为为F时，时，PR必为必为T 综上所证，当综上所证，当(PQ)(QR)为为T时，时，PR必为必为T 所以所以(PQ)(QR)(PR)32常用的永真蕴含式常用的永真蕴含式(1)（1）P Q P P Q Q（2）P P Q Q P Q（3）P PQ（4）Q PQ（5）(PQ)P（6）(PQ)Q33常用的永真蕴含式常用的永真蕴含式(2)（7）P(PQ)Q（8）Q(PQ)P（9）P(P Q)Q（10）(PQ)(QR)PR（11）(P Q)(PR)(Q

12、R)R（12）(PQ)(RS)(P R)(Q S)（13）(PQ)(QR)(P R)34永真蕴含的性质永真蕴含的性质设设A、B、C是命题公式是命题公式（1）若）若AB，则，则AB，BA；（2）若）若AB，则则 P AP B；P AP B；（补充）；（补充）PAPB；（补充）；（补充）(注意：注意：APBP；APBP；PAP B或或PAPB 都不一定成立。）都不一定成立。）（3）若）若AB，PQ，则，则 P AQ B（4）若）若AB，BC，则，则AC；35利用常用永真式证明永真蕴含式利用常用永真式证明永真蕴含式证明：证明：(PQ)(S Q)(S R)R P 证明：由于证明：由于S RR SRS,

13、因此因此(PQ)(S Q)(S R)R(PQ)(S Q)(RS)R /根据逻辑等价的根据逻辑等价的代代 换规则换规则(PQ)(S Q)S /根据根据P(PQ)Q(PQ)Q /根据根据P(PQ)Q P /根据根据 Q(PQ)Q 36永真蕴含式中的代换规则永真蕴含式中的代换规则设命题公式设命题公式AB如果在命题公式如果在命题公式C中出现中出现A的地方用的地方用B替换替换后后(不一定是每一处不一定是每一处)得到命题公式得到命题公式D 则则CD不一定成立不一定成立。例如：已知：例如：已知：QRQ 若用若用RQ替代替代P Q中的中的Q，可得命题，可得命题 P(RQ)，但是，但是P Q P(RQ)不成立，因为，当不成立，因为，当P、Q、R均为假均为假时，时，P Q为真，但是为真，但是P(RQ)为为假。假。