# 命题与联结词
命题是真假性唯一的陈述句，不能可真可假。若陈述句中存在悖论，或者分情况确定真假，也不构成命题

最简单的命题是**原子命题**，它是由简单陈述句构成的命题，将其抽象为符号，如`p`,`q`,`r`。它的作用和地位可以类比于单词，具有最基本的语义，也称为**原子语句**



由原子命题通过**联结词**联结而成的陈述句称为**复合命题**。逻辑联结词可以如下列出
- $\neg p$ ：**非**，否定联结词，称$\neg p$为**否定式**。$p$为正文字，$\neg p$为负文字
- $p\wedge q$：**与**，合取联结词，称$p\wedge q$为**合取式**
- $p\vee q$：**或**，析取联结词，称$p\vee q$为**析取式**
- $p\Rightarrow q$：**蕴含**，蕴含联结词，称$p\Rightarrow q$为**蕴含式**，$p$为前件，$q$为后件
- $p\Leftrightarrow q$：**双向蕴含**，等价联结词，当且仅当

规定联结词具有优先级
$$
()\to \neg\to\wedge,\vee\to\Rightarrow,\Leftrightarrow
$$
同级联结词从左到右结合。联结词的真假如下表

| $p,q$ | $\neg p$ | $p\wedge q$ | $p\vee q$ | $p\Rightarrow q$ | $p\Leftrightarrow q$ |
| :---: | :---: | :---: | :---: | :---: | :---: |
|啥啊|  $p$假时真   |  $pq$都真时真   |  $pq$都假时假   |  $p$真$q$假时假   |  $pq$真假相同时真   |
|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

比较难以理解的是蕴含联结词。可以这样理解：$p\Rightarrow q$为真意味着p蕴含q，即当p为真时q一定为真，而不要求p为假时q的真假性。也就是说p蕴含q不成立仅有一种可能，即p为真时q为假

# 逻辑等价
在所有的模型中两个语句真假相同称为**逻辑等价**。基本的逻辑等价可以列出如下表

| 定律         | 表达式1                                   | 表达式2                                   |
| ------------ | :----------------------------------------: | :----------------------------------------: |
| 双重否定律   | $\neg \neg A \equiv A$                   |                                          |
| 恒等律       | $A \lor A \equiv A$                      | $A \land A \equiv A$                     |
| 交换律       | $A \lor B \equiv B \lor A$               | $A \land B \equiv B \land A$             |
| 结合律       | $(A \lor B) \lor C \equiv A \lor (B \lor C)$ | $(A \land B) \land C \equiv A \land (B \land C)$ |
| 分配律       | $A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$ | $A \land (B \lor C) \equiv (A \land B) \lor (A \land C)$ |
| 德·摩根律    | $\neg (A \lor B) \equiv \neg A \land \neg B$ | $\neg (A \land B) \equiv \neg A \lor \neg B$ |

存在一些为常数的情况

| 定律   | 表达式1                  | 表达式2                  |
| ------ | :---------------------: | :----------------------: |
| 零律   | $A \lor 1 \equiv 1$      | $A \land 0 \equiv 0$     |
| 同一律 | $A \lor 0 \equiv A$      | $A \land 1 \equiv A$     |
| 排中律 | $A \lor \neg A \equiv 1$ |                          |
| 矛盾律 |                          | $A \land \neg A \equiv 0$|

此外还有一些常用的逻辑恒等式

| 定律             | 表达式                                  |
| ---------------- | --------------------------------------- |
| 蕴涵等值式       | $A \Rightarrow B \equiv \neg A \lor B$ |
| 等价等值式       | $A \Leftrightarrow B \equiv (A \Rightarrow B) \land (B \Rightarrow A)$ |
| 假言易位         | $A \Rightarrow B \equiv \neg B \Rightarrow \neg A$ |
| 等价否定等值式   | $A \Leftrightarrow B \equiv \neg A \Leftrightarrow \neg B$ |
| 归谬论           | $(A \Rightarrow B) \land (A \Rightarrow \neg B) \equiv \neg A$ |

# 合取范式与析取范式

首先需要定义**简单析取式**和**简单合取式**

:::tip{title="简单析取式"}
有限个文字用“或”连接形成的析取式
:::
简单析取式的例子可以列出如下
- $p$
- $\neg p$
- $p\lor q$
- $p\lor \neg q$
- ...


