《真值表与等价公式课件》由会员分享，可在线阅读，更多相关《真值表与等价公式课件（25页珍藏版）》请在金锄头文库上搜索。
1、2020/8/5,1,离散数学(Discrete Mathematics),医学信息工程系, ,2020/8/5,第1章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,1.4.1 真值表(Truth Table) 1.4.2 等价公式(Propositional Equivalences) 1.4.1 真值表 前面在定义联结词时,曾经使用过真值表,下面给出 真值表的定义. 定义1.4.1 (对公式的赋值或解释)设P1 , P2 ,Pn是出 现在公式A中的全部的命题变元, 给P1 , P2 ,Pn各指 定一个真值，称为对A的一个赋值或解释。若指定的 一组值使A的真值
2、为真(假), 称这组值为A的成真(假)赋值.,2020/8/5,比如:对公式(PQ)R,赋值011(即令P=0,Q=1,R=1) 为(PQ)R的成真赋值; 另一组赋值010为(PQ)R的成假赋值；还有000，001，111 考虑：含有n个命题变元的公式共有多少组不同的赋值？ 定义1.4.2(真值表)在命题公式A中, 对于命题变元的每一组赋值和由它们所确定的命题公式A的真值列成表，称做命题公式A 的真值表。,2020/8/5,对公式A构造真值表的具体步骤为： （1）找出公式中所有命题变元P1 , P2 ,Pn , 列出全部的2n组赋值。 （2）确定过渡子公式，并加入到真值表。 （3）计算各个过渡
3、子公式的真值，并最终计算出公式A的真值。,2020/8/5,例题1：构造 PQ,2020/8/5,例题2：构造(PQ) P,2020/8/5,例题3：构造(PQ)( P Q ),2020/8/5,例题4：构造 (PQ) ( P Q ),2020/8/5,小结： PQ真值表与 PQ 的真值表,等价（逻辑相等）： PQ PQ,2020/8/5,小结： P Q 真值表与 (PQ)( PQ )的真值表,等价（逻辑相等）： P Q (PQ)( PQ ),2020/8/5,1.4.2 等价公式 给定n个 命题变元, 按合式公式的形成规则可以形成无数多个命题公式, 但这些无穷尽的命题公式中，有些具有相同的真
4、值表。考虑：由n个命题变元能生成? 种真值(表)不同的命题公式？,2020/8/5,1.4.2 等价公式 定义1.4.3: 给定两个命题公式A和B,设P1 , P2 ,Pn为出现于A和B中的所有原子变元,若给P1 , P2 ,Pn任一组真值指派, A和B的真值都相同,则称A和B是等价的或逻辑相等.记作A B 注: (1) “ ”不是逻辑联结词. (2)命题公式之间的逻辑相等关系具有： 自反性：A A ；对称性：若A B，则B A； 传递性：若A B且B C，则A C。,2020/8/5,证明公式等价的方法： 1. 真值表法 2. 等值演算法,例题5： 证明P Q (PQ)(QP),2020/8
5、/5,例：判断公式 P(QR)、(PQ)R是否等价。,2020/8/5,2、等值演算法(Equivalent Caculation),2020/8/5,2020/8/5,重要的等价式(补充):,2020/8/5,其中P, Q, R等代表任意命题公式. 这样上面的每一个公式都是一个模式, 它可以代表无数多个同类型的命题公式. 例如, PP1 中, 用(PQ)置换P,则得 (PQ)(PQ)1 ,用P置换P,则得 (P)(P)1 。 等值演算中使用的一条重要规则：置换规则。 定义1.4.4(子公式)：如果X是wff A的一部分,且X本身也是wff，则称X是A的子公式。例如, P(PQ)为Q (P(P
6、Q)的子公式。,2020/8/5,定理1.4.1(置换定理Axiom of replacement)设X是wff A的子wff，若XY，则若将A中的X用Y来置换，所得公式B与A等价，即AB。 证：因为对变元的任一指派,X与Y真值相同，所以Y 取代X后，公式B与公式A对变元的任一指派真值 也相同,所以AB。 注: 满足定理1.4.1的条件的置换称为等价置换(或等价代换). 定义1.4.5(等值演算)：根据已知的等价公式,推演出另外一些等价公式的过程称为等值演算.,2020/8/5,例1：证明 Q（P（PQ）QP,证: Q（P（PQ） QP,(吸收律),2020/8/5,例2： 证明 PQQPQ
7、证： (PQ)Q (PQ)(QQ) (分配律) (PQ)1 (否定律) PQ (同一律),2020/8/5,例3：证明（PQ）（QR） PQR 证： （PQ）（QR） （PQ）（QR） (蕴含等值式) （PQ）（QR） (蕴含等值式) （PQ）（QR） (德。摩根律) （PQR）（QQR） (分配律) PQR (否定律、零一律),2020/8/5,例4：验证P(QR) (P Q) R 证: 右 (P Q) R (蕴含等值律) P Q R (德.摩根律) P ( Q R) (组合律) P (Q R) (蕴含等值律) P (Q R) (蕴含等值律),2020/8/5,练： 1.(P Q) (P R) P (Q R) 2.(P Q) ( P Q) (P Q) (P Q),2020/8/5,第1章 命题逻辑（Propositional Logic） 1.4真值表与等价公式,等值演算在计算机硬件设计中,在开关理论和电子元器件中都占有重要地位. 小结: 本节介绍了真值表、公式等价、等值演算和等价置换等概念，给出了常用的重要等价公式（24个）。重点掌握用真值表法验证公式的等价性和等值演算法推演两个公式等价。,
