集合演算

式の組み立てについての帰納法（構造的帰納法）で示す。$u=\varepsilon(x)$ とおく。$t=a_i$ なら、$x\in A_i\iff u_i=1$ は所属の型の定義そのものである。$t=\mathbf 0$ なら両辺とも偽、$t=\mathbf 1$ なら両辺とも真である。
$t=s\cup r$ で $s,r$ について主張が成り立つとする。$x\in s[\vec A]\cup r[\vec A]$ は「$\hat s(u)=1$ または $\hat r(u)=1$」と同値で、値が 0 か 1 なのでこれは $\max(\hat s(u),\hat r(u))=1$ と同値である。$\cap$ は $\min$、$s\setminus r$ は「$\hat s(u)=1$ かつ $\hat r(u)=0$」すなわち $\hat s(u)(1-\hat r(u))=1$、$\triangle$ は「ちょうど一方が 1」すなわち $\hat s(u)+\hat r(u)-2\hat s(u)\hat r(u)=1$、補集合は $\hat s(u)=0$ すなわち $1-\hat s(u)=1$ と同値であり、同じ形で示せる。$\square$

$x\in X$ を任意にとる。$x$ が属する区画は $R_{\varepsilon(x)}$ だけなので、$x\in\bigcup_{\varepsilon\in S_t}R_\varepsilon$ は $\varepsilon(x)\in S_t$、すなわち $\hat t(\varepsilon(x))=1$ と同値である。lem-setop-membership により、これは $x\in t[A_1,\dots,A_n]$ と同値である。両辺はともに $X$ の部分集合なので、二つの集合は等しい。$\square$

(c)⇒(a)：thm-setop-normal-form により、$\hat s=\hat t$ なら $S_s=S_t$ で、両辺は同じ区画の和である。(a)⇒(b) は明らかである。
(b)⇒(c)：$\varepsilon\in\{0,1\}^n$ を任意にとり、$X=\{*\}$ の部分集合を $\varepsilon_i=1$ なら $A_i=\{*\}$、$\varepsilon_i=0$ なら $A_i=\emptyset$ と定める。すると $\varepsilon(*)=\varepsilon$ であり、lem-setop-membership により $*\in s[\vec A]\iff\hat s(\varepsilon)=1$、$*\in t[\vec A]\iff\hat t(\varepsilon)=1$ である。(b) から二つの集合は等しいので $\hat s(\varepsilon)=\hat t(\varepsilon)$ である。$\square$

どの等式も、変数 $a,b,c$ の式 $s,t$ によって $s[A,B,C]=t[A,B,C]$ と書ける。cor-setop-identity の (c)⇒(a) により、$\hat s=\hat t$ を確かめればよい。たとえば分配律の第 1 式では、$u,v,w\in\{0,1\}$ について $\min(u,\max(v,w))=\max(\min(u,v),\min(u,w))$ を示せばよく、$u=0$ なら両辺は $0$、$u=1$ なら両辺は $\max(v,w)$ である。吸収律の第 1 式は $\max(u,\min(u,v))=u$ で、$u=1$ なら両辺 $1$、$u=0$ なら両辺 $0$ である。De Morgan の第 1 式は $1-\max(u,v)=\min(1-u,1-v)$ で、$\max(u,v)=1$ となるのは $u,v$ の一方が $1$ のとき、すなわち $\min(1-u,1-v)=0$ のときに限る。

