真值表逻辑等价永真蕴涵课件

命题公式的真值表v对命题公式中各分量（命题变元）指派所有可能的真值，以及由此而确定的命题公式的真值汇列而成的表称为真值表。真值表示例1vPQ的真值表PQPP Q0011011110001101真值表示例2v(PQ)P的真值表PQP Q(P Q)PFFFTFTFTTFFTTTTT真值表示例3v构成(PQ)R的真值表PQRP Q(P Q)R0000100101010010110110001101011101011111真值表结论v含有n个命题变元的命题公式中，n个变元共有？组不同的取值？回答：2n组永真式和永假式v永真式(重言式)在命题变元的不同指派下，真值总是真的命题公式，记为1或Tv永假式(矛盾式)在命题变元的不同指派下，真值总是假的命题公式，记为0或F永真式举例v(PQ)P的真值表PQP Q(P Q)P1001010110011111(P Q)P是永真式是永真式永假式举例v(PQ)P)的真值表PQP Q(P Q)P)0000010010001110(P Q)P)是永假式是永假式逻辑等价v在真值表中，两个命题公式A和B 在分量的不同指派下，其真值总是相同的，则称这两个命题公式A和B是逻辑等价的v记做AB逻辑等价例1v证明PQ PQPQP QPQ0011011110001111逻辑等价例2v证明 PQ(PQ)(QP)PQ(P Q)(Q P)PQ0000011110111100常用的逻辑等价公式(1)vPQ PQvPQ(PQ)(QP)(PQ)(PQ)vPQ(PQ)(QP)常用的逻辑等价公式(2)vP P (对合律)v(PQ)R P(QR)(结合律)(PQ)R P(QR)vPQ QP (交换律)PQ QPvP(QR)(PQ)(PR)(分配律)P(QR)(PQ)(PR)vP(PQ)P (吸收律)P(PQ)P常用的逻辑等价公式(3)v(PQ)P Q (摩根律)(PQ)P Qv PP P (等幂律)PP Pv P0 P (同一律)P1 Pv P1 1 (零律)P0 0v P P 1 (否定律)P P 0代换规则v设命题公式A和B逻辑等价，即AB，v如果在命题公式C中出现A的地方用B替换后(不一定是每一处)得到命题公式Dv则CD。代换规则示例1v证明P(PQ)PQ 证明:因为PQ PQ，利用代换规则得 P(PQ)P(PQ)(P P)(PQ)0(PQ)PQ 命题的演算v利用代换规则从一个命题得到另一个逻辑等价的命题称为命题的演算。证明逻辑等价、永真（假）式的方法（1）v方法一：真值表法 设P1,Pn为命题A和B包含的所有命题变元。P1 PnA Bv1v1v2v2v3v3 A BP1 PnA000P1 PnA111A为永真式为永真式A为永假式为永假式证明逻辑等价、永真（假）式的方法（2）方法二：命题演算 AB:AB A为永真式:A1 A为永假式:A0证明逻辑等价例v证明(PQ)PQ 证明:因为PQ (PQ)(QP)(PQ)(PQ)(QP)(PQ)(QP)(PQ)(QP)(PQ)(QP)(PQ)(QP)PQ证明逻辑等价例2v证明(PQ)P 1 证明:(PQ)P (P Q)P (PQ)P (PP)Q 1Q 1 对偶式v设A是命题公式，且A中仅有联结词，v在A中将，1，0分别换成，0，1后所得的命题公式称为A的对偶式，记为A*对偶式示例v命题公式P(QR)的对偶式为?P(QR)v命题公式(P0)Q的对偶式为?(P1)Q对偶原理v设A、B为仅有命题变元和联结词，构成的命题公式，A*为A的对偶式，B*为B的对偶式v如果AB，则A*B*永真蕴含式v设A、B是命题公式，如果AB是永真式v则称A永真蕴含Bv记为：AB永真蕴涵的证明方法（1）欲证：ABv方法一：构造AB的真值表v方法二：利用等价演算证明 AB1v方法三：证明当A为真时，B必为真。v方法四：利用常用的等价公式和永真蕴涵 公式证明。v方法五：范式永真蕴含式例1（1）v证明PQP 证明：方法一 等价于证明PQP为永真式。PQP的真值表如下:PQP QP001011101111由真值表可知：由真值表可知：P QP为永真公式，故为永真公式，故P QP。永真蕴含式例1（2）v证明PQP 证明：方法二：等价演算 等价于证明(PQ)P 1 (PQ)P (PQ)P PQP 1 故PQ P 永真蕴含式例1（2）v证明PQP 方法三：证明PQP为永真式等价于证明当PQ为真时，P必为真。若PQ为真，则P为真且Q为真，因此P必为真。永真蕴含式例2v证明(PQ)(QR)PR 证明：等价于证明：当(PQ)(QR)为T时，PR必为T。若(PQ)(QR)为T时，有：(PQ)为T且(QR)为T。下面根据R的取值分两种情况讨论PR 的取值：(1)当R取值为T时，显然，PR为T。(2)当R取值为F时，由(QR)为T可知：Q必为F，进而，由(PQ)为T可知：P必为F。因此，当R为F时，PR必为T 综上所证，当(PQ)(QR)为T时，PR必为T 所以(PQ)(QR)(PR)常用的永真蕴含式(1)（1）PQ P PQ Q（2）P PQ Q PQ（3）P PQ（4）Q PQ（5）(PQ)P（6）(PQ)Q常用的永真蕴含式(2)（7）P(PQ)Q（8）Q(PQ)P（9）P(PQ)Q（10）(PQ)(QR)PR（11）(PQ)(PR)(QR)R（12）(PQ)(RS)(PR)(QS)（13）(PQ)(QR)(P R)永真蕴含的性质v设A、B、C是命题公式（1）若AB，则AB，BA；（2）若AB，则 PAPB；PAPB；（补充）PAPB；（补充）(注意：APBP；APBP；PAPB或PAPB 都不一定成立。）（3）若AB，PQ，则 PAQB（4）若AB，BC，则AC；利用常用永真式证明永真蕴含式v证明：(PQ)(SQ)(SR)RP(课本P270：例6.9(2)证明：由于SRRSRS,因此(PQ)(SQ)(SR)R(PQ)(SQ)(RS)R /根据逻辑等价的代 换规则(PQ)(SQ)S /根据P(PQ)Q(PQ)Q /根据P(PQ)Q P /根据Q(PQ)Q 永真蕴含式中的代换规则v设命题公式ABv如果在命题公式C中出现A的地方用B替换后(不一定是每一处)得到命题公式D 则CD不一定成立。v例如：已知：QRQ 若用RQ替代P Q中的Q，可得命题 P(RQ)，但是P Q P(RQ)不成立，因为，当P、Q、R均为假时，P Q为真，但是P(RQ)为假。证明永真蕴含式的方法v证明ABv方法一：利用真值表证明AB为永真式v方法二：利用等价演算证明：AB 1v方法三：假设A为真，证明B必为真。v方法四：利用常用的蕴含永真公式证明 （注意代换的条件）A（或）（或）（或）Bv方法五：范式（下次课介绍）课堂练习vP257：3（4）vP270：2（1）课堂练习解答(1)P257：3(4)左式A（BC）（AB）C （结合律）（AB）C （AB）C （根据摩根率）（AB）C课堂练习解答(2)P270：2(1)(PQ)(PR)(QS)(PQ)(PR)(QS)(PQ)(PR)(QS)(PS)(PR)/根据(PQ)(QR)PR(PS)(PR)(P(PR)(S(PR)/结合律 R(S(PR)/根据P(PR)R(RS)(R(PR)RS /根据PQ P 作业vP 257：2(2)、3（7、8）