# 系数表示法与点值表示法
一个$N$次多项式有$N+1$个系数, 它们可以唯一确定这个多项式; 此外可以取$N+1$个点, 计算多项式在这些点的值; 这样$N+1$个不同的键值对也可以唯一确定一个$N$次的多项式

在计算多项式乘法时, 系数表示法需要$O(n^2)$的时间复杂度, 而点值表示法只需要$O(n)$的复杂度. 这是因为两个多项式乘积在一点的值等于它们俩在这点值的乘积

如果能有很快的方法在系数表示法与点值表示法之间转换, 将能极大地加速多项式乘法



# 单位根与FFT

首先将系数表达式转化为点值不能朴素地计算, 这是因为计算一个点值需要$N$次乘法, 这样复杂度仍然是$O(n^2)$, 没有意义. 不过若是取单位根
$$
x_k=e^{2k\pi/N}
$$

它的任意次方都可以以常数复杂度求出, 而不用进行乘法
$$
x_k^m=e^{2mk\pi/N}
$$

如果有多项式
$$
f(x)=a_0+a_1x+\cdots+a_Nx^N=\sum_{n=0}^{N-1} a_kx^n
$$

那么
$$
f(x_k)=\sum_{n=0}^{N-1} a_ke^{i2\pi nk/N}
$$

这个形式容易让人想起一位故人, 因而不妨取单位根是负指数,那么不妨再直接一点
$$
f(x_k)=\sum_{n=0}^{N-1} a_ke^{-i2\pi nk/N}=DFT\{a\}[k]
$$

因而

:::info{title="Note"}
点值表示是系数表示的离散傅里叶变换
:::

而FFT的复杂度是$O(n\log n)$, 这就实现了加速

自然, 将点值表示还原回系数表示, 也只需要进行傅里叶逆变换
$$
a_k=IDFT\{x\}[k]
$$
进行傅里叶逆变换也可以由FFT以$O(n\log n)$的复杂度完成

FFT加速多项式乘法

# 傅里叶变换与离散傅里叶变换DFT
一个时域上的函数 $x(t)$ 其傅里叶变换定义为
$$
\tilde{X}(\omega)=\int_{-\infty}^{+\infty}x(t)e^{-i\omega t}d t
$$
如果用频率表示, 将$\omega=2\pi f$代入可得
$$
\tilde{X}(f)=\int_{-\infty}^{+\infty}x(t)e^{-i2\pi f t}d t
$$



对于计算机而言, 记录的下来的函数是对真实函数的**采样**. 如果记采样的时间周期为$T$, 那么采样得到的离散函数自变量应当是采样轮次
$$
x[n]=x(nT)
$$

为了得到离散傅里叶变换, 需要具体地描述采样的过程. 利用$\delta$函数
$$
\delta_s(t)=\sum_{-\infty}^{+\infty}\delta(t-nT)
$$

将它与$x(t)$相乘得到采样后的信号
$$
x_s(t)=\sum_{-\infty}^{+\infty}x(t)\delta(t-nT)
$$
它在除了采样点$nT$之外的点都为零, 虽然在采样点取值正无穷, 但是鉴于
$$
\int_{-\infty}^{+\infty}x(t)\delta(nT)=x(nT)
$$

如果认为采样的过程是对一段段的时间积分,即
$$
x[n]=\int_{nT-T/2}^{nT+T/2}x(t)dt
$$

那么确实有
$$
x[n]=\int_{nT-T/2}^{nT+T/2}x_s(t)dt
$$

当$nT$包含在积分区间内时,积分就为$x(nT)$,否则为零. 因而认为$x_s(t)$是$x[n]$在连续下的形式, 对$x[n]$做傅里叶变换就是在对$x_s(t)$做傅里叶变换. 鉴于$\delta$函数性质优良, 那么
$$
X_s(\omega)=\int_{-\infty}^{+\infty}\left(\sum_{-\infty}^{+\infty}x(t)\delta(t-nT)\right)e^{-i\omega t}dt=\sum_{-\infty}^{+\infty}x(nT)e^{-i\omega nT}
$$

不过显然不可能进行无穷多次采样. 假定在$0\sim t_0$的时间内进行$N$次采样,采样间隔为$T$, 其余未采样的地方视为周期的, 即将$x(t)$视为周期函数

$$
x(t)=\begin{cases}
x(t)&t\in[0,t_0)\\
x(t+kt_0)&\text{其他},k\in \mathbb{N}
\end{cases}
$$

