コンテンツへスキップ
Topos Uranos
日本語

ド・モルガンの法則と分配法則

要約

この課は、数学全体が使う二つの同値の族で演繹の単元を締めくくる。否定が連言や選言をどのように通り抜けるかを述べるド・モルガンの法則と、連言が選言に対して、選言が連言に対してどのように分配されるかを述べる分配法則である。これらを証明する前に、それらが依拠する区別を明らかにする。同じ記号列を指示する二つの式は、同じ論理式なので、そのまま互いに置き換えてよい。これに対して、同値であるにすぎない二つの論理式は、別の論理式の内部では、同値なものの置換によって、層ごとにしか置き換えられない。この注意のもとで、二つのド・モルガンの法則、その変種（そのなかに含意の否定がある）、二つの分配法則を、それぞれ両方の向きで、演繹によって証明する。問題では、それらを使ってべき等律、吸収律、結合律、簡単な標準形、そしてド・モルガンの法則と対偶を組み合わせた演繹を得る。

学習目標

  1. 記号列の恒等式（略記をその展開でどこでも置き換えることを許す）と、証明可能な同値（同値なものの置換を通してしか論理式の内部での置き換えを許さない）とを区別し、演繹の中で同値を連鎖させる。
  2. 二つのド・モルガンの法則とその変種を、含意の否定も含めて演繹によって証明し、そこで二重否定の置換の規則が果たす役割を見きわめる。
  3. 連言の選言に対する分配律と選言の連言に対する分配律を両方の向きで証明し、それぞれの場合に適切な場合分けによる証明を選ぶ。
  4. 一歩ごとに根拠づけた同値の連鎖によって論理式を簡単な標準形に変形し、べき等律、吸収律、結合律を演繹によって得る。
  5. ド・モルガンの法則を対偶や結合子の導入則・除去則と組み合わせる、前提つきの演繹を構成する。

この単元のこれまでの課は、一つずつ積み重ねて演繹の道具を作ってきた。公理の体系とモーダス・ポネンス、四つの基本技法と二重否定の置換、結合子の対称性と古典論理の技法である。この課は新しい規則を一つも加えず、それらをいっしょに働かせる。そうであるなら、この課の面白さは、ほかのコースで知っているかもしれない言明そのものよりも、それを得る方法にある。各行は、公理、前提、定義、二つの原始規則のどちらか、またはすでに証明された結果によって根拠づけられなければならず、どの行も「自明に見える」ことに頼ってはならない。

使うものとそのつなぎ方

