跳转至

第一章 命题逻辑的基本概念

命题（Proposition）

  • 命题的定义：命题是一个非真即假的 陈述句。
    • 命题是一个陈述句，命令句、疑问句和感叹句都不是命题
    • 命题只有两个取值：真或假
  • 真假命题:凡与事实相符的陈述句为真语句，而与事实不符的陈述句为假语句。
    • 通常用大写字母 \(T/1\) 表示真值为真， 用 \(F/0\) 表示真值为假
    • 因为只有两种取值，所以这样的命题逻辑称为 二值逻辑。
  • 命题变项（变元）：用大写字母 \(P, Q, R, \cdots\) 表示命题变项。
    • 命题与命题变项含义是不同的，命题指具体的陈述句，是有确定的真值。
    • 命题变项的真值不定，只当将某个具体命题代入命题变项时，命题变项化为命题，方可确定其真值。
  • 命题的分类
    • 简单命题/原子命题(Primitive proposition)：不包含任何的与、或、非一类联结词的命题。
      • 简单命题不可再分割，如再分割就不是命题了。
    • 复合命题/分子命题(Compound proposition)：由一个或几个简单命题用联结词（如与、或、非）联结所构成的新的命题。
      • 复合命题自然也是陈述句，其真值依赖于构成该复合命题的各简单命题的真值以及联结词，从而复合命题有确定的真值。

命题联结词及真值表

否定词 \(\neg\)

  • 定义：否定词（negation）\(\neg\) 是个一元联结词，亦称否定符号。
    • 一个命题 \(P\) 加上否定词就形成了一个新的命题，记作 \(\neg P\)，这个新命题是命题的否定，读作非 \(P\)。
  • 真值规定：
    • 若命题 \(P\) 的真值为真，那么 \(\neg P\) 的真值就为假
    • 若 \(P\) 的真值为假，那么 \(\neg P\) 的真值就为真

  • 真值表：

    \(P\) \(\neg P\)
    T F
    F T

合取词 \(\wedge\)

  • 定义：合取词（conjunction）\(\wedge\) 是个二元命题联结词，亦称合取符号。
    • 将两个命题 \(P,Q\) 联结起来，构成一个新的命题 \(P \wedge Q\)，读作 \(P,Q\) 的合取，也可读作 \(P\) 与 \(Q\)。

  • 真值表：

    \(P\) \(Q\) \(P \wedge Q\)
    T T T
    T F F
    F T F
    F F F

析取词 \(\vee\)

  • 定义：析取词（disjunction）\(\vee\) 是个二元命题联结词，亦称析取符号。
    • 将两个命题 \(P,Q\) 联结起来，构成一个新的命题 \(P \vee Q\)，读作 \(P,Q\) 的析取，也读作 \(P\) 或 \(Q\)。

  • 真值表：

    \(P\) \(Q\) \(P \vee Q\)
    T T T
    T F T
    F T T
    F F F

蕴涵词 \(\rightarrow\)

  • 定义：蕴涵词（implication）\(\rightarrow\) 也是个二元命题联结词，亦称推断符号。
    • 将两个命题 \(P,Q\) 联结起来，构成一个新的命题 \(P \rightarrow Q\)，读作如果 \(P\) 则 \(Q\)，或读作 \(P\) 蕴涵 \(Q\)。
    • 如果 \(P\) 那么 \(Q\)，其中 \(P\) 称前件（前项、条件），\(Q\) 称后件（后项、结论）
  • 真值规定：规定只有当 \(P\) 为 \(\mathrm{T}\) 而 \(Q\) 为 \(\mathrm{F}\) 时，\(P \rightarrow Q=\mathrm{F}\)，而 \(P=\mathrm{F}\)、\(Q\) 任意，或 \(P=\mathrm{T}\)、\(Q=\mathrm{T}\) 时，\(P \rightarrow Q\) 均取值为 \(T\)。

  • 真值表：

    \(P\) \(Q\) \(P \rightarrow Q\) \(\neg P \vee Q\)
    T T T T
    T F F F
    F T T T
    F F T T

  • 等值：\(P \rightarrow Q = \neg P \vee Q\)

  • 蕴涵词 \(\rightarrow\) 与自然用语“如果……那么……” 有一致的一面，可表示因果关系。然而 \(P, Q\) 是无关的命题时， 逻辑上允许讨论 \(P \rightarrow Q\)。 并且 \(P = F\) 则 \(P \rightarrow Q = T\)， 这在自然用语中是不大使用的。
  • 蕴含式 \(P \rightarrow Q\) 可以用多种方式陈述：
    • \(P\) 是 \(Q\) 的充分条件
    • \(Q\) 是 \(P\) 的必要条件
    • 若 \(P\)，则 \(Q\)
    • 除非 \(Q\)，才 \(P\)
    • 只要 \(P\)，就 \(Q\)
    • 只有 \(Q\)，才 \(P\)
    • \(Q\) 每当 \(P\)
    • \(P\) 仅当 \(Q\)
    • 除非 \(Q\)，否则非 \(P\)
  • 给定命题 \(P \rightarrow Q\)
    • 逆命题：\(Q \rightarrow P\)
    • 否命题：\(\neg P \rightarrow \neg Q\)
    • 逆否命题：\(\neg Q \rightarrow \neg P\)

