命题逻辑-2

1-4 真值 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 和等价 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 定义1-4.1 设pl，p2，…，pn是出现在公式A中的全部命题 变元，给pl，p2，…，pn各指定一个真值，称为对公式 A的一个赋值或解释。若指定的赋值使A的真值为T，则 称这个赋值为A的成真赋值，若使A的真值为F，则称这 个赋值为A的成假赋值。 例如: 给公式(p∨q→r)赋值011是指p=0，q=1，r=1，它是 该公式的成真赋值；赋值110是指p=1，q=1，r=0，它是 该公式的成假赋值。 真值表 定义1-4.2 在命题公式A中，对 A的每一个赋值，就确定了A 的一个真值，把它们汇列成 表，称该表为命题公式A的 真值表。 表1-4.1 p q ¬p ¬p∨q 0 0 1 1 0 1 1 1 1 0 0 0 1 1 0 1 例1: 构造命题公式¬p∨q的真值表，并求成真赋值和成假 赋值。 解：命题公式¬p∨q的真值表如表1-4.1所示。00，01，11 是成真赋值，10是成假赋值。 真值表 例2: 构造命题公式(p∧q)∨(¬p∧¬q)的真值表，并求成真 赋值和成假赋值。 解：命题公式(p∧q)∨(¬p∧¬q)的真值表如表1-4.2所示。 00，11是成真赋值，01，10是成假赋值。 表1-4.2 p q p∧q ¬p ¬q ¬p∧¬q (p∧q)∨(¬p∧¬q) 0 0 0 1 1 1 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 1 0 0 0 1 命题公式的等价 定义1-4.3 设A和B是两个命题公式，对A和B的任一赋值，A和B的真值 都相同，则称A和B是等价的或逻辑相等的，记为A⇔B。 例3: 根据等价的定义，可以用真值表证明 p→(q→p)⇔¬p→(p→¬q) 证明：构造p→(q→p)和¬p→(p→¬q)的真值表，如表1-4.3所示。 p→(q→p)和¬p→(p→¬q)所在的列完全相同，它们具有相同的真值 表。所以p→(q→p)⇔¬p→(p→¬q) 表1-4.3 p q ¬p ¬q q→p p→(q→p) p→¬q ¬p→(p→¬q) 0 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 0 1 等价式的性质 可以证明，命题公式等价有下面的三条性质： ⑴ 自反性，即对任意命题公式A， A⇔A ⑵ 对称性，即对任意命题公式A和B，若A⇔B，则 B⇔A ⑶ 传递性，即对任意命题公式A，B和C，若 A⇔B，B⇔C，则A⇔C 等价演算法 等价演算法是证明等价的另外一种方法， 其基本思想是：先用真值表证明一组基本等价 式，以它们为基础进行公式之间的演算。基本 等价式常叫命题定律。 常用的命题定律 1.双重否定律 A⇔¬¬A 2.幂等律 A∧A⇔A，A∨A⇔A 3.结合律 (A∨B)∨C⇔A∨(B∨C), (A∧B)∧C⇔A∧(B∧C) 4.交换律 A∨B⇔B∨A，A∧B⇔B∧A 5.分配律 A∧(B∨C)⇔(A∧B)∨(A∧C), A∨(B∧C)⇔(A∨B)∧(A∨C) 6.吸收律 A∨(A∧B)⇔A，A∧(A∨B)⇔A 7.德.摩根律 ¬(A∨B)⇔¬A∧¬B,¬(A∧B)⇔¬A∨¬B 常用的命题定律 8. 同一律 A∨0⇔A，A∧1⇔A 9. 零律 A∨1⇔1，A∧0⇔0 10. 排中律 A∨¬A⇔1 11. 矛盾律 A∧¬A⇔0 12. 条件等价式 A→B⇔¬A∨B 13. 双条件等价式 A↔B⇔(A→B)∧(B→A) 14. 假言易位式 A→B⇔¬B→¬A 15. 双条件否定等价式 A↔B⇔¬A↔¬B 验证 以上公式都可以用真值表证明。下面仅验证德摩根律: ¬(A∨B)⇔¬A∧¬B 解：表1-4.4是¬(A∨B)和¬A∧¬B的真值表，从表中可以看 出德摩根律成立。 表1-4.4 A B ¬A ¬B ¬A∧¬B A∨B ¬ (A∨B) 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 1 0 等价置换 定义1.3.4如果X是合式公式A的一部分且X本身也是合式公 式，则称X为公式A的子公式。 例如，A⇔q→(p∨(p∧q))，X⇔p∧q，则X是A的子公式。 定理1.3.1设X是合式公式A的子公式，若X⇔Y，如果将A中的 X用Y来置换，得到的公式记为B，则B与A等价，即A⇔B 证明：对A、B的任一赋值，X与Y的真值相同，而A、B的其它 部分完全相同，公式B与公式A的真值必相同，因此 A⇔B。 满足此定理的置换叫做等价置换。 等价演算法实例 例4: 用等价演算法证明 p↔q⇔(p∧q)∨(¬p∧¬q) 证明：p↔q⇔(p→q)∧(q→p) (双条件等价式) ⇔(¬p∨q)∧(¬q∨p) (条件等价式) ⇔(¬p∧¬q)∨(¬p∧p)∨(q∧¬q)∨(q∧p)(分配律) ⇔(¬p∧¬q)∨0∨0∨(q∧p) (矛盾律) ⇔(¬p∧¬q)∨(q∧p) (同一律) ⇔(p∧q)∨(¬p∧¬q) (交换律) 因此p↔q⇔(p∧q)∨(¬p∧¬q) (等价的传递性) 1-5 重言式与蕴含式 定义1-5.1 设A是命题公式。 (1) 若对A的任意赋值，其真值永为真，则称命题 公式A为重言式或永真式。 (2) 若对A的任意赋值，其真值永为假，则称命题 公式A为矛盾式或永假式。 (3) 若A不是矛盾式，则称命题公式A为可满足的。 重言式 ¾ 由定义1-5.1可以看出，任何重言式都是可满足 的。 ¾ 显然，重言式的真值表的最后一列全为T，矛盾 式的真值表的最后一列全为F，可满足的公式真 值表的最后一列至少有一个T。根据这个结论借 助于真值表可以判断一个公式是否为重言式， 矛盾式或可满足的。当然也可以用等价演算法 判断公式的类型。 用等价演算法判断下列公式的类型 例1 q∨¬ ((¬p∨q)∧p); 解：q∨¬((¬p∨q)∧p) ⇔q∨¬((¬p∧p)∨(q∧p)) (分配律) ⇔q∨¬(0∨(q∧p)) (矛盾律) ⇔q∨¬(q∧p) (同一律) ⇔q∨(¬q∨¬p) (德摩根律) ⇔(q∨¬q)∨¬p (结合律) ⇔1∨¬p (排中律) ⇔1 (零律) 由此可知，上式为重言式。 用等价演算法判断下列公式的类型 例2 (1) (p∨¬p)→((q∨¬q)∧r); (2) (p→q)∧¬p 解：(1) (p∨¬p)→((q∧¬q)∧r) ⇔ 1→((q∧¬q)∧r) (排中律) ⇔ 1→(0∧r) (矛盾律) ⇔ 1→0 (零律) ⇔ 0 (条件联结词的定义) 由此可知， (1)为矛盾式。 (2) (p→q)∧¬p ⇔ (¬p∨q)∧¬p (条件等价式) ⇔¬p (吸收律) 由此可知， (2)是可满足的。 重言式 定理1-5.1 任何两个重言式的合取或析取都是重言式。 证明：设A、B是重言式，对A和 B的任何赋值，总有A为1， B为1，所以 A∧B⇔1，A∨B⇔1，故A∧B和A∨B都是 重言式。 推论: 任何两个矛盾式的合取或析取是矛盾式。 定理1-5.2 一个重言式，对同一分量出现的每一处都用同 一合式公式置换，其结果仍是重言式。 推论: 一个矛盾式，对同一分量出现的每一处都用同一合 式公式置换，其结果仍是矛盾式。 利用定理证明 例3 利用定理1-5.2证明 ((p∨q)∧r)∨¬((p∨q)∧r)为重言式。 证明：由排中律知p∨¬p为重言式，以 ((p∨q)∧r)去置换其中的p，得公式 ((p∨q)∧r)∨¬((p∨q)∧r)，根据定理 1-5.2，这是重言式。 定理证明 定理1-5.3 设A、B为两个命题公式，A⇔B当且仅当A↔B是 重言式。 证明：设A⇔B，下证A↔B是重言式。 给A，B的任何赋值，因为A⇔B，所以A，B具有相同的 真值，由双条件联结词的定义知A↔B为真，所以A↔B 为重言式。 设A↔B为重言式，下证A⇔B。 给A，B的任何赋值，因为A↔B为重言式，故A，B的真 值相同，由命题公式等价的定义知A⇔B 蕴含式 定义1-5.2 设A和B是命题公式，若A→B是重言式，则称A蕴 含B，记为A⇒B。 根据定义可以用真值表或等价演算证明A⇒B。 例3 用真值表证明: (1)Ｐ⇒ Ｐ∨Ｑ；(2)ＰΛＱ⇒ P 证明: Ｐ→（Ｐ∨Ｑ）和（ＰΛＱ）→Ｐ为永真式. T T TT T T T T F T TT T TF T F T FF T TTF F T FF T FFF （ＰΛＱ）→ＰＰ→（Ｐ∨Ｑ）QP 证明方法 ¾ A⇒B定义为：A→B为重言式。又由条件命题的定义知， 仅在A⇔T，B⇔F时，A→B为假，其余情况都为真。故要 证明A⇒B，只需排除A⇔T，B⇔F的情况。于是就有了证 明A⇒B的第二种方法： ⑴ 对A指定真值T，若由此推出B的真值不为F，而为T， 则A→B是重言式，即A⇒B。 ⑵ 对B指定真值F，若由此推出A的真值不为T，而为F， 则A→B是重言式，即A⇒B。 证明蕴含式 例4 推证¬p∧(p∨q)⇒q 解：证法1： 假定 ¬p∧(p∨q)为T ⇒ ¬p为T 且 p∨q为T ⇒ p为F 且 p∨q为T ⇒ q为T。 所以， ¬p∧(p∨q)⇒q 证法2： 假定q为F，则p可以为T或F。 ① 当p为T时，¬p为F，所以¬p∧(p∨q)为F。 ② 当p为F时，(p∨q)为F，所以¬p∧(p∨q)为F。 故， ¬p∧(p∨q)⇒q 常用的永真蕴含式 I1 ＰΛＱ⇒ Ｐ （ＰΛＱ⇒ Ｑ） I2 Ｐ⇒Ｐ∨Ｑ （Ｑ⇒Ｐ∨Ｑ） I3 ¬P ⇒Ｐ→Ｑ I4 Ｑ⇒ Ｐ→Ｑ I5 ¬（Ｐ→Ｑ） ⇒ Ｐ I6 ¬（Ｐ→Ｑ） ⇒ ¬Ｑ I7 ＰΛ（Ｐ→Ｑ） ⇒Ｑ I8 （Ｐ→Ｑ）Λ¬Ｑ⇒ ¬Ｐ I9 ¬ＰΛ（Ｐ∨Ｑ） ⇒ Ｑ I10 （Ｐ→Ｑ）Λ（Ｑ→Ｒ） ⇒ （Ｐ→Ｒ） I11 （Ｐ∨Ｑ）Λ（Ｐ→Ｒ）Λ（Ｑ→Ｒ） ⇒ Ｒ I12 （Ｐ→Ｑ）Λ（Ｒ→Ｓ） ⇒ （ＰΛＲ→ＱΛＳ） I13 （Ｐ↔Ｑ）Λ（Ｑ↔Ｒ） ⇒ （Ｐ↔Ｒ） 等价式和蕴含式有下面的关系 定理1-5.4 设A，B为任意两个命题公式，则A⇔B的充分必要条件是 A⇒B且B⇒A 证明：设A⇔B，下证A⇒B且B⇒A 因为A⇔B，所以A↔B⇔T 由双条件等价式得：(A→B)∧(B→A)⇔A↔B⇔T 因而A→B与B→A都是重言式，故有A⇒B且B⇒A。 设A⇒B且B⇒A，下证A⇔B。 因为A⇒B且B⇒A，所以A→B与B→A都是重言式，重言 式的合取也是重言式，即 (A→B)∧(B→A)⇔T 再由双条件等价式得：(A↔B)⇔(A→B)∧(B→A)⇔T 即A↔B为重言式，故有A⇔B。 蕴含式的性质 设A、B、C为合式公式。 ⑴ A⇒A (即蕴含是自反的) ⑵ 若A⇒B且A为重言式，则B必为重言式。 ⑶ 若A⇒B且B⇒C，则A⇒C (即蕴含是传递的) ⑷ 若A⇒B且A⇒C，则A⇒B∧C ⑸ 若A⇒B且C⇒B，则A∨C⇒B ⑹ 若A⇒B，C是任意公式，则 A∧C⇒B∧C 证明：仅证明 ⑸。 因为A⇒B，C⇒B, 所以A→B⇔T，C→B⇔T (A∨C)→B⇔¬(A∨C)∨B⇔(¬A∧¬C)∨B ⇔(¬A∨B)∧(¬C∨B)⇔(A→B)∧(C→B)⇔T∧T⇔T 由等价的传递性，(A∨C)→B⇔T，故A∨C⇒B 1-4 真值表和等价公式 真值表 真值表 命题公式的等价 等价式的性质 等价演算法 常用的命题定律 常用的命题定律 验证 等价置换 等价演算法实例 1-5 重言式与蕴含式 重言式 用等价演算法判断下列公式的类型 用等价演算法判断下列公式的类型 重言式 利用定理证明 定理证明 蕴含式 证明方法 证明蕴含式 常用的永真蕴含式 等价式和蕴含式有下面的关系 蕴含式的性质