ch1 命题逻辑的基本概念

1. 命题

命题是一个能判断真假且非真即假的陈述句。

命题的真值：命题所表达的判断结果。

真值只取两个值：真或假（\(1\) 或 \(0\)）。

真命题：与事实相符或表达的判断正确，真值为真。

假命题：与事实不符或表达的判断错误，真值为假。

规定：任何命题的真值都是唯一的，不能非真非假，也不能既真又假。

简单命题：不能被分解成更简单的命题，也称原子命题。

复合命题：由简单命题通过联结词联结而成的命题。

2. 联结词

1. 否定联结词（非，\(\lnot\)）

   设 \(p\) 为命题，复合命题 “非 \(p\)” 称为 \(p\) 的否定式，记作 \(\lnot p\)。

   \(\lnot p\) 为真当且仅当 \(p\) 为假。

2. 合取联结词（与，\(\land\)）

   设 \(p,q\) 是两个命题，复合命题 “\(p\) 并且 \(q\)” 称为 \(p\) 与 \(q\) 的合取式，记作 \(p \land q\)。

   \(p\land q\) 为真当且仅当 \(p\) 与 \(q\) 同时为真。

3. 析取联结词（或，\(\lor\)）

   设 \(p,q\) 是两个命题，复合命题 “\(p\) 或 \(q\)” 称为 \(p\) 与 \(q\) 的析取式，记作 \(p \lor q\)。

   \(p\lor q\) 为假当且仅当 \(p\) 与 \(q\) 同时为假。

4. 蕴涵联结词（如果 \(\dots\)，则 \(\dots\)，\(\to\)）

   设 \(p,q\) 是两个命题，复合命题 “如果 \(p\)，则 \(q\)” 称为 \(p\) 与 \(q\) 的蕴涵式，记作 \(p \to q\)。其中 \(p\) 是前件，\(q\) 是后件。

   \(p\to q\) 为假当且仅当 \(p\) 为真 \(q\) 为假。\(p\to q\) 的逻辑关系为 \(q\) 是 \(p\) 的必要条件。

   • 等价表述：\(\lnot p \lor q\)
     • 只要 \(p\)，就 \(q\)
     • 因为 \(p\)，所以 \(q\)
     • \(p\) 仅当 \(q\)
     • 只有 \(q\) 才 \(p\)
     • 除非 \(q\) 才 \(p\)
     • 除非 \(q\)，否则非 \(p\)
   • 作为推理式，只要前件为假，那么后件无论真假，该命题都是对的。举个例子：如果太阳从西边出来，我就不姓张。其实不论我是否姓张，太阳都不会从西边出来，所以这句话是对的。
   • 作为推理式，前后件之间未必存在内在联系。举个例子：如果 \(3+3=6\)，则雪是白色的。因为前件 “\(3+3=6\)” 为真，后件 “雪是白色的” 为真，因此该命题为真。

5. 双蕴涵联结词（当且仅当，\(\leftrightarrow\)，也称等价联结词）

   设 \(p,q\) 是两个命题，复合命题 “\(p\) 当且仅当 \(q\)” 称为 \(p\) 与 \(q\) 的等价式，记作 \(p \leftrightarrow q\)。

   \(p \leftrightarrow q\) 为真当且仅当 \(p\) 与 \(q\) 同时为真或同时为假。 \(p \leftrightarrow q\) 的逻辑关系为 \(p\) 与 \(q\) 互为充要条件。

   • 等价表述：
     • \((p \to q) \land (q \to p)\)
     • \((\lnot p \to \lnot q) \land (p \to q)\)

联结词是两个命题真值之间的联结，而不是命题内容之间的连接，因此复合命题的真值只取决于构成它们的简单命题的真值，而与它们的内容无关，与二者之间是否有关系无关。

联结词优先级：

• 从左到右优先级递减：\(()\)，\(\lnot\)，\(\land\)，\(\lor\)，\(\to\)，\(\leftrightarrow\)

真值表：

\(p\)	\(q\)	\(\lnot p\)	\(p \land q\)	\(p \lor q\)	\(p \to q\)	\(p \leftrightarrow q\)
\(0\)	\(0\)	\(1\)	\(0\)	\(0\)	\(1\)	\(1\)
\(0\)	\(1\)	\(1\)	\(0\)	\(1\)	\(1\)	\(0\)
\(1\)	\(0\)	\(0\)	\(0\)	\(1\)	\(0\)	\(0\)
\(1\)	\(1\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)