那么它可以进行傅里叶级数展开
$$
x(t)=\sum_{-\infty}^{+\infty}e^{i2\pi n t/t_0}\dfrac{1}{t_0}\int_0^{t_0}x(t)e^{-i2\pi nt/t_0}dt
$$

这说明它的傅里叶变换是离散的
$$
X(\omega)=\sum_{-\infty}^{+\infty}2\pi\delta(\omega-n\omega_0)\dfrac{1}{t_0}\int_0^{t_0}x(t)e^{-in\omega_0 t}dt,\quad \omega_0=\dfrac{2\pi}{t_0}
$$

利用$\omega=2\pi f$将其写为频率
$$
X(f)=\sum_{-\infty}^{+\infty}\delta(f-nf)f_0\int_0^{t_0}x(t)e^{-i2\pi nf_0 t}dt,\quad f_0=\dfrac{1}{t_0}
$$


将周期的$x_s(t)$代入后式得到
$$
f_0\int_0^{t_0}x(t)e^{-i2\pi nf_0 t}dt=f_0\sum_{k=0}^{N-1}x(kT)e^{-i2\pi n kTf_0}
$$
鉴于$f_0=1/t_0=1/NT$,那么

$$
f_0\int_0^{t_0}x(t)e^{-i2\pi nf_0 t}dt=f_0\sum_{k=0}^{N-1}x(kT)e^{-i2\pi n k/N}
$$

记

:::info{title="离散傅里叶变换DFT"}
$$
X[n]=\sum_{k=0}^{N-1}x[k]e^{-i2\pi n k/N}
$$
:::

鉴于$e^{-2\pi nk/N}$的周期性, 只需要计算$0<n<N-1$即可

# FFT的数学基础
根据DFT的表达式不难发现, 如果进行朴素的乘法, 求解一个$X[n]$复杂度为$O(n)$, 求解全部$N$个的复杂度为$O(n^2)$

不过稍加分析,不难发现求解的主要复杂度在于后面的相位项
$$
W[n,k]=\exp\left\{-i\dfrac{2\pi}{N}nk\right\}
$$

由于$k$与$x[k]$相联系, 从$n$处想办法. 注意到
$$
W[n+N/2,k]=\exp\left\{-i\dfrac{2\pi}{N}nk\right\}\exp\left\{-i\pi k\right\}
$$

这意味着当$k$为偶数时有
$$
W[n+N/2,k]=W[n,k]
$$

因而计算$X[n]$时考虑将$n$分奇偶
$$
X[n]=\sum_{k=0}^{N-1}x[k]W[n,k]=\sum_{k=0}^{N/2-1}x[2k]W[n,2k]+\sum_{k=0}^{N/2-1}x[2k+1]W[n,2k+1]
$$

后面的$2k+1$不是偶数, 就把它变成偶数, 利用
$$
W[n,2k+1]=W[n,1]W[n,2k]
$$

那么
$$
X[n]=\sum_{k=0}^{N/2-1}x[2k]W[n,2k]+W[n,1]\sum_{k=0}^{N/2-1}x[2k+1]W[n,2k]
$$

鉴于$W[n+N/2,k]=W[n,k]$, 那么
$$
X[n+N/2]=\sum_{k=0}^{N/2-1}x[2k]W[n,2k]+W[n+N/2,1]\sum_{k=0}^{N/2-1}x[2k+1]W[n,2k]
$$

不好处理的是$W[n+N/2,1]$, 不过不难发现
$$
W[n+N/2,1]=\exp\left\{-i\dfrac{2\pi}{N}n-\pi i\right\}=-\exp\left\{-\dfrac{2\pi}{N}n\right\}=-W[n,1]
$$

这就意味着

:::info{title="递推式1"}
$$
X[n+N/2]=X[n]\text{的偶数部分}-W[n,1]\cdot X[n]\text{的奇数部分}
$$
:::


这告诉我们, 知道了$X[n]$的偶数部分就等于知道了$X[n+N/2]$的偶数部分, 奇数也一样;

---

下一步是求解奇数和偶数部分. 先考察偶数部分
$$
\sum_{k=0}^{N/2-1}x[2k]W[n,2k]
$$

