Ctrl+K

論理式の線形表現

2. 論理式の線形表現#

2.1. 説明#

二値状態を判別する インジケータ変数 を用いると，状態間の論理的な結びつけが可能となる． AND や OR のみならず全ての論理式を記述でき，広範な応用分野の源泉となっている．

論理式を表現する上で大別して \(3\) つの捉え方がある．

  1. 論理式を制約条件として捉える場合

    • 例えば命題 \(P\) と \(Q\) があった場合に，論理和 \(P\lor Q\) を真とする意味で制約条件を扱いたい場合

    • この場合は論理式が偽であることは制約条件が成立しないことを意味するので，偽の状態は許容されない．

  2. 論理式を論理変数として捉える場合

    • 例えば命題 \(P\) と \(Q\) があった場合に，論理和 \(P\lor Q\) を真とする意味で論理変数を扱いたい場合

    • この場合は論理式が偽であることは \(1\) つの状態であり，偽の状態も定式化の一部として許容される．

  3. 論理式を制約条件式間の論理条件として捉える場合

    • 例えば制約条件の論理式 \(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.1.1. 対応一覧表 (制約条件)#

以下，\(z_1\) や \(z_2\) などはすべて命題論理式に対応する真偽値を意味する．

2.1.1.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\bar{\land} z_2\)

\(z_1 + z_2 \leq 1\)

NOR

\(z_1\bar{\lor} z_2\)

\(z_1 + z_2 = 0\)

XOR

\(z_1\veebar z_2\)

\(z_1 + z_2 = 1\)

XNOR

\(z_1\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\) か) に関係しないことと対応している．

  • 含意は 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 の線形表現から含意の線形表現 (およびその逆) が演繹できる．

(2.4)#\[(1-z_1) + z_2 \geq 1 \iff z_1\leq z_2\]

2.1.1.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\) を簡約せずに残した．

(2.5)#\[z_1 \leq z_2\cdot z_3\]

  • \(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.1.1.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\frac{|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 条件である．

  • 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) に関する線形表現を得るための考え方の例は次のとおり．

  1. \(P\implies Q\) という命題のため，\(f_{N,M}(\{z_i\}_i) \leq z\) であり，\(f\) を決定すればよい．

  2. \(f\) は線形でなければならないから次の形をしている．

    (2.6)#\[f_{N,M}(\{z_i\}_i) = \sum_{i=1}^N A_i(N,M) \cdot z_i + B(N,M)\]

  3. \(f\) は論理変数が真である総数 \(c:=\sum_{i=1}^N z_i\) を比較する必要があり，どの論理変数も特別視しないため，線形結合の重みに偏りがあってはならない．よって次式のとおり \(c\) についての一次関数となる．

    (2.7)#\[f_{N,M}(c) = A(N,M)\cdot c + B(N,M)\]

  4. \(\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\) が機能する．

  5. 前項までの \(f\) の値の変化は \(N-M+1\) 個ある \(c\) が真となりうるパターンについて \(\varepsilon\) の元の数値を \(f\) がとり，それ以外は \(\mu\) の元の数値を取ればよいとわかる．そしてその直線の傾きは正である．

  6. 傾きと切片を真の数が最大となる \(N\) 個の場合に \(f=1\) であり，最小となる \(M\) 個の場合に \(1/(N-M+1)\) となるように決定する．このように決定した \(f\) は次式で与えられる．

    (2.8)#\[f_{N,M}(c) = \frac{c - M + 1}{N - M + 1}\]

  7. 「\(N\) 変数のうち \(M\) 変数以下が真ならば真」の場合についても同様に考えることで，線形表現が得られる．

  8. 「\(N\) 変数のうち \(M\) 変数が真ならば真」や「\(N\) 変数のうち \(M_1\) 変数以上かつ \(M_2\) 変数以下が真ならば真」は \(f\) の傾きが一回だけ変化するので，\(2\) つの線形制約式が必要である．それらは「\(N\) 変数のうち \(M\) 変数以上が真ならば真」と「\(N\) 変数のうち \(M\) 変数以下が真ならば真」を共に課せばよいことと対応している．

    (2.9)#\[\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.1.2. 対応一覧表 (論理変数)#

2.1.2.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\)

  • AND 演算は \(\min\) 演算に等しい．

(2.10)#\[\begin{split}z_1\land z_2 &= \min(z_1,z_2), \\ \bigwedge_{i\in I} z_i &= \min_{i\in I} z_i\end{split}\]

  • OR 演算は \(\max\) 演算に等しい．

