
AND と OR だけで NOT を表現できない理由

目次
Twitter で「AND と OR だけで NOT を表現できるかを ChatGPT に聞くとバグる」といったツイートを見かけて、ふと思った。
実際、 AND と NOT ならば、ド・モルガン則により OR を表現することができる。
$$ q \lor r = \lnot(\lnot q \land \lnot r) $$
ここまでできれば「ならば」$p \implies q$ や「同値」$p \iff q$ も表現できる。
ここから示唆されるように、実は AND と NOT だけで、真理関数のありうるすべての演算を表現できる。これを完全性と呼ぶ。
AND と NOT は完全。他にも OR と NOT も完全。
面白いもので言えば、以前スマリヤンの教科書で読んだけれど、シェーファーストローク $\mid = \lnot(p \land q)$ も、この一つの演算子だけで完全になる。 これは以下の 2 つの式が成り立つことを見ればその理由がわかる。(証明はこの記事の最後につけた)
$$ \lnot p \iff (p \mid p) $$
$$ p \land q \iff (p \mid q) \mid (p \mid q) $$
ここで改めて思う – 完全な演算子を見てみると、必ず NOT の要素が入っている。
本当に NOT が必要なのか?必要ならば、なぜ必要なのか?
ということで調べた。
結論を言えば、本当に必要。単調性がキーになる。
単調性の定義#
$f: \{0,1\}^n \to \{0,1\}$ が単調 (monotone) であるとは、
任意の $(a_1,\dots,a_n), (b_1,\dots,b_n) \in {0,1}^n$ に対して、 $$(a_1 \le b_1,\dots,a_n \le b_n) \implies f(a_1,\dots,a_n) \le f(b_1,\dots,b_n)$$
が成り立つことをいう。(ここでは非減少な広義の単調のことをシンプルに単調と表現している)
なぜ否定が必要か#
まず 2 変数演算 $\land$ と $\lor$ はそれぞれ単調である。
AND
$$ x \land y = \begin{cases} 1, & \text{if } x=1 \text{ and } y=1,\\ 0, & \text{otherwise}. \end{cases} $$
入力の一方または両方を 0→1 に変えると、出力が 0→1 に変わることはあっても、1→0 に下がることはない。実際、$\alpha_i \le \beta_i$ の条件下で以下が成り立つ:
$$ (\alpha_1 \land \alpha_2) \le (\beta_1 \land \beta_2). $$
OR
$$ x \lor y = \begin{cases} 0, & \text{if } x=0 \text{ and } y=0,\\ 1, & \text{otherwise}. \end{cases} $$
実際、$\alpha_i \le \beta_i$ の条件下で以下が成り立つ:
$$ (\alpha_1 \lor \alpha_2) \le (\beta_1 \lor \beta_2). $$
ここから、 AND と OR のみで構成された式が必ず単調になることを帰納法的に示すことができる。以下はその証明の簡略版
- $\land$ と $\lor$ を $\square$ と表現しよう。 $\square$ は単調である。
- $\phi$ と $\psi$ を単調な式とする。
- $\alpha \le \beta$ なとき、 $$ (\phi \square \psi)(\alpha) = \phi(\alpha) \square \psi(\alpha) \le \phi(\beta) \square \psi(\beta) = (\phi \square \psi)(\beta) $$
が成り立つ。
まとめると、 AND と OR のみからなる式は必ず単調 である。
これの対偶を考えれば、 非単調な式は AND と OR のみからなる式では表現できない ということ。
以上からも、 AND と OR からのみ構成される演算は、真理関数のありうるすべての演算の中でも、真に部分的な演算しか表現できないことがわかる。
一方で NOT の非単調
故に、 NOT は AND と OR のみからなる式では表現できないということがわかる。
おわり
付録:シェーファーストロークによる否定と連言の表現#
$\lnot p = (p \mid p)$#
シェーファーストロークの定義より: $$p \mid p = \lnot(p \land p)$$
ここで $$p \land p \iff p$$
したがって $$\lnot(p \land p) \iff \lnot p$$
まとめると $$p \mid p = \lnot(p \land p) = \lnot p$$
$p \land q = (p \mid q) \mid (p \mid q)$#
定義より $$p \mid q = \lnot(p \land q)$$
連言そのものは二重否定で $$p \land q = \lnot(\lnot(p \land q))$$ だが、$\lnot(p \land q)$ は $p \mid q$ と書けるので $$p \land q = \lnot(p \mid q)$$
上で証明した否定の書き換えにより、「$r$ の否定」は $r \mid r$ と表せる ここで $r = (p \mid q)$ とおけば $$\lnot(p \mid q) = (p \mid q) \mid (p \mid q)$$
まとめると $$p \land q = \lnot(p \mid q) = (p \mid q) \mid (p \mid q)$$