一般化されたド・モルガンの法則と分配法則

任意個の項についての法則

意味論的帰結と同値の課では、二つの項についての同値の法則を確立した。その中には、$\wedge$ と $\vee$ の交換律と結合律、ド・モルガンの法則、二つの分配律が含まれる。ところで、選言標準形の論理式は連言の選言であり、各連言は必要なだけの項をもつ。論理式をこの形に変形するには、任意の長さの連言と選言を否定し、まとめ直し、分配しなければならない。そうであるならば、二項の法則はそのままでは足りない。それらを $n$ 項に拡張し、しかもすべての $n$ について一度に拡張しなければならない。

固定した各 $n$ について、$n$ 項のド・モルガンの法則は、$2^n$ 行の真理値表（$n$ 個の変数で書かれる）によって検証でき、前の課の一様代入を両辺のあいだの双条件に適用すれば、任意の論理式に拡張される。しかし $n$ の値は無限に多く、どれだけの数の表でもそれらを尽くすことはできない。このことから、「すべての $n$ について」という主張は二つの論理式のあいだの同値ではなく、無限に多くの同値についての言明であり、メタ言語で定式化されたものであることが従う。その証明は、自然数と論理式に関する帰納法の課の証明と同様に外部の証明であり、その道具は項の個数に関する帰納法である。記法 $\bigwedge_{i=1}^{n} \varphi_i$ もまたメタ言語に属する。それは言語の新しい記号ではなく、白丸と黒丸からなる記号列の名前であって、$(\varphi \wedge \psi)$ がそうであるのと同じである。

ここで、混同してはならない三つの関係を定めておこう。等式 $\alpha = \beta$ は、$\alpha$ と $\beta$ が同じ記号列であることをいう。定義は $:=$ で書かれ、記号列に名前を導入する。定義を展開して得られるものは等しいのであって、単に同値なのではない。意味論的同値 $\alpha \eqsem \beta$ は、$v(\alpha) = v(\beta)$ がすべての付値 $v$ について成り立つことをいう。演繹の単元の証明可能な同値 $\alpha \dashv\vdash \beta$ は、二つの論理式のそれぞれが他方から導かれることをいう。この課は最初の二つを扱い、三つ目は一つの注釈にだけ現れる。

用いるもの

命題論理の意味論の課からは、次のものを用いる。付値、すなわち変数 $v_1, v_2, \ldots$ から $\{0, 1\}$ への関数と、そのすべての論理式への拡張（同じ文字 $v$ で書く）。公式の略記から計算した派生結合子の値 $v(\neg\varphi) = 1 - v(\varphi)$、$v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi)$（したがって連言が値 $1$ をとるのは、その二つの成分がともに値 $1$ をとるとき、かつそのときに限り、また $v((\varphi \vee \psi)) = 1$ であるのは $v(\varphi) = 1$ または $v(\psi) = 1$ であるとき、かつそのときに限る）。一致補題（二つの付値がある論理式の変数で一致するならば、その論理式で一致する）。そして論理式 $\top$ と $\bot$、すなわち固定したトートロジーと固定した矛盾式。意味論的帰結と同値の課からは、次のものを用いる。$\eqsem$ が反射的、対称的、推移的であること。意味論的置換定理。そして名前つきの法則の一覧。交換律 $(\varphi \wedge \psi) \eqsem (\psi \wedge \varphi)$ と $(\varphi \vee \psi) \eqsem (\psi \vee \varphi)$、結合律 $(\varphi \wedge (\psi \wedge \chi)) \eqsem ((\varphi \wedge \psi) \wedge \chi)$ と $\vee$ についての同様の法則、ド・モルガンの法則 $\neg(\varphi \wedge \psi) \eqsem (\neg\varphi \vee \neg\psi)$ と $\neg(\varphi \vee \psi) \eqsem (\neg\varphi \wedge \neg\psi)$、分配律 $(\varphi \wedge (\psi \vee \chi)) \eqsem ((\varphi \wedge \psi) \vee (\varphi \wedge \chi))$ と $(\varphi \vee (\psi \wedge \chi)) \eqsem ((\varphi \vee \psi) \wedge (\varphi \vee \chi))$、二重否定 $\neg\neg\varphi \eqsem \varphi$、べき等律 $(\varphi \vee \varphi) \eqsem \varphi$、恒等律 $(\varphi \wedge \top) \eqsem \varphi$、そして排中律 $\models (\varphi \vee \neg\varphi)$。これらの法則は任意の論理式 $\varphi$、$\psi$、$\chi$ について成り立ち、これらはメタ変数である。

以下の証明の各段階では、論理式の一部を、それと同値な別の部分で置き換える。意味論的置換定理は、これを一度に一つの出現について許す。次の補題はその特別な場合であり、否定、連言、選言の各部分について一度にこれを与える。これが構文上の自明なことではない点に注意しなければならない。$\neg\alpha$ は記号列 $(\alpha \downarrow \alpha)$ であり、その中に $\alpha$ は二回現れる。したがって $(\alpha \wedge \beta)$ は $\alpha$ の出現を八つ、$\beta$ の出現を八つ含む。