双条件词 \(\leftrightarrow\)

  • 定义：双条件词（biconditional）\(\leftrightarrow\) 是个二元命题联结词，亦称等价符号。
    • 将两个命题 \(P,Q\) 联结起来构成新命题 \(P \leftrightarrow Q\)，读作 \(P\) 当且仅当 \(Q\)，或读作 \(P\) 等价于 \(Q\)。

  • 真值表：

    \(P\) \(Q\) \(P \leftrightarrow Q\)
    T T T
    T F F
    F T F
    F F T

  • 等值：

    \[ \begin{aligned} P \leftrightarrow Q &= (P \wedge Q) \vee (\neg P \wedge \neg Q)\\ &= (P \vee \neg Q) \wedge (\neg P \vee Q)\\ &= (P \rightarrow Q) \wedge (Q \rightarrow P) \end{aligned} \]

其他条件词

  • 异或 \(\bar{\vee}:P \bar{\vee} Q=(\neg P \wedge Q) \vee(P \wedge \neg Q)\)
  • 与非 \(\uparrow:P \uparrow Q=\neg(P \wedge Q)\)
  • 或非 \(\downarrow:P \downarrow Q=\neg(P \vee Q)\)

合式公式

  • 合式公式（简记为 \(\mathrm{Wff}\)）的定义：
    1. 简单命题(包括简单命题常量与命题变项)是合式公式
    2. 如果 \(A\) 是合式公式，那么 \(\neg A\) 也是合式公式
    3. 如果 \(A, B\) 是合式公式，那么 \((A \wedge B)\)，\((A \vee B)\)，\((A \rightarrow B)\) 和 \((A \leftrightarrow B)\) 是合式公式
    4. 当且仅当经过有限次地使用 1, 2, 3 所组成的符号串才是合式公式
  • 这个定义给出了建立合式公式的一般原则，也给出了识别一个符号串是否是合式公式的原则
  • 在实际使用中，为了减少圆括号的数量，可以引入一些约定
    • 如规定联结词优先级的办法，可按 \(\neg\)，\(\wedge\)，\(\vee\)，\(\rightarrow\)，\(\leftrightarrow\) 的排列次序安排优先的级别
    • 多个同一联结词按从左到右的优先次序

重言式、可满足式和矛盾式

  • 重言式：如果一个公式，对于它的任一解释 \(I\) 下其真值都为真，就称为重言式（永真式）
    • 如 \(P \vee \neg P\) 是一个重言式
    • 显然由 \(\vee\)、\(\wedge\)、\(\rightarrow\) 和 \(\leftrightarrow\) 联结的重言式仍是重言式
  • 可满足式：一个公式，如有某个解释 \(I_{0}\)，在 \(I_{0}\) 下该公式真值为真，则称这公式是可满足的
    • 如 \(P \vee Q\)， 当取 \(I_{0} = (T, F)\)， 即 \(P = T, Q = F\) 时便有 \(P \vee Q = T\)，所以是可满足的
    • 重言式都是可满足的
  • 矛盾式：如果一个公式，对于它的任一解释 \(I\) 下真值都是假，便称是矛盾式，又称永假式、不可满足式
    • 如 \(P \wedge \neg P\) 是矛盾式
  • 三类公式间的关系
    1. 公式 \(A\) 永真，当且仅当 \(\neg A\) 永假
    2. 公式 \(A\) 可满足，当且仅当 \(\neg A\) 非永真
    3. 不是可满足的公式必永假
    4. 不是永假的公式必可满足
  • 代入规则
    • \(A\) 是一个公式，对 \(A\) 使用代入规则得到公式 \(B\)，若 \(A\) 是重言式，则 \(B\) 也是重言式。
    • 为保证重言式经代入规则仍得到保持，要求：
      • 公式中被代换的 只能是命题变元（原子命题） ，不能是复合命题
      • 对公式中某命题变项施以代入，必须对该公式中出现的 所有同一命题 变项代换同一公式

命题形式化

  • 简单自然语句的形式化

    自然语言 合式公式
    ……是…… \(P\)
    ……不是…… \(\neg P\)
    既……又…… \(P \wedge Q\)
    如果……，那么…… \(P \rightarrow Q\)
    ……，但是…… \(P \wedge Q\)
    ……或…… \(P \vee Q\)

  • 较复杂自然语句的形式化

    自然语言 合式公式
    ……或……都能…… \(P \wedge Q\)
    ……或……（两者不能同时发生） \(P \overline{\vee } Q\)
    ……，除非…… \(\neg P \rightarrow Q\)

  • 波兰表达式

    • 使用联结词构成公式的三种方式：
      • 中缀式：\(P \vee Q\)
      • 前缀式：\(\vee\ P\ Q\) ，又称 波兰式
      • 后缀式：\(P\ Q\ \vee\) ，又称 逆波兰式
    • 将中缀式化成波兰式/逆波兰式，可由内层括号逐步向外层脱开（或是按运算优先级顺序逐步写成前缀式）

  • 悖论：悖论是自相矛盾的命题。

    • 即如果承认这个命题成立，就可推出它的否定命题成立
    • 反之，如果承认这个命题的否定命题成立，又可推出这个命题成立