§E16.3Boolean 代数

証明. まず$n=0$なら、$\mathbf2^0=\{()\}$であり$e_{()}$は空の連言$1$である。全体の結びは$1$、直交性は空虚であり、$S=\varnothing$と$S=\{()\}$の二場合で補元の式はそれぞれ$\neg0=1$と$\neg1=0$になる。

$n\ge1$とする。分配則と補元律により

$a\ne c$なら、$a_i\ne c_i$を満たす添字$i\in\{1,\ldots,n\}$が存在する。$e_a\wedge e_c$は$b_i\wedge\neg b_i$を因子にもつから$0$である。

$x=\bigvee_{a\in S}e_a$、$y=\bigvee_{a\notin S}e_a$と置く。前半から$x\vee y=1$であり、分配則と直交性から$x\wedge y=0$である。Boolean 代数では補元は一意である。実際、$u,v$がともに$x$の補元なら

であり、同様に$v=u\wedge v$である。したがって$u=v$である。ゆえに$y=\neg x$である。▨

証明. 置換後の$\neg(p_0\to p_0)$はすべての付値で値$0$をもつ。論理式の構造帰納法により、置換は任意の定数付き論理式の真理値を保つ。原始論理式の包含と置換は商上で互いに逆である。$p_0,q_0\in P$のどちらを選んでも、二つの矛盾式はすべての付値で値$0$をもつため同じ同値類になる。▨

証明. 反射律、対称律、推移律は$\mathbf2$における等号の対応する性質から従う。二組の仮定の下では、任意の付値$v$について直下の論理式の真理値が一致する。否定と含意の真理値は直下の真理値だけから定まるので、構成後の真理値も一致する。派生結合子については定義を展開すればよい。▨

証明.命題 2.4により、代表元を意味論的に同値な論理式へ取り替えても$\wedge,\vee,\neg$の結果の同値類は変わらない。$\bot$と$\top$の真理値は定義によりそれぞれ$0$と$1$である。以上により全演算の well-definedness が示された。

Boolean 代数の各公理の両辺を代表する論理式は、$\mathbf2$の真理値演算の同じ恒等式を表す。例えば、任意の付値$v$について

である。したがって商では分配則が成り立つ。結合律、可換律、冪等律、吸収則、単位元律、補元律も$\mathbf2$の対応する恒等式を各付値で確認することで得られる。ゆえに$\mathcal B(P)$は Boolean 代数である。▨

証明.$\varphi$と$\psi$に現れる命題変数を重複なく$p_1,\ldots,p_n$とする。ここでは$n=0$も許す。$b_i=g(p_i)$と置き、補題 1.4の$e_a$を作る。各$a\in\mathbf2^n$に対し、付値$v_a:P\to\mathbf2$を$v_a(p_i)=a_i$および$p\notin\{p_1,\ldots,p_n\}$ならば$v_a(p)=0$によって定める。

$\operatorname{Var}(\theta)\subseteq\{p_1,\ldots,p_n\}$を満たす任意の論理式$\theta$について

を構造帰納法で示す。この変数条件は直下の論理式へ継承されるため、否定と含意の場合に帰納法の仮定を適用することができる。

$\theta=\bot$の場合、真となる行の集合は空であるから右辺は$0$である。$\theta=p_j$の場合、右辺は

である。$\theta=\neg\alpha$の場合、帰納法の仮定と有限分割補題の補元の式により、右辺の添字集合は$v_a\not\models\alpha$を満たす行へ移り、値は$\neg\llbracket\alpha\rrbracket_g^B$となる。

$\theta=\alpha\to\beta$の場合、含意が真となる行の集合は

である。有限分割補題、分配則、冪等律により、対応する$e_a$の結びは

したがって$(*)$は変数が$p_1,\ldots,p_n$に含まれるすべての論理式で成り立つ。特に$\varphi$と$\psi$はこの条件を満たす。$\varphi\equiv_{\mathrm{sem}}\psi$なら$(*)$の右辺の添字集合が等しいから、両評価値も等しい。▨

証明. 存在を示すため

と定める。補題 3.2により、この値は代表元$\varphi$の選択に依存しない。Boolean 評価の再帰式から、$\overline g$は補元と含意を保存する。$\land,\lor,0,1$の定義を展開すれば、$\overline g$はそれらも保存する。さらに$\overline g(\eta(p))=\overline g([p])=g(p)$である。

$h:\mathcal B(P)\to B$も$h\circ\eta=g$を満たす Boolean 準同型とする。$h([\varphi])=\llbracket\varphi\rrbracket_g^B$を$\varphi$に関する構造帰納法で示す。$\bot$の場合は$h(0)=0$、命題変数の場合は$h([p])=g(p)$である。否定と含意の場合は、$h$が Boolean 演算を保存することと帰納法の仮定から従う。したがってすべての同値類で$h=\overline g$であり、一意性を得る。▨

証明. 変数を含まない定数付き論理式の値は、構造帰納法により$0$または$1$である。したがって同値類は$[\bot]$と$[\top]$の二つだけであり、両者は二元 Boolean 代数をなす。Boolean 準同型は定数$0,1$を保存するため、表示した写像以外に存在せず、この写像はすべての Boolean 演算を保存する。▨

証明. 前半は定理 4.2で$B=\mathbf2$とした場合である。後半では$v=h\circ\eta$と置く。自由性の一意性により、$v$が誘導する準同型は$h$に等しい。▨