$BO@M}3X!J4pAC1i=,!K(B

# 論理学（基礎演習）

京都大学・科学哲学科学史 現代文化学共通ホームページ

数学基礎論あれこれ

皆さんの質問

第１回　4月16日　記号論理とは
その由来、文章の記号化、命題論理の式、
真理値、真理値表、数による計算、論理記号の相互関係
参照：情報系の数学入門（林・八杉著）３章（３・１[1]-[3]）

第２回　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 以下である"を表す。）
この論理式が正しい数学の集合と正しくない集合をそれぞれ与えよ。
正しくないほうは、反例をあげよ。
課題　３　述語論理の推論１２（存在記号の除去）が正しさを保存することを示せ。
以上

5月21日 述語論理の体系 LK
シークエント、始式、推論図、証明図、などの説明（「証明論入門」１章-2）
注： 述語論理の健全性の証明の最後を忘れていました。次回行います。
もし忘れそうだったら、注意してくださいね。
なお、6月11日は休講です。補講をするかどうかは、進み具合いできめます。

５月２８日、６月4日：　述語論理の体系（ヒルベルト型）の健全性証明完了
述語論理の体系LKの説明、証明図の例、健全性と無矛盾性
カット除去定理（定理の記述のみ）、カット除去の系、（部分論理式、無矛盾性）

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

お知らせ：講義は（夏休み前は）6月2５日が最後ということなので
7月に補講をするかもしれません。完全性の証明をしたいからです。
2５日に相談します。

質問への答え

(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
というとであるが、これは証明図の中で明示的に使ってはいけない、ということか？

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

＊レポート 1 配点と解答

課題１ 「咲いたら」は「咲くならば」、「でも」は「かつ」と解釈。
「朝顔が冬に咲かないからといって、地震が起きないとは限らない」
は、分かりにくい。文章を聞いた自然な感じでは、
「「...咲かないからといって、...起きない」とは限らない」
つまり「咲かないならば起きない」全体を否定していると考えるのが自然。
そうすると (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)が恒真であることを示してもよい。

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

６月２５日　述語論理の完全性定理（ゲーデル）証明　概要・分解の木
完全性は論理式の恒真性を形式的な証明可能性で置きかえることができる、
重要な定理
この講義の方法はProof Theory (G. Takeuti) の方針にそっている。

＊補講のお知らせ！ 7月9日（金）１時間目 新館２F第２演習室
完全性定理の証明の完結

７月９日　述語論理の完全性証明完了

＊レポート ３：提出は１０月最後の週
課題（１）完全性定理の概要をレポート用紙３枚以内にまとめよ。
（２）「 => （ならば）左」と 「exists （存在記号） 右」の分解を定義せよ。
（３）論理式 exists x forall y (P(x) => P(y)) の分解の木を作り、
恒真性を示せ。
（４）　（３）の論理式の証明図を作成せよ。

＊質問募集！　完全性定理の証明はアウトラインだけだったので、
こまかいことは、質問に応じて９月２４日に説明します。質問を
９月２２日までにメールで送ってください。
yasugi@cs.kyoto-u.ac.jp （csです。まちがえないで）
なお、２４日に分解の木の応用をいくつかします。

＊教室について：以前教務課で教室の変更が可能かもしれないといわれましたが、
よく調べたら空きはないそうですので、９月からも同じ教室です。

＊レポート２　（述語論理、形式的体系）の解答と＜＜再提出＞＞について

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

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

では解答。

課題　１　「誰でも何か好きな動物があるとは限らない」を、
述語論理の式として表せ。
前にも触れたと思いますが、「...とは限らない」の表現方法には意見の相違も
あると思います。しかし「ふつうは」次のようにします。
単に命題 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が
正しい。

以上

9月24日　分解の木の例　証明可能な場合、不可能な場合
実数の構成（集合論の発生と数学基礎論論争に向けて）

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

＊山下さんから質問がきました。皆さんも興味があるかもしれないので、
ここ
に貼っておきます。質問はできるだけもとの通りにしてあります。
そのほうが疑問が良く伝わるからです。答えは多少変更してあります。

10月8日：カントルの集合論概観、クロネッカーとヒルベルト（１９００年まで）

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

10月15日：数学の既存に関する論争の、1900年ー1930年、および1930年の出来事についての概観。
詳しいことは話せませんでした。興味のある方は前出の私の未完成のメモ
ここや
数学基礎論あれこれ
を参考にしてください。
また、後日いくつか参考資料の表を作ります。

＊しばらくごぶさたしました。忙しくて講義進行状況を
かけませんでした。
そういっているうちに今年度の講義が終わってしまいました。
最後はゲーデルのオリジナルで不完全性定理の概要を解説しました。
最後のレポートの問題のプリントを配布しましたが、入手していない方は
メール（yasugi@cc.kyoto-su.ac.jp）へ連絡ください。
長く出席したのに、３回目のレポートを提出していないのは残念です。
そういう方はメール連絡をください。相談に応じます。
ではレポートを楽しみにしています。

成績は一月末に提出しました。最終（４回目）のレポートを含めて
最低３回レポートを提出した人のみ評価しました。
（一回抜けていても評価の対象にしました。）
最後のレポート未提出の場合には棄権とみなしました。

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

参考書　情報系の数学入門　林・八杉著　オーム社　（集合・写像・論理・計算・
帰納法・命題論理の式、真理値、恒真性の判定アルゴリズム、述語論理の式）
数理論理学　林著　コロナ社　（述語論理の証明論）
証明論入門　竹内・八杉著　共立出版　（述語論理と算術体系の証明論）
論理パズルとパズルの論理　八杉・林著　遊星社（論理パズルの解き方）
ゲーデルの謎を解く　林著　岩波 科学ライブラリ（不完全性定理解説）
萩谷著 岩波 （計算機科学のための論理）
小野
Goedel's Incompleteness Theorems Raymond M. Smullyan
Oxford University Press (不完全性定理）
これは丸善から訳が出ているが、それがひどい。訳を読む場合には
知らせてください。多少の正誤表を送ります。
S.C.Kleene, Introduction to Metamathematics（古い本ですが、
数理論理学の基礎がしっかり書かれていて、今でも辞典のように使える。）
G. Gentzen, Investigations into logical deduction
(English translation: The Collected Papers of Gerhard Gentzen
North-Holland, 1969, 68-131)
順次付け加えていきます。

関連ページ
パズルランド

「集合と論理」

「抽象化の技法」

Last modified: Fri Feb 25 00:17:21 JST 2000