(2.11)#\[\begin{split}z_1\lor z_2 &= \max(z_1,z_2), \\ \bigvee_{i\in I} z_i &= \max_{i\in I} z_i\end{split}\]

  • AND や OR は上限と下限の \(2\) つの制約条件が必要になっているが，目的関数に \(z\) が含まれており，最大化もしくは最小化することが有利であるならば，上限・下限の制約条件の一方を課さなくても良い場合がある．

  • 目的関数を利用して制約を一部課さなくても良い場合には，論理変数を閉区間 \([0,1]\) の中で連続緩和できる場合がある．その場合には離散変数の数を削減して，問題の複雑度が下がることを期待できる．

  • NAND や XOR など他の基本的な二項論理演算は NOT・AND・OR から合成できるため，これによりそれらの線形表現もまた合成できる．

2.1.2.2. 連続変数との積#

\(\mathbb{B}:=\{0,1\}\) として次の連続変数 \(x\) との積で定義される連続変数 \(y\) があったとする．

(2.12)#\[\begin{split}& y = x\cdot z,~ x\in\mathbb{R},~ z\in\mathbb{B}, \\ & L \leq x \leq U\end{split}\]

これの線形表現は次のとおり．

(2.13)#\[\begin{split}& L\cdot z \leq y \leq U\cdot z, \\ & L\cdot (1-z) \leq x - y \leq U\cdot (1-z)\end{split}\]

2.1.2.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.1.3. 制約条件式間の論理条件#

NOT・AND・OR の三組は全ての論理命題を表すことができる． 制約条件の成立を命題と考える場合に，これらが記述できれば，問題の制約をすべて記述できる．

NOT 条件は \(f(x)\geq 0\) に対して \(f(x) < 0\) などと small ε を用いて機械的に記述できる． また AND 条件は制約条件式がすべて満たす場合であり，通常定式化で制約条件式を羅列されていることに自明に対応している．

重要

非自明な論理条件は OR 条件を含んだ条件であり，これらはまた離接制約ともよばれている． 以下に述べる OR 条件の記述には論理変数が必要になるため，OR 条件が混ざると必然的に整数計画問題のクラスになる． これは NOT や AND 条件との大きな違いである．

2.1.3.1. 離接制約と OR 条件#

制約条件間の OR 条件を含む記述は離接制約の記述と呼ばれて，次のことを言う．

制約条件の集まりを \(\{f_i(x) \leq 0\}_{i \in C_k}\) とする． つまりある \(k (\in K)\) に対して \(C_k\) という制約条件の集まりが対応する． \(z_k\) を \(C_k\) が成り立つか否かを表す論理変数とする． この場合に何れか一つの制約が少なくも真であることを要求する連言標準形で書かれた制約を離接制約という．

(2.14)#\[\bigvee_{k\in K} z_k ~ \mathrm{is ~ truthy.}\]

つまり次を要求する．

(2.15)#\[\sum_{k\in K} z_k \geq 1\]

これは純粋に OR 条件だけであるが， 例えば LEAST・MOST・EXACTLY などを通して OR 条件を含んだ場合を課すことが考えられる． これらが課されて各論理変数に付与された後は，Big M を用いて制約条件に次のようにこれら論理変数を挿入させる．

(2.16)#\[f_i(x) \leq M_i\cdot (1-z_k),~ \forall i\in C_k\]

\(z_k=1\) ならば \(C_k\) に属している制約条件は元の制約条件となり， 一方で \(z_k=0\) ならば Big M のために真偽が問われない自由な制約条件となる．

Big M は問題に表れる変数 \(x\) の最大値がわかっていれば次式で厳密に求めることができる．

(2.17)#\[M_i = \max_{x=\{x_j\}_{j\in J_i}} f_i(x)\]

また同じことだが \(f_i(x) = g_i(x) - U_i\) と変数項と定数項とに分解した場合の制約条件と Big M は次式である．

(2.18)#\[\begin{split}& g_i(x) + M_i\cdot z_k \leq \max_{x=\{x_j\}_{j\in J_i}} g_i(x),~ \forall i\in C_k, \\ & M_i = \max_{x=\{x_j\}_{j\in J_i}} g_i(x) - U_i,~ \forall i\in C_k\end{split}\]

2.2. 例題#

2.2.1. 彩色数問題#

「互いに隣り合う \(2\) つの領域には異なる色を彩色するとき，使用する色の数を最小化せよ」という問題を彩色数問題という． この問題は四色定理から高々最大でも彩色数 \(4\) が解となるはずである．

彩色数問題の定式化は次のとおり．

2.2.1.1. 集合・定数・変数#

  • INPUT (集合・定数)

    • \(COLORS\) は使用する色の集まり

    • \(v\in V\) は彩色対象の集まり

    • \((v1,v2)\in A\) は \(v1 \in V\) と \(v2 \in V\) が「互いに隣り合っている」という接続関係

  • OUTPUT (変数)

    • \(z[v, c]\) は \(v\) に色 \(c\) を彩色するかどうか

    • \(use[c]\) は色 \(c\) を使用するかどうか

2.2.1.2. 制約条件#

  • 「彩色したら色を使ったことになる」ため，\(z[v, c]\) と \(use[c]\) の間には次の論理関係がある．

