命题#

**命题（proposition）**是能够确定真假的陈述句。

• 命题的取值只有两种：真（True）或假（False）；
• 疑问句、祈使句通常不是命题；
• 含有未确定自由变量、因而无法判断真假的陈述也不是命题。

原子命题#

**原子命题（atomic proposition）**是内部结构不再分析的最简单命题。

例如：

• $p$：北京是中国的首都；
• $q$：13 能被 6 整除。

复合命题#

**复合命题（compound proposition）**由若干原子命题通过逻辑联结词构成。

例：判断是否为命题#

TIP

判断一句话是否为命题，先问：在给定论域和语境下，它现在能否被唯一判断为真或假？

真值表#

其中最容易出错的是蕴含：

$p\to q$ 只有在 $p$ 为真而 $q$ 为假时为假，其余三种情况均为真。

角度一：承诺#

$p\to q$ 可以理解为一个承诺：

只要 $p$ 发生，我就保证 $q$ 发生。

只有出现“$p$ 已发生，但 $q$ 没发生”时，承诺才被违反。若 $p$ 没发生，就没有证据说明承诺被违反。

角度二：集合包含#

把命题对应的真值集合记作集合，则 $p\to q$ 表示：

若 $p$ 为假，可把 $p$ 看成空集，而空集是任意集合的子集，因此 $p\to q$ 为真。

WARNING

“前件为假，所以蕴含为真”是形式逻辑的定义。它不表示前件与后件之间具有现实因果关系。

蕴含消除#

右侧只有在 $\alpha$ 为真、$\beta$ 为假时为假，恰好与蕴含的真值表一致。

逆否命题#

**图片占位符：**插入 PPT 第 10 页的德摩根定律集合图，用于直观展示“交集取补变并集”“并集取补变交集”。

假言推理（Modus Ponens）#

与消解（And-Elimination）#

与导入（And-Introduction）#

双重否定消去#

单项归结（Unit Resolution）#

因为 $\alpha\lor\beta$ 为真，而 $\beta$ 为假，所以只能由 $\alpha$ 保证析取式为真。

归结（Resolution）#

其中 $\beta$ 与 $\neg\beta$ 被消去。

更一般地，若一个析取式中含有 $\alpha_k$，另一个前提能够推出 $\neg\alpha_k$，则可从析取式中消去 $\alpha_k$。

TIP

归结法的核心操作是：

1. 先消去公式中的 $\to$ 和 $\leftrightarrow$；
2. 找到一对互补文字，如 $\beta$ 与 $\neg\beta$；
3. 消去该对文字，保留其余析取项；
4. 重复操作，直到得到目标或推出矛盾。

例 1：证明 $\gamma$ 成立#

已知：

证明：$\gamma$。

先消去蕴含：

依次归结：

因此 $\gamma$ 成立。

例 2：证明命题集不可满足#

命题集为：

由前两个公式归结：

由后两个公式归结：

于是同时推出 $\beta$ 和 $\neg\beta$，产生矛盾，所以该命题集不可满足。

例 3：证明另一个命题集不可满足#

已知：

推理：

最终同时得到 $\alpha$ 与 $\neg\alpha$，所以命题集不可满足。

析取范式（DNF）#

有限个简单合取式构成的析取式：

其中每个 $\alpha_i$ 是若干文字的合取。

例如：

合取范式（CNF）#

有限个简单析取式构成的合取式：

其中每个 $\alpha_i$ 是若干文字的析取。

例如：

性质#

• 一个析取范式为假，当且仅当其中每个简单合取式都为假；
• 一个合取范式为真，当且仅当其中每个简单析取式都为真；
• 任一命题公式都存在与其逻辑等价的 DNF 和 CNF；
• DNF 和 CNF 一般都不唯一。

转换流程#

1. 消去 $\to$ 与 $\leftrightarrow$；
2. 用德摩根定律把否定推进到原子命题前；
3. 用分配律整理成 DNF 或 CNF。

例：求 DNF 与 CNF#

求：

先消去蕴含：

