結論

先に結論から。

リテラル $X_{0}, X_{1}, \dots, X_{N-1}$ に対して、以下の条件 A, B, C は同値である。

A： $X_{0}, X_{1}, \dots, X_{N-1}$ のうち、True であるのは 1 個以下である
B：任意の $i, j$ ( $0 \le i \lt j \lt N$ ) に対して、節 $(\lnot X_{i} \lor \lnot X_{j})$ を充足する
C：新たなリテラルの値を適切に定めたとき、以下をすべて充足する
- 1：節 $(\lnot X_{i} \lor Y_{i})$ ( $i = 0, 1, \dots, N-1$ )
- 2：節 $(\lnot Y_{i} \lor Y_{i+1})$ ( $i = 0, 1, \dots, N-2$ )
- 3：節 $(\lnot Y_{i} \lor \lnot X_{i+1})$ ( $i = 0, 1, \dots, N-2$ )

背景

リテラル $X_{0}, X_{1}, \dots, X_{N-1}$ のうち、True であるのは高々 1 個であるという条件を、2-SAT で記述することを考える。

なお、この条件は、 $X_{i}$ を 0-1 変数とみなしたときに、 tex: X_{0} + X_{1} + \dots + X_{N-1} \le 1] とも言い換えられる。

さて、上述の条件は、各 $(i, j)$ ( $0 \le i \lt j \lt N$ ) について、節 $(\lnot X_{i} \lor \lnot X_{j})$ をすべて追加することで表現できる。しかし、これでは節の個数が $O(N^{2})$ となって計算量的に厳しいことがある。実は新たな変数を用意することで、節の個数を $O(N)$ にできる。

累積 OR を表すリテラルを用意

リテラル $X_{0}, X_{1}, \dots, X_{N-1}$ に対して、次のような累積 OR を表すリテラル $Y_{0}, Y_{1}, \dots, Y_{N-1}$ を用意する。

$Y_{0} = X_{0}$
$Y_{1} = X_{0}$ $\mathrm{or}$ $X_{1}$
$Y_{2} = X_{0}$ $\mathrm{or}$ $X_{1}$ $\mathrm{or}$ $X_{2}$
$\dots$
$Y_{N-1} = X_{0}$ $\mathrm{or}$ $X_{1}$ $\mathrm{or}$ $X_{2}$ $\mathrm{or}$ $\dots$ $\mathrm{or}$ $X_{N-1}$

このとき、次のことが言える (再掲)。

リテラル $X_{0}, X_{1}, \dots, X_{N-1}$ に対して、以下の条件 A, B, C は同値である。

A： $X_{0}, X_{1}, \dots, X_{N-1}$ のうち、True であるのは 1 個以下である
B：任意の $i, j$ ( $0 \le i \lt j \lt N$ ) に対して、節 $(\lnot X_{i} \lor \lnot X_{j})$ を充足する
C：新たなリテラルの値を適切に定めたとき、以下をすべて充足する
- 1：節 $(\lnot X_{i} \lor Y_{i})$ ( $i = 0, 1, \dots, N-1$ )
- 2：節 $(\lnot Y_{i} \lor Y_{i+1})$ ( $i = 0, 1, \dots, N-2$ )
- 3：節 $(\lnot Y_{i} \lor \lnot X_{i+1})$ ( $i = 0, 1, \dots, N-2$ )

C について、2 番目は「 $Y_{0}, Y_{1}, \dots, Y_{N-1}$ は、False, False, ..., False, True, True, ..., True の形になること」を表している。

1 番目は、2 番目と組み合わせることで「ある $i$ に対して $X_{i}$ が True であるとき、 $Y_{i}, Y_{i+1}, \dots, Y_{N-1}$ も連鎖的に True とあること」を表している。

3 番目は、1 番目・2 番目と組み合わせることで「ある $i$ に対して $X_{i}$ が True であるとき、 $Y_{i}, Y_{i+1}, \dots, Y_{N-1}$ も True であり、それに伴い $X_{i+1}, X_{i+2}, \dots, X_{N-1}$ は False となること」を表している。

ちゃんと証明

A ⇒ C

A を満たすとき、リテラル $X_{0}, X_{1}, \dots, X_{N-1}$ のうち True であるものは高々 1 個である。

リテラル $X_{0}, X_{1}, \dots, X_{N-1}$ がすべて False であるとき、 $Y_{0}, Y_{1}, \dots, Y_{N-1}$ をすべて False にすることで、条件 B を満たす。

リテラル $X_{i}$ のみが True で、他はすべて False であるとき、 $Y_{0}, Y_{1}, \dots, Y_{i-1}$ を False として $Y_{i}, Y_{i+1}, \dots, Y_{N-1}$ を True とすることで、条件 B を満たす。

C ⇒ A

リテラル $Y_{0}, Y_{1}, \dots, Y_{N-1}$ がすべて False であるとき、節 $(\lnot X_{i} \lor Y_{i})$ を充足するためには、リテラル $X_{0}, X_{1}, \dots, X_{N-1}$ がすべて False である必要がある。これは条件 A を満たす。

リテラル $Y_{i}$ が True であるような最小の $i$ をとってくると、 $Y_{0}, Y_{1}, \dots, Y_{i-1}$ は False であり、 $Y_{i}, Y_{i+1}, \dots, Y_{N-1}$ は True である。このとき、節 $(\lnot X_{i} \lor Y_{i})$ と節 $(\lnot Y_{i} \lor \lnot X_{i+1})$ をすべて充足するためには、 $X_{i}$ = True として他はすべて False とする必要がある。これは条件 A を満たす。