股関節おじさんの勉強部屋 全称除去の定義と練習問題
述語論理における全称記号∀を取り除く推論規則を見ていきます。 別名を普遍例化と呼ぶようです。 全称除去(普遍例化) 定義 例:「全ての犬は動物である。ポチは犬である。従って、ポチは動物である」ある項 a について公理スキーマとして記号的に表...
股関節おじさんの勉強部屋
股関節おじさんの勉強部屋 
股関節おじさんの勉強部屋 全称導入の練習問題
やりながら全称導入の理解を深めます。 全称導入 ∀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)(∀導入...
股関節おじさんの勉強部屋 全称導入と仮定の解消
∀導入定義の人の認識を結びつけるために藻掻きます。 全称導入と仮定の解消 定義 これが全称導入の定義 A(c)⊢∀x∈X:A(x)WIIS A(c)の論理式を満たすようなcは集合Xの任意の要素xに対しても成立する。cは全てのXの要素を表現す...
股関節おじさんの勉強部屋 含意の結合法則
結合法則は(A∨B)∨C⇔A∨(B∨C)のようなかっこの位置を入れ替えても意味が変わらない法則。含意にも成り立つのか確かめてみます。 含意の結合法則 証明 1.(A→B)→C(仮定)2.¬(¬A∨B)∨C(同値変形)3.A∧¬B∨C(ド・モ...
股関節おじさんの勉強部屋 ∀除去練習問題
∀除去の理解が曖昧なので練習問題やります。やってれば何か掴んでくるだろうってことで。 全称除去 練習問題 その1 P(d) , ∀x(P(x) → (P(x) → Q(x))) ⊢ Q(d) 1.∀x(P(x)→(P(x)→Q(x))),P...
股関節おじさんの勉強部屋 全称導入
所謂一般化ってやつじゃないなと。全称記号∀除去は別名「普遍汎化」とも呼ぶようです。 普遍汎化 定義 もし$\displaystyle \vdash P(x)$が導出されていれば、$\displaystyle \vdash \forall x...
股関節おじさんの勉強部屋 自然数の0×x=0の証明
x×0=0は定義通り。 0×x=0 証明 数学的帰納法を用います。 x=0の場合は定義通り。1.0×02.0…(1) x=1の場合1.0×1(仮定)2.(0×0)+0(定義)3.0+0(1)より4.0…(2) x=2の場合1.0+2(仮定)...
股関節おじさんの勉強部屋 自然数の0+x=xの証明
x+0=xは定義されていますが、逆バージョン0+x=xは証明定義されていませんのて証明していきます。 0+x=x 証明 1.0+0(仮定)1.0(加法定義)3.0+0⇔0…14.0+1(仮定)5.S(0+0)(加法定義)6.S(0)(1より...
股関節おじさんの勉強部屋 1×0=0と1×1=1の証明
自然数の乗法 定義 自然数の加法は再帰的に、以下のように定義できる。すべての自然数 a に対して、a + 0 = aすべての自然数 a, b に対して、a + suc(b) = suc(a + b)1 := suc(0) と定義するならば、...
股関節おじさんの勉強部屋 1+1=1×2の証明
自然数の加法と乗法 定義 自然数の加法は再帰的に、以下のように定義できる。1.すべての自然数 a に対して、a + 0 = a2.すべての自然数 a, b に対して、a + suc(b) = suc(a + b)1 := suc(0) と定...
股関節おじさんの勉強部屋 偶数と奇数の述語論理の表現
なんとなくで述語論理の論理式を作ってみます。偶数と奇数を述語論理で表現してみます。我流なので悪しからず。 述語論理の練習 偶数 ∀k∈Ν∃x∈Ν(2k=x)任意の自然数kに対するある自然数xが存在する、それは2k=xを満たすような関係である...
股関節おじさんの勉強部屋 含意から三段論法を演繹
三段論法と仮定 証明 下のような論理式「AならばBかつBならばC、ならばAならばCである」(A→B∧B→C)→(A→C)「AならばBかつBならばCかつCであるならば、AならばCである」(A→B∧B→C)∧A→C 大枠の含意(A→B∧B→C)...