用德摩根定律：

这已经是析取范式。

再用分配律：

这就是合取范式。

个体#

个体是研究领域中能够独立存在的具体或抽象对象。

例如：

• Richard；
• 北京；
• 中国；
• 某个实数；
• 某个人。

个体变元、个体常项与个体域#

• $x,y$ 等表示个体变元；
• Richard、北京、$0.1$ 等具体取值称为个体常项；
• 个体允许取值的范围称为个体域或论域。

谓词#

谓词用于刻画个体的属性，或描述多个个体之间的关系，其输出只能为真或假。

• 一元谓词 $P(x)$：描述一个个体的属性；
• 二元谓词 $R(x,y)$：描述两个个体之间的关系；
• $n$ 元谓词 $P(x_1,\ldots,x_n)$：描述多个个体之间的关系。

例如：

客观事实的符号化#

1. Richard 是国王：

   $$King(Richard)$$

2. Lucy 和 Lily 是姐妹：

   $$Sister(Lucy,Lily)$$

3. 北京是中国的首都：

   $$Capital(Beijing,China)$$

函数#

例如：

输入个体后，函数输出另一个值。

谓词#

例如：

将“吉普车”代入后，$Car(\text{吉普车})$ 已经成为一个能够判断真假的命题。

函数输出“值”，谓词输出“真假”。

全称量词#

全称量词用 $\forall$ 表示“一切”“所有”“任意一个”。

表示论域中的所有个体都满足性质 $P$。

存在量词#

存在量词用 $\exists$ 表示“存在一个”“至少一个”“某些”。

表示论域中至少存在一个个体满足性质 $P$。

例：用量词描述事实#

所有国王都是人：

所有国王都头戴皇冠：

其中 $HeadOn(Crown,x)$ 表示 $x$ 头戴皇冠。形式化时要同时找出谓词及其输入对象。

WARNING

量词的含义依赖论域。例如 $(\exists x)(x^2=2)$ 在实数域中为真，在有理数域中为假。

所有 $A$ 都是 $B$#

全称命题通常使用蕴含：只有先满足 $A(x)$，才要求其满足 $B(x)$。

有些 $A$ 是 $B$#

存在命题通常使用合取：需要找到同一个个体，同时满足 $A$ 和 $B$。

没有 $A$ 是 $B$#

等价地：

并非所有 $A$ 都是 $B$#

等价地：

TIP

常见记忆：

• “所有……”常写成 $\forall+\to$；
• “存在……”常写成 $\exists+\land$。

约束变元#

受到量词约束的变量称为约束变元。

例如：

其中 $x$ 是约束变元。

自由变元#

没有受到任何量词约束的变量称为自由变元。

例如：

若前面没有量词，则 $x,y$ 都是自由变元。

量词作用域#

量词只对其作用域中的变量生效。括号能够明确作用域：

一般不加括号时，量词只约束其后的第一个完整公式，因此书写时应尽量加括号。

若 $B$ 中不含自由变量 $x$，则：

原因是 $B$ 不依赖 $x$，所以量词是否包住 $B$ 不改变 $B$ 的真假。

成立的分配律#

全称量词对合取满足分配律：

存在量词对析取满足分配律：

一般不成立的分配律#

反例#

令论域为 $\{1,2\}$，并设：

对于全称量词：

• 对每个 $x$，$A(x)\lor B(x)$ 都为真，所以 $(\forall x)(A(x)\lor B(x))$ 为真；
• $(\forall x)A(x)$ 为假，$(\forall x)B(x)$ 也为假，所以右侧为假。

对于存在量词：

• 没有同一个 $x$ 同时满足 $A(x)$ 与 $B(x)$，所以 $(\exists x)(A(x)\land B(x))$ 为假；
• 存在某个 $x$ 满足 $A$，也存在某个可能不同的 $x$ 满足 $B$，所以右侧为真。

这说明“存在一个人同时满足两个条件”与“分别存在人满足两个条件”含义不同。

项（term）#

项是描述对象的逻辑表达式，递归定义为：

