john7rv

述語論理には「全ての」や「〜がある」を表せる量化子記号がある

∀xA(x)

全てのxについてAである

∃xA(x)

Aであるxが存在する

全称量化子と存在量化子では変項は束縛される

∀x(A(x)B(y))

ではxは束縛変項でありyは自由変項である

束縛変数のスコープは

量化子の直後の式か直後のカッコの範囲

までである
∀x(A(x)B(y))
であれば
束縛の範囲(スコープ)は(A(x)B(y))までである
∀xAx⇒By
であればスコープは
Ax
までである
しかし
∀x(Ax⇒By)
であればスコープはカッコの中である
(Ax⇒By)
となる

束縛変数の意味を知るにはまず開式と閉式を知らなければならない

A(x) ⇒ B(x)
という式があっても、この変数xがなんであるのか定まっていなければ
証明として意味をなさない
なぜならこのままでは変数xにはなんでも代入できてしまうからだ
これを開式という
これを閉じるにはxに具体的な何かを定めないといけない　
x = 偶数　
のように定めればこの式は閉じていることになり閉式という
これで証明として意味をなすようになる
しかし述語論理においては
変数に具体的なものを定めなくても
量化子で束縛した変数だけがある式も閉式と見なすことができる

その式に自由変数が存在しなければ閉式となる

全称量化子と存在量化子は否定に対して裏表のような関係がある
それが全てではないということは、否定されたものがどこかに存在することであり
あるものが存在しないことは、それが否定されたものが全てであるということである
これは文章の意味を良く理解すればそのとおりであることがわかる
そのためそれぞれの否定形を置き換えることができる

not∀x P(x)   は    ∃x not P(x)

これの意味は
「全てがPであるわけではない」　は　「Pでないものが存在する」　と同じである
同値なのでお互いに置き換えられる

not∃x P(x)   は   ∀x not P(x)

「Pであるものは存在しない」　　は　　「全てはPではない」　と同じである
同値なので相互に置き換えられます

全称も存在も前後を入れ替えることができます

∀a(∀b(P(a,b)))  は   ∀b(∀a(P(a,b)))

aとbを入れ替えても同値である

∃a(∃b(P(a,b)))  は   ∃b(∃a(P(a,b)))

aとbを入れ替えても同値