自然演繹法（命題論理および述語論理）
1.連言記号の導入
連言導入
∧＋
p, q → p∧q
２つの命題が与えられているとき，その２つの命題から，その２つの命題を連言記号で結合した命題を導くことができる．
[例]
義昭はカレーを食べる．
義昭はコーヒーか紅茶を飲む．
∴義昭はカレーを食べて，コーヒーか紅茶を飲む．
「義昭はカレーを食べる」をp，「義昭はコーヒーを飲む」をq，「義昭は紅茶を飲む」をrとする．
p, q∨r → p∧(q∨r)
1(1) p・・・・・・・・仮定
2(2) q∨r・・・・・・仮定
1,2(3) p∧(q∨r)・・・・(1)(2)∧＋
説明：
まず，前提 p, q∨r を仮定として，最初に記す．(1)(2)(3)等は演繹の順序を示す通し番号である．
前提(1)(2)の命題の右に（・・・）仮定と記す．そして，(1)(2)という前提から，連言導入によって，結論(3)を導く．(1)と(2)という前提に連言導入を適用したしるしとして，(3)の命題の右に（・・・）(1)(2)∧＋と記す．
さらに，下記の要領で，通し番号の左側に，チェック番号を記す．
「仮定」については，通し番号の左に，通し番号と同じ番号を（）をつけずに記す．
「仮定以外」については，通し番号の左に，それが基づいている仮定のチェック番号を記す．チェック番号が複数個になるときは，同一番号は重複させずに，番号順に記す．
[例]について見ると．
(1)(2)については，仮定なので，通し番号と同じ番号を記す．従って，1(1)および，2(2)となっている．
(3)については，仮定ではない（仮定以外）ので，(3)が基づく仮定のチェック番号を記す．(3)が基づく仮定は(1)と(2)である．(1)の前に1が，(2)の前に2が記してあるので，(3)の前には，1と2をあわせて記す．従って，1,2(3)となる．
さて，この演繹の最終行で，1,2(3)となっていることの意味は，(1)(2)という仮定から(3)の命題が導かれているということである．それ故，この推論は妥当である．このように，最終行のチェック番号によって，演繹が成功していること，すなわち，その推論が妥当であることを確認することができる．
2.連言記号の消去
連言消去
∧−
p∧q → p または p∧q → q
ある連言命題が与えられているとき，そこから，その連言記号で結合された２つの命題のいずれか一方を導くことができる．
[例] p∧(q∧r) → (p∧q)∧r
1(1) p∧(q∧r) ・・・・・仮定
1(2) p・・・・・・・・・(1)∧−
1(3) q∧r・・・・・・・・(1)∧−
1(4) q・・・・・・・・・(3)∧−
1(5) r・・・・・・・・・(3)∧−
1(6) p∧q・・・・・・・(2)(4)∧＋
1(7) (p∧q)∧r・・・・・(6)(5)∧＋
3.選言記号の導入
選言導入
∨＋
p → p∨q または p → q∨p
ある命題が与えられているとき，そこから，その命題と他の任意の命題を選言記号で結合した命題を導くことができる．
[例] p → p∨p
1(1) p・・・・・・・仮定
1(2) p∨p・・・・・(1)∨＋
4.選言記号の消去
選言消去
∨−
p → A かつ q → A ならば p∨q → A
ある選言命題が与えられているとする．そのとき，選言記号の左側の命題を仮定とおけば，そこから，命題Aを導くことができ，かつ，選言記号の右側の命題を仮定とおいても，そこから命題Aを導くことができるならば，選言命題から結論Aを導くことができる．
[例] p∨(q∧r) → (p∨q)∧(p∨r)
1(1) p∨(q∧r) ・・・・・・・・仮定
2(2) p・・・・・・・・・・・・[仮定]
2(3) p∨q・・・・・・・・・・(2)∨＋
2(4) p∨r・・・・・・・・・・(2)∨＋
2(5) (p∨q)∧(p∨r)・・・・・(3)(4)∧＋
6(6) q∧r・・・・・・・・・・[仮定]
6(7) q・・・・・・・・・・・・(6)∧−
6(8) r・・・・・・・・・・・・(6)∧−
6(9) p∨q・・・・・・・・・・(7)∨＋
6(10) p∨r・・・・・・・・・・(8)∨＋
6(11) (p∨q)∧(p∨r)・・・・・(9)(10)∧＋
1(12) (p∨q)∧(p∨r)・・・・・(1)(2)(5)(6)(11)∨−
5.条件法記号の消去
条件法消去
⊃−
p⊃q, p → q
ある条件命題とその前件命題が与えられているとする．そのとき，その２つの命題から，その条件命題の後件の命題を導くことができる．
[例] p⊃(q⊃r), p, q → r
1(1) p⊃(q⊃r)・・・・・仮定
2(2) p・・・・・・・・・仮定
3(3) q・・・・・・・・・仮定
1,2(4) q⊃r・・・・・・(1)(2)⊃−
1,2,3(5) r・・・・・・・(3)(4)⊃−
6.条件法記号の導入
条件法導入
⊃＋
A, p → q ならば A → p⊃q
ある前提からある結論が導けるとする．そのとき，その前提を前件とし，その結論を後件とする条件命題を導くことができる．
[例] p⊃q → (p∧r)⊃(q∧r)
1(1) p⊃q・・・・・・・・仮定
2(2) p∧r・・・・・・・・[仮定]
2(3) p・・・・・・・・・(2)∧−
2(4) r・・・・・・・・・(2)∧−
1,2(5) q・・・・・・・・(1)(3)⊃−
1,2(6) q∧r・・・・・・・(5)(4)∧＋
1(7) (p∧r)⊃(q∧r)・・・(2)(6)⊃＋
7.否定記号の導入
否定導入
〜＋
A, p → q∧〜q ならば A → 〜p
ある命題から矛盾が導かれるとすれば，その命題の否定が成り立つ．
[例] p⊃q, p⊃〜q → 〜p
1(1) p⊃q・・・・・・・仮定
2(2) p⊃〜q・・・・・・仮定
3(3) p・・・・・・・・[仮定]
1,3(4) q・・・・・・・・(3)(1)⊃−
2,3(5) 〜q・・・・・・・(3)(2)⊃−
1,2,3(6) q∧〜q・・・・(4)(5)∧＋
1,2(7) 〜p・・・・・・・(3)(6)〜＋
8.否定記号の消去
否定消去
〜〜−
〜〜p → p
ある命題 p の否定の否定から，命題 p を導くことができる．
[例] p⊃〜〜q, p → q
1(1) p⊃〜〜q・・・・・・仮定
2(2) p・・・・・・・・・仮定
1,2(3) 〜〜q・・・・・・・(2)(1)⊃−
1,2(4) q・・・・・・・・・(3)〜〜−
9.双条件記号の導入
双条件導入
≡＋
(p⊃q)∧(q⊃p) → p≡q
(p⊃q)∧(q⊃p) というかたちの命題から， p≡qというかたちの命題を導くことができる．
[例] p⊃q, 〜p⊃〜q → p≡q
1(1) p⊃q・・・・・・・・・仮定
2(2) 〜p⊃〜q・・・・・・・仮定
3(3) q・・・・・・・・・・[仮定]
4(4) 〜p・・・・・・・・・[仮定]
2,4(5) 〜q・・・・・・・・・(4)(2)⊃−
2,3,4(6) q∧〜q・・・・・・(3)(5)∧＋
2,3(7) 〜〜p・・・・・・・・(4)(6)〜＋
2,3(8) p・・・・・・・・・・(7)〜〜−
2(9) q⊃p・・・・・・・・・(3)(8)⊃＋
1,2(10) (p⊃q)∧(q⊃p)・・・(1)(9)∧＋
1,2(11) p≡q・・・・・・・・(10)≡＋
10.双条件記号の消去
双条件消去
≡−
p≡q → (p⊃q)∧(q⊃p)
p≡q というかたちの命題から， (p⊃q)∧(q⊃p)というかたちの命題を導くことができる．
自然演繹法（述語論理に特有なルール）
11.全称記号の消去
全称消去
∀−
(a)∀xFx → Fu (uは任意の個体)
(b)∀xFx → Fa (aは特定の個体)
すべての個体についてFが当てはまるならば，その命題は任意の個体あるいは特定の個体についても当てはまる．
(a)の例 ∀x(Fx⊃Gx) → Fu⊃Gu
(b)の例 ∀x(Fx⊃Gx) → Fa⊃Ga
[例]
すべての人間は動物である．
太郎は人間である．
∴太郎は動物である．
∀x(Fx⊃Gx) → Fa⊃Ga
1(1) ∀x(Fx⊃Gx) ・・・・・仮定
2(2) Fa・・・・・・・・・・仮定
1(3) Fa⊃Ga・・・・・・・・(1)∀−
1,2(4) Ga・・・・・・・・(2)(3)⊃−
問題11 次の推論を記号化し，自然演繹法で導出しなさい．
新入生はすべてラテン語と論理学を受講する．
宏隆は論理学を受講していない．
∴宏隆は新入生ではない．
12.全称記号の導入
全称導入
∀＋
A → Fu ならば，A → ∀xFx (uは任意の個体)
(Aは任意の命題(の列)で，uを含まない)
任意の個体uについてFが当てはまるという命題Fuが命題(の列)Aから導出できるならば，命題(の列)Aから，すべての個体についてFが当てはまるという命題∀xFxを導出してよい．ここで，Aはuを含まないという条件を変項条件という．
[例]
すべての物体は消滅する．
すべてのものは物体である．
∴すべてのものは消滅する．
∀x(Fx⊃Gx), ∀xFx → ∀xGx
1(1) ∀x(Fx⊃Gx)・・・・・仮定
2(2) ∀xFx ・・・・・・・・仮定
1(3) Fu⊃Gu・・・・・・・(1)∀−
2(4) Fu・・・・・・・・・(2)∀−
1,2(5) Gu・・・・・・・・・(3)(4)⊃−
1,2(6) ∀xGx・・・・・・・・(5)∀＋
問題12 次の推論を記号化し，自然演繹法で導出しなさい．
すべての人間はかぜをひく．
すべての教師は人間である．
∴すべての教師はかぜをひく．
13.存在記号の導入
存在導入
∃＋
(a)Fu → ∃xFx (uは任意の個体)
(b)Fa → ∃xFx (aは特定の個体)
任意の個体についてFが当てはまるなら，あるいは特定の個体についてFが当てはまるならば，少なくともひとつの個体についてFが当てはまる．
[例]
浩孝は黒豚の角煮を食べた．
∴黒豚の角煮を食べた者がいる．
Fa → ∃xFx
1(1) Fa・・・・・仮定
1(2) ∃xFx・・・(1)∃＋
問題13 次の推論を記号化し，自然演繹法で導出しなさい．
すべてのものはエイドスをもつ．
∴エイドスをもつものがある．
14.存在記号の消去
存在消去
∃−
A, Fu → C ならば，A, ∃xFx
(変項条件：A, Cはuを含まない．uは任意の個体)
[例 1] ∀x(Fx⊃Gx), ∃xFx → ∃xGx
1 (1) ∀x(Fx⊃Gx) ・・・・・仮定
2 (2) ∃xFx・・・・・・・・・仮定
3 (3) Fu ・・・・・・・・・・[仮定]
1 (4) Fu⊃Gu・・・・・・・・(1)∀−
1,3 (5) Gu・・・・・・・・・・(3)(4)⊃−
1,3 (6) ∃xGx・・・・・・・・・(5)∃＋
1,2 (7) ∃xGx・・・・・・・・・(2)(3)(6)∃−
この例では，仮定(1)と任意の仮定(3)から結論(6)が導かれている．従って，∃−を適用して，(1)と(2)から(7)を導いてもよい（この場合は，仮定(3)は不要である）．また，変項条件も守られている（つまり，uは(1)(2)にも(6)にも現れていない）．
[例 2]
すべてのクルマは国産品である．
高級なクルマがある．
∴高級な国産品がある．
「・・・はクルマである」をF，「・・・は国産品である」をG，「・・・は高級である」をHとする．
∀x(Fx⊃Gx), ∃x(Fx∧Hx) → ∃x(Hx∧Gx)
1(1) ∀x(Fx⊃Gx)・・・・・・・・仮定
2(2) ∃x(Fx∧Hx)・・・・・・・・仮定
1(3) Fu⊃Gu・・・・・・・・・・(1)∀−
3(4) Fu∧Hu・・・・・・・・・・[仮定]
3(5) Fu・・・・・・・・・・・・(4)∧−
3(6) Hu・・・・・・・・・・・・(4)∧−
1,3(7) Gu・・・・・・・・・・・・(3)(5)⊃−
1,3(8) Hu∧Gu・・・・・・・・・・(6)(7)∧＋
1,3(9) ∃x(Hx∧Gx)・・・・・・・・(8)∃＋
1,2(10) ∃x(Hx∧Gx)・・・・・・・(2)(4)(9)∃−
問題14 次の推論を記号化し，自然演繹法で導出しなさい．
黒い豚がいる．
∴黒いものがある．