一、命题、联结词与命题公式

• 布尔值：一个要么是（假）$0$、要么是（真）$1$ 的值。记布尔值集合为 ${\mathbb B} = \{ 0, 1\}$。

  • 布尔常量：$0$ 和 $1$ 都是布尔常量。
  • 布尔变量：比如用记号记录下 $x \in { \mathbb B }$，它就要么是 $0$，要么是 $1$。

• 命题：一个要么是假、要么是真的陈述。

  • 命题常量（常项）：任何给出了确定解释的命题。
  • 命题变量（变项）：即可以「代入」任意命题的 $p, q$ 等变项。
    • 可以定义变量 $p \in {\mathbb P}$，其中 $\mathbb P$ 是所有命题构成的集合。
    • 命题的解释：「$p:$ 1+1=2」，赋予命题变量以解释，让其成为常量。
  • 命题的真值：命题的真或假。
  • 谓词：带一个变量的命题，如记为 $p(x)$。A1-3 中会详细介绍。

• 命题公式：零次或有限次应用 $\neg, \wedge, \vee, \to, \leftrightarrow$ 等形成的命题符号串。优先级：$\neg, (\wedge, \vee), (\to, \leftrightarrow)$。命题公式记为 $A(p), B(p, q), \cdots$

  • 命题的联结词（逻辑运算符）：主要是下面 5 种：

    • $\neg$：否定（非），Negation (NOT)
    • $\wedge$：合取（与），Conjunction (AND)
    • $\vee$：析取（或），Disjunction (OR)
    • $\to$：蕴含，Implication
    • $\leftrightarrow$：等价，Equivalence (IFF, if and only if)

  • 真值表： $n$ 个命题变项时有 $2^n$ 个取值情况。将取值情况按字典序列成表，得到真值表。

    

  • 命题公式的解释：命题公式在给定确定的、具体命题变量的解释后，其自身就变为一个命题。

  • 特殊的命题公式：

    • 永假式（矛盾式）
    • 永真式（重言式）
    • 可满足式：不是永假式就是可满足式，即可以为真。
    • 非重言式的可满足式：即可能为真可能为假。

  • 蕴含和等价与条件的关系：

    • $A \to B$ 表示 A 是 B 的充分条件、B 是 A 的必要条件。
    • $A \leftrightarrow B$ 表示 A 是 B 的充分必要条件，反之亦然。

  模糊逻辑

  模糊逻辑中命题的真值介于零与一之间，表明真的程度（或概率）。这时的否定为一减 P；析取是两个命题的真值最大值。

二、等值演算

• 等值演算：当 $A\leftrightarrow B$ 为永真式，称命题公式 $A$ 与 $B$ 等价，记为 $A \Leftrightarrow B$。

  • 比如：$p \to q \Leftrightarrow \neg p \vee q$。

• 基本的等值式

  下面 16 行的证明方法都是列真值表。

  1. 双重否定律：$\neg \neg A \Leftrightarrow A$

  2. 等幂律：$A \wedge A \Leftrightarrow A$，$A \vee A \Leftrightarrow A$

  3. 吸收律：$A \wedge (A \vee B) \Leftrightarrow A$，$A \vee (A \wedge B) \Leftrightarrow A$

  4. 零律（支配律）：$A \wedge 0 \Leftrightarrow 0$，$A \vee 1 \Leftrightarrow 1$

     • 某运算的零元比较霸道，和别的元素做完此运算都变成它。
     • $0$ 是与运算的零元，$1$ 是或运算的零元。

  5. 同一律（恒等律）：$A \wedge 1 \Leftrightarrow A$，$A \vee 0 \Leftrightarrow A$

     • 某运算的幺元比较谦虚，和别的元素做完此运算都保留原样。
     • $1$ 是与运算的幺元，$0$ 是或运算的幺元。

  6. 矛盾律：$A \wedge \neg A \Leftrightarrow 0$

  7. 排中律：$A \vee \neg A \Leftrightarrow 1$

     • 虽然矛盾律是所有数学家认可的，但有的模糊数学系统排除排中律，即修改命题的定义让其不是非黑即白的，以兼容「本命题是假的」这样非真非假的模糊说法，因而不保证排中律，因而就不能实现反证法。

  8. 交换律：$A \wedge B \Leftrightarrow B \wedge A$，$A \vee B \Leftrightarrow B \vee A$

  9. 结合律：

     • $A \wedge (B \wedge C) = (A \wedge B) \wedge C$
     • $A \vee (B \vee C) = (A \vee B) \vee C$

  10. 分配律：

      • $A \wedge (B \vee C) = (A \wedge B ) \vee (A \wedge C)$
      • $A \vee (B \wedge C) = (A \vee B ) \wedge (A \vee C)$

      <aside> ⚠️ 分配律拓展：

      $(A \vee B) \wedge (C \vee D) \\ = (A \wedge C ) \vee (A \wedge D) \vee (B \wedge C) \vee (B \wedge D)$

      $(A \wedge B) \vee (C \wedge D) \\ = (A \vee C ) \wedge (A \vee D) \wedge (B \vee C) \wedge (B \vee D)$

      </aside>

  11. 德·摩根律：

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

  12. 蕴含等值式：$A\rightarrow B \Leftrightarrow \neg A \vee B$

  13. 假言易位*️⃣：$A \rightarrow B \Leftrightarrow \neg B \rightarrow \neg A$

      • 其说明：「若 $p$ 则 $q$」形式的原命题和「若 $\neg q$ 则 $\neg p$」形式的逆否命题为等价命题。

      二级结论

      • 蕴含对合取和析取的后分配律
        • $(p \to q) \wedge (p \to r) \Leftrightarrow p \to (q \wedge r)$
        • $(p \to q) \vee (p \to r) \Leftrightarrow p \to (q \vee r)$
      • 蕴含对合取和析取的前分配律
        • $(p \to r) \vee (q \to r) \Leftrightarrow (p \wedge q)\to r$
        • $(p \to r) \wedge (q \to r) \Leftrightarrow (p \vee q)\to r$

  14. 等价等值式*️⃣：$A \leftrightarrow B \Leftrightarrow( A \rightarrow B) \wedge (B \rightarrow A)$

      • 其说明：「$p$ 与 $q$ 互为充分必要条件」即 $p$ 是 $q$ 的充分条件和必要条件。

  15. 等价否定等值式*️⃣：$A \leftrightarrow B \Leftrightarrow \neg A \leftrightarrow \neg B$

      • 其说明：「$p$ 与 $q$ 互为充分必要条件」形式的命题与「$\neg p$ 与 $\neg q$ 互为充分必要条件」形式的命题为等价命题。

      等价的其他性质：

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

  16. 归谬论*️⃣：$(A \rightarrow B) \wedge (A \rightarrow \neg B) \Leftrightarrow \neg A$

      • 其是反证法的理论基础。反证法通过证明左边是永真式，得到右边是永真式即 $A$ 是永假式。
      • 根据蕴含的分配律，一般写成 $A \rightarrow (B \wedge \neg B) \Leftrightarrow \neg A$。

  提示

  带 *️⃣ 的是重要的证明手段。比如根据等价等值式，可以通过证明 $A \rightarrow B$ 和 $B \rightarrow A$ 均为真来证明 $A \leftrightarrow B$ 为真。

