論理学（基礎演習）

数学基礎論あれこれ

皆さんの質問

第２回　4月23日　真理値関数の論理式による表現（３・１[4]）
式の恒真性、充足可能性、和積標準形、恒真性の判定（３・２[1],[3],[4]）
述語論理の記法（３・６[1]）
第３回　4月30日　述語論理の式の定義、例、出現、有効範囲、束縛、自由、
述語論理の意味論
参照：上記3章3.6の終わりまで；数理論理学（林著） ２章2.1,2.2
注：述語論理の意味論を厳密にしましたが、 集合や写像の記法など、わかりにくいかもしれません。
これらの記法については、次回に簡単に説明します。
しかしこれは一度きちんと定義されることを確認すれば、後はあまり気にしなくていいです。
第４回 5月7日 集合・写像・関係の概観（情報系の数学入門 第１章）
述語論理の形式的体系の定義(Kleene, Introduction to Metamaehtmacis, p.82)
第5回5月14日 命題論理の健全性

レポート！ 提出：レポート１　６月４日　；　レポート２　６月２５日
できるだけLaTexまたはそのほかのワープロで書いてください。

レポート１（命題論理と集合・写像・関係）
課題　１　「朝顔が冬に咲いたら、地震が起こる。でも朝顔が冬に咲かないからと
いって、地震が起きないとは限らない」を論理式で表せ。
課題　２　１　の和積標準形を求めよ。
課題　３　２　は恒真か？恒真ならばその理由を述べ、そうでなければ、
反例をあげよ。
課題　４　２項関係 P(x,y) で、写像を定義するもの（各 x に対して、高々一個の
y について P(x,y) となる）の例をあげよ。その写像のグラフを定義せよ。
課題　５　アキ「アヤは妖精じゃないよね」
　　　　　アヤ「当たり前よ」
　　　　　マヤ「だから、もしアヤが妖精だったら、アキは天使よね」
アキが正しいときに、マヤは正しい？

レポート２　（述語論理、形式的体系）
課題　１　「誰でも何か好きな動物があるとは限らない」を、
述語論理の式として表せ。
課題　２　(exists x)(forall y)leq(x,y)
（ただし、leq(x,y)は "x はy 以下である"を表す。）
この論理式が正しい数学の集合と正しくない集合をそれぞれ与えよ。
　　　正しくないほうは、反例をあげよ。
課題　３　述語論理の推論１２（存在記号の除去）が正しさを保存することを示せ。
以上

カット除去定理に興味のある人は「証明論入門」の１章の３、またはGentzenの ３６年の論文を見てください。

(1) LK体系の演習問題(14)「(AvC)^(BvC)→(A^B)vCを証明せよ」
これの証明の際、まず(AvC),(BvC)→(A^B),Cを証明した後、
直接(AvC)^(BvC)→(A^B)vCにもっていってもよいのでしょうか？

「直接」が「一回の推論で」という意味ならばちがいます。
(AvC),(BvC)→(A^B),C　から１にもっていくには、「and 左」を二回、
「or 右」を二回適用して、左右の「減」を使えばできます。

実際には(AvC),(BvC)→(A^B),Cではなくて、
(AvC),(BvC)→(A^B)vCを証明して、
それから求めるものを導くほうが手っ取り早いでしょう。

(2) A-->B,C とB,C-->D からカットを適用して A-->Dを得られるか？

カットは一回に一つの論理式だけをカットアウトするので、
そうはいきません。左右のコンマは違う意味をもつことを思い出してください。

(3) A1,A2,...,Am-->B1,B2,...,Bnは内容的にはA1andA2and...Am=>B1orB2or...Bn
というとであるが、これは証明図の中で明示的に使ってはいけない、ということか？

そうです。これはあくまでも説明で、（実際には同等であることが示されますが、
それは証明すべきことであって、証明の推論としては使えません。）
証明は推論図のリスト以外には使えません。

課題１ 「咲いたら」は「咲くならば」、「でも」は「かつ」と解釈。
「朝顔が冬に咲かないからといって、地震が起きないとは限らない」
は、分かりにくい。文章を聞いた自然な感じでは、
「「...咲かないからといって、...起きない」とは限らない」
つまり「咲かないならば起きない」全体を否定していると考えるのが自然。
そうすると (P=>Q) and not(notP=>notQ) となる。
しかし、「咲かないならば 起ることもあるしおこらないこともある」
と解釈して後のほうを (notP=>Q or notQ)とか(notP=>Q) or (notP=>notQ)
としたものも大筋認めた。実はこれだと後の命題は明らかに恒真になる。
実は「とは限らない」というのは厳密には命題論理の範囲では表現できないとも
考えられる。しかしここでは、文章をなんとか命題論理で記号化する、という
練習なので、「A=>Bとは限らない」は、「Aが正しければ必然的にBも正しい、のではない」と解釈する。
課題２ 最初の論理式のときのみ答えを書く。順に
(notP or Q) and not(not notP or notQ), (notP or Q) and (not not not P and not notQ),
(notP or Q) and notP and Q

課題３ 恒真性の判定方法により、恒真ではない。v(P)=Tまたは v(Q)=F のときは全体がF

