证明 2SAT is NL-complete。证明包括: 1) 证明 2SAT 属于 NL；2)证明 PATH ≤L 2SAT。

首先证明2SAT属于NL。

定义2SAT问题为：给定一个包含n个布尔变量的公式，每个变量的取值要么为真，要么为假，求判断这个公式是否有一个满足条件的布尔变量取值。可以证明2SAT问题可以转化为一个有向图，对于每个变量，建立两个点，分别表示它的真和假，对于每个子句(x ∨ y)，建立两条有向边(¬x, y)和(¬y, x)，表示如果x为假，则y必须为真，如果y为假，则x必须为真。然后，对于每个点x，求它的强连通分量，检查是否存在一个强连通分量，它同时包含x和¬x，如果存在这样的强连通分量，则2SAT问题无解，否则有解。

可以证明，这个算法可以在NL中实现。因为我们可以使用非确定性图遍历算法（如BFS），依次遍历每个点的强连通分量，并检查是否存在包含x和¬x的强连通分量。这个算法的空间复杂度为O(n)，因此，2SAT属于NL。

接着证明PATH ≤L 2SAT。

定义PATH问题为：给定一个有向图G和两个节点s和t，求是否存在一条从s到t的路径。我们可以将PATH问题转化为2SAT问题。对于图G中的每个节点v，建立两个变量xv和¬xv，表示节点v是否在路径中。对于每条有向边(u, v)，添加两个子句(¬xu, xv)和(¬xv, xu)，表示如果节点u在路径中，则节点v也必须在路径中。然后，添加两个子句(xs, ¬xt)和(¬xs, xt)，表示起点s必须在路径中，终点t不能在路径中。对于每个节点v，添加子句(xv, ¬¬xv)，表示节点v必须为真或者路径中没有包含它。最后，将所有子句联合起来，求解2SAT问题。

可以证明，如果2SAT问题有解，那么就存在一条从s到t的路径。因为有解意味着存在一种变量取值，使得每个子句都至少有一个变量为真。对于每个节点v，如果xv为真，那么节点v在路径中，否则节点v不在路径中。因为路径中的每个节点都满足条件，所以从s到t存在一条路径。

另一方面，如果存在一条从s到t的路径，那么2SAT问题有解。因为存在一条从s到t的路径，可以将路径上的节点全部标记为真，其他节点全部标记为假。对于每个子句(x ∨ y)，如果x为假，则y必须为真，否则x必须为真。因为路径上的每个节点都满足条件，所以2SAT问题有解。

因此，可以得出PATH ≤L 2SAT的结论，即2SAT是NL-complete的。