Tragic Logic

基礎知識のような何か

論理記号

∧とか∨とか⊃とかそれぞれ「かつ」「または」「ならば」を意味する.
他にも, ¬(否定)とか∀(任意の)とか∃(存在する)とか使うかも.
結合は, ∀, ∃, ¬が強く, 右結合, ∧が次に強く, 左結合, ∨がその次に強く, 左結合, ⊃は最も弱く, 右結合.

真理値

命題には真と偽しかなくて,

• A∧BはA,Bともに真のときのみ真, それ以外は偽.
• A∨BはA,Bともに偽のときのみ偽, それ以外は真.
• A⊃BはAが真でBが偽のときのみ偽, それ以外は真.
• ¬AはAが真のときは偽, Aが偽のときは真.

まあこんな感じ.

数学的帰納法

なんか自然数nに関する命題があって, 以下の二つが成り立てば任意のnで成り立つよ〜ってな考えかた.

• n=1(自然数が0のときはn=0)のとき成り立つ
• n=kのとき成り立つならばn=k+1のときも成り立つ.

構造的帰納法

めんどいから省略(使うんかなあ, これ)

∀と∃

∀x.P(x) みたいに書く. 意味は「任意のxについてP(x) (が成り立つ)」 ∃x.P(x) みたいに書く. 意味は「P(x)が成り立つようなxが存在する.」 「存在する」の意味は微妙だけど, まあ数学的に存在するなら存在するという ことにしようかと. つまりもちろん自然数は自然数個「存在する」んだけど, 実数もちゃんと実数個「存在する」みたいな.

Let's tragic logic

畑さんの論理

すべての人は畑さんである.

証明:
いきなり, すべての人が畑さんであることを証明するのは難しい. そこで補題として, 『「すべての人は畑さんである」または「畑さんはこの世に一人もいない」』 を証明する.

補題の証明:
この世に何人の人間がいるかわからないが, その人数が自然数であることは自明である. そこで, 任意のnに対してn人の人間の集団が命題を満たすことを示せば十分である. これを数学的帰納法を用いて示す.

• n=1で成り立つこと(帰納法の基底)
  一人だけなのだから, 当然その人は畑さんであるか畑さんでないかなので, これは成り立つ
• n=kのとき成り立つことからn=k+1のとき成り立つことが言えること(帰納法ステップ)
  k+1人の集団から一人(Aとしよう)取り除くと, 集団はk人であるから, 帰納法の仮定により「全員畑さんである」か「畑さんは一人もいない」 かのどちらかである.
  一方, 今取り除いたのと別の人(Bとしよう)を取り覗いたk人の集団を考える. このときもやはり帰納法の仮定から「全員畑さんである」か 「畑さんは一人もいない」かのどちらかである.
  つまり, 上記二通りのいずれでも取り除かれなかった人の集団は 「全員畑さんである」か「畑さんは一人もいない」かのどちらかであり, これが「全員畑さんである」場合, 最初の例からBが畑さんであることがわかり, 二番目の例からAが畑さんであることがわかる. これが「畑さんは一人もいない集団」である場合, 最初の例からBが畑さんでない ことがわかり, 二番目の例からAが畑さんでないことがわかる. したがってn=k+1のときも成り立つことが言えた.

本命題の証明:
この世に少なくとも一人畑さんがいることは自明である. (少なくとも私は畑さんと呼ばれる人を知っている) したがって, 補題により, すべての人は畑さんである //証明終了

ポケットをたたけば

100円のお茶と100円のコーヒーが売られており, 手元に丁度100円あるとする. このとき, お茶とコーヒーの両方を買うことができる

証明:
「お茶とコーヒーの両方を買うことができる」とは, 命題の構造を厳密に見ると「お茶を買うことができ, かつコーヒーを買うことができる」ということである.
100円持っているのだから, 「お茶を買うことができる」
また, 100円持っているのだから, 「コーヒーを買うことができる」
「お茶を買うことができる」と「コーヒーを買うことができる」が共に真なのだから, 「お茶を買うことができる」∧「コーヒーを買うことができる」も真.
したがって「お茶を買うことができ, かつコーヒーを買うことができる」
ゆえに100円あればお茶とコーヒーの両方を買うことができる. //証明終了

どちらが勝つ？

以下の条件を満たすゲームは先手必勝法が存在するか 後手必勝法が存在するかのいずれかである.

