2. 論理式の線形表現#
2.1. 導入#
二値状態を判別する インジケータ変数 を用いると，状態間の論理的な結びつけが可能となる． AND や OR のみならず全ての論理式を記述でき，広範な応用分野の源泉となっている．
論理式を表現する上で大別して \(3\) つの捉え方がある．
論理式を制約条件として捉える場合
例えば命題 \(P\) と \(Q\) があった場合に，論理和 \(P\lor Q\) を真とする意味で制約条件を扱いたい場合
この場合は論理式が偽であることは制約条件が成立しないことを意味するので，偽の状態は許容されない．
論理式を論理変数として捉える場合
例えば命題 \(P\) と \(Q\) があった場合に，論理和 \(P\lor Q\) を真とする意味で論理変数を扱いたい場合
この場合は論理式が偽であることは \(1\) つの状態であり，偽の状態も定式化の一部として許容される．
論理式を制約式間の論理条件として捉える場合
例えば制約条件の論理式 \(C_f := [f(x)\geq 0]\) と \(C_g := [g(x)\geq 0]\) があった場合に，論理和 \(C_f\lor C_g\) などと少なくとも何れか一方を真とする意味で論理変数を扱いたい場合
この場合は論理式が偽であることは制約条件が成立しないことを意味するので，偽の状態は許容されない．
ここで制約条件の論理式 \(C = [f(x) \geq 0]\) とは制約条件 \(f(x) \geq 0\) が真ならば \(1\) であり， 偽ならば \(0\) をとることを意味するもので，\([P]\) は命題 \(P\) に対する Iverson 括弧 である．
注釈
ところで，ここでの主題は「論理式の 線形 表現」であるが，何故，そもそも 線形 にこだわるのだろうか． これは 定式化の複雑さ と直結するためである．
簡単に言えば「定式化可能であること」と「現実的な計算資源の下で求解可能であること」とは， 分けて考えなければならない重要な違いだということである．
2.2. 対応一覧表 (制約条件)#
以下，\(z_1\) や \(z_2\) などはすべて命題論理式に対応する真偽値を意味する．
2.2.1. 基本的な論理条件#
名称 |
論理式 |
線形表現 |
|---|---|---|
含意 |
\(z_1\implies z_2\) |
\(z_1 \leq z_2\) |
逆含意 |
\(z_2\implies z_1\) |
\(z_1 \geq z_2\) |
同値 |
\(z_1\iff z_2\) |
\(z_1 = z_2\) |
恒真 |
\(z\) |
\(z = 1\) |
NOT |
\(\lnot z\) |
\(1 - z = 1 \iff z = 0\) |
AND |
\(z_1\land z_2\) |
\(z_1 + z_2 = 2 \iff z_1 = z_2 = 1\) |
OR |
\(z_1\lor z_2\) |
\(z_1 + z_2 \geq 1\) |
NAND |
\(z_1\mathrel{\bar{\land}} z_2\) |
\(z_1 + z_2 \leq 1\) |
NOR |
\(z_1\mathrel{\bar{\lor}} z_2\) |
\(z_1 + z_2 = 0\) |
XOR |
\(z_1\veebar z_2\) |
\(z_1 + z_2 = 1\) |
XNOR |
\(z_1\mathrel{\bar{\veebar}} z_2\) |
\(z_1 = z_2\) |
OR |
\(\bigvee_{i=1}^N z_i\) |
\(\sum_{i=1}^N z_i \geq 1\) |
AND |
\(\bigwedge_{i=1}^N z_i\) |
\(\sum_{i=1}^N z_i = N \iff (\forall i)(z_i = 1)\) |
\(1\) を真偽値の何れに対応させるかは自由だが，多くの文献がそうであるように真値に対応させている．
含意は前提命題が偽ならば全体の命題は真である．このことは \(z_1\implies z_2\) の線形表現 \(z_1 \leq z_2\) について，\(z_1=0\) である場合には \(z_1\leq z_2\) は必ず真であり，帰結 \(z_2\) の真偽 (\(0\) か \(1\) か) に関係しないことと対応している．
含意 (IMP) は if \(z_1\) then \(z_2\) のことであり，
if文に関係する命題文に対応する．同値は XNOR と同じ線形表現を持つ．
逆含意は if not \(z_1\) then not \(z_2\) とも翻訳できる．
NAND は if \(z_1\) then not \(z_2\) とも翻訳できる．
OR は if not \(z_1\) then \(z_2\) とも翻訳できる．
含意 \(z_1\implies z_2\) は \((\lnot z_1)\lor z_2\) に同値である．よって OR の線形表現から含意の線形表現 (およびその逆) が演繹できる．
各種の論理演算の真理値表は次のとおりである．
\(z_1\) |
\(z_2\) |
恒真 |
OR |
逆含意 |
\(z_1\) |
含意 (IMP) |
\(z_2\) |
同値 (XNOR) |
AND |
NAND |
XOR |
NOT \(z_2\) |
非含意 |
NOT \(z_1\) |
逆非含意 |
NOR |
恒偽 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
\(1\) |
\(1\) |
\(1\) |
\(1\) |
\(1\) |
\(1\) |
\(1\) |
\(1\) |
\(1\) |
\(1\) |
\(0\) |
\(0\) |
\(0\) |
\(0\) |
\(0\) |
\(0\) |
\(0\) |
\(0\) |
\(1\) |
\(0\) |
\(1\) |
\(1\) |
\(1\) |
\(1\) |
\(0\) |
\(0\) |
\(0\) |
\(0\) |
\(1\) |
\(1\) |
\(1\) |
\(1\) |
\(0\) |
\(0\) |
\(0\) |
\(0\) |
\(0\) |
\(1\) |
\(1\) |
\(1\) |
\(0\) |
\(0\) |
\(1\) |
\(1\) |
\(0\) |
\(0\) |
\(1\) |
\(1\) |
\(0\) |
\(0\) |
\(1\) |
\(1\) |
\(0\) |
\(0\) |
\(0\) |
\(0\) |
\(1\) |
\(0\) |
\(1\) |
\(0\) |
\(1\) |
\(0\) |
\(1\) |
\(0\) |
\(1\) |
\(0\) |
\(1\) |
\(0\) |
\(1\) |
\(0\) |
\(1\) |
\(0\) |
2.2.2. 三変数にわたる論理条件#
論理式 |
線形表現 |
|---|---|
\(z_1\implies z_2\land z_3\) |
\((z_1 \leq z_2)\land(z_1\leq z_3)\) |
\(z_1\implies z_2\land z_3\) |
\(2z_1 \leq z_2 + z_3\) |
\(z_1\implies z_2\lor z_3\) |
\(z_1 \leq z_2 + z_3\) |
\(z_2\lor z_3\implies z_1\) |
\((z_1 \geq z_2)\land(z_1\geq z_3)\) |
\(z_2\lor z_3\implies z_1\) |
\(2z_1 \geq z_2 + z_3\) |
\(z_2\land z_3\implies z_1\) |
\(z_1 \geq z_2 + z_3 - 1\) |
\(z_1\implies z_2\land z_3\) は \((z_1\implies z_2)\land (z_1\implies z_3)\) に同値である．よって二変数にわたる論理条件から三変数にわたる論理条件 \((z_1 \leq z_2)\land(z_1\leq z_3)\) が演繹できる．ここで次のようなこともできたが，非線形となるため \(\land\) を簡約せずに残した．
\(z_1\implies z_2\lor z_3\) は \((z_1\implies z_2)\lor (z_1\implies z_3)\) に同値である．よって二変数にわたる論理条件から三変数にわたる論理条件 \((z_1 \leq z_2)\lor (z_1\leq z_3)\) が演繹できる．これは更に \(z_1\leq z_2 + z_3\) に簡約できる．
2.2.3. 計数に関係する論理条件#
名称 |
条件 |
線形表現 |
|---|---|---|
LEAST |
少なくとも \(N\) |
\(\sum_{i\in I} z_i \geq N\) |
MOST |
高々 \(N\) |
\(\sum_{i\in I} z_i \leq N\) |
EXACTLY |
厳密に \(N\) |
\(\sum_{i\in I} z_i = N\) |
MAJORITY |
過半数 |
\(\sum_{i\in I} z_i \geq \lfloor |I|/2\rfloor + 1\) |
SEMI-LEAST |
\(0\) または少なくとも \(N(\geq 2)\) |
\(\bigwedge_{j\in I} (\frac{1}{N-1}\sum_{\substack{i\in I\\i\neq j}}z_i\geq z_j)\) |
LEAST で \(N=1\) は \(N\) 変数の OR 条件である．
MOST で \(N=1\) は SOS1 のための条件としても解釈できる．
EXACTLY で \(N=1\) は one-hot 制約とよばれることがある．
MAJORITY は過半数が真の場合に限り真である論理条件である．
条件 |
論理式 |
線形表現 |
|---|---|---|
\(N\) 変数のうち \(M\) 変数以上が真ならば真 |
\((\sum_{i=1}^N z_i \geq M) \implies z\) |
\(\frac{1}{N-M+1} \sum_{i=1}^N (z_i - M + 1) \leq z\) |
\(N\) 変数のうち \(M\) 変数以下が真ならば真 |
\((\sum_{i=1}^N z_i \leq M) \implies z\) |
\(1 - \frac{1}{M+1}\sum_{i=1}^N z_i\leq z\) |
ヒント
上記の論理変数の計数 (COUNTING) に関する線形表現を得るための考え方の例は次のとおり．
\(P\implies Q\) という命題のため，\(f_{N,M}(\{z_i\}_i) \leq z\) であり，\(f\) を決定すればよい．
\(f\) は線形でなければならないから次の形をしている．
(3)#\[f_{N,M}(\{z_i\}_i) = \sum_{i=1}^N A_i(N,M) \cdot z_i + B(N,M)\]\(f\) は論理変数が真である総数 \(c:=\sum_{i=1}^N z_i\) を比較する必要があり，どの論理変数も特別視しないため，線形結合の重みに偏りがあってはならない．よって次式のとおり \(c\) についての一次関数となる．
(4)#\[f_{N,M}(c) = A(N,M)\cdot c + B(N,M)\]\(\varepsilon:=(0,1]\subset\mathbb{R}\) および \(\mu:=(-\infty,0]\subset\mathbb{R}\) とし，例として「\(N\) 変数のうち \(M\) 変数以上が真ならば真」を考える．これは \(f\) が「\(c\) が \(M\) 以上ならば \(\varepsilon\) の元の数値を取り，そうでなければ \(\mu\) の元の数値を取る」であれば，\(f_{N,M}(c) \leq z\) が機能する．
前項までの \(f\) の値の変化は \(N-M+1\) 個ある \(c\) が真となりうるパターンについて \(\varepsilon\) の元の数値を \(f\) がとり，それ以外は \(\mu\) の元の数値を取ればよいとわかる．そしてその直線の傾きは正である．
傾きと切片を真の数が最大となる \(N\) 個の場合に \(f=1\) であり，最小となる \(M\) 個の場合に \(1/(N-M+1)\) となるように決定する．このように決定した \(f\) は次式で与えられる．
(5)#\[f_{N,M}(c) = \frac{c - M + 1}{N - M + 1}\]「\(N\) 変数のうち \(M\) 変数以下が真ならば真」の場合についても同様に考えることで，線形表現が得られる．
「\(N\) 変数のうち \(M\) 変数が真ならば真」や「\(N\) 変数のうち \(M_1\) 変数以上かつ \(M_2\) 変数以下が真ならば真」は \(f\) の傾きが一回だけ変化するので，\(2\) つの線形制約式が必要である．それらは「\(N\) 変数のうち \(M\) 変数以上が真ならば真」と「\(N\) 変数のうち \(M\) 変数以下が真ならば真」を共に課せばよいことと対応している．
(6)#\[\begin{split}& \frac{\sum_{i=1}^N z_i - M_1 + 1}{N-M_1+1}\leq z, \\ & 1 - \frac{1}{M_2+1}\sum_{i=1}^N z_i\leq z\end{split}\]
2.3. 対応一覧表 (論理変数)#
2.3.1. 基本的な論理式#
名称 |
論理式 |
線形表現 |
|---|---|---|
NOT |
\(z=\lnot z_1\) |
\(z = 1 - z_1\) |
AND |
\(z=z_1\land z_2\) |
\(2z \leq z_1 + z_2 \leq z + 1\) |
OR |
\(z=z_1\lor z_2\) |
\(z\leq z_1 + z_2 \leq 2z\) |
AND |
\(z=\bigwedge_{i=1}^N z_i\) |
\(N\cdot z \leq \sum_{i=1}^N z_i \leq z + N - 1\) |
OR |
\(z=\bigvee_{i=1}^N z_i\) |
\(z\leq \sum_{i=1}^N z_i \leq N\cdot z\) |
含意 |
\(z=(z_1\implies z_2)\) |
\(z \leq (1-z_1) + z_2 \leq 2z\) |
逆含意 |
\(z=(z_1\impliedby z_2)\) |
\(z \leq z_1 + (1-z_2) \leq 2z\) |
非含意 |
\(z=\lnot(z_1\implies z_2)\) |
\(2z \leq z_1 + (1-z_2) \leq z+1\) |
逆非含意 |
\(z=\lnot(z_1\impliedby z_2)\) |
\(2z \leq (1-z_1) + z_2 \leq z+1\) |
NAND |
\(z=z_1 \mathrel{\bar{\land}} z_2\) |
\(z \leq (1-z_1) + (1-z_2) \leq 2z\) |
NOR |
\(z=z_1 \mathrel{\bar{\lor}} z_2\) |
\(2z \leq (1-z_1) + (1-z_2) \leq z+1\) |
AND 演算は \(\min\) 演算に等しい．
OR 演算は \(\max\) 演算に等しい．
AND や OR は上限と下限の \(2\) つの制約条件が必要になっているが，目的関数に \(z\) が含まれており，最大化もしくは最小化することが有利であるならば，上限・下限の制約条件の一方を課さなくても良い場合がある．
目的関数を利用して制約を一部課さなくても良い場合には，論理変数を閉区間 \([0,1]\) の中で連続緩和できる場合がある．その場合には離散変数の数を削減して，問題の複雑度が下がることを期待できる．
NAND や NOR など他の基本的な二項論理演算は，NOT・AND・OR から合成できるため，これによりそれらの線形表現もまた合成できる．
XOR や XNOR も NOT・AND・OR から合成できるため，それらの線形表現から合成可能であるが，より洗練した線形表現を得るにはもう一工夫必要となる．
危険
しばしばこの話題の初学者は AND 演算 \(z = z_1\land z_2\) について次の定式化を考えてしまう．
これは非線形表現であって，必ず避けなければならない！
ではどのようにして線形に表現できるのか，と思い悩み考えることは， 誰しもが通る最初の一歩でもあり，その解答はコロンブスの卵のように見えることだろう．
注釈
表に示した線形表現とは別の表現で言及されることもあるが等価に変形できることに注意する． 例えば AND 演算 \(z=z_1\land z_2\) に対して，次の線形表現を考えることができるが，これは表に示した線形表現に帰着できる．
何故ならば，この第三式は \(z_1 + z_2 \leq z + 1\) に他ならず，最初の二つの不等式について両辺和をとれば \(2z \leq z_1 + z_2\) に他ならない． これは表に示した線形表現である．
Tip
\(N\) 項にわたる AND および OR について，特に \(N=0\) の場合を考えると，それら線形表現の中辺にある総和が空和となって \(0\) となる． すると，AND の線形表現から \(z\geq 1\)，つまり，\(z=1\) で恒真となる．同様に OR の線形表現では \(z\leq 0\) で，つまり，\(z=0\) と恒偽となる． これらの結果は，AND と OR が \(0\) 項演算の場合の結果に一致する．
2.3.2. 連続変数との積#
\(\mathbb{B}:=\{0,1\}\) として次の連続変数 \(x\) との積で定義される連続変数 \(y\) があったとする．
これの線形表現は次のとおり．
Tip
連続変数同士の積を線形に帰着させる話題については，セパラブルな関数 を参照されたい．
2.3.3. 算術に関係する論理変数#
\(y\) が整数変数ならば次の算術条件を記述できる．
名称 |
条件 |
線形表現 |
|---|---|---|
EVEN |
\(x\in 2\mathbb{Z}\) |
\(x - 2y = 0\) |
ODD |
\(x\in 2\mathbb{Z} + 1\) |
\(x - 2y = 1\) |
MODULO |
\(x \equiv A \pmod{B}\) |
\(x - B\cdot y = A\) |
これから「整数変数 \(x\) が偶数ならば真」と「整数変数 \(x\) が奇数ならば真」なる論理変数 \(z\) が次で記述できる．
名称 |
論理式 |
線形表現 |
|---|---|---|
EVEN |
\(z=[x\in 2\mathbb{Z}]\) |
\(x - 2y = 1-z\) |
ODD |
\(z=[x\in 2\mathbb{Z} + 1]\) |
\(x - 2y = z\) |
ここに \([P]\) は命題 \(P\) が真である場合に \(1\) を，偽である場合に \(0\) を意味する括弧であり， Iverson 括弧 とよばれるものである．
2.4. 制約式間の論理条件#
NOT・AND・OR の三組によって，全ての論理命題を表すことができる． 制約条件の成立を命題と考える場合に，これらが記述できれば，問題の制約をすべて記述できる．
NOT 条件は \(f(x)\geq 0\) に対して \(f(x) < 0\) などと small ε を用いて機械的に記述できる． また AND 条件は制約式がすべて満たす場合であり，通常定式化で制約式を羅列されていることに自明に対応している．
重要
非自明な論理条件は OR 条件を含んだ条件であり，これらはまた離接制約ともよばれている． 以下に述べる OR 条件の記述には論理変数が必要になるため，OR 条件が混ざると必然的に整数計画問題のクラスになる． これは NOT や AND 条件との大きな違いである．
2.4.1. 離接制約と OR 条件#
制約条件間の OR 条件を含む記述は離接制約の記述と呼ばれて，次のことを言う．
制約条件の集まりを \(\{f_i(x) \leq 0\}_{i \in C_k}\) とする． つまりある \(k (\in K)\) に対して \(C_k\) という制約条件の集まりが対応する． \(z_k\) を \(C_k\) が成り立つか否かを表す論理変数とする． この場合に何れか一つの制約が少なくも真 1truthy とは「真として評価される値」を意味する．今の場合，\(1\) は数としての \(1\) ではなく，真偽値の真値に対応させているため，これは truthy に他ならない．なお偽値に対応させて評価される値は falsy という． であることを要求する連言標準形で書かれた制約を 離接制約 という．
つまり次を要求する．
これは純粋に OR 条件だけであるが， 例えば LEAST・MOST・EXACTLY などを通して OR 条件を含んだ場合を課すことが考えられる． これらが課されて各論理変数に付与された後は，Big M を用いて制約条件に次のようにこれら論理変数を挿入させる．
\(z_k=1\) ならば \(C_k\) に属している制約条件は元の制約条件となり， 一方で \(z_k=0\) ならば Big M のために真偽が問われない自由な制約条件となる．
Big M は問題に表れる変数 \(x\) の最大値がわかっていれば次式で厳密に求めることができる．
また同じことだが \(f_i(x) = g_i(x) - U_i\) と変数項と定数項とに分解した場合の制約条件と Big M は次式である．
2.5. 例題#
2.5.1. 彩色数問題#
「互いに隣り合う \(2\) つの領域には異なる色を彩色するとき，使用する色の数を最小化せよ」という問題を彩色数問題という． この問題は四色定理から高々最大でも彩色数 \(4\) が解となるはずである．
彩色数問題の定式化は次のとおり．
2.5.1.1. 集合・定数・変数#
INPUT (集合・定数)
\(COLORS\) は使用する色の集まり
\(v\in V\) は彩色対象の集まり
\((v_1,v_2)\in A\) は \(v_1 \in V\) と \(v_2 \in V\) が「互いに隣り合っている」という接続関係
OUTPUT (変数)
\(z_{v,c}\) は \(v\) に色 \(c\) を彩色するかどうか
\(use_c\) は色 \(c\) を使用するかどうか
2.5.1.2. 制約条件#
「彩色したら色を使ったことになる」ため，\(z_{v,c}\) と \(use_c\) の間には次の論理関係がある．
「隣り合う \(2\) つの領域は互いに異なる色を使う」ということを「隣り合う \(2\) つの領域には同じ色が使えない」と読み替えると，NAND の論理関係にあるとわかる．
「領域は必ず何かしらの色で彩色する」ということは「どの領域も必ず一色を選ぶ」に等しいため，「厳密に \(1\)」の論理関係にあるとわかる．
以上の論理式から次の線形表現を得る．
2.5.1.3. 目的関数#
問題設定から使用する色の数を最小化したいため，目的関数は次でかける．
2.5.1.4. まとめ#
以上をまとめると彩色数問題の定式は以下のとおり．
2.5.2. 論理式の合成#
NOT・AND・OR の三組は全ての論理関数を表すことができる． これから原理的にはそれらの線形表現が得られていれば，任意の論理変数を合成できる． また，OR は De Morganの法則を通して，NOT と AND からも合成できる． 以下では合成例として，二項論理演算で記述される論理式を見てみる． 中には，機械的な合成で得られないものもある．
2.5.2.1. 含意と逆含意#
含意 (\(\implies\)) およびその逆含意 (\(\impliedby\)) は次式に等しい．
よって \(z=(z_1\implies z_2)\) なる含意の論理変数は次で合成できる．
同様に \(z=(z_1\impliedby z_2)\) なる逆含意の論理変数は次で合成できる．
2.5.2.2. OR#
De Morganの法則 \(z_1\lor z_2=\lnot(\lnot z_1\land \lnot z_2)\) を用いて，OR の線形表現を AND と NOT の線形表現から次のように演繹できる．
De Morganの法則 \(z_1\lor z_2=\lnot(\lnot z_1\land \lnot z_2)\) より，OR は二つの論理変数 NOT の AND に等しい．
これを整理すると，次が得られる．
これは OR の線形表現に他ならない．
2.5.2.3. 非含意と逆非含意#
非含意 (\(\mathrel{\rlap{\mkern1em\text{/}}\implies}\)) およびその逆非含意 (\(\mathrel{\rlap{\mkern1.2em\text{/}}\impliedby}\)) は次式に等しい．
よって \(z=(z_1\mathrel{\rlap{\mkern1em\text{/}}\implies} z_2)\) なる非含意の論理変数は次で合成できる．
同様に \(z=(z_1\mathrel{\rlap{\mkern1.2em\text{/}}\impliedby} z_2)\) なる逆非含意の論理変数は次で合成できる．
2.5.2.4. NAND#
NAND (\(\mathrel{\bar{\land}}\)) は次式に等しい．
よって \(z=z_1 \mathrel{\bar{\land}} z_2\) なる NAND の論理変数は次で合成できる．
2.5.2.5. NOR#
NOR (\(\mathrel{\bar{\lor}}\)) は次式に等しい．
よって \(z=z_1 \mathrel{\bar{\lor}} z_2\) なる NOR の論理変数は次で合成できる．
2.5.2.6. XOR#
XOR (\(\veebar\)) は次式に等しい．
よって \(z=z_1 \veebar z_2\) なる XOR の論理変数は次で合成できる．
ここで，中間的な論理変数 \(w_1=\lnot z_1 \land z_2\) と \(w_2=z_1\land \lnot z_2\) を設けているが， より簡便な線形表現を次の議論で見出すこともできる． Iverson 括弧 のところで，XOR は \([P\veebar Q] = |[P] - [Q]|\) を満たすことを見た． このときの議論は，次のようにしても振り返ることができる．
まず，\(z = z_1 \veebar z_2 = (\lnot z_1 \land z_2) \lor (z_1\land \lnot z_2)\) に対して， 非線形項を許した \(z_1\lor z_2 = z_1 + z_2 - z_1z_2\) を用いて，次の非線形項を含んだ等式を得る．
冪等の性質を用いることで，この等式は続けて次のように整理できて，XOR の絶対値を用いた表現が改めて得られる．
ここで，最右辺は次の線形な定式化が可能である．
これは中間変数を用いずに，XOR を線形に定式化できたことを意味する． 特に，最初の二つの不等式は \(z\geq |z_1 - z_2|\) に相当し，残りの二つの不等式は \(z\leq |z_1 - z_2|\) に相当している．
Tip
補助変数 \(w\in\mathbb{B}\) を追加することで定式化（拡張定式化）することもできる．
拡張定式化によって，変数は増えるが，制約式 (facet) は減る傾向にある． XOR は制約式の数が，AND や OR と比較して四つ必要であり，拡張定式化によって一つにできるという点で特徴的である．
2.5.2.7. XNOR#
XNOR (\(\mathrel{\bar{\veebar}}\)) は XOR の否定であるから、\(z=z_1 \mathrel{\bar{\veebar}} z_2\) に対して，次が成り立つ．
これを変形すると次が得られる．
よって，XOR の線形表現に対して，\(z\) を \(1-z\) と置き換えた次が XNOR の線形表現である．
これらを整理して次の XNOR の線形表現が得られる．
なお，XNOR は同値と等価なので，\(z=(z_1\iff z_2)\) もまた上記の線形表現となる．
2.5.3. 選択数検出変数#
\(0\) または \(1\) をとる \(n\) 個ある変数 \(\{z_i\}_{i=1}^n\) のうち， 一つだけ \(1\) をとるかどうかを判定する変数 \(z\) を選択数検出変数と呼んで，これを立式しよう．
\(\sum_{i=1}^n z_i\) は \(0\) から \(n\) の値をとるため，選択数検出変数の定式化のために，余分に以下の変数を導入することにしよう．
これらは何れかが \(1\) でなければならないから，次を満たす必要がある．
そして，Iverson 括弧で書いた部分の線形な定式化として，次を与えることができる．
ここで，便宜のために，式 \(e\) を定義した． これらは確かに所望の（線形な）制約式となっている． そして，これら制約式はさらに次の等価な定式化にもできて，制約式の数を一つ減らすことができる．
ところで，興味深いことに，ここから更に，定式化の強弱 で述べた強い定式化へと書き換えることができる．
2.5.4. \(0\)-\(n\) 変数#
\(0\) または \(1\) をとる変数の総和 \(f(z)=\sum_{i=1}^m z_i\) に対して，次の制約条件が課されたとする．
ここで \(n\) は \(2\) 以上のある整数であり，\(n\leq m\) とする． この制約条件は新たな変数 \(x\in\mathbb{B}\) を用いて，次の等式制約を課すという自明な定式化を考えることができる．
これに対して，上記の新たな変数 \(x\) を用いることなしに， 元々ある \(m\) 個の変数について以下の制約式を課すことで， 線形に定式化することもできる．
ここで，\(\delta_{i,j}\) は Kronecker の \(\delta\) であり，\(\delta_{i,j}=[i=j]\) である．
上記の定式化でよいことは次の考察からわかる．
まず，すべての変数が \(0\) となる場合は，これらの不等式を満たすことは，明らかであるから，そうでない場合を考える． すると，第一の不等式から，\(m\) 個ある変数のうち，高々 \(n\) 個までしか \(1\) の値をとれないとわかる．
次に第二の不等式について，\(z_1=1\) の場合を考えてみると， \(j=1\) について，\(1-n + z_2 + \cdots +z_m\geq 0\) となる． よって，\(z_2\) 以降の \(m-1\) 個の変数のうち，\(n-1\) 個以上が \(1\) でないと，不等式を満たせない． 既に \(z_1=1\) であるから，第一の不等式と合わせて厳密に \(n-1\) 個の変数が \(1\) でなければならない．
このとき，\(j=2\) について，\(z_2=0\) であれば，\(z_3\) 以降の変数は，何れか \(n-1\) 個が \(1\) であればよい． 一方で，\(z_2=1\) であれば，\(z_3\) 以降の \(m-2\) 個の変数のうち，\(n-2\) 個が \(1\) でなければならない．
以上のことを \(j=3\) 以降についても繰り返せば，\(z_2\) 以降の何れかの変数のうち，\(n-1\) 個が \(1\) であれば， 第二の不等式が任意の \(j\) について成り立っていることがわかる． ここまでのことは，\(z_1=1\) の場合から始めたが，他のどの変数から始めても，不等式が対称なので同じ結論に至る． 故に，\(f(z) \in \{0,n\}\) となる．
2.5.5. 制約条件間の含意#
\(2\) つの制約条件 \(f_1(x) \leq 0\) と \(f_2(x) \leq 0\) があって， これらの間で次の含意を課したいとする．ここで Iverson 括弧 を用いた．
この制約条件の記述は次のとおり．
論理変数として \(z_k=[f_k(x) \leq 0]\) を定めると，記述したい制約条件は次のように書ける．
含意 \(P\implies Q\) は次を意味するものとして定義されるものだった．
よって記述したい制約条件は OR 条件を含むため離接制約であり，次のように記述すればよい． 但し \(\varepsilon\) は small ε である．
ここで 不等式制約の切り替え による条件記述を行った．
ところで別の話題として \((1-z_1) + z_2 \geq 1\) を \((1-z_1) + z_2 = 1\) とした場合を想定するならば， \(z_2 = z_1 (=:z)\) となるため，より簡便な次の記述となる．
関連
引用書式