离散数学中命题逻辑的真值表如下：

PQP ∧ QP ∨ Q¬ PP → QP ↔ Q
TTTTFTT
TFFTFFF
FTFTTTF
FFFFTTT

下面对各逻辑运算符进行解释：

  • P ∧ Q（合取）：仅当 P 和 Q 同时为真时，其结果才为真，否则为假。
  • P ∨ Q（析取）：只要 P 或者 Q（或者两者同时）为真，结果即为真，否则为假。
  • ¬ P（否定）：若 P 为假，结果为真；若 P 为真，结果为假。
  • P → Q（蕴含）：只有在 P 为真且 Q 为假的情况下，其结果才为假，其他情况均为真。常被读作“若 P，则 Q”。
  • P ↔ Q（等价）：当且仅当 P 和 Q 的真值一致时（同为真或同为假），结果为真，否则为假。

以下通过具体例子来进一步说明

合取

假设有两个命题 P 和 Q：

  • P：今天天气晴朗。
  • Q：学校举行户外运动会。

逻辑与运算“P ∧ Q”代表“今天天气晴朗并且学校举行户外运动会”。只有当 P 和 Q 均为真时，整个表达式才是真的。

析取

依旧使用上述命题 P 和 Q。 逻辑或运算“P ∨ Q”表示“今天天气晴朗或者学校举行户外运动会”。只要 P 或者 Q（或者二者同时）为真，整个表达式就为真。

否定

使用命题 P：

  • P：今天天气晴朗。

逻辑非运算“¬P”即“今天天气不晴朗”。当 P 为真时，¬P 为假；当 P 为假时，¬P 为真。

蕴含

例子 1：假设有两个命题 P 和 R：

  • P：你完成了作业。
  • R：你可以出去玩。

逻辑蕴含运算“P → R”表示“如果你完成了作业，那么你可以出去玩”。这里，P 是前提（前件），R 是结论（后件）。当 P 为真而 R 为假时，整个表达式为假；在其他情形下（即 P 为真 R 也为真，或者 P 为假时），整个表达式为真。需要注意的是，逻辑蕴含并不等同于因果关系，它仅仅关注真值之间的关联。在实际生活中，我们会说“如果完成了作业（P），那么就可以出去玩（R）”，但这并不表明完成作业是能够出去玩的唯一原因或者必要条件。

为了更好理解蕴含，再举一个例子： 例子 2：假设有两个命题 P 和 R：

  • P：我当选美国总统。
  • R：我就给你涨工资。

对于蕴含式 P → R ：

  • 为真的情况：
    • 我当选了美国总统，并且我给你涨了工资（$T \to T$），结果为真。
    • 我没有当选美国总统，那么无论我是否给你涨工资（$F \to T$ 或 $F \to F$），我都没有违背当初的诺言，所以整个蕴含式的结果依然为真。
  • 为假的情况：
    • 我当选了美国总统，但我没有给你涨工资（$T \to F$），此时我违背了诺言，结果为假。

等价

使用命题 P 和另一个命题 S：

  • P：你完成了作业。
  • S：你的作业已经提交。

逻辑等价运算“P ↔ S”表示“你完成了作业当且仅当你的作业已经提交”。当 P 和 S 的真值相同（即都为真或者都为假）时，整个表达式为真；否则为假。这意味着 P 和 S 在逻辑层面是等价的，它们的真假情况必然一致。

范式 (Normal Forms)

在命题逻辑中，范式是公式的一种标准形式。简单来说，就像数学里的“多项式标准形式”，范式是为了让复杂的逻辑表达变得更有规律、更容易比较。

析取范式与合取范式

我们可以把逻辑公式看作是“文字”（命题或其否定）的组合：

  1. 析取范式 (DNF)：
    • 白话理解：它是“括号里的全是‘且’，括号之间全是‘或’”。
    • 直观感觉：就像在列举“方案 A 或 方案 B 或 方案 C”，只要其中一个方案里的条件全满足了，整个公式就成立。
    • 例如：$(P \land Q) \lor (\neg P \land R)$
  2. 合取范式 (CNF)：
    • 白话理解：它是“括号里的全是‘或’，括号之间全是‘且’”。
    • 直观感觉：就像在定规矩，你必须同时满足“规则 1 且 规则 2 且 规则 3”。而每条规则内部可能比较宽松（比如规则 1 是“有票 OR 有证”）。
    • 例如：$(P \lor Q) \land (\neg P \lor R)$

最小项与最大项

如果我们把真值表的每一行看作一个“特定的场景”：

  • 最小项 (Minterm)：
    • 白话理解：它是真值表里的“精确命中”。
    • 每个最小项都对应真值表里唯一一个让结果为“真”的行。它像是一把“专匙开专锁”，只有那一种特定的输入组合能让它变真。
    • 通常记作 $m_i$。
  • 最大项 (Maxterm)：
    • 白话理解：它是真值表里的“精准雷区”。
    • 每个最大项都对应真值表里唯一一个让结果为“假”的行。只要踏进这个特定的输入组合，结果立刻变假。
    • 通常记作 $M_i$。

对应关系：$\neg m_i \Leftrightarrow M_i$。你可以理解为：让某个场景“唯一成立”条件的否定，正好就是让那个场景“唯一不成立”的条件。

主范式 (Principal Normal Forms)

主范式就像是逻辑公式的“身份证”或“指纹”。虽然同一个逻辑意思可以用很多种花里胡哨的公式表达，但它们化简到最后，主范式是唯一的。

  1. 主析取范式 (PDNF)：
    • 白话理解：它直接告诉你，真值表里哪些行的结果是“真”。它把所有让公式为真的“最小项”都列出来，用“或”连在一起。
    • 如果主析取范式包含了所有可能的情况，说明这公式“怎么着都是对的”（重言式）。
  2. 主合取范式 (PCNF)：
    • 白话理解：它反过来告诉你，真值表里哪些行的结果是“假”。它把所有让公式为假的“最大项”都找出来，用“且”连在一起。
    • 如果主合取范式包含了所有可能的情况，说明这公式“怎么着都是错的”（矛盾式）。