(第2讲)命题逻辑.ppt

CS|SWUSTXDC1.2.1 命题公式的 一些基本概念例 考虑： G1 ： ┐ (P→Q)→P ；G2 ： (P→Q)∧P ；G3 ： ┐ (Ｐ ∧┐ Ｑ )┐(P→Q) 解 ：下面分别列出公式 G1 、 G2 、 G3 的真值表P Q ┐(P→Q)→P P Q (P→Q)∧P0 0 1 0 0 00 1 1 0 1 01 0 1 1 0 01 1 1 1 1 1Ｇ 1的真值表： Ｇ 2的真值表：一、命题公式的分类CS|SWUSTXDCP Q ┐( Ｐ ∧┐ Ｑ ) ┐( Ｐ→ Q)0 0 00 1 01 0 01 1 0G3的真值表：§公式 G1对所有可能的解释具有 “真 ”值§公式 G3对所有可能的解释均具有 “假 ”值§公式 G2则具有 “真 ”和 “假 ”值CS|SWUSTXDC定义1. 公式 G1称为 永真公式 (重言式 )，如果在它的所有解释之下都为 “真 ”2. 公式 G3称为 永假公式 (矛盾式 ),如果在它的所有解释之下都为 “假 ”3. 公式 G2称为 可满足的 ，如果它不是永假的CS|SWUSTXDC从上述定义可知三种特殊公式之间的关系：1) 永真式 G的否定 ┐ G是矛盾式；矛盾式 G的否定┐ G是永真式。

2) 永真式一定是可满足式 ,可满足式不一定是永真式3) 可满足式的否定不一定为不可满足式 (即为永假式 )CS|SWUSTXDC列出下列公式的真值表，并验证其是否是永真公式1)． (P→Q)  (┐P∨Q )；(2)． ((P→Q )∧P )→Q 3). P(Q∧ R)解： ⑴ 、 ⑵ 、 ⑶ 的真值表如下：例 1CS|SWUSTXDC(1)、 (2)的真值表如下：P Q (P→Q)  (┐P∨Q ) ((P→Q )∧P )→Q0 0 1 10 1 1 11 0 1 11 1 1 1例 1公式（ 1）、（ 2）都是永真公式CS|SWUSTXDC（ 3）的 真值表为 ：P Q R P(Q∧ R)0 0 0 0 1 0 0 1 0 1 0 1 0 0 10 1 1 1 01 0 0 0 01 0 1 0 01 1 0 0 01 1 1 1 1例 （ 续）公式（3）是可满足公式CS|SWUSTXDC(1) 永真式的否定是矛盾式 , 矛盾式的否定是永真式 , 所以研究其一就可以了2) 永真式的合取 , 析取 , 蕴含 , 等值等都是重言式 这样 , 由简单的永真式可推出复杂的永真式。

3) 永真式中有许多非常有用的恒等式和永真蕴含式（类似于我们说的公理）永真式 在数理逻辑的研究中占有特殊且重要的地位 CS|SWUSTXDC永真式的代入规则一永真式中某个 命题变元 出现的每一处均代入以同一公式后 , 所得的仍是永真式例如 P∨ ┒P为永真式 ,以 R∧ Q代 P得(R∧ Q)∧┒ (R∧ Q)⇔ 1, 仍正确 它的思想就如同在代数中 , 若 x 2-y2=(x+y)(x-y)则 (a+b)2-(mn)2=(a+b+mn)(a+b-mn) 是 一样的 这条规则之所以正确是由于永真式之值不依赖于变元的值的缘故CS|SWUSTXDC考察命题公式： P↔Q 与 P∧ Q∨┒ P∧┒ Q 它们的真值表如下： 两个命题公式 , 如果有相同的真值表 , 则称它们是 逻辑等价命题 以上两个命题因后两列的真假值完全一致 , 所以它们是 逻辑等价命题 二、 命题公式的相等的概念CS|SWUSTXDC设 A: A(P1, P2, …, Pn), B: B(P1, P2,…, Pn)是两个命题公式 , 这里 Pi(i=1, 2, …, n)不一定在两公式中同时出现 如果 A  B是重言式 , 则 A与 B对任何指派都有相同的真值。

记为 A￿ B, 叫做逻辑恒等式 , 读做 “A恒等于 B”恒等式CS|SWUSTXDCq设 A， B为两命题公式，由定义判断 A与 B是否逻辑等价应判断 A↔ B是否为重言式 ，若 的真值表最后一列全为 1，则 A↔ B重言式，因而 A⇔ B q若 A， B的真值表是 完全 相同 的，则 A⇔ B CS|SWUSTXDC考察命题公式： P↔Q 与 P∧ Q∨┒ P∧┒ Q 它们的真值表如下： P↔Q ⇔ P∧ Q∨┒ P∧┒ Q CS|SWUSTXDC￿ 　 首先，双条件词 “ ” 是一种逻辑联结词，公式 GH是命题公式，其中 “ ” 是一种逻辑运算， GH的结果仍是一个命题公式 而逻辑等价 “ ” 则是描述了两个公式 G与 H之间的一种逻辑等价关系， G H表示 “ 命题公式 G等 价 于命题公式 H”， G H 的结果 不 是命题公式 ￿￿ 其次，如果要求用计算机来判断命题公式 G、 H是否逻辑等价（即 G H）， 则计算机通过 “ 计算” 公式 GH是否是永真公式，而得出结论 ” 与 “ ” 的区别CS|SWUSTXDC§ 由于 “ ”不是一个联结词，而是一种关系，为此，这种关系具有如下三个性质：§ （ 1）自反性 G G；§ （ 2）对称性 若 G H，则 H G；§ （ 3）传递性 若 G H， H S，则 G S。