形式的演繹体系の課からは、次のものを借りる。ウカシェヴィチの公理 A1、A2、A3、モーダス・ポネンス（MP）とその前提つきの形、反射性（φ∈Γ\varphi \in \Gamma ならば Γ⊢φ\Gamma \vdash \varphi）、単調性、カット（Γ⊢φi\Gamma \vdash \varphi_i がすべての ii について成り立ち、かつ Γ∪{φ1,…,φn}⊢ψ\Gamma \cup \{\varphi_1, \ldots, \varphi_n\} \vdash \psi ならば、Γ⊢ψ\Gamma \vdash \psi）、演繹定理、そして証明可能な同値（φ⊣⊢ψ\varphi \dashv\vdash \psi とは、{φ}⊢ψ\{\varphi\} \vdash \psi かつ {ψ}⊢φ\{\psi\} \vdash \varphi であること）とその性質である。証明可能な同値は反射的、対称的、推移的であり、φ⊣⊢ψ\varphi \dashv\vdash \psi ならば、Γ⊢φ\Gamma \vdash \varphi であるのは Γ⊢ψ\Gamma \vdash \psi であるとき、かつそのときに限る。四つの演繹技法の課からは、二重否定（φ⊣⊢¬¬φ\varphi \dashv\vdash \neg\neg\varphi）、対偶、とくに (φ→ψ)⊣⊢(¬ψ→¬φ)(\varphi \rightarrow \psi) \dashv\vdash (\neg\psi \rightarrow \neg\varphi)、そして本コースの体系の第二の原始規則である二重否定の置換を借りる。この規則のもとでも演繹定理は成り立ち続ける。χ′\chi' が χ\chi から部分論理式 θ\theta の一つの出現を ¬¬θ\neg\neg\theta に置き換えて、あるいは ¬¬θ\neg\neg\theta の一つの出現を θ\theta に置き換えて得られるならば、χ\chi から χ′\chi' が推論される。こうして行 ii から得た行の根拠は二重否定置換(i)(i) と書く。その直接の帰結には (φ↓ψ)⊣⊢(¬¬φ↓ψ)(\varphi \downarrow \psi) \dashv\vdash (\neg\neg\varphi \downarrow \psi)、(φ↓ψ)⊣⊢(φ↓¬¬ψ)(\varphi \downarrow \psi) \dashv\vdash (\varphi \downarrow \neg\neg\psi)、そして一般に χ⊣⊢χ′\chi \dashv\vdash \chi'（χ′\chi' が χ\chi から二重否定置換によって得られるとき）がある。ゆえに、二重否定置換(i)(i) は χ⊣⊢φ\chi \dashv\vdash \varphi の形の行にも適用され、φ\varphi の中の二重否定を変えるのに使える。結合子の対称性の課からは、同値なものの置換（同値置換）と対称性を借りる。そのなかには (φ∨ψ)⊣⊢(ψ∨φ)(\varphi \vee \psi) \dashv\vdash (\psi \vee \varphi) と (φ∧ψ)⊣⊢(ψ∧φ)(\varphi \wedge \psi) \dashv\vdash (\psi \wedge \varphi) がある。

古典論理の技法の課からは、次の規則を借りる。いずれも前提の集合 Γ\Gamma を伴う。選言導入（∨\vee導入）：Γ⊢φ\Gamma \vdash \varphi ならば Γ⊢(φ∨ψ)\Gamma \vdash (\varphi \vee \psi) かつ Γ⊢(ψ∨φ)\Gamma \vdash (\psi \vee \varphi)。選言除去（∨\vee除去、選言三段論法）：Γ⊢(φ∨ψ)\Gamma \vdash (\varphi \vee \psi) かつ Γ⊢¬φ\Gamma \vdash \neg\varphi ならば Γ⊢ψ\Gamma \vdash \psi。連言導入（∧\wedge導入）：Γ⊢φ\Gamma \vdash \varphi かつ Γ⊢ψ\Gamma \vdash \psi ならば Γ⊢(φ∧ψ)\Gamma \vdash (\varphi \wedge \psi)。連言除去（∧\wedge除去）：Γ⊢(φ∧ψ)\Gamma \vdash (\varphi \wedge \psi) ならば Γ⊢φ\Gamma \vdash \varphi かつ Γ⊢ψ\Gamma \vdash \psi。排中律：⊢(φ∨¬φ)\vdash (\varphi \vee \neg\varphi)。そして場合分けによる証明（場合分け）の二つの形：Γ∪{φ}⊢χ\Gamma \cup \{\varphi\} \vdash \chi かつ Γ∪{¬φ}⊢χ\Gamma \cup \{\neg\varphi\} \vdash \chi ならば Γ⊢χ\Gamma \vdash \chi。また、Γ∪{φ}⊢χ\Gamma \cup \{\varphi\} \vdash \chi、Γ∪{ψ}⊢χ\Gamma \cup \{\psi\} \vdash \chi かつ Γ⊢(φ∨ψ)\Gamma \vdash (\varphi \vee \psi) ならば Γ⊢χ\Gamma \vdash \chi。演繹では、第一の形は二つの行を挙げて場合分け(i,j)(i, j) と、第二の形は三つの行を挙げて場合分け(i,j,k)(i, j, k) と引用し、順序は言明のとおり、二つの場合、そして最後に選言である。あの課はさらに、すでに証明された規則はどれも文脈 Γ\Gamma の中で成り立つことを注意しており、ここでも二重否定と対偶はそのように用いる。

記号列の名前と同値な論理式

