存在二阶逻辑是一阶逻辑的推广，它的能力更加强大，可以表达更多的性质，表示更多的问题，是更为复杂的研究对象。首先给定词汇表$\Sigma=(V,\Phi,\Pi,r)$，关系$P\notin \Pi$，是一个新的$r(P)$-元关系，一个存在二阶逻辑的表达式形如$\exists P\phi$，其中$\phi$为基于词汇表$\Sigma’=(V,\Phi,\Pi\cup {P },r)$的一个一阶逻辑表达式，显然$\phi$一定会涉及到$P$这个新的关系。如果只看表达式$\exists P\phi$，它的直观意义是说存在一个关系$P$使得表达式$\phi$成立(即在某个模型下被满足)。注意这里我们用的是存在量词，$\exists P\phi$，实际上定义要求存在二阶逻辑的表达式必须为$\exists P\phi$的形式，开头不能出现全称量词。

    称适合$\Sigma$的一个模型$M=(U,\mu)$满足$\exists P\phi$，如果存在一个关系$P^M\subseteq U^{r(P)}$，使得$P^M$扩充到$M$后得到的新模型$M\cup{P^M}$满足$\phi$。这个定义也是比较平凡的，$\Pi$中新增了一个关系$P$，那$M$中的函数$\mu$当然要给$P$一个函数值，也就是$P^M$。

REACHABILITY问题的二阶逻辑表达式

    图的可达性问题用二阶逻辑进行表达式是非常复杂的，这里实际上讨论的是不可达(UNREACHABILITY)问题的二阶逻辑表达式，其补即为可达性。首先定义$\phi(x,y)$如下：

$$\phi(x,y)=\exists P[\forall u \forall v \forall w(P(u, u) \wedge(G(u, v) \Rightarrow P(u, v)) \wedge((P(u, v) \wedge P(v, w)) \Rightarrow P(u, w)) \wedge \neg P(x, y))]$$

$\phi(x,y)$中$P(u,u)$表明图$P$的自反性，$G(u, v) \Rightarrow P(u, v)$表示图$G$是$P$的子图，$(P(u, v) \wedge P(v, w)) \Rightarrow P(u, w)$表明图$P$具有传递性，故图$P$必然包含图$G$的自反和传递闭包，$\phi(x,y)$最后合取了$\neg P(x, y)$，故若$\phi(x,y)$为true的话，$P(x, y)$必须为false才行，也就是$(x,y)$不是图$P$的边，注意这里的$x$和$y$都是图$G$的点，如果$x$到$y$存在通路，由于图$P$包含图$G$的自反和传递闭包，那$(x,y)$一定是图$P$的边，但现在$(x,y)$不是图$P$的边，所以$x$到$y$一定没有通路，所以$\phi(x,y)$就表达$x$和$y$之间没有通路。

    另外这里$P$是包含$G$的图，所以$P$肯定不只一个，但$\phi(x,y)$要求只要存在满足条件的$P$即可，实际上这也是显然存在的，只需让$P$取图$G$的自反和传递闭包即可。于是$\phi(x,y)$-GRAPHS恰恰描述了REACHABILITY问题的补，即UNREACHABILITY问题。

    虽然$\phi(x,y)$表述的是不可达，但$\neg \phi(x,y)$并不是表述的可达，因为这里是两个问题类之间的互补，并不是单独的二阶逻辑表达式取否。二阶逻辑在取否下不封闭，另外要确切的表达REACHABILITY问题，需要更多的工作，这里不再讨论。

Hamilton通路问题的二阶逻辑表达式

    Hamilton通路问题非常简洁，即给定一个图，是否有一条通路通过每个顶点恰好一次？目前。没有多项式时间的算法判定一个图是否有一条Hamilton通路，设此问题的二阶逻辑表达式为$\psi=\exists P\chi$，实际上$P$是图$G$顶点的一个线性序，也就是一个二元关系，$\chi$是下面三个部分的合取，每个部分有不同的作用：

1. $G$的所有顶点可由$P$比较：$\forall x \forall y(P(x, y) \vee P(y, x) \vee x=y)$，即要么为$x< y$，要么$x>y$，要么$x=y$
2. $P$是传递的，但不是自反的：$\forall x \forall y \forall z[\neg P(x, x) \wedge((P(x, y) \wedge P(y, z)) \Rightarrow P(x, z))]$
3. $P$中任意先后相邻两点在$G$中一定邻接：$\forall x \forall y[(P(x, y) \wedge \forall z(\neg P(x, z) \vee \neg P(z, y))) \Rightarrow G(x, y)]$，这里的$P(x,y)$表示$x,y$之间有通路，$\forall z(\neg P(x, z) \vee \neg P(z, y))$是$\exists z( P(x, z) \land P(z, y))$的否，代表$x,y$之间没有别的点，即$x,y$相邻

    显然$\psi$-GRAPHS与Hamilton通路问题相同，事实上，满足这三个性质的$P$一定是线性序，而且任意两个先后相邻的元素必在$G$中邻接，故$P$是一个Hamilton通路。