:::tip{title="简单合取式"}
有限个文字用“与”连接形成的合取式
:::
简单合取式的例子可以列出如下
- $p$
- $\neg p$
- $p\land q$
- $p\land \neg q$
- ...

进一步定义**析取范式**与**合取范式**

:::tip{title="析取范式DNF（与或式，先与再或）"}
有限个简单合取式用“或”连接形成的析取式
$$
A_1\lor A_2\lor\cdots\lor A_n
$$
其中$A_i$是简单合取式
:::

:::tip{title="合取范式CNF（或与式，先或再与）"}
有限个简单析取式用“与”连接形成的合取式
$$
A_1\land A_2\land\cdots\land A_n
$$
其中$A_i$是简单析取式
:::

可以利用逻辑等价将命题改为析取范式或是合取范式

# 有效性和可满足性

**重言式**：在所有模型都为真的语句，又称为**有效的**语句，如
$$
A\lor \neg A
$$

**矛盾式**：在所有模型都为假的语句，如
$$
A\land \neg A
$$

**可满足式**：非矛盾式的语句。重言式是可满足式，但是可满足式不是重言式

重言式的反是矛盾式，可以利用这个关系证明命题，即**反证法**
$$
A\Rightarrow B 等价于 A\land \neg B 矛盾
$$

逻辑学（一）——命题与逻辑

# 逻辑的基本概念
逻辑是用符合语法的语言来表示信息从而能够推理结论

1. 语法(Syntax) 定义语句所用的语言规范
2. 语义(Semantics) 定义语句的“含义”,即每个语句在每个可能世界的真值(True or False)

若定义语法为算数语法，那么合法的语句的一个例子是
$$
x+2\geq y
$$

而$x2+y$不符合算数语法，不是语句。在世界$x=7,y=1$中$x+2\geq y$为真，而在$x=0,y=6$的世界中该语句为假



# 模型
在逻辑学的描述中，变量是布尔的，也就是拥有两个取值，`1`和`0`，也即`真`和`假`

模型就是“可能的世界”的抽象描述，如三个布尔变量ABC，它们会构成8个可能的世界，也就是具有8个可能的模型
$$
\{A,B,C\}=\{0,0,0\}, \{0,0,1\}, \{0,1,0\}, \{0,1,1\}, \{1,0,0\}, \{1,0,1\}, \{1,1,0\}, \{1,1,1\}
$$

每个模型都代表着一个“世界”，即可能出现的情况（有点像随机事件发生的平行世界？）


# 蕴含

蕴含描述两个语句的关系

:::info{title="Note"}
A蕴含B：意为当A为真时B一定为真
:::

它的另一种解释是：在A为真的每个世界中B都为真。蕴含记为`|=`，A蕴含B即记为
$$
A|=B
$$

如果令$W(A)$为所有使得$A$为真的世界的集合，$W(B)$为所有使得$B$为真的世界的集合，那么这两个集合是包含的关系
$$
W(A)\subset W(B)
$$

# 推断

推断是针对推理算法的，对一个语句执行推理算法可以得到另一个语句。记推理算法为I,则记
$$
A|-_IB
$$

意为推理算法I从A导出了B。对于推理算法，我们关心的是它的**可靠性**与**完备性**

- 可靠性：假定算法I从A导出了B，经检验对于所有这样的A和B，都有A蕴含B（推导是对的）
    $$
    若A|-_IB则A|=B，称I可靠
    $$
- 完备性：若A蕴含B，则对A施加算法I一定能得到B
    $$
    若A|=B则A|-_IB，称I完备
    $$

逻辑学（零）——模型，蕴含与推断

CSP与传统搜索不同的是采用因子化表示状态
- 因子化表示为一组变量，变量有自己的值
- 求解问题时，每个变量的值须满足对该变量约束




# 约束满足问题
可以以三部分定义约束满足问题
- 变量集合X，$\{X1,X2,\cdots,X_n\}$
- 域集合D，表征变量的取值范围，每个变量都需要有与$\{D_1,D_2,\cdots,D_n\}$
- 约束集合C，规定哪些变量取值是允许的

约束可以抽象地表示为
$$
<变量组，组中的变量应满足的关系>
$$

CSP希望对变量进行赋值，不违反约束的赋值是**合法赋值**，每个变量都被赋值则为**完美赋值**。CSP的解是**合法完美赋值**

# 约束传播
CSP下可以通过约束传播的过程进行推断。选择变量赋值时，需要考虑的合法选项会减少

