論理とプログラム２００１

質問票受取り。

その一：再帰的関数の（５）と（６）がよくわからない。
定義の読み方を書きます。
(5) f[x_,y_] := If[x=0,h[x,y],g[f[x-1,y],x,y]]
x,y は入力値です。x=0のとき、h[0,y]を出力（つまりf[0,y]の値はh[0,y]）。
x>0のとき（つまりx=0でないとき）、f[x,y]の値は g[f[x-1,y],x,y]である。
すなわちf[x,y]の計算をf[x-1,y]の計算に「帰着」させる。こうしてx-1,x-2,...
とxの値を小さくしていってしまいに 0 のときに直接h[0,y]の値を得る。それを使って,br> 逆にf[1,y],f[2,y],...,f[x-1,y],を計算していき、最後にf[x,y]を得る。
これはMathematicaの再帰的定義(recursion)（計算）の一つの形と全く同じ。
(6) f[x_,y_] := If[g[x,y]=0,y,f[x,y+1]]
g[x,y]の値が0になる、y以上の最小のyの値を求める。g[x,y]=０ならば、出力はy、
そうでなければ次はゼロになるかもしれない、という期待でf[x,y+1]を計算しようとする。
(6)の定義をf[x,y+1]にあてはめると、
f[x,y+1]=If[g[x,y+1]=0, y+1,f[x,y+2]]となる。もしg[s,y+1]=0ならば答えはy+1,
そうでなければy+2を試す。こうしてどこかでg[x,z]=0となれば、その最初のzが答え。
実際にはg[x,z]が決してゼロにならなければ計算はいつまでも続くが答えは出ない。

そのニ：真と偽があるのに恒真と言いきれるもの（論理式）があるのか？
例　(forall x)(P(x)=>(exists y)P(y)); A or notA

その三：「人は誰でも誰かを愛するが、愛する相手が自分を愛しているとは 限らない」
これを表す論理式の成り立ちがわからない。
まずこの文章は二つの文章を「かつ」で結んでいる。
「人はだれでも誰かを愛する」（これをAとおく）
「愛する相手が自分を愛しているとは限らない」（これをBとおく）
A：ここで必要なのは「・・・は人である」と「・・・は＊＊＊を愛する」である
・・・や＊＊＊を変数x,yなどで表す。「x は人である」を H(x)、「x は y を愛する」
をL(x,y)とおく。「人は誰でも」は 「どんな x についても x が人ならば」という
意味だから、(forall x)(H(x)=>...)。「x が誰かを愛する」は、誰か、とは人の
ことだから、(exists y)(H(y) and ***)となる。***は「x が y を愛する」だから
L(x,y)。...にこれ全体をいれると
(forall x)(H(x)=>(exists y)(H(y) and L(x,y)))
B：これは「愛する相手が自分を愛する」を否定している。それで最後に not を
つけることにして、「・・・」の部分を論理式にする。
自分と相手と２種類の人がいるので、前者を x 、後者を y とおく。
「・・・」は「x が y を愛するならば、y が x を愛する」（これをCとおく）
ということである。 x も y も人であることが要請されているので、C
の前提に「x が人で、y が人である」を加える。ここで x も y も誰でよいので
「すべての x とすべての y について」である。したがって全体は
(forall x)(forall y)(H(x) and H(y) and L(x,y)=>L(y,x))であり、これ全体の
前に not をつければできあがり！

forall や exists の使い方がよくわからない。
このことに限りませんが、まずテキストをじっくり読んでください。
次にノートで該当するところをじっくり読んでください。
そうして理解したら同じことをテキストを見ないで自分で考え直してください。
なにごとも自分で時間をかけて、手を動かして（文字通り手間隙かけて）
勉強する以外に最終的に理解することはできないのです。
その上で、具体的な疑問があれば質問してください。

レポート課題配布

レポート回収