• 一些二级结论：

  • $0 \rightarrow q \Leftrightarrow 1$，$1 \rightarrow q \Leftrightarrow q$。
  • $p \rightarrow 0 \Leftrightarrow \neg p$，$p \rightarrow 1 \Leftrightarrow 1$。

• 由于有结合律，可以定义一组 $n$ 个命题之合取和析取：

  $$ \bigwedge_{i=1}^n p_i = p_1 \wedge p_2 \wedge \cdots \wedge p_n \\ \bigvee_{i=1}^n p_i = p_1 \vee p_2 \vee \cdots \vee p_n $$

  • 特别地，定义零个命题之合取为 $1$，零个命题之析取为 $0$（因为是单位元）。

三、连接词全功能集

1. 其他的联结词

• 除去 $0, 1, p, q, \neg p, \neg q$，一共有 10 个二元联结词（真值函数），前面已经介绍了 4 个，剩下的 4 个如下：
  • 排斥或（也就是异或，XOR）：$p \veebar q \Leftrightarrow (\neg p \wedge q) \vee (p \wedge \neg q)$
    • 排斥或具有交换律、结合律、同 $\wedge$ 运算符合分配律。
  • 不蕴含：$p \nrightarrow q \Leftrightarrow \neg(p \leftrightarrow q)$
    • 蕴含和不蕴含都是不对称的，将 $p, q$ 换一下顺序能得到最后的 2 个。
  • 与非（NAND, NOT AND）：$p \uparrow q \Leftrightarrow \neg(p \wedge q)$
  • 或非（NOR, NOT OR）： $p \downarrow q \Leftrightarrow \neg(p \vee q)$

2. 全功能集

• 冗余的连接词：如果一个联结词可由其他进行定义，则称它是冗余的。
  • 全功能集：该联结词集合可以表示任意真值函数。
  • 极小全功能集：不含冗余联结词的全功能集。
    • $\{ \neg, \wedge \}$ 和 $\{ \neg, \vee \}$ 是极小全功能集。
    • 一个重要的极小全功能集是 $\{ \uparrow \}$ 即仅有 NAND。没错。比如它可以做到（未验证）：
      1. NOT：$\neg p = p \uparrow p$
      2. AND：$p \wedge q = (p \uparrow q) \uparrow (p \uparrow q)$
      3. OR：$p \vee q = (p \uparrow p) \uparrow (q \uparrow q)$
      4. $p \to q = (p \uparrow p) \uparrow q$
      5. $p \leftrightarrow q \Leftrightarrow (p \uparrow q) \uparrow ((p \uparrow p) \uparrow (q \uparrow q))$

四、杂项

1. 对偶

• 对偶式：对于仅含 $\neg, \vee, \wedge$ 的如命题公式 $A$，将其中的 $\wedge$ 与 $\vee$ 对换、$0$ 与 $1$ 对换，得到对偶式，记为 $A^*$。
• 对偶定理一：$\neg A(p_1, p_2, \cdots p_n) \Leftrightarrow A^*(\neg p_1, \neg p_2, \cdots \neg p_n)$
  • 德摩根律是该结论的特殊情况，可以用德摩根律为基础证明该定律。