1. 常量符号和变量符号是项；
2. 若 $f$ 是 $n$ 元函数符号，$t_1,\ldots,t_n$ 是项，则 $f(t_1,\ldots,t_n)$ 也是项；
3. 有限次使用上述规则得到的表达式是项。

原子谓词公式#

若 $P$ 是 $n$ 元谓词，$t_1,\ldots,t_n$ 是项，则：

称为原子谓词公式。

合式公式（well-formed formula）#

合式公式由以下规则生成：

1. 命题常项、命题变项、原子谓词公式是合式公式；
2. 若 $A$ 是合式公式，则 $\neg A$ 也是；
3. 若 $A,B$ 是合式公式，则 $A\land B$、$A\lor B$、$A\to B$、$A\leftrightarrow B$ 也是；
4. 若 $A(x)$ 是合式公式，则 $(\forall x)A(x)$ 和 $(\exists x)A(x)$ 也是；
5. 只有有限次使用上述规则构成的表达式才是合式公式。

全称量词消去（UI）#

既然所有个体都满足 $A$，任取一个个体也满足 $A$。

全称量词引入（UG）#

这里的 $y$ 必须代表任意个体，不能带有只对某个特殊对象成立的额外假设。

存在量词消去（EI）#

引入一个新的常量 $a$，表示某个满足 $A$ 的对象。

存在量词引入（EG）#

已知某个具体对象满足 $A$，就能推出至少存在一个对象满足 $A$。

例 1：证明蕴含关系的传递性#

已知：

证明：

推理：

1. 全称量词消去：

   $$P(y)\to Q(y)$$

2. 全称量词消去：

   $$Q(y)\to R(y)$$

3. 消去蕴含：

   $$\neg P(y)\lor Q(y)$$ $$\neg Q(y)\lor R(y)$$

4. 对 $Q(y)$ 与 $\neg Q(y)$ 归结：

   $$\neg P(y)\lor R(y)$$

5. 恢复为蕴含：

   $$P(y)\to R(y)$$

6. 因 $y$ 是任意个体，进行全称量词引入：

   $$(\forall x)(P(x)\to R(x))$$

例 2：由存在条件推出新的存在结论#

已知：

证明：

推理：

1. 对全称命题实例化：

   $$F(a)\to(G(a)\land H(a))$$

2. 对存在命题实例化：

   $$F(a)\land P(a)$$

3. 与消解得到：

   $$F(a),\qquad P(a)$$

4. 由假言推理：

   $$G(a)\land H(a)$$

5. 与消解得到 $H(a)$；再与 $P(a)$ 合取：

   $$P(a)\land H(a)$$

6. 存在量词引入：

   $$(\exists x)(P(x)\land H(x))$$

例：若干事实的谓词表示#

1. Tom 不仅喜欢踢足球，还喜欢打篮球：

   $$Like(Tom,Football)\land Like(Tom,Basketball)$$

2. Tom 的所有同学都喜欢他：

   $$(\forall x)(Classmate(Tom,x)\to Like(x,Tom))$$

3. 不是所有男生都喜欢打篮球：

   $$\neg(\forall x)(Boy(x)\to Like(x,Basketball))$$

   等价于：

   $$(\exists x)(Boy(x)\land\neg Like(x,Basketball))$$

4. 一个人是华侨，当且仅当他在国外定居且具有中国国籍：

   $$(\forall x) \left[ OverseasChinese(x) \leftrightarrow (Overseas(x)\land Chinese(x)) \right]$$

5. 男生都爱看世界杯：

   $$(\forall x)(Boy(x)\to Like(x,WorldCup))$$

例：每一个奇数都存在一个大于它的奇数#

定义：

形式化为：

注意 $\forall x\exists y$ 的次序：对不同的 $x$，可以选择不同的 $y$。

例：苏格拉底三段论#

定义：

$a$ 表示苏格拉底。

前提：

由全称量词消去：

再由假言推理：

即苏格拉底会死。

例：飞机问题#

前提：