UNREACHABILITY问题与Hamilton通路问题的异同

    由上面的两个例子可以看出，存在二阶逻辑具有强大功能，后面其功能会进一步体现。现在我们再分析UNREACHABILITY问题和HAMILTON通路问题的异同，已知前者是多项式时间可求解的，而后者被相信没有确定多项式时间算法可解，为什么会有这样的差异，是否和它们的二阶逻辑表达式有关？实际上是有关系的。对于UNREACHABILITY问题表达式：

$$\phi(x,y)=\exists P[\forall u \forall v \forall w(P(u, u) \wedge(G(u, v) \Rightarrow P(u, v)) \wedge((P(u, v) \wedge P(v, w)) \Rightarrow P(u, w)) \wedge \neg P(x, y))]$$

这是一个前缀范式，$P$后面仅有全称量词，而且是合取范式的形式，有分句$P(u, u)$， $G(u, v) \Rightarrow P(u, v)$，$ \neg P(x, y)$，$ \neg P(u, v) \vee \neg P(v, w) \vee P(u, w)$，第二个分句涉及到$G(u,v)$，则可以控制变量的选择使得这个涉及到$P$外关系$G$的分句恒为真，故这种分句可以删去，不影响整个句子的判断，最后只剩下由$P$的原子表达式构成的分句：

$$P(u, u), \quad \neg P(x, y), \quad \neg P(x, y) \vee \neg P(y, z) \vee P(x, z)$$

这三个分句中，每个都至多有一个非负的涉及$P$的原子表达式，和之前一样，这些分句也称作HORN分句。

     称存在二阶逻辑表达式为一个HORN表达式，如果其前缀形式中仅有一阶全称量词，且其每个分句至多含有一个非负的关于$P$的原子表达式。显然UNREACHABILITY问题的表达式是一个HORN表达式，Hamilton通路问题表达式不是HORN表达式，因为其分句$P(x, y) \vee P(y, x) \vee x=y$显然不满足HORN表达式的条件。实际上就是这个不同，导致一个多项式时间内可求解，一个不确定能否在多项式时间内可求解，也就是下面的定理：

对于任意存在二阶逻辑的HORN表达式$\exists P\phi$，问题$\exists P\phi$-GRAPHS可由确定的多项式时间算法求解

    这个定理的证明并不复杂，设$\exists P \phi=\exists P \forall x_1 \cdots \forall x_k \eta$，其中$\eta$为HORN分句的合取，$P$为$r$-元关系，给定一个图$G$，顶点集合$V=\{1,2,\cdots ,n\}$，此集合也是字母表的变量集合，$\exists P\phi$-GRAPHS就是问图$G$是否是一个$\exists P\phi$的YES实例，即是否存在一个关系$P\subseteq \{1,2,\cdots,n\}$使得$\phi$可满足。

    对于$x_1 \cdots \forall x_k\in V$，由于$\eta$必须对$x_1 \cdots \forall x_k$的任意取值都成立，故可将$\exists P\phi$重写为

$$\exists P \phi=\underset{v_{1}, \cdots, v_{k}}{\wedge} \eta\left[x_{1} \leftarrow v_{1}, \cdots, x_{k} \leftarrow v_{k}\right]$$

其中$v_1, \cdots, v_k \in V$，显然$v_1, \cdots, v_k $共有$n^k$个选择，不妨设$h$为$\eta$中分句的个数，则$\exists P\phi$中共有$hn^k$个分句，且每个分句均为HORN分句。

    $\exists P\phi$的所有分句中至多有三种原子表达式，分别为$G(v_i,v_j)$，$v_i=v_j$，$P(v_{i_1},\cdots v_{i_r})$，前两种通过询问图$G$的邻接矩阵可以快速计算是0还是1，所以可以对$\exists P\phi$做如下简化：

1. 如果一个原子表达式取值为0，则将该表达式从其分句中删除
2. 若一个原子表达式取值为1，则将此表达式所在分句删除
3. 重复执行前两步，若最终得到含有空分句的表达式，即某个分句中的所有原子表达式均取0，则$\phi$显然不被满足，即$G$不满足$\phi$

    经此处理后，留下至多$hn^K$个分句，每个分句均形为$P\left(v_{i_{1}}, \cdots, v_{i_{r}}\right)$和$\neg P\left(v_{i_{1}}, \cdots, v_{i_{r}}\right)$的析取，且分句都为HORN分句，由于每个$P\left(v_{i_{1}}, \cdots, v_{i_{r}}\right)$独立的取值0或1，故可以用不同的Boolean变量$x^{v_{i_1} \cdots, v_{i_{r}}}$代替它的每次出现，得到新的表达式$F$。显然存在$P$使得$\phi$可满足当且仅当$F$是可满足的，且我们利用使得$F$满足的变量取值可以具体构造出这个关系$P$。由于留下的每个分句都是HORN分句，故$F$是一个有至多$hn^k$个分句和至多$n^r$个变量的普通HORN表达式，其中$k$和$r$都是常数，于是利用HORNSAT问题的多项式时间算法，可以求解$F$的满足问题，也就可以构造关系$P$，也就是求解$\exists P\phi$-GRAPHS问题，且这个求解过程显然是多项式时间内可以完成的，原命题得证。