• 一个很棒的真值表工具网站

3. 合式公式及其赋值

命题常项（常元）：简单命题是命题逻辑中最基本的研究单位，其值是确定的，又称为命题常项或命题常元。

命题变项（变元）：真值可以变化的陈述句为命题变项或命题变元。常用 \(p\)，\(q\)，\(r \dots\) 表示命题变项。

当 \(p\)，\(q\)，\(r \dots\) 表示命题变项时，它们变成了取值为 \(0\) 或 \(1\) 的变项，因而命题变项已不再是一个固定的命题。

合式公式（命题公式）的表示：将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串。

合式公式：

1. 单个命题变项是合式公式，并称为原子命题公式。
2. 若 \(A\) 是合式公式，则 \((\lnot A)\) 也是合式公式。
3. 若 \(A\)，\(B\) 是合式公式，则 \((A \land B)\)，\((A \lor B)\)，\((A \to B)\)，\((A \leftrightarrow B)\) 也是合式公式。
4. 只有有限次地应用 \(1 \sim 3\) 形成的符号串才是合式公式。

设 \(A\) 为合式公式，\(B\) 为 \(A\) 中的一部分，若 \(B\) 也是合式公式，则称 \(B\) 为 \(A\) 的子公式。

设 \(p_1\)，\(p_2\)，\(\dots\)，\(p_n\) 是出现在公式 \(A\) 中的全部的命题变项，给 \(p_1\)，\(p_2\)，\(\dots\)，\(p_n\) 各指定一个真值，称为对 \(A\) 的一个赋值或解释。若指定的一组值使 \(A\) 的真值为 \(1\)，则称这组值为 \(A\) 的成真赋值；若使 \(A\) 的真值为 \(0\)，则称这组值为 \(A\) 的成假赋值。

4. 真值表及其构造方法

真值表：将命题公式 \(A\) 在所有赋值下的取值情况列成表，称作 \(A\) 的真值表。

构造真值表的具体步骤：

1. 找出公式中所含的全体命题变项 \(p_1\)，\(p_2\)，\(\dots\)，\(p_n\)（若无下标就按字典序排列），列出 \(2^n\) 个赋值。规定赋值从 \(00\dots 0\) 开始，然后按二进制加法，直到 \(11\dots 1\) 为止。
2. 按照运算的优先次序写出各子公式。
3. 对应各个赋值计算出各子公式的真值，直到最后计算出公式的真值。

5. 命题公式的分类

设 \(A\) 为任一命题公式，

1. 若 \(A\) 在它的各种赋值下取值均为真，则称 \(A\) 是重言式或永真式。
2. 若 \(A\) 在它的各种赋值下取值均为假，则称 \(A\) 是矛盾式或永假式。
3. 若 \(A\) 不是矛盾式，则称 \(A\) 是可满足式。

6. 重言式与代入规则

【代入规则】一个重言式，对其中所有相同的命题变项都用同一个合式公式代换，其结果仍为一个重言式。

换言之，\(A\) 是一个公式，对 \(A\) 使用代入规则得到公式 \(B\)，若 \(A\) 是重言式，则 \(B\) 也是重言式。

7. 命题形式化

所谓命题形式化（符号化），就是用命题公式的符号串来表示给定的命题。

命题符号化的方法：

1. 明确给定命题的含义。
2. 对复合命题，找联结词，分解出各个原子命题。
3. 设原子命题符号，并用逻辑联结词联结原子命题符号，构成给定命题的符号表达式。

8. 波兰表达式

若一个式子中同时使用两种或以上运算符放置方式时，无论对运算符的优先级怎样规定，括号都不能完全避免。

将中置、后置全部换成前置，或将中置、前置全部换成后置，这样便可不使用任何括号。

将中置表示化成波兰式（前置表示），可由内层括号逐步向外层脱开（或由外层向内层逐层脱开）的办法。

以波兰式表达的公式，当计算机识别处理时，可以自右向左扫描一次完成，避免了重复扫描。同样后置表示（逆波兰式）自左向右一次扫描可以识别处理一个公式，而且看起来更合理，常为计算机的程序系统所采用。