§ 这三条性质体现了 “ ”的实质含义 CS|SWUSTXDC常用的逻辑恒等式 1.双重否定律 2.等幂律 3.交换律 4.结合律 5.分配律 CS|SWUSTXDC常用的逻辑恒等式 6.德 .摩根律 7.吸收律 8.零律 9.同一律 10.排中律 11.矛盾律 CS|SWUSTXDC12.蕴涵等值式 13.等价等值式 14.假言易位 15.等价否定等值式 16.归缪论 CS|SWUSTXDC替换规则 (Rule of Replacement)设有恒等式 A ⇔ B, 若在公式 C中出现 A的地方 , 替换以 B(不必每一处 )而得到公式 D, 则 C ⇔ D 如果 A是命题公式 C中完整的一部分 , 且 A本身是复合公式 , 则称 A是 C的子公式 , 规则中 “公式 C中出现 A”意指 “A是 C的子公式 ”这条规则的正确性是由于在公式 C和 D中 , 除替换部分外均相同 , 但对任一指派 , A和 B的真值相同 , 所以 C和 D的真值也相同 , 故 C ⇔ DCS|SWUSTXDC(a)证明 P∧ ┒Q∨ Q ⇔ P∨ Q 证： P∧┒ Q∨ Q⇔ Q∨ P∧ ┒Q E4 ⇔ (Q∨ P)∧ (Q∨ ┒Q)￿ E9⇔ (Q∨ P)∧ 1￿ E20和替换规则⇔ Q∨ P ￿ E19⇔ P∨ Q￿ E4 CS|SWUSTXDC证明 (P→ Q)→( Q∨ R) ⇔ P∨ Q∨ R证 (P→ Q)→( Q∨ R) ⇔ ( ┒P∨ Q)→( Q∨ R)￿ E14和替换规则⇔ ┒(┒P∨ Q)∨ (Q∨ R)￿ E14⇔ P∧ ┒Q∨ (Q∨ R) E10、 E1和替换规则⇔ (P∧┒ Q∨ Q)∨ R)￿ E6⇔ P∨ Q∨ R 例（ a）和替换规则 CS|SWUSTXDC定理 1 设 A和 A*是对偶式。

P 1, P2,…, Pn是出现于A和 A *中的所有命题变元，于是 ┒A(P1, P2, …, Pn) ⇔ A *(┒P1, ┒P2, …, ┒Pn)例 A*(┒P, ┒Q, ┒R) ⇔ ┒(┒P)∧ (┒Q∨┒ R) 所以 , ┒A(P, Q, R) ⇔ A *(┒P, ┒Q, ┒R) A(P， Q， R) ⇔ ┒P∨ Q∧ R┒A(P， Q， R) ⇔ ┒(┒P∨ Q∧ R)⇔ ┒(┒P)∧ ┒(Q∧ R)⇔ ┒(┒P)∧ (┒Q∨ ┒R) A*(P, Q, R) ⇔ ┒P∧ (Q∨ R)三、 命题公式的对偶原理CS|SWUSTXDC定理 2 若 A⇔ B, 且 A、 B为命题变元 P1, P2,….., Pn及联结词 ∧ 、 ∨ 、 ┒构成的公式 , 则 A* ⇔ B*此定理常称为 对偶原理 A(P1P2, …, Pn)↔ B(P1, P2, …, Pn) 永真 故 ┒A(P1, P2, … , Pn) ↔ ┒B( P1, P2, … , Pn) ￿ 永真 由定理 1得 A*(┒P1, ┒P2, … , ┒Pn) ↔ B* (┒P1, ┒P2, … , ┒Pn) ￿ 得 A*(P1, P2, …, Pn) ↔ B*(P1, P2, …, Pn) ￿ 所以， A* ⇔ B*。

证明 A⇔ B意味着 永真因上式是永真式 , 故使用代入规则 , 以 ┒ Pi代 Pi,1≤ i≤ n, CS|SWUSTXDC例 若 (P∧ Q)∨ (┒P∨ (┒P∨ Q)) ⇔ ┒P∨ Q则由对偶原理立即可知下式成立：￿￿ (P∨ Q)∧ (┒P∧ (┒P∧ Q)) ⇔ ┒P∧ Q￿￿。