1. 每架飞机或者停在地面，或者飞在天空；
2. 并非每架飞机都飞在天空。

证明：有些飞机停在地面。

定义：

形式化前提：

目标：

证明：

由第二个前提：

存在量词消去，取某个 $a$：

由第一个前提进行全称量词消去：

由 $Plane(a)$ 和假言推理：

再与 $\neg InSky(a)$ 作单项归结：

因此：

最后使用存在量词引入：

证毕。

总体结果#

总体看，不用药恢复率更高。

按性别分组#

分组后：

• 男性中，用药组恢复率 $93\%>87\%$；
• 女性中，用药组恢复率 $73\%>69\%$。

出现反转的关键是：

• 男女性别本身与恢复率相关；
• 用药组与不用药组的性别构成严重不平衡；
• 性别成为影响“是否用药”和“是否恢复”关系的混杂因素。

因此，仅比较总体条件概率可能掩盖数据生成过程中的结构。

另一个经典例子是 1973 年加州大学伯克利分校的研究生录取数据：总体上男性录取率高于女性，但在若干主要院系内部比较时，女性录取率并不低。原因之一是不同性别申请院系的难度分布不同。

**图片占位符：**插入 PPT 第 45 页的药物恢复率表，以及第 47 页的伯克利录取率表，用于展示辛普森悖论的总体—分组反转。

关联（Association）#

问题形式：

观察到 $A$ 时，$Y$ 会怎样？

数学形式：

它能够直接由观测数据中的联合分布计算。

干预（Intervention）#

问题形式：

主动把 $A$ 设置为某个值时，$Y$ 会怎样？

数学形式：

这里的 $do(A=a)$ 表示人为干预，不等同于被动观察到 $A=a$。

反事实（Counterfactual）#

问题形式：

某件事已经发生；在同一对象、同一背景下，若当时采取另一种行动，结果会怎样？

它需要同时考虑已经观察到的事实和没有发生的替代情形。

三者的区别是：

外生变量 $U$#

外生变量（exogenous variables）由模型外部决定，模型不解释它们如何产生。

它们通常表示：

• 未建模的背景条件；
• 外部扰动；
• 噪声；
• 个体差异。

内生变量 $V$#

内生变量（endogenous variables）由模型中的结构函数决定。

结构函数 $F$#

对每个内生变量 $V_i$，都有一个赋值函数：

其中 $PA_i$ 表示会直接影响 $V_i$ 的其他内生变量。

如果变量 $X$ 出现在 $Y$ 的结构函数 $f_Y$ 中，则 $X$ 是 $Y$ 的直接原因。

例：治疗、肝脏功能与水污染#

设：

• $X$：治疗方案；
• $Y$：肝脏功能；
• $Z$：水污染。

若认为治疗方案和水污染都会影响肝脏功能，可用图表示为：

其中水污染可能作为模型外部背景因素进入 $Y$ 的结构方程。

例：商品销量#

设：

• $X$：商品与其他商品的价格差；
• $Y$：广告费；
• $Z$：商品销量。

一个完全指定的结构方程可以写为：

因此 $X$ 和 $Y$ 都是 $Z$ 的直接原因，因果图为：

若具体函数未知，可写成部分指定模型：

其中 $U_1,U_2,U_3$ 表示未建模的外部因素。

TIP

老师对这一部分的要求以“理解模型组成与箭头含义”为主；后面的概率分解和独立性判断更需要熟练掌握。

写法步骤#

1. 对图中每个节点写一个概率因子；
2. 若节点没有父节点，写边缘分布 $P(X)$；
3. 若节点有父节点，写 $P(X\mid Parents(X))$；
4. 把所有因子相乘。

例：气候、产量和价格#

因果图：

其中：

• $X$：气候好；
• $Y$：水果产量高；
• $Z$：水果价格低。

联合概率分解为：

若：

则：

例：复杂 DAG#

PPT 第 58 页的图可分解为：

**图片占位符：**插入 PPT 第 58 页的复杂 DAG。读图时逐个寻找父节点，再写对应的条件概率因子。