DS@命题公式等值演算@常用等值式模式

abstract

• 命题公式等值演算@常用等值式模式

等值式

• $A\iff B$表示的是等价式命题$p$:$A\leftrightarrow B$是一个重言式

  • 若$A,B$有相同的真值表,意味着$A,B$在任意赋值下都有相同的真值,那么根据等价联结词的为真的定义,复合公式$A\leftrightarrow B$的真值总是真,从而$A\leftrightarrow B$是重言式
  • 反之,若$A\leftrightarrow B$是重言式,根据等价联结词$\leftrightarrow$的定义,$A,B$在任何赋值下都相等,所以$A,B$有相同的真值表

• 定义:若$A,B$两个命题构成的等价式$A\leftrightarrow B$为重言式,则$A,B$是等值的,记为$A\iff B$

• 符号$\leftrightarrow$和$\iff$不同

  • 前者是逻辑联结词,用来构成命题公式,构成的公式得真值取决于被联结得两个命题(或命题公式)是否有相同的真值决定的;
  • 后者在逻辑等值演算中来描述等值关系,是一种命题间有相同真值的关系的记法,这里$A\iff B$
  • $A\iff B$表示的是等价式复合命题命题$p$:$A\leftrightarrow B$是一个重言式
  • 并且,这里的等价以及等值和自然语言中的等价是不同
    • 等价联结词$\leftrightarrow$联结的复合命题的真值仅取决于被联结的两个命题是否有相同的真值而不要求它们有内在关联(可有可无)
    • 而自然语言中的等价描述的是内在完全相同的意思
  • 此外,等值号$\iff$还要和一般等号$=$区别

• 不等值号:$\nLeftrightarrow$

等值的判断

真值表法

• 由定义可知,我们可以构造公式$A\leftrightarrow B$的真值表是否全为1来判断$A,B$是否等值
  • 事实上,只要真值表最后一列中出现0,那么直接断定$A,B$不等值
  • 更加简化的方法是单独观察真值表中$A$,$B$的真值是否每一行都一样,存在不一样的,则说明$A,B$不等值,否则等值
• 小结:
  • $A,B$等值($A\iff B$)的充要条件是$A,B$真值表相同($A\leftrightarrow B$是重言式)

等值演算法

• 参见下节铺垫和介绍

任意置换命题

• 设$A$是一个命题公式,含有命题变项$p_1,\cdots ,p_n$,又设$A_1,\cdots ,A_n$是任意的命题公式,对每一个$i(i=1,\cdots ,n)$,把$A$中的所有出现$p_i$都替换为$A_i$,所得到的新命题公式记为$B$
• 这里不要求$p_i=A_i$,和后续的置换规则中的等值置换有所不同

重言式和矛盾式的置换性质性质

• 根据重言式和矛盾式的定义,对于任意赋值,重言式真值总为1,矛盾式真值总为0;

  • 对于同一组赋值,$A$:

    • 	重言式	矛盾式
      A	A=B=1	A=B=0

  • 若$A$是重言式,则其任意置换命题$B$也是重言式

  • 若$A$是矛盾式,则其任意置换命题$B$也是矛盾式

• 例如$p\leftrightarrow \neg \neg p$是重言式,从而其置换命题$A\leftrightarrow \neg \neg A$也是重言式

等值模式

• 称关系$A\iff B$是关于$A,B$的等值式模式,等值模式两边的公式真值表相同
• 即,任意两个真值表相同的公式$A,B$($A\leftrightarrow B$是重言式),可以抽象为一个等值式模式
• 设公式$F$是包含$A$的公式,可以将$A$替换为$B$,替换前后$F$的真值表相同

常用等值式模式

1. 双重否定律:$A\iff \neg \neg A$

2. 幂等律:$A\iff A\vee A$,$A\iff A\wedge A$

3. 交换律:$A\vee B\iff B\vee A$,$A\wedge B\iff B\wedge A$

4. 结合律:$(A\vee B)\vee C\iff A(B\vee C)$

5. 分配律:

   1. $A\vee (B\wedge C)$ $\iff$ $(A\vee B)\wedge (A\vee C)$($\vee$对$\wedge$的分配律)
   2. $A\wedge (B\vee C)$ $\iff$ $(A\wedge B)\vee (A\wedge C)$($\wedge$对$\vee$的分配律)