課題４ 各 x に対してP(x,y) が成り立つ y が高々一つあるようなP(x,y)を考える。
例 P(x,y): Aを（現在の）人々の集合、Bを正の整数の集合、人xに対して、もしその人が
パスポートを持っているならば、そのパスポートの番号をyとすると、Pは直積集合AxB上の
関係で、関数を定義する。
P(x,y): y=x^2 + 3 のように数学で習った関数を使えば、明らかに、題意を満たす。
関数のグラフは絵を描くのではない！xとyのペアの集合である！
G_P = {; x in A, y in B, P(x,y)}
グラフということばに惑わされた人がほとんどでしたね。
プリントの定義を見直しておいてください。グラフを正しく考えた人はおまけをあげました。

課題５ 「アヤが妖精」をX, 「アキが天使」をYとおく。アキは notX といい、
マヤは X=>Y といった。v(notX)=T ならば v(X=>Y)=T (Yの真理値によらない）。
ゆえにアキの言明が正しければ、マヤも正しい。
または、 notX =>(X=>Y)が恒真であることを示してもよい。

配点は１が６、２が４、３と４が３、５が４、です。合計２０点。
ずいぶん細かいですが、各問題にいくつかポイントがあって、それを数えたら
こうなりました。

難しかったですか？下に解答の概要を書きます。各問１０点、合計３０点満点です。

レポートは成績をつけるためでもありますが、一番の効用は理解を助けることです。
不満足な成績のまま消化不良で終わってほしくありません。そこで、以下の要領で
再提出を認めます。９月にレポートを返却します。その成績にしたがって
次のように してください。提出は１０月最後の講義の後で。
（１）合計点が２０点未満の人：　以下の解答を理解し、できるだけ正確かつ簡潔に
書きなおして提出のこと。ただし、満点は２０点です。
（前回の繰り返しでもいいですから、３問すべて書いてください。）
（２）合計点が２０点を越えた人：　述語論理について１ページ程度レポートを
書いてください。ボーナス点を５点出します。（内容は問いません。）

では解答。

課題　１　「誰でも何か好きな動物があるとは限らない」を、 述語論理の式として表せ。
前にも触れたと思いますが、「...とは限らない」の表現方法には意見の相違も
あると思います。しかし「ふつうは」次のようにします。
単に命題 A と書いたら、「A である」と主張しているとみなし
「Aであるとは限らない」は 「A ではない」考える。すなわち
not A で表す。　さて、この問題について
H(x): x は人である、　A(y): y は動物である、L(x,y): x は y を好む、とおき
これらを使って条件を正確に書く。「誰でも」は”すべての人”、
「好きな動物がある」は”ある動物があって、それを好きである”と表す。
最後に全体を否定すればできあがり。
あるいは「好きな動物がある人がいる、また、好きな動物がない人もいる」
という表現でもいいです。
注：　このように何を基本的な述語にするか、を決め、文章を記号化することは
いろいろな場面で、大変に重要なことです。

課題　２　(exists x)(forall y)leq(x,y) （ただし、leq(x,y)は "x はy 以下である"を表す。）
この論理式が正しい数学の集合と正しくない集合をそれぞれ与えよ。 正しくないほうは、反例をあげよ。
lea(x,y)をふつうの数の「...以下」と考えれば、この式は「最小値 x がある」
を表します。数の集合で最小値をもつものはたくさんあります。どんどん小さく
なる数がなければいいわけです。自然数0,1,2,3...は当然そうですね。
レポートではこれは避けて別に自分で最小値のある集合を作ってください。
正しくないほうは、その反対にどんどん小さくなる数のある集合、たとえば有理数
の集合はそうです。ほかにも考えてください。反例とは、各 x について
それより小さい y を作ればいいのです。有理数ならば x-1 が簡単な例です。

課題　３　述語論理の推論１２（存在記号の除去）が正しさを保存することを示せ。
A(x)=>Cが正しいときにexistsA(x)=>Cも正しいことを示す。ある集合 S と述語の S 上
での解釈においてA(x)=>Cが正しいとする。（xにSのどんな要素を代入熕j
次にexistsA(x)が正しいとする。つまりある S の要素 c について x=c のときに
A(x) が正しい。このとき最初の前提より C が正しい。ゆえにexistsA(x)=>Cが
正しい。

以上

＊二回ほど数学基礎論の歴史について話します。後日レポートの課題にします。
テキストとしてファイルを おきますので、参考にしてください。
（消去しました。）
また、歴史的なことの参考書はいろいろあります。この科目は歴史が主体ではないので
一−二だけあげておきますが、興味のある方は申し出てください。

注意！ レポート３の提出日を11月5日に延期します。

講義への感想をありがとうございました。来年度の参考に
します。なお、黒板が壊れていたことと、教室が暗いために
字が読みにくかった、という意見が複数ありました。
私も板書していて、黒板がはがれているところでは悲しくなりました。
また、教室が大きすぎてかつ暗いので、皆さんの反応がよく分からず、
残念でした。この点は内井先生にお願いして、来年度は改善した
いただけそうです。皆さんには遅すぎたかもしれませんが、ご意見は
役にたちました。また、今年度の経験から、来年度はテキストを使う
ことにしました。
では、今後の学業の成功を祈ります。

「集合と論理」

「抽象化の技法」