记$N'=N/2$, 将偶数位置单独挑出来合成一份$N'$长度的序列, 得到$x'[k],k=0\sim N'$, 那么
$$
W[n,2k]=\exp\left\{-i\dfrac{2\pi}{N}n2k\right\}=\exp\left\{-i\dfrac{2\pi}{N'}nk\right\}=W'[n,k]
$$

那么就可以将偶数部分改写为
$$
X[n]\text{的偶数部分}=\sum_{k=0}^{N'-1}x'[k]W'[n,k]
$$
这不正好是偶数序列$x'[k]$的傅里叶变换. 再考察奇数部分
$$
\sum_{k=0}^{N/2-1}x[2k+1]W[n,2k+1]
$$
如法炮制,令$N'=N/2$, 将奇数位置挑出来合成$x'[k]$, 那么
$$
W[n,2k+1]=W[n,1]W[n,2k]=W[n,1]W'[n,k]
$$
那么就可以将奇数部分改写为
$$
X[n]\text{的奇数部分}=W[n,1]\sum_{k=0}^{N'-1}x'[k]W'[n,k]
$$
进而得到奇数部分和偶数部分的递推式

:::info{title="递推式2"}
$$
X[n]\text{的偶数部分}=DFT\{x的偶数序列\}[n]
$$
$$
X[n]\text{的奇数部分}=W[n,1]DFT\{x的奇数序列\}[n]
$$
:::

# 快速傅里叶变换FFT算法

0. 初始化长度为$N$的序列$x^{(0)}$
1. 对于当前序列$x^{(m)}$, 求解它的FFT只需要求解前半部分的奇数和偶数部分, 后半部分即可由递推式自然得到
   $$
   X[n+N/2]=X[n]\text{的偶数部分}-W[n,1]\cdot X[n]\text{的奇数部分}
   $$
2. 求解前半部分$n=0\sim N/2-1$, 利用递推式
   $$
   X[n]\text{的偶数部分}=DFT\{x的偶数序列\}[n]
   $$
   $$
   X[n]\text{的奇数部分}=W[n,1]DFT\{x的奇数序列\}[n]
   $$
   问题转化为分别求解奇偶序列的FFT

如此, FFT是一种二分法, 其时间复杂度为$O(n\log n)$

# 快速逆傅里叶变换IFFT
注意到
$$
x[n]=\dfrac{1}{N}\sum_{k',k=0}^{N-1}x[k]e^{-i2\pi n(k-k')/N}=\dfrac{1}{N}\sum_{k'=0}^{N-1}X[k']e^{i2\pi nk'/N}
$$

因而定义离散傅里叶逆变换IDFT

:::info{title="离散傅里叶逆变换IDFT"}
$$
x[n]=\dfrac{1}{N}\sum_{k=0}^{N-1}X[k]e^{i2\pi nk/N}
$$
:::

它长得跟DFT一样,只不过将$i$改为了$-i$,并除了个$N$, 那么计算IFFT实际上只需要
$$
IFFT\{X\}=\dfrac{1}{N}FFT\{X;i\to -i\}
$$

快速傅里叶变换FFT

# 主定理
主定理是用于计算如下递推形式的时间复杂度
$$
T(n)=aT\left(\dfrac nb\right)+f(n)
$$



根据$f(n)$与 $\log_ba$ 的大小关系分为四种情况
$$
f(n)\stackrel{?}{>=<}n^{\log_ba}
$$

1. $f(n)=O\left(n^{\log_ba-\epsilon}\right)$ 可以理解为 $f(n)<n^{\log_ba}$, 则有
$$
T(n)=\Theta\left(n^{\log_ba}\right)
$$
2. $f(n)=\Theta\left(n^{\log_ba}\right)$ 可以理解为 $f(n)=n^{\log_ba}$, 则有
$$
T(n)=\Theta\left(n^{\log_ba}\log n\right)
$$
3. $f(n)=\Omega\left(n^{\log_ba+\epsilon}\right)$ 可以理解为 $f(n)>n^{\log_ba}$, 则有
$$
T(n)=f(n)
$$
4. 第四种情形是特殊的, 当$f(n)=\Omega\left(n^{\log_ba}\log^kn\right)$ 即 $f(n)=n^{\log_ba}\log^kn$时
$$
T(n)=\Theta\left(n^{\log_ba}\log^{k+1}n\right)
$$

# 简化的主定理

如果取$f(n)$是多项式复杂度的, 即 $f(n)=O(n^d)$, 递推式即
$$
T(n)=aT\left(\dfrac nb\right)+O(n^d)
$$
那么就能讲主定理简化为

1. $d<\log_ba$
$$
T(n)=O\left(n^{\log_ba}\right)
$$
2. $d=\log_ba$
$$
T(n)=O(n^d\log n)
$$
3. $d>\log_b a$
$$
T(n)=O(n^d)
$$

时间复杂度分析:主定理

# 一阶马尔可夫链
某一时刻状态转移的概率只依赖前一个状态，状态之间以一定概率转移



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

将概率写为矩阵，$P_{ij}$表示从状态$i$转移到状态$j$的概率

$$
P=\begin{pmatrix}
0.9&0..075&0.25\\
0.15&0.8&0.05\\
0.025&0.25&0.5
\end{pmatrix}
$$
$P_{ij}$也可以用条件概率写为
$$
P(j|i)
$$
那么初态也可以写完一个向量，$a_i$表示系统处于状态$i$的概率，那么经过$k$次状态转移后，系统的状态就是
$$
P^k a
$$

若令$k\to\infty$，则状态的分布达到稳定；该稳定的状态与初态无关

# 隐马尔可夫模型

隐马尔可夫模型中，系统的状态不能直接观察到，只能通过**传感器**反映。通常来说给定状态转移模型，它只与上一刻的状态有关
$$
P(R_t|R_{t-1})
$$
和传感器模型，它只与当前状态有关
$$
P(U_t|R_t)
$$
还需要给定一个初始分布
$$
P(R_0)
$$
此后先根据转移模型得到转移的分布（此处是矩阵乘法）
$$
P(R_t)=P(R_t|R_{t-1})P(R_{t-1})
$$
然后根据传感器的结果$u_t$修正分布（此处是向量的点乘）
$$
P(R_t|u_t)=\alpha P(u_t|R_t)\cdot P(R_t)
$$

# 确定性环境的决策
定义
- 状态的集合$S$
- 每个状态下可以采取的动作集合$A$
- 奖励函数$R(s,a,s')$，它表示在状态$s$时采取动作$a$转移到状态$s'$获得的奖励

可以定义**效用**是历史所有动作的累加，称为**加性奖励**
$$
U_h(s_0,a_0,s_1,a_1,\cdots)=R(s_0,a_0,s_1)+R(s_1,a_1,s_2)+\cdots
$$

更常用的是**加性折扣奖励**
$$
U_h(s_0,a_0,s_1,a_1,\cdots)=\gamma^0R(s_0,a_0,s_1)+\gamma^1R(s_1,a_1,s_2)+\cdots
$$
其中$\gamma$称为折扣因子，接近$0$时倾向于当前奖励，接近$1$时倾向于长期奖励，等于$1$时退化为纯加性奖励

<center><br><hr width=40%><br></center>

**策略**就是在所有状态下应该采取的动作，**最优策略**是能产生最大效用的策略，它与初始状态无关

由状态$s$开始执行策略$\pi$的效用为
$$
U^\pi(s)=\sum_{t=0}^\infty R(s_t,\pi(s_t),s_{t+1})
$$

若采取加性折扣奖励，则策略$\pi$的效用为
$$
U^\pi(s)=\sum_{t=0}^\infty \gamma^t R(s_t,\pi(s_t),s_{t+1})
$$

# 马尔可夫决策过程MDP

与确定性环境的决策不同的是，马尔可夫决策过程采取动作后得到的状态是随机的，由**转移模型**刻画。$T(s,a,s')$表示采取动作$a$后从状态$s$转移到状态$s'$的概率，即
$$
T(s,a,s')=P(s'|s,a)
$$

那么动作的效用也应由期望定义
$$
U(s_0,a)=E[R(s_0,a,s_t)]=\sum_tP(s_t|s_0,a)R(s_0,a,s_t)
$$

采用策略$\pi$的效用也应该由期望定义（采样加性折扣奖励）
$$
U^\pi(s)=E\left[\sum_{t=0}^\infty \gamma^t R(s_t,\pi(s_t),s_{t+1})\right]
$$

 # 效用与贝尔曼方程
 
 一个**状态的效用**定义为从该状态出发的期望总奖励，正如上一节所说，从状态$s_0$开始执行策略$\pi$获得的期望效用为
$$
U^\pi(s_0)=E\left[\sum_{t=0}^\infty \gamma^t R(s_t,\pi(s_t),s_{t+1})\right]
$$

会存在一个最优的策略$\pi^*$，它比其它的策略具有更大的效用
$$
U^{\pi^*}(s)=\max(U^\pi(s))
$$

假定已知了$\pi^*$的效用为$U(s)$，在状态$s$下，最佳策略$\pi^*$应当选取期望效用最大的动作
$$
\pi^*(s)=\argmax_a \sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma U(s')]
$$

该动作的效用即为该状态的效用，即**贝尔曼方程**

:::info{title="Note"}
$$
U(s)=\max_a \sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma U(s')]
$$
:::

它的解就是各状态的效用

<center><br><hr width=40%><br></center>

同样可以定义**动作效用**为给定状态下采取给定动作的期望效用
$$
Q(s,a)= \sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma U(s')]
$$
进而写出关于动作效用的贝尔曼方程
$$
Q(s,a)= \sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma \max_{a'}Q(s',a')]
$$

# 价值迭代算法
价值迭代方法是一个求解贝尔曼方程的迭代方法，可以描述如下

0. 初始化所有效用为零
1. 枚举每个状态，对于当前状态$s$，枚举允许的所有动作，计算它们的效用
$$
Q(s,a)= \sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma U(s')]
$$
2. 选择具有最大效用的动作$a$，用它的效用更新$s$的效用
$$
U'(s)=\max_a Q(s,a)
$$
3. 更新完所有状态后，令$U=U'$，返回`1`进行下一轮迭代

价值迭代最终可以收敛于贝尔曼方程的唯一解

# 策略迭代算法
与价值迭代算法不同，策略迭代算法针对于策略。它可以描述如下

0. 初始化策略$\pi$
1. 依据策略$\pi$计算每个状态的效用（进行迭代求解）
$$
U^\pi(s)=\sum_{s'}P(s'|s,\pi(s))[R(s,\pi(s),s')+\gamma U^\pi(s')]
$$
2. 基于计算得到的效用改进策略$\pi$
$$
\pi'(s)=\argmax_a \sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma U^\pi(s')]
$$
3. 若改进的策略无变化，则停止迭代；否则回到`1`继续迭代

# 被动强化学习

被动强化学习指的是采取固定的策略$\pi$，尝试学习效用函数$U^\pi(S)$

一个简单的方法是**直接效用估计**
- 进行多次实验，统计每个状态的效用
- 对每个状态的效用进行平均，只要实验的次数足够多，均值将收敛到期望值

由于忽视了状态之间的联系，直接效用估计收敛速度较慢。解决这个问题可以使用**自适应动态规划**
- 通过反馈可以得到奖励函数
- 通过动作的结果可以得到转移模型
- 将学习到的转移模型与奖励函数代入贝尔曼方程中求解各个状态的效用

另外可以从另一个角度出发得到**时序差分学习TD**，它采取迭代的方式计算效用

0. 初始化效用$U^\pi$
1. 学习ing：如果在状态$s$下采取动作$\pi(s)$达到了状态$s'$，则更新$s$的效用；其中$N(s)$是$s$出现的频率，替换概率
$$
U^\pi(s)=U^\pi(s)+\alpha N(s)[R(s,\pi(s),s')+\gamma U^\pi(s')-U^\pi(s)]
$$
2. 反复执行更新操作直到收敛

TD方法调整状态的效用来达到与其观测到的后继状态一致，而自适应动态规划调整状态的效用来达到与所有可能发生的后继状态一致

TD**不需要通过转移模型**来进行更新

# 主动强化学习

可以利用策略迭代方法或者价值迭代方法求解最优策略，称为**主动自适应动态规划**

主动动态规划是基于贪心的，不一定收敛到最优策略，因而引入$\epsilon-$贪心法，即以$\epsilon$的概率尝试当前策略以外的动作，以$1-\epsilon$的概率做出当前策略的动作，称其为**探索与利用**

- 探索：尝试所学习到“最优策略”以外的动作
- 利用：选择当前最优的动作

在选择动作时，若要进行探索，则应选取当前状态下探索次数少的动作

同样也可以推广得到**主动时序差分学习**，不过随着策略的更新，效用函数$U^\pi$也要更新；在进行“探索”时会尝试多种策略，这意味着需要保存多个效用函数，这不好，进而将效用迭代换为**动作效用的迭代**

> $$
> Q(s,a)= \sum_{s'}P(s'|s,a)[R(s,a,s')+\gamma \max_{a'}Q(s',a')]
> $$

更新规则与被动类似，同样使用频率代替转移模型

$$
Q(s,a)=Q(s,a)+\alpha N(s)[R(s,a,s')+\gamma\max_{a'}Q(s',a')-Q(s,a)]
$$

这种方法称为**Q-learning**，其中的$Q$函数是最佳策略下的动作效用；与之对应的是**SARSA**，它使用实际采取的动作效用进行更新（不计算平均）
$$
Q(s,a)=Q(s,a)+\alpha [R(s,a,s')+\gamma\max_{a'}Q(s',a')-Q(s,a)]
$$

当进行探索时，若产生负面奖励，由于平均，Q-learning不会惩罚该动作，而SARSA会

Q-learning是一种离策略（off-policy）学习算法，它所学习的Q值回答了问题“假设我停止使用我正在使用的任何策略，并依照（根据估计）选择最佳动作的策略开始行动，那么这个动作在该状态下的价值是多少？”

 SARSA是一种同策略（on-policy）的算法，它通过学习Q值回答了问题“假设我坚持自己的策略，那么这个动作在该状态下的价值是多少？”

马尔可夫与强化学习

# 量词实例化
定义置换就是用一个变量替换另一个变量，如
$$
\theta=\{a/b\}
$$
是说这个置换的名字叫$\theta$，它将语句中的变量$a$都换成变量$b$。应用一个变换可以这样表示
$$
SUBSET(\theta,\alpha)
$$
表示对语句$\alpha$应用置换$\theta$



**全称量词实例化**可以用任意的变量置换全称量化的变量，如对于
$$
\forall x \, (King(x) \land Greedy(x) \Rightarrow Evil(x))
$$
令置换 $\theta = \{x / John\}$，可得到
$$
King(John) \land Greedy(John) \Rightarrow Evil(John)
$$

**存在量词实例化**同样使用置换，不过置换的变量应当是从未出现的，称为**斯科伦常量**，如
$$
\exists x \, (Crown(x) \land OnHead(x, John))
$$
可得
$$
Crown(C_1) \land OnHead(C_1, John)
$$
其中$C_1$是斯科伦常量，它从未出现过。在进行实例化后，得到的语句应取代原先的语句，意为**存在量词实例化只能进行一次**。但是全称量词可以多次实例化，可以获得多种不同的结果

# 量词约简为命题推断
量词的约简分为两步

1. 对全称量词的语句，枚举所有的对象进行实例化
2. 对存在量词的语句，用斯科伦常量进行一次实例化

不过此处会出现问题，函数作用与对象上会得到对象，它还能再被函数作用一次得到新的对象。这回陷入无限的嵌套中

对于该问题有**Herbrand定理**

:::info{title="Note"}
如果有限的一阶语句蕴含某个语句$\alpha$，则一定存在有限步的推导。即将这些一阶语句命题化后存在一个有限嵌套深度的子集可以完成证明
:::

这说明一阶逻辑的蕴含问题是半可判定的，也就是说存在有限步内能判断语句成立，却不能判断语句不成立

不过即便不考虑函数，对于$n$个对象和一个$k$元谓词，实例化的复杂度也是指数级的
$$
n^k
$$
其中有大量无关的语句。为了只实例化需要的实例，需要引入**一般化肯定前件**（GMP）

# 一般化肯定前件
对于$n$个原子语句$p_1,p_2,\cdots,p_n$和$1$个蕴含语句，更准确来说应该是**一阶确定子句**，只有一个正文字
$$
p_1'\land p_2'\land\cdots\land p_n'\Rightarrow q
$$

如果能找到一个置换$\theta$使得对应语句**相同**
$$
SUBSET(\theta,p_i)=SUBSET(\theta,p_1')
$$
注意等值表示的是相同而不是逻辑上的相等。那么给定前件为$p_1',p_2',\cdots,p_n'$的该蕴含语句
$$
p_1',p_2',\cdots,p_n',(p_1'\land p_2'\land\cdots\land p_n'\Rightarrow q)
$$
可以被替换为结论的置换
$$
SUBSET(\theta,q)
$$
一个简单的例子是
$$
\forall x \, (King(x) \land Greedy(x) \Rightarrow Evil(x))\\
King(John)\\
\forall y \, Greedy(y)\\
Brother(John, Richard)
$$
由于取置换
$$
\theta = \{x/John, y/John\}
$$
各语句被置换后有
$$
Subst(\theta, p_1') = Subst(\theta, p_1) = King(John)
$$
$$
Subst(\theta, p_2') = Subst(\theta, p_2) = Greedy(John)
$$
那么原来的蕴含语句$Subst(\theta, q)$就应被实例化为
$$
Evil(John)
$$
没有多余的实例化

GMP的核心在于那个置换，称为**合一子**。两个语句的合一子可能不止一种，但是会存在一个最一般的合一子，其他所有的何意子都可以在其基础上再施加置换得到，称为**最一般合一子MGU**

不过使用GMP的条件是所有的变量假设均为全称量词，并且只能作用于一阶确定子句。在这个条件下，GMP是可靠且完备的

# 一阶逻辑的归结
## 一阶逻辑转换为合取范式
要对一阶逻辑使用归结，应当先将一阶逻辑语句转换为合取范式CNF。要将语句转化为CNF，应当**先消去蕴含**，利用逻辑等值式
$$
A\Rightarrow B\equiv \neg A\lor B
$$
使用时需要注意，虽然需要对$\forall,\exists$取反，但是内层的$\Rightarrow$取反时不应影响外层的量词，如
$$
\forall x [\forall y \, Animal(y) \Rightarrow Loves(x, y)] \Rightarrow [\exists y \, Loves(y, x)]
$$
$$
\rightarrow \forall x\neg [\forall y \neg  Animal(y) \lor Loves(x, y) \lor (\exists y \, Loves(y, x))]
$$
其中$\forall x$是外层的量词，作用于蕴含的两端，不受取反影响；而蕴含的前提中$\exists y$不作用于结论，应当取反

第二步是**将非号移到量词作用域的内部**，形成一系列由`与`和`或`连接的原子语句，如
$$
\forall x\neg [\forall y \neg  Animal(y) \lor Loves(x, y) \lor (\exists y \, Loves(y, x))]
$$
$$
\rightarrow \forall x \, [\exists y \, Animal(y) \land \neg Loves(x, y) \lor (\exists y \, Loves(y, x))]
$$

第三步是变量标准化，不同语句间如果不是同一个对象应使用不同的名字，虽然量词的修饰允许，但为了后续步骤还是需要这样做，如此处将蕴含结论的$y$换为了另一个名称$z$
$$
\forall x \, [\exists y \, Animal(y) \land \neg Loves(x, y) \lor (\exists y \, Loves(y, x))]
$$
$$
\rightarrow \forall x \, [\exists y \, Animal(y) \land \neg Loves(x, y) \lor \exists z \, Loves(z, x)]
$$

第四步是将**存在量词实例化**。需要注意的是，此处实例化并不是化为斯科伦常量，而是**斯科伦函数**。它是所有基本对象的函数，代表未知的确定函数，这是因为斯科伦常量太过一般，至少斯科伦函数能提供自变量的信息。如
$$
\forall x \, [\exists y \, Animal(y) \land \neg Loves(x, y) \lor \exists z \, Loves(z, x)]
$$
$$
\rightarrow \forall x \, [Animal(F(x)) \land \neg Loves(x, F(x)) \lor Loves(G(x), x)]
$$
不一样的变量应替换为不一样的斯科伦函数

最后将全称量词去除，因为斯科伦函数可以是所有基本对象的任意函数，本身就是对所有基本对象的实例化。上面的例子中，最后将得到语句
$$
Animal(F(x)) \land \neg Loves(x, F(x)) \lor Loves(G(x), x)
$$
不过为了得到CNF的形式，还需将其转为合取
$$
[Animal(F(x)) \lor Loves(G(x), x)] \land [\neg Loves(x, F(x)) \lor Loves(G(x), x)]
$$

## 一阶逻辑的归结规则

:::info{title="Note"}
对于两个一阶逻辑的CNF语句，若其中各有一个文字，在某种置换规则$\theta$作用下互为反文字，则这两个文字可以被消去
:::

具体来说，对于一阶逻辑语句
$$
a_0\land a_1\land a_2\land\cdots\land a_n
$$
$$
b_0\land b_1\land b_2\land\cdots\land b_m
$$
若存在一个置换规则使得$\theta$使得
$$
SUBSET(\theta,b_0)=\neg a_0
$$
则它们两个等价于
$$
SUBSET(\theta,a_1\land a_2\land\cdots\land a_n\land b_1\land b_2\land\cdots\land b_m
$$
归结是可靠且完备的