1. 节点一致性：单个变量的取值在其域中
2. 弧一致性：单个变量的取值满足二元约束

如对于约束“X,Y是整数，并且$Y=X^2$”中，`整数`是节点一致性，$Y=X^2$是弧一致性

# AC3
AC3算法用于进行弧一致性约束，可以描述如下

0. 将所有的弧（两个变量的二元约束）加入队列
1. 从队列中取出弧$(X_i,X_j)$
2. 检查两个变量$X_i,X_j$是否有不满足该约束的取值，若有则删除取值
3. 若`2`操作使得某些变量的域变小，则将这些变量关联的弧加入队列
4. 回到`1`循环，直到队列为空

# 路径一致性3-Consistency

弧一致性只考虑了二元约束，可能并不能很好地约束变量的域。此时需要引入第三个变量通过观测变量的三元推断将二元约束收紧

可以进一步推广到k-Consistency

约束满足问题(CSP: Constraint Satisfaction  Problem)

# 双人零和博弈
双人零和博弈是两个玩家进行的**零和博弈**。零和博弈即
- 参与双方的效用相反，一个玩家的效用高就意为着另一个玩家的效用低
- 零和博弈是纯竞争而没有合作，不存在双赢

博弈双方可以采用同一效用值，一方使得效用最大，一方使得效用最小





可以给予双人零和博弈一个形式化的描述。将两个参与者分别称为`MIN`和`MAX`，`MAX`先移动，然后`MIN`移动，直到博弈结束

一个博弈中的状态需要有以下必要的属性：`将要移动的玩家`，`可以采取的动作`，`是否终止`。不妨给予定义
- $S_0$： 初始状态，即博弈开始时的状态
- To-Move(s)： 状态s下将要移动的玩家
- Action(s)： 状态s下全体合法移动的集合
- 转移模型Result(s,a)： 状态s下执行动作a产生的状态
- 中止测试Is-terminal(s)： 判断是否博弈结束
- 效用函数Utility(s)： 终止状态s下的效用函数


# 极小极大搜索(MiniMaxSearch)

极小极大算法适用于确定性的零和博弈，一方最小化结果，另一方最大化结果。假定所有参与者都最佳移动，极小极大算法期望中构造一棵**状态空间搜索树**，博弈双方轮流行动，如图

![image.png](/static/img/a6490ed19352ff04642a3c5131ea4e3f.image.webp)

在博弈中，双方都选择对自己最有利的行为，即`MAX`选择效用最大的状态进行转移，`MIN`选择效用最小的状态进行转移。但是对于非终止状态无法定义效用，因而对于状态`s`定义**极小极大值**
$$
MINMAX(s)=
\begin{cases}
Utility(s)&s是终止状态\\
所有可转移状态的最大MINMAX&MAX玩家将要移动\\
所有可转移状态的最小MINMAX&MIN玩家将要移动
\end{cases}
$$

即

:::info{title="Note"}
MIN节点的MINMAX是`MIN`玩家能确保获得的最小效用，MAX阶段的MINMAX是`MAX`玩家能确保获得的最大效用
:::

对于`MIN`玩家而言，最佳的行动策略就是选取拥有最小MINMAX的状态；对于`MAX`玩家而言，最佳的行动策略就是选取拥有最大MINMAX的状态

极小极大搜索是对博弈树进行完整的深度优先搜索。记博弈树的最大深度为`m`，每个节点的合法行动数为`b`，那么它的时间复杂度是指数级的
$$
O(b^m)
$$
由于是深度优先搜索，空间复杂度倒不大，为$O(bm)$。虽然它是完备的，但是需要的资源是非常难以满足的

# $\alpha-\beta$剪枝
$\alpha-\beta$剪枝是对博弈树进行修剪，剪去了对结果没有影响的部分。$\alpha$剪枝是针对`MAX`玩家而言的，$\beta$剪枝是针对`MIN`玩家而言的

定义$\alpha$


:::tip{title="定义"}
$\alpha$是到目前为止所有路径上所有`MAX`选择点的MINMAX最大值
:::

如果在执行极大极小搜素时发现某个`MAX`将行动的节点其MINMAX小于$\alpha$，那么该节点以及它所有的兄弟节点都不需要考虑。这是因为`MAX`玩家应该尽可能选择高MINMAX值的节点所在分支，而不会允许`MIN`玩家逼自己选择较低MINMAX值的分支