6. 德摩根律:

   • $\neg (A\vee B)$ $\iff$ $\neg A\wedge \neg B$

   • $\neg (A\wedge B)$ $\iff$ $\neg A\vee \neg B$

7. 吸收律:

   • $A\vee (A\wedge B)$ $\iff$ $A$

   • $A\wedge (A\vee B)$ $\iff$ $A$

8. 零律:

   • $A\vee 1$ $\iff$ $1$

   • $A\wedge 0$ $\iff$ $0$

9. 同一律:

   • $A\vee 0$ $\iff$ $A$
   • $A\wedge 1$ $\iff$ $A$

10. 排中律:

    • $A\vee \neg A$ $\iff$ $1$

11. 矛盾律:

    • $A\wedge \neg A$ $\iff$ $0$

12. 蕴含等值式

    • $A\to B$ $\iff$ $\neg A\vee B$

    • 分析

      • $A$	$B$	$A\to B$	Note
        0	0	1	$\neg$
        0	1	1	$\vee$
        1	0	0	$\vee$
        1	1	1	$\vee$或$\wedge$

      • 显然$\neg A\vee B$满足该真值表

      • 而$A\vee \neg B$,不满足

13. 等价等值式:

    • $A\leftrightarrow B$ $\iff$ $(A\to B)\wedge (B\to A)$ $\iff$ $(\neg A\vee B)\wedge (\neg B\vee A)$

    • $A$	$B$	$A\leftrightarrow B$	Note
      0	0	1	$\neg (A\vee B)$,或$\neg (A\vee B)$或$A\to B$
      0	1	0	$\wedge$,
      1	0	0	$\wedge ,\to$
      1	1	1	$\vee$或$\wedge$或$\to$

14. 假言易位:

    • $A\to B$ $\iff$ $\neg B\to \neg A$
    • 即逆否命题是等值的

15. 等价否定等值式:

    • $A\leftrightarrow B$ $\iff$ $\neg A\leftrightarrow \neg B$

16. 归谬论:

    • $(A\to B)\wedge (A\to \neg B)$ $\iff$ $\neg A$

等值演算

• 又一致得等值式(等值式模式)推演出另外一些等值式得过程称为等值演算
• 等值演算是布尔代数或逻辑代数的重要组成部分

等值演算置换规则

• 置换公式:若$\varphi (A)$是含有公式$A$的命题公式,$\varphi (B)$是用$B$置换$\varphi (A)$中$A$(的所有出现)后得到的命题公式
  • 若$A\iff B$,则$\varphi (A)$ $\iff$ $\varphi (B)$;
• 这是显然的,因为对任意一组赋值,$A,B$是等值的,从而对于命题公式$\varphi (A),\varphi (B)$是一样的

等值式模式的代入实例

• 将模式等值式两边以相同的方式替换字母(将模式等值式的两边的$A_i$替换为公式$A_i^{\prime }$,如果有一边确实相应字母则跳过),则代入后两侧分别得到一个新命题公式,两边仍然保持等值
• 向等值式模式代入具体公式得到的具体等值式称为等值式模式的代入实例
• 例如等值式模式$A\to B$ $\iff$ $\neg A\vee B$
  • $A,B$分别用$A=p,B=q$代入,得代入实例$p\to q$ $\iff$ $\neg p\vee q$,
  • $A,B$分别用$A=(p\vee q\vee r)$,$B=(p\wedge q)$代入,得到代入实例 $p\vee q\vee r)\to (p\wedge q)$ $\iff$ $\neg (p\vee q\vee r)\vee (p\wedge q)$

等值演算示例

• 运用前面介绍的等值式模式和置换规则

• $(p\to q)\to r$

  • $\iff$ $(\neg p\vee q)\to r$
  • $\iff$ $\neg (\neg p\vee q)\vee r$
  • $\iff$ $(p\wedge \neg q)\vee r$
  • $\iff$ $(p\vee r)\wedge (\neg q\vee r)$

小结

• 验证两个命题公式是等值的,通常用等值演算法比真值表法更加方便

• 但是等值演算法却不能直接验证两个公式不等

• 可以用等值演算法化简,然后结合真值表法(或者举出使得两个公式不等的赋值实例)验证两个公式不等

• 例如$(p\to q)\to r$ $\nLeftrightarrow$ $p\to (q\to r)$,可以将它们都化简为仅含$\vee ,\wedge ,\neg$三种最基础的逻辑联结词再判断