(2.19)#\[z[v, c] \implies use[c]\]

  • 「隣り合う \(2\) つの領域は互いに異なる色を使う」ということを「隣り合う \(2\) つの領域には同じ色が使えない」と読み替えると，NAND の論理関係にあるとわかる．

(2.20)#\[z[v1,c] \bar{\land} z[v2,c]\]

  • 「領域は必ず何かしらの色で彩色する」ということは「どの領域も必ず一色を選ぶ」に等しいため，「厳密に \(1\)」の論理関係にあるとわかる．

以上の論理式から次の線形表現を得る．

(2.21)#\[\begin{split}& \mathrm{subject~to:}~ \\ & z[v,c] \leq use[c],~ \forall v\in V,~ c\in COLORS, \\ & z[v1,c] + z[v2,c] \leq 1,~ (v1,v2)\in A,~ c \in COLORS, \\ & \sum_{c\in COLORS} z[v,c] = 1,~ \forall v\in V\end{split}\]

2.2.1.3. 目的関数#

問題設定から使用する色の数を最小化したいため，目的関数は次でかける．

(2.22)#\[\mathrm{Minimize:}~ \sum_{c\in COLORS} use[c]\]

2.2.1.4. まとめ#

以上をまとめると彩色数問題の定式は以下のとおり．

(2.23)#\[\begin{split}& \mathrm{Minimize:}~ \sum_{c\in COLORS} use[c] \\ & \mathrm{subject~to:}~ \\ & z[v,c] \leq use[c],~ \forall v\in V,~ \forall c\in COLORS, \\ & z[v1,c] + z[v2,c] \leq 1,~ \forall (v1,v2)\in A,~ \forall c \in COLORS, \\ & \sum_{c\in COLORS} z[v,c] = 1,~ \forall v\in V\end{split}\]

2.2.2. NAND・XOR の合成#

NOT・AND・OR の三組は全ての論理関数を表すことができる． これから原理的にはそれらの線形表現が得られていれば，任意の論理変数を合成できる． 以下では NAND・XOR で合成例として見てみる．

2.2.2.1. NAND#

NAND (\(\bar{\land}\)) は次式に等しい．

(2.24)#\[z_1 \bar{\land} z_2 = (\lnot z_1) \lor (\lnot z_2)\]

よって \(z=z_1 \bar{\land} z_2\) なる NAND の論理変数は次で合成できる．

(2.25)#\[z \leq (1-z_1) + (1-z_2) \leq 2z\]

2.2.2.2. XOR#

XOR (\(\veebar\)) は次式に等しい．

(2.26)#\[z_1 \veebar z_2 = (\lnot z_1 \land z_2) \lor (z_1\land \lnot z_2)\]

よって \(z=z_1 \veebar z_2\) なる XOR の論理変数は次で合成できる．

(2.27)#\[\begin{split}& z \leq w_1 + w_2 \leq 2z, \\ & 2w_1 \leq (1-z_1) + z_2 \leq w_1 + 1, \\ & 2w_2 \leq z_1 + (1-z_2) \leq w_2 + 1\end{split}\]

2.2.3. 制約条件間の含意#

\(2\) つの制約条件 \(f_1(x) \leq 0\) と \(f_2(x) \leq 0\) があって， これらの間で次の含意を課したいとする．ここで Iverson 括弧 を用いた．

(2.28)#\[[f_1(x)\leq 0] \implies [f_2(x) \leq 0]\]

この制約条件の記述は次のとおり．

論理変数として \(z_k=[f_k(x) \leq 0]\) を定めると，記述したい制約条件は次のように書ける．

(2.29)#\[z_1 \implies z_2\]

含意 \(P\implies Q\) は次を意味するものとして定義されるものだった．

(2.30)#\[P\implies Q \iff (\lnot P)\lor Q\]

よって記述したい制約条件は OR 条件を含むため離接制約であり，次のように記述すればよい． 但し \(\varepsilon\) は small ε である．

(2.31)#\[\begin{split}(1-z_1) + z_2 &\geq 1, \\ f_k(x) &\geq \varepsilon - M_k\cdot z_k, \quad \forall k\in\{1,2\}, \\ f_k(x) &\leq M_k\cdot (1-z_k), \quad \forall k\in\{1,2\}\end{split}\]

ここで 不等式制約の切り替え による条件記述を行った．

ところで別の話題として \((1-z_1) + z_2 \geq 1\) を \((1-z_1) + z_2 = 1\) とした場合を想定するならば， \(z_2 = z_1 (=:z)\) となるため，より簡便な次の記述となる．

(2.32)#\[\begin{split}f_k(x) &\geq \varepsilon - M_k\cdot z, \quad \forall k\in\{1,2\}, \\ f_k(x) &\leq M_k\cdot (1-z), \quad \forall k\in\{1,2\}\end{split}\]

2.3. 関連#

目次