再清晰一些的说法是，记该节点为`n`，它的父节点是`MIN`玩家做选择，`MAX`玩家是处于`n`还是`n`的兄弟是由`MIN`玩家决定的。`MIN`玩家一定会选择最小的MINMAX，轮到`MAX`玩家选择时，能确保的效用一定小于等于`n`节点的MINMAX，因而`MAX`玩家不会给`MIN`玩家选择的机会，即不会选择`n`所在的分支

:::info{title="Note"}
$\alpha$剪枝：若某一个MAX节点的MINMAX小于$\alpha$，则将其兄弟全部剪枝
:::

这对于`MIN`玩家也是同理，定义$\beta$值

:::tip{title="定义"}
$\beta$是到目前为止所有路径上所有`MIN`选择点的MINMAX最小值
:::
$\beta$剪枝策略是

:::info{title="Note"}
$\beta$剪枝：若某一个MIN节点的MINMAX大于$\beta$，则将其兄弟全部剪枝
:::

$\alpha-\beta$剪枝的有效性依赖于节点的检查顺序。最坏的顺序是每次都考察最大的MAX和最小的MIN，无法减去任何的兄弟节点，最好顺序是考察最小的MAX和最大的MIN，可以剪去尽可能多的兄弟节点。在完美顺序下的时间复杂度为
$$
O(b^{m/2})
$$

# 启发式$\alpha-\beta$数搜索
在资源受限的情形下应使用**深度受限搜索**，即
- 截断测试(Cutoff-Test)代替终止测试
- 启发式评价函数EVAL代替效用函数Utility

评价函数评估非终止节点的分值，理想中应尽可能接近实际的MINMAX。由于深度受限，评价函数不可能完全与效用函数等同，会出现**视野效应**，即无法考虑搜索深度以外的情形

# 蒙特卡洛树搜索 (MCTS)
蒙特卡洛树搜索是基于概率模拟的结果构建启发式评价函数，一种常用的选择是Upper Confidence Bounder
$$
UCB(s)=\dfrac{U(s)}{N(s)}+C\cdot\sqrt{\dfrac{\log N(s的父亲)}{N(s)}}
$$
其中
- $U(s)$是经过$s$节点所有模拟效用值之和
- $N(s)$为经过$s$节点的所有模拟次数
- $C$是一个常数，常取$\sqrt2$，用于平衡利用和探索

前一项$\dfrac{U(s)}{N(s)}$代表“经验”，即该节点的平均效用；后一项是考虑到其父节点的效用对它效用的修正，代表“探索”

# 随机博弈
随机博弈即一方选择动作后状态的转移并不确定，即存在“机会节点”
<center>
    <img src="/static/img/cda106b45f9ad41c9862e5b384bf945a.image.webp" width=70%/>
</center>

此时极小极大搜索中的MINMAX就可以变为期望MINMAX
$$
ExpectMINMAX(s)=
\begin{cases}
Utility(s)&s终止状态\\
Max:ExpectMINMAX(s的所有后继)&MAX玩家将要移动\\
Min:ExpectMINMAX(s的所有后继)&MIN玩家将要移动\\
ExpectMINMAX(s的所有后继)的数学期望&下一步是机会节点
\end{cases}
$$

极小极大搜索与α-β剪枝

# 局部束搜索Local Beam Search
朴素的贪心局部搜索仅保留一个状态，较难找到全局最优解；若同时保留多个状态，则有更大的概率得到全局最优解，即**局部束搜索**



可以将算法描述如下

0. 初始化：随机产生k个状态
1. 对于每个状态，迭代生成$k$个后继节点，共生成$k^2$个后继状态
2. 从$k^2$个后继状态中选取$k$个最好的状态，回到`1`循环，直到找到目标状态

局部束搜索的问题在于$k$个状态多样性不足，一个改进的方案是在步骤`2`中随机选取后继状态增加多样性，即**随机束搜索**

# 遗传算法

遗传算法模拟了自然界中生物进化的过程：遗传变异-自然选择

- 个体：一个可能的状态
- 种群：一些个体组成的集合
- 杂交：以两个或更多的个体为基础构造新的个体，参与遗传的个体数目称为**混合数**，自然界中的混合数一半为2，算法实现中可以更多
- 突变：新生成的个体出现亲本没有的特征
- 适者生存：使得**适应度评价函数**值更高的个体可以继续在种群中生存下去

遗传算法能够找到问题的最优解，具有足够大的多样性