述語論理と
∀（全称）∃（存在）
３回の講義の概観： 命題論理 （真理値） 命題論理 （公理と推論規則） １ 1 述語論理 （モデルと解釈） 述語論理 （公理と推論規則） ２ ３ 意味論 semantics syntax 構文論述語論理は命題論理よりも複雑
例題： 次の文は真か偽か？ （曖昧な文です） 「すべての自然数 x に対して x ＜ y を満たすよう な自然数 y が存在する」 （小野先生の例題） 1 解釈（その ） preview 1. 解釈（その一） すべての x に対して「x ＜ y を満たすような y が存在する」：∀x ∃y （x ＜ y） 2. 解釈（その二） 「すべての x に対して x ＜ y を満たす」ような y が存在する ：∃y ∀x （x ＜ y） 2 曖昧述語と対象変数
• 命題とは真理値（真偽）が確定している文のこと 真偽のいずれかの値{ t, f } をとる：命題変数 • 対象変数を含む文の真理値は確定しない 例： ｘ≦ 200 yは素数である 復習 このような文を扱うために命題関数P を考えるP :
D
T
, ここに T = { t, f } 例： 対象領域 D として自然数の集合を考えるP :
D×D
T,
2変数（引数）の述語 • 対象変数 individual variable, object variable • 命題関数 propositional function 3述語 predicate
• 述語: 命題関数の具体的な表現 例: Le, Prime Le (x, 200) : （x ≦200）, ２変数（引数） Prime(y) ： 「yは素数である」 • 対象領域 D の要素を対象 object, individual という 対象領域 D の上を動く変数を対象変数 D の定数を 述語記号 対象領域 D の上を動く変数を対象変数、D の定数を 対象定数 object (individual) constant という • 全称記号∀, と存在記号∃ ∀x P(x): すべての x∈D に対して P(x) が真になる ∃y Q(y): ある y ∈D が存在して Q(y) が真になる ↑ 正確な記法を次に述べる。∀と∃が多重になるときに注意 4 述語論理の項 term
• 今までに登場したもの： 対象変数、対象定数 • さらに必要なもの： 対象領域の上の関数記号 関数記号の例： 自然数の上の ＋, × 項term の定義： 項term の定義： 1. 個々の対象定数、対象変数は項である 2. f が n 変数（引数）の関数記号で, t1, t2, …, tn が 項であるならば f (t1, t2,…, tn) は項である 項の例： 200, x, y, (3＋x), 6×(x＋y). ＋(3,x), ×(6, ＋(x, y)) とも書く論理式 formula, wff
述語記号： 述語を表す記号 1. P が n 変数（引数）の述語記号で t1, t2, …, tn が 項ならば 、P(t1, t2, …, tn) は論理式である 2. A, B が論理式ならば、A∧B, A∨B, A⇒B, ￢Aは、 いずれも論理式である 3. A が論理式で x が対象変数ならば 、 (∀x A), (∃x A)は論理式である 注：「1」の形の論理式を原子(atomic)論理式 という 例： ∀x（∀y（∃q（∃r（x=q×y+r））））, = は述語記号 復習：⇔は省略してよい∀, ∃ quantifier
限定記号, 量化記号, 限量子 「すべての x に対して R（x, y） を満たす y が存在 する」 という文は曖昧である 前出 1. ∀x ∃y （x ＜ y） すべての自然数 x に対して，x よりも大きな 自然数 y （例えば x＋1 ）が存在する （真） 2. ∃y ∀x （x ＜ y） ある自然数 y が存在して，y は如何なる （すべての）自然数 x よりも大きい （偽） 7自由変数と束縛変数
freeand boundvariables• ∀x ∃y （x ＜ y） の変数 x, y は、変数と呼ばれて
いるが、代入の対象にならない ∀z∃y （z ＜ y） と書いても意味が変わらない • 変数には２種類ある。自由変数と束縛変数 • ここで注意するべき事は、同じ変数が自由であり、 同時に束縛されることがある 例： ∃y （x ＝y＋y ）∧ ∃z （y＝ z＋z＋1 ） x は偶数である y は奇数である • 自由変数と束縛変数を出現occurrenceという単位 で区別しなければならない 8
出現 occurrence
1. A が原子論理式であるとき、A に含まれる変数 x の出現 は、すべて自由な出現である 2. A がB∧C, B∨C, B⇒C, ￢B のいずれかであるとする。も し x が B または C における自由な出現であるならば、そ の x は A において自由である。もし x が B または C にお ける束縛された出現であるならば、その x は A において ける束縛された出現であるならば、その x は A において 束縛されている 3. A が(∀z B) または(∃z B)であるとする。もし z が x であ るときは、Aにおける x の出現は束縛されている。 z が x と異なる場合には、もし x が B における自由な出 現であるならば、その x の出現は A において自由であ る。もし x が B における束縛された出現であるならば、 その x の出現は A において束縛されている 9自由
変数と束縛変数（例）
• 例： ∃y （x＝y＋y ）∧ ∃z（y＝z＋z＋1 ） • 論理式が自由変数を一つも含まない時 閉論理式closed formula という • 論理式 A に含まれる自由変数xに項 t を代入し て得られる論理式を A[t/x] と表す 10 て得られる論理式を A[t/x] と表す • 代入をめぐる珍現象： （小野先生の例題） ∃z（x＝y×z） : x は y の倍数である ∃z（x＝100×z） : x は 100 の倍数である ∃z（x＝z×z） : x は平方数である • これを避けるために自由変数と束縛変数の記号 の種類を分ける流儀の教科書もある代入の方法
• A は ∀zB または ∃zB の形の論理式とする • A[t/x]は zが x のとき A[t/x] は A 自身（束縛変数に代入不可） zが x とは異なる変数のとき、 t にzが出現しなければ、 t にzが出現しなければ、A[t/x] は ∀zA[t/x] または ∃zA[t/x]
t にzが出現する場合は、 A[t/x] は ∀w（（A[w/z]）[t/x]） または ∃w（（A[w/z]）[t/x] ） ただしwは A にも t にも現れない新しい対象変数 i.e. 項 t に変数wが現れることがない 11
代入に関する補足説明
• 前のスライドの変数wは新しい変数である。 これは対象変数の集合が無限集合であるこ とを意味する。つまり必要があれば、いつでも 「新しい変数」を選ぶことができる 「新しい変数」を選ぶことができる。 • 前のスライドの面倒な操作を一言で表現すれ ば「束縛変数が項 t に出現する場合には、束 縛変数を新しい変数に、あらかじめ書き換え ておく」ということである。 12論理式の意味
• 述語論理の論理式の意味を考えるには、対象領域 domain を定める必要がある
（解釈 interpretation, モデル model, 構造 structure）
• 空でない集合D を定める 対象定数にDの要素（元）を対応づける • 対象定数にDの要素（元）を対応づける 対象変数はDの上を動く 関数記号にDの上の関数を対応づける 述語記号にDの上の述語を対応づける ※ 13 具体的な要素、関数、述語 単なる記号 に を対応 ※ ただし述語記号＝（等号）の解釈は通常の等号とする
解釈
٧ 閉論理式
• M ٧ A 解釈 M において論理式 A が真 • M ٬ A 解釈 M において論理式 A が偽 1. A が原子論理式のときM ٧ P(t1, t2, …, tn) とな るのは、Pの解釈が項 t1, t2, …, tn の解釈にお ٬٧ いて真になる場合である. 2. M ٧ A∧B となるのは （M ٧ AかつM ٧ B ）, 3. M ٧ A∨B となるのは（M ٧ AまたはM ٧ B）, 4. M ٧ A⇒B となるのは （M ٧ A ならばM ٧ B）, 5. M ٧ ￢A となるのは M٬A の時である . 14 ٬٧: MSゴシック(UTF) M: Lucida Calligraph（続） 解釈
٧
閉
論理式
6. M ٧ ∀x A となるのは、すべての D の要素 u に対してM ٧ A[u/x] となるとき, 7. M ٧ ∃x A となるのは、D のある要素 u が存在 してM ٧ A[u/x] となるときである. ٬٧ 15 ٬٧: MSゴシック(UTF) M: Lucida Calligraph 論理式B に対して、B に含まれる自由変数が x1, x2, …, xm であるとき、 ∀x1∀x2…∀xm B をB の閉包universal closureという. BC と書く 8. M ٧ B となるのは M ٧ BC となるときである.恒真な（valid）論理式
• いかなる解釈（モデル）に対しても真になる論理式 を恒真な valid 論理式という 「述語論理におけるトートロジー」ということもある • どのような解釈をしても真になるということは、個別 の対象要素、関数記号、述語記号の解釈に依存し ないという意味である すなわち論理式の形（構造）により、恒真であるか 否かが定まる 16恒真な論理式の例（その一）
A は x を自由変数として含まない 1. ∀x A ⇔ A, ∃x A ⇔ A 2. ∀x B ⇔ ∀y（B[y/x]）, ∃x B ⇔ ∃y （B[y/x]） ここに y は B に含まれていない新しい変数 3. A ∧ ∀x B ⇔ ∀x （A∧B）, ∨ ∃ ∃ （ ∨ ） A ∨ ∃x B ⇔ ∃x （A∨B） 4. A ∨ ∀x B ⇔ ∀x （A∨B）, A ∧ ∃x B ⇔ ∃x （A∧B） 5. ∀x B ∧ ∀x C ⇔ ∀x （B∧C）, ∃x B ∨ ∃x C ⇔ ∃x （B∨C） 6. （∀x B ∨ ∀x C）⇒∀x （B∨C）, ∃x（B ∧ C）⇒（∃x B∧∃x C）恒真な論理式の例（その二）
7. ∀x∀y B ⇔ ∀y∀x B , ∃x∃y B ⇔ ∃y∃x B
8. ∃x∀y B ⇒∀y∃x B 9. ∀x B ⇒∃x B 10. ￢∀x B ⇔ ∃x￢B, ￢∃x B ⇔ ∀x￢B 11 （A ⇒∀x B） ⇔ ∀x（A ⇒ B） ド・モルガンの法則 （関連の話題が前出） 11. （A ⇒∀x B） ⇔ ∀x（A ⇒ B）, （A ⇒∃x B） ⇔ ∃x（A ⇒ B） 12. （∀x B ⇒ A） ⇔ ∃x（B ⇒ A）, （∃x B ⇒ A） ⇔ ∀x（B ⇒ A） 13. ∃x（B ⇒ C） ⇔ （∀x B ⇒ ∃x C） 14. ∀x（B ⇒ C）⇒（∀x B ⇒ ∀x C） 15. ∀x（B ⇒ C）⇒（∃x B ⇒ ∃x C）
恒真な論理式の説明
• （∃x B ⇒ A） ⇔ ∀x（B ⇒ A） １２の下
• この論理式に含まれる自由変数が y1, …, ym の
とき、任意の解釈M について次をいえばよい
M ٧y1…∀ym｛（∃x B ⇒ A） ⇔ ∀x（B ⇒ A）｝
上は閉論理式であるから次をいう（解釈 4 6） • 上は閉論理式であるから次をいう（解釈 4, 6） すべての u1, …,um ∈ D に対して M ٧（∃x B ⇒ A）[u1/y1,…,um/ym] ⇔M ٧ ∀x（B ⇒ A）[u1/y1,…,um/ym] • 以下の説明では、既に上のような項の代入が済 んでいると仮定する 19