1．$\subseteq$ は thm-setop-normal-form による。逆に $S\subseteq\{0,1\}^n$ をとる。$S=\emptyset$ なら $\mathbf 0$ の値が $\emptyset$ である。$S\neq\emptyset$ なら、$\varepsilon\in S$ ごとに式 $r_\varepsilon:=a_1^{\varepsilon_1}\cap\cdots\cap a_n^{\varepsilon_n}$（$a_i^1=a_i$、$a_i^0=a_i^c$）をとり、それらを $\cup$ でつないだ式を $t_S$ とする。$\hat r_\varepsilon(u)=1$ となるのは $u=\varepsilon$ のときだけなので $\hat t_S(u)=1\iff u\in S$ であり、thm-setop-normal-form により $t_S[A_1,\dots,A_n]=\bigcup_{\varepsilon\in S}R_\varepsilon$ である。
2．$T\subseteq N$ に $\Phi(T):=\bigcup_{\varepsilon\in T}R_\varepsilon$ を対応させる。空の区画は和に寄与しないので $\bigcup_{\varepsilon\in S}R_\varepsilon=\Phi(S\cap N)$ であり、1 により $\Phi$ は $\mathcal P(N)$ から $\mathcal A$ への全射である。$T\neq T'$ なら、たとえば $\varepsilon\in T\setminus T'$ について $R_\varepsilon$ は空でなく、$\Phi(T)$ に含まれ、区画どうしは交わらないので $\Phi(T')$ と交わらない。よって $\Phi(T)\neq\Phi(T')$ で、$\Phi$ は全単射である。したがって $|\mathcal A|=|\mathcal P(N)|=2^{|N|}$ である。$|N|\leq2^n$ で、等号は $N=\{0,1\}^n$ のときに限る。$\square$

1．$f$ が恒等的に $0$ なら、三つの組でそれぞれ $(a_1^c\cup a_1)^c$、$a_1\cap a_1^c$、$a_1\mathbin{\triangle}a_1$ が $f$ を表す。そうでなければ $S=\{\varepsilon\mid f(\varepsilon)=1\}$ は空でなく、thm-setop-count の証明の式 $t_S$ は $\cup,\cap,{}^c$ だけを使い $\hat t_S=f$ を満たす。$t_S$ の中の $s\cap r$ をすべて $(s^c\cup r^c)^c$ に置き換えると $\{\cup,{}^c\}$ の式になり、$\min(x,y)=1-\max(1-x,1-y)$ なので真理関数は変わらない。同様に $s\cup r$ を $(s^c\cap r^c)^c$ に置き換えれば $\{\cap,{}^c\}$ の式になる。$\{\triangle,\cap,\mathbf 1\}$ については、$s^c$ を $\mathbf 1\mathbin{\triangle}s$ に、$s\cup r$ を $(s\mathbin{\triangle}r)\mathbin{\triangle}(s\cap r)$ に置き換える。$x,y\in\{0,1\}$ について $\widehat{\triangle}$ は $x+y$ を $2$ で割った余りなので、$1+x\equiv1-x$、$x+y+xy\equiv\max(x,y)\pmod 2$（$x=y=1$ のとき $3\equiv1$、それ以外は直接確かめる）であり、真理関数は変わらない。
2．式の組み立てについての帰納法による。変数の真理関数は $u=(0,\dots,0)$ で $0$ であり、$\max(0,0)$、$\min(0,0)$、$0\cdot(1-0)$、$0+0-0$ はどれも $0$ である。一方 $\widehat{a_1^c}(0,\dots,0)=1$ である。
3．変数と定数の真理関数は単調で、単調な関数の $\max$ と $\min$ は単調である。$\widehat{a_1\setminus a_2}$ は $(1,0)$ で $1$、$(1,1)$ で $0$ であり、$\widehat{a_1^c}$ は $(0,\dots)$ で $1$、$(1,\dots)$ で $0$ なので、どちらも単調でない。
4．帰納法による。$t=a_i$ なら $\ell=i$ で等号が成り立つ。$t=s\setminus r$ なら $t$ の最も左の変数は $s$ のそれであり、$\hat t=\hat s(1-\hat r)\leq\hat s\leq u_\ell$ である。$n=2$ で $\{\setminus\}$ の式 $t$ が $\hat t(u)=\max(u_1,u_2)$ を満たすとすると、$u=(1,0)$ で $1\leq u_\ell$ から $\ell=1$、$u=(0,1)$ から $\ell=2$ となり矛盾する。
5．帰納法による。変数と定数はこの形である。$x,y\in\{0,1\}$ について $x+y-2xy\equiv x+y\pmod 2$ なので、この形の二つの関数の $\triangle$ もこの形である。$u_1u_2\equiv c+\alpha u_1+\beta u_2$ とすると、$u=(0,0)$ から $c=0$、$(1,0)$ から $\alpha=0$、$(0,1)$ から $\beta=0$ となり、$(1,1)$ で $1\equiv0$ となって矛盾する。$\square$