全称導入の練習問題

やりながら全称導入の理解を深めます。

全称導入

∀x∀yP(x, y) ⊢ ∀y∀xP(x, y)

1.∀x∀yP(x, y)(前提)
2.∀yP(x,y)(∀除去)
3.P(x,y)(∀除去)
4.∀xP(y)(∀導入)
5.P(y,x)(∀導入)
6.P(x,y)→P(y,x)(→導入)

全称除去、導入の定義通りに変更しただけです。

∀x(P(x) → Q(x)) , ∀x(Q(x) → R(x)) ⊢ ∀x(P(x) → R(x))

1.∀x(P(x) → Q(x)) , ∀x(Q(x) → R(x))(前提)
2.P(x)→Q(x),Q(x)→R(x)(∀除去)
3.P(x)(仮定)
4.Q(x)(→除去)
5.R(x)(→除去)
6.P(x)→R(x)(→導入)
7.∀x(P(x)→R(x))(∀導入)

∀x(P(x) → Q(x)) , ∀x(Q(x) → R(x))
に同じ代数用意して三段論法を適用しています。

∀x((P(x) ∧ Q(x)) → R(x)) ⊢ ∀x(P(x) → (Q(x) → R(x))

1.∀x((P(x) ∧ Q(x)) → R(x))(前提)
2.P(x)∧Q(x)→R(x)(∀除去)
3.P(x) → (Q(x) → R(x)(同地変形)
4.∀x(P(x) → (Q(x) → R(x))(∀導入)

3行目の同地変形の演繹はリンクから。

(A∧B)→C⇔A→(B→C)の証明

これまでに証明した命題論理の定理を用いた証明を行います。 (A∧B)→C⇔A→(B→C) 証明 1.(仮定)2.¬(A∧B)∨C(→言い換え)3.¬A∨¬B∨C(ド・モルガンの法則)4.¬A∨(¬B∨C)(結合法則)5.A→(¬B∨C)(→...

riku-nagahama.xyz

2023.07.19

∀x(P(x) → Q(x)) , ∀x(Q(x) → R(x)) ⊢ ∀x((P(x) ∨ Q(x)) → R(x))

1.∀x(P(x) → Q(x)) , ∀x(Q(x) → R(x))(前提)
2.P(x)→Q(x),Q(x)→R(x)(∀除去)
3.P(x)(仮定)
4.Q(x)(→除去)
5.R(x)(→除去)
6.P(x)→R(x)(→導入)
7.P(x)∨Q(x)(仮定)
8.R(x)(∨除去)
9.P(x)∨Q(x)→R(x)(→導入)
10∀x((P(x) ∨ Q(x)) → R(x))(∀導入)
11.∀x(P(x) → Q(x)) , ∀x(Q(x) → R(x)) ⊢ ∀x((P(x) ∨ Q(x)) → R(x))