命題論理の言語の課で見たように、↓\downarrow 以外の結合子は、公式で唯一の定義をもつ略記である：¬φ:=(φ↓φ)\neg\varphi := (\varphi \downarrow \varphi)、(φ∨ψ):=¬(φ↓ψ)(\varphi \vee \psi) := \neg(\varphi \downarrow \psi)、(φ∧ψ):=¬(¬φ∨¬ψ)(\varphi \wedge \psi) := \neg(\neg\varphi \vee \neg\psi)、(φ→ψ):=(¬φ∨ψ)(\varphi \rightarrow \psi) := (\neg\varphi \vee \psi)、(φ↔ψ):=((φ→ψ)∧(ψ→φ))(\varphi \leftrightarrow \psi) := ((\varphi \rightarrow \psi) \wedge (\psi \rightarrow \varphi))、(φ⊻ψ):=¬(φ↔ψ)(\varphi \veebar \psi) := \neg(\varphi \leftrightarrow \psi)。定義は論理式について何も主張しない。すでに存在していた記号列に二つ目の名前を与えるだけである。ゆえに、二つの式が同じ記号列を指示するなら、より大きな論理式の内部も含めて、どこでも一方を他方の代わりに置くことができる。書かれるのは同じ白丸と黒丸の並びだからである。たとえば、¬(φ∧ψ)\neg(\varphi \wedge \psi) と ¬¬(¬φ∨¬ψ)\neg\neg(\neg\varphi \vee \neg\psi) は同じ記号列である。後者は、前者の内部に連言の展開を書けば得られる。演繹では、この名前の変更は「定義」で根拠づけ、その後に展開または畳み込む結合子を添える。

ところで、証明可能な同値は恒等式ではない。φ⊣⊢¬¬φ\varphi \dashv\vdash \neg\neg\varphi であるとは、それぞれから他方が導かれるということであって、同じ記号列であるということではない。¬¬φ\neg\neg\varphi は φ\varphi よりずっと長い。したがって、φ⊣⊢φ′\varphi \dashv\vdash \varphi' を知っていても、それだけでは、より大きな論理式の内部で φ′\varphi' を φ\varphi の代わりに書くことは許されない。「両辺を否定する」ことも許されない。φ⊣⊢φ′\varphi \dashv\vdash \varphi' から ¬φ⊣⊢¬φ′\neg\varphi \dashv\vdash \neg\varphi' が従うことは定理、すなわち同値なものの置換であり、その証明は対偶を用いる。自明な操作ではない。体系が論理式の任意の場所で置換を直接許す場合はただ一つしかない。θ\theta を ¬¬θ\neg\neg\theta に置き換える場合とその逆であり、これが二重否定の置換の規則である。そして演繹体系の課は、標識を用いて、この場合でさえ公理とモーダス・ポネンスからは導かれないことを示したので、これを要請しなければならなかった。この注意は衒学ではない。それこそが証明を記号の操作から区別するものであり、記号の操作は、ほかの結合子に、あるいはほかの体系で適用されると、偽な結論に導きかねない。

二つの結果が、何が許されるかを正確に定める。第一は、形式的演繹体系の課の、証明可能な同値の性質に関する命題である。Γ⊢φ\Gamma \vdash \varphi かつ φ⊣⊢φ′\varphi \dashv\vdash \varphi' ならば Γ⊢φ′\Gamma \vdash \varphi' であり、したがって証明可能な同値は行の論理式全体に適用できる。また、証明可能な同値は反射的、対称的、推移的であるので、同値は連鎖させられ（χ⊣⊢φ\chi \dashv\vdash \varphi かつ φ⊣⊢φ′\varphi \dashv\vdash \varphi' ならば χ⊣⊢φ′\chi \dashv\vdash \varphi'）、同じ記号列を指示する二つの式は、反射性によって証明可能な同値である。第二は次の補題で、引用しやすいように、同値なものの置換の選言と連言への拡張をまとめたものである。対称性の課は、この置換を否定、含意、否定論理和について証明し、例題の一つでこの二つの結合子に拡張している。

補題選言と連言における置換

φ⊣⊢φ′\varphi \dashv\vdash \varphi' ならば、任意の論理式 ψ\psi について、(φ∨ψ)⊣⊢(φ′∨ψ)(\varphi \vee \psi) \dashv\vdash (\varphi' \vee \psi)、(ψ∨φ)⊣⊢(ψ∨φ′)(\psi \vee \varphi) \dashv\vdash (\psi \vee \varphi')、(φ∧ψ)⊣⊢(φ′∧ψ)(\varphi \wedge \psi) \dashv\vdash (\varphi' \wedge \psi)、(ψ∧φ)⊣⊢(ψ∧φ′)(\psi \wedge \varphi) \dashv\vdash (\psi \wedge \varphi') である。

証明

  1. (φ∨ψ)=¬(φ↓ψ)(\varphi \vee \psi) = \neg\resaltar{(\varphi \downarrow \psi)}

    選言は、定義により、否定論理和の否定である。

  2. (φ↓ψ)⊣⊢(φ′↓ψ)\dato{int}{(\varphi \downarrow \psi) \dashv\vdash (\varphi' \downarrow \psi)}

    否定論理和についての同値なものの置換が、内側の層の同値を与える。

  3. (φ∨ψ)⊣⊢(φ′∨ψ)\dato{disy}{\resaltar{(\varphi \vee \psi)} \dashv\vdash \resaltar{(\varphi' \vee \psi)}}

    否定についての同値なものの置換がそれを外側の層 ¬(φ↓ψ)⊣⊢¬(φ′↓ψ)\neg(\varphi \downarrow \psi) \dashv\vdash \neg(\varphi' \downarrow \psi) へ運び、これが選言である。同様に、(ψ↓φ)⊣⊢(ψ↓φ′)(\psi \downarrow \varphi) \dashv\vdash (\psi \downarrow \varphi') によって右側の置換が得られる。

  4. (φ∧ψ)=¬(¬φ∨¬ψ),¬φ⊣⊢¬φ′(\varphi \wedge \psi) = \neg(\resaltar{\neg\varphi} \vee \neg\psi), \qquad \neg\varphi \dashv\vdash \neg\varphi'

    連言は否定の選言の否定である。否定についての置換により、まず ¬φ⊣⊢¬φ′\neg\varphi \dashv\vdash \neg\varphi' が得られる。

  5. ¬(¬φ∨¬ψ)⊣⊢¬(¬φ′∨¬ψ),(φ∧ψ)⊣⊢(φ′∧ψ)\neg(\neg\varphi \vee \neg\psi) \dashv\vdash \neg(\neg\varphi' \vee \neg\psi), \qquad \resaltar{(\varphi \wedge \psi)} \dashv\vdash \resaltar{(\varphi' \wedge \psi)}

    選言についてすでに証明した部分を ¬φ\neg\varphi と ¬φ′\neg\varphi' に適用すると (¬φ∨¬ψ)⊣⊢(¬φ′∨¬ψ)(\neg\varphi \vee \neg\psi) \dashv\vdash (\neg\varphi' \vee \neg\psi) が得られ、再び否定についての置換が同値を連言へ運ぶ。右側も同様に論じる。

以下では、「同値置換」は同値なものの置換を、この補題の形も含めて、そのどの形でも表し、層ごとに何度も続けて適用して、任意の深さにある部分論理式に達することができる。行が行 ii から、すでに証明された同値を論理式全体に、あるいは同値置換によってその部分の一つに適用して得られるとき、その行はその同値の名前と行番号で根拠づける：二重否定(i)(i)、「同値置換、ド・モルガン(i)(i)」。名前の変更は、どんな同値も適用せず、同じ記号列を書き直すだけであり、同じように「定義」で根拠づけ、その後に展開または畳み込む結合子を添える：定義 ∧\wedge (i)(i)。形式的演繹体系の課の命題は、行 ii が Γ⊢φ\Gamma \vdash \varphi を主張する場合にも、次々と延長されていく同値 χ⊣⊢φ\chi \dashv\vdash \varphi を主張する場合にも、そうした行が根拠づけられていることを保証する。