完全性の定理
本文では厳密な区別をしていないが、論理学（というか、記号学）には、
意味論（semantics）と構文論（syntax）という二つの重要な区別がある。
意味論的とは、その記号が何を意味するか、に関わる視点であり、
構文論的とは、その記号がどのように並んでいるか、に注目する視点である。
下の公理系を見てみると、
ルカシェヴィツの公理系L
原始記号 ¬, ⊃
論理式 Aが式ならば、¬A, A⊃B は式
公理１ A⊃（B⊃A）
公理２ （A⊃（B⊃C））⊃（（A⊃B）⊃（A⊃C））
公理３ （¬A⊃¬B）⊃（B⊃A）
（公理４ ∀ｘ（A⊃Fｘ）⊃（A⊃Fｘ））
推論規則１ A, A⊃B → B （MP）
（推論規則２ Fx → ∀xFx ）
ここには、ただ記号の配列の規則が書かれているだけである。
そこで使われている記号の「意味」に関しては、何も述べられていない。
「Ａ」や「¬」や「⊃」がどういう「意味」なのか、どうでもよいし、
それが「真」であるとか、「偽」であるとか、「トートロジー（恒真式）」であるとか、どうでもよい。
公理系による証明も、次のように定義される。
「証明」とは、有限な式の列を言う。その式の列の各行は、
a) 公理であるか、
b) それ以前の式に推理規則を適用した式であるか、
のどちらかである。
この式の列の最後の式を定理といい、この式の列をその定理の証明という。
公理系とは形式化された記号の配列の規則にすぎず、「意味」は問われない。
（記号の意味を定めることを、「解釈する」とか「モデルを作る」という。
命題論理の最も標準的な解釈（principal interpretation）が、本文に示した<V>＝付値関数によるものである。）
したがって、この公理系によって証明される定理はすべて「真」なる命題なのか、また逆に、
すべての「真」なる命題はこの公理系で証明できるのか、ということを、メタ・レベルで証明する必要がある。
（公理系の公理や定理が持つ性質に関する定理だから、メタ・レベルの定理であり、メタ論理学の定理であることになる。）
それが完全性の定理である。
式Aが定理である（公理系で証明できる）ことを、→Ａ、恒真式（妥当式）であることを、⇒Ａと書くと、
→Ａ ならば ⇒A であることを、健全性（soundness）
⇒Ａ ならば →A であることを、狭い意味での完全性（completeness）
といい、両者をあわせて、広い意味での「完全性」という。
命題論理の完全性
ルカシェヴィッツの公理系Ｌの完全性を証明する。
健全性に関しては、例題８の解答で書いた証明で十分であろう（再録）。
（ルカシェヴィッツ「二値命題計算の完全性の証明」による）。
無矛盾性の証明は、そう難しくない。
まず、補助定理「公理系で証明できない命題が存在すれば、その公理系は無矛盾である」を証明する。
無矛盾性の説明のところで書いている要領でやれば、「公理系に矛盾があるなら、その公理系では全ての命題が定理となる」というメタ定理は簡単に証明できるから、その対偶をとればよい（補助定理の証明終り）。
次に、その公理系では証明できない命題が存在することを証明する。
そのためには、命題の持つ性質の中で、次のような性質Eを見つけてやればよい。
１）要素命題pはこの性質Eを持たない。
２）公理はすべてこの性質Eを持つ。
３）性質Eは遺伝する、つまり、性質Eを持つ命題に推論規則を適用して得られた命題もその性質Eを持つ。
これには、「トートロジーである」という性質を利用すればよい。
つまり、任意の要素命題 p は、１と０という二つのどちらの値も取りうるとし、その上で、上の真理関数と同じように値を割り振る付値関数（ルカシェーヴィッツの公理系Lを使うと、v(¬A)=0なのは、A=1のとき、その時に限る。v(A⊃B)=0なのは、A=1かつB=0のとき、その時に限る。）を導入すると、
１）要素命題には、「常に１の値をとる」という性質は属さない。
２）公理にはすべて、「常に１の値をとる」という性質が属していることがわかる。
３）AとA⊃Bがともに１の値を取るならば、上の付値関数の定義によって、Bは常に１の値を取る。
したがって、要素命題pはこの公理系では証明できない。
よって補助定理により、この公理系は無矛盾。（証明終り）
完全性の定理の前半（健全性）の証明も難しくない。上の無矛盾性の証明が既に健全性の証明になっている。（証明終り）
完全性に関しては、命題論理に限ってならば、カルマールによる証明が最も簡単（と言うか、最も短い証明）である。
補助定理
命題論理の式Aを構成する要素命題を p1, …, pn とし、関数δを次のように定義する。
これらの命題に１または０の値を割り振ったとき、δp
は、
ｖ(p)=1 なら δp = p
ｖ(p)=0 なら δp = ¬p
となる。
このとき、
δp1, …, δpn →δA
補助定理の証明
数学的帰納法で証明する。
１）式Aが一つの要素命題から成るときには、
ｖ（p）＝１のとき、p→p
ｖ（p）＝０のとき、¬p→¬p
であるから、
Lの定理 →A⊃A に演繹定理を適用すれば A→A
だから、
δp1→δA
２）これ以外の場合は、式Aは、¬Bという形か、B⊃Cという形をしているはずである。
BやCについては上の補助定理は証明されていると仮定する。
２-１）式Aが¬Bの場合
（１）Aの値が１であるとき、Bの値は０であるから、
δp1, …, δpn →¬B （＝A＝δA）
（２）Aの値が０であるとき、Bの値は１であるから、
δp1, …, δpn →B （＝¬A＝δA）
すなわち
δp1, …, δpn →δA
２-２）式AがB⊃Cの場合
（１）Aの値が１であるとき、Bの値が０ またはCの値が１である。
Bの値が０であれば、仮定により、
δp1, …, δpn →¬B
添加法則（Lの公理１ A⊃（B⊃A））により
δp1, …, δpn →¬C⊃¬B
対偶法則（Lの公理３ （¬A⊃¬B）⊃（B⊃A））により
δp1, …, δpn →B⊃C （＝δA）
Cの値が１であれば、仮定により、
δp1, …, δpn →C
添加法則により
δp1, …, δpn →B⊃C （＝δA）
ゆえに
δp1, …, δpn →δA
（２）Aの値が０であるとき、Bの値が１かつ
Cの値が０である。
仮定により
δp1, …, δpn →B
δp1, …, δpn →¬C
上の二式から
δp1, …, δpn →B∧¬C
ド・モルガンの法則A∧¬B≡¬（¬A∨B）と定義A⊃B≡¬A∨Bによって、
δp1, …, δpn →¬（B⊃C） （＝δA）
ゆえに
δp1, …, δpn →δA
完全性の定理の証明
式Aが恒真式であるとする。すると、式Aの中の要素命題p1, …, pn にいかなる値を割り当てても、Aの値は１（ゆえにδA＝A）である。
p1, …, pn に１と０の値を割り当てる仕方は、全部で2のn乗通りあるが、それらを全て辞書的な順序で書いて、補助定理を適用すると、
p1, …, pn →A
p1, …, ¬pn →A
…
¬p1, …, ¬pn →A
となる。
最初の二つ式に演繹定理を適用すると、
p1, …, pn-1 →pn⊃A
p1, …, pn-1 →¬pn⊃A
これらに両刀論法（A⊃B）∧（¬A⊃B）⊃B を適用すると、
p1, …, pn-1 →A
が得られる。
以下同じ要領で、左辺の仮定を順に消去してゆけば、
→A
が得られる。
すなわち、Aが恒真式ならば、Aは定理である。
述語論理の完全性
ヘンキンの定理
（述語論理は授業で詳しく扱う気がしないので、この項目もあまり書く気がしないが、気長に待ってみてほしい。）