• プレイヤーは先手と後手の二人である.
• 先手後手先手後手…と交互にn回ずつ手を選択し, 終了する.
• 集合Sがあり, 各一手はSの元の一つである.
• プレイヤーは手の選択のときその時点までの手選択の情報を知ることができる.
• 2n引数関数fがあり, fに全ての手選択を渡すと「先手の勝ち」か「後手の勝ち」 を返す. ゲーム終了時, fにより勝敗が決定する.
• 上記のn,S,f, や, 各ルールはプレイヤーに公開されている.

証明:
「先手必勝法が存在する」とはどういうことか, 式に書いてみよう. これは,
「∃x1.∀y1. … ∃xn.∀yn.(f(x1,y1,…,xn,yn)=先手の勝ち)」
と書き表すことができる.
「先手必勝法が存在しないならば後手必勝法が存在する」を示せば 本命題を示したことになるので, この式を否定した式から, 後手必勝法の存在 が導ければ十分である.
「先手必勝法が存在しない」とは,
「¬∃x1.∀y1. … ∃xn.∀yn.(f(x1,y1,…,xn,yn)=先手の勝ち)」ということである
この式を変形すると,

= ∀x1.¬∀y1. … ∃xn.∀yn.(f(x1,y1,…,xn,yn)=先手の勝ち)
= ∀x1.∃y1.¬∃x2.… ∃xn.∀yn.(f(x1,y1,…,xn,yn)=先手の勝ち)
…
= ∀x1.∃y1.… ∀xn.∃yn.¬(f(x1,y1,…,xn,yn)=先手の勝ち)

となる. 条件(ゲームのルール)により, ¬(f(x1,y1,…,xn,yn)=先手の勝ち)は f(x1,y1,…,xn,yn)=後手の勝ち を意味する.
したがって, ∀x1.∃y1.… ∀xn.∃yn.(f(x1,y1,…,xn,yn)=後手の勝ち)が成り立つ.
この式は後手必勝法の存在を意味する. //証明終了

どちらも必勝？

上の条件を満たすゲームについて,
先手必勝法が存在し, かつプレイすると必ず後手が勝つようなゲーム が存在する.

証明:
集合Sとして, 実数全体の集合, nとして1をとる. f(x,y)として, 「xが選択不能ならば先手の勝ち, xが選択可能ならば後手の勝ち」 というゲームを考えればよい. //証明終了

大里くんはどこにいる？

以下の補題を示す.

• 1. 大里くんが京都にいるなら関西にいる
• 2. 大里くんが東京にいるなら関東にいる
• 3. (A⊃B)∧(C⊃D)⊃(A⊃D)∨(C⊃B)

補題1：自明.

補題2：自明.

補題3の証明:
(A⊃B)∧(C⊃D)が偽の時は全体が真である. したがって(A⊃B)∧(C⊃D)が真のときのみ考える.
BもしくはDが真の時は全体が真である. したがってB,Dが共に偽のときのみ考える.
このとき, A, Cは共に偽である. ゆえに全体は真である. //証明終了

本命題の証明:
補題3の命題において, Aとして「大里くんは京都にいる」, Bとして「大里くんは関西にいる」, Cとして「大里くんは東京にいる」, Dとして「大里くんは関東にいる」とする. 補題1,2より, 「大里くんが京都にいるなら関西にいる」かつ「大里くんが東京にいるなら関東にいる」が成り立つ. したがって, 「大里くんが京都にいるなら関東にいる」または「大里くんが東京にいるなら関西にいる」が成り立つ. //証明終了

サンタは存在する. その1

サンタが存在するとすれば, サンタは存在する.

サンタが存在しないとすれば, (※) は正しくない. したがって「(※)が正しいならばサンタは存在する」は正しい. これは (※) そのものであるから, (※) は正しい. これは矛盾であるから, サンタは存在する. //証明終了

サンタは存在する. その2

※ コメント：せっかくだから気前よくサンタが 1万人いることを示しちゃいましょう.

A が真のとき, 全体は明らかに真であるから, A が偽のときのみ考えれば良い. A が偽のとき, A⊃B は B によらずに真であるから, (A⊃B)⊃A は偽. よって全体は真.

A として, 「サンタは1万人いる」, B として, 「サンタは(存在するとしても)高々一人である」, とする.

A⊃B は明らかに偽なので, (A⊃B)⊃A は真である. 補題により, ((A⊃B)⊃A)⊃A であるから, A は真である. よって サンタは1万人存在する. //証明終了