2008年度論理学演習

宿題の累計成績

• 2008年度論理学演習成績

シラバス

授業のテーマと目的

哲学的分析には論理学が不可欠である。本演習では、命題論理、述語論理に関する問題演習を通じて、論理学に対する基礎体力を養った上で、記号論理学の標準的知識（対象言語とメタ言語の区別、証明論と意味論の区別、等）を身につけることを目標とする。

授業計画と内容

本演習では、命題論理と述語論理について、基本的な訓練を行うことで、モデル理論と証明論をマスターし、その二つをつなぐ「完全性定理」を証明することを目標とする。主に前期に命題論理を扱い、後期に述語論理を扱う予定である。その後、関連した話題として有限オートマトン、チューリング・マシン、決定不可能な問題なども論じる。余裕があれば非古典論理（様相論理など）の基礎的な話題も適宜補足する。

対象回生

2--4回生、大学院生

コメント

頭で考えるよりもまず手を動かそう。なお、遅れて提出された宿題は採点しない。

成績評価の方法

ほぼ毎回出題する宿題の累計成績に準じて行う。

履修要件

特になし

テキスト

内井惣七「真理・証明・計算」ミネルヴァ書房

参考 website

• 論理学演習: 内井惣七名誉教授の論理学演習の website. 本演習の受講者にもアドバイスがあるので、ぜひ見に行ってみよう。

授業の予定・記録・連絡

2008/04/08

• 授業の概略の説明とイントロを行いました。
• 授業で用いたスライドはこちら。
  • 授業の折は、スライド p.19 の図を「ヴェン図」と説明したが、これは間違い。 なぜなら、簡単に言えば「ヴェン図」というのは描かれた図形の全ての交わり の可能性を示すものでなければならないからだ。この「全ての」という制限を落としたのがオイラー図。だからスライド p.19 で書いた図はオイラー図である。内井惣七名誉教授からの指摘に感謝したい。もう少し違いについて明確に知りたい受講者は、田中一之・鈴木登志雄著「数学のロジックと集合論」 培風館 2003年の、pp.199-201 を読まれたし。コピーがほしい場合は教師まで。(2008/04/22)

2008/04/15

• 本日は、命題論理の記号法と真理関数の理論を説明しました。
• 宿題の答案の書き方を説明し損ねたので、ここで説明しておきます。
  • 解答用紙はルーズリーフかレポート用紙で（a4 ないし b5）。また、両面使用でも片面使用でもいずれでもよい。
  • 名前と所属を必ず書くこと。
  • あまり詰めて書かない。問題ひとつ（例えば、(1)）をとき終わったら、次の行から次の問題（例えば (2)）の解答を始めること。
  • なるたけ大きな字で。
  • Word などで書くことは否定はしませんが、手書きを強く勧めます。
  • 宿題はホッチキスで綴じて提出する。
• 今回の宿題について注意：p.26 の (問題3) (1) は全ての記号式に正当化のための真理表をつけておくこと。また、p.26 の(問題1), (問題2) についても自身の解答を正当化する真理表をつけておくこと。
• 宿題答案の書き方含め、授業時間外の質問は まで。

2008/04/22

• 命題論理への真理中心アプローチ：正しい推論と分析的反証法を主に説明しました。
• また 2008/04/08 に記述のある、ヴェン図とオイラー図の違いを説明。
• 今日提出してもらった宿題はすでに採点済みです。 2008年度論理学演習成績に名前がわからないように点数が掲載してあります。
• 今回の宿題についての注意
  • 分析的反証法を使う箇所では、どの規則を適用したかを必ず書いておくこと。
  • 枝分かれが生じる規則（例えば（∨真）など）に関する注意： （∨真）を (A ∨B)∨C に適用する場合は必ず二回の規則適用にすること。
  • p.32 (問題3) のストアの命題論理の推論では、我々が学んだ「または」∨がそのままでは使えないことに注意。
  • p.32 (問題1)(問題2) はともに分析的反証法でトートロジーの判定（すべての枝で×がつけばトートロジー、 ひとつのある枝で○がつけばトートロジーでない）をするのは同じ。 しかし、p.32 問題１では、分析的反証法でトートロジーでないことがわかった場合に、 トートロジーでないことを真理表を使って確認しておくこと（真理表のうちの特定の一行だけを書けば十分）。 p.32問題2ではこのようなチェックは必要ない。(2008/04/27)

2008/04/29

• 休講です。

2008/05/06

• 休講です。

2008/05/13

• 命題論理への真理中心アプローチ：分析的推論と選言標準形を説明。 またゲンツェンの自然演繹への導入を行いました。
• 昨日提出してもらった宿題を採点しました （2008年度論理学演習成績を見てください）。 いくつかコメントがあるので以下に記します。
  • 一行で適用してよいのは、一つの式に対する一つの規則だけ。 機械になったつもりでやること！
  • 分析的反証法で枝分かれが生じる規則（（& 偽）や（∨真）） の使い方、書き方を理解すること。自己流で「枝分かれ」させない。
  • いつ分析が終わる（分析の枝に○をつける）のか、を理解すること。 ひとつの枝に出現しているすべての論理式に規則を適用し 尽くさないと○をつけてはならない。そうしないと○のついた枝から自動的に 反例となる真理表が作れない。
  • 二つ以上の枝で分析の規則を同期（二つの枝に同時に同じ規則を適用すること） させる必要はない。もちろん場合によってはさせてもよい。
• 今回の宿題は p.35 問題1, 2 です。上のコメントに注意して頑張ってください。
• いくつか宿題に関して質問があったので以下に答えておきます。(2008/05/18)
  • p.35 の問題1で言われている(1), (2), (3) とは、p.33の一番下にある (1), (2), (3) のこと。
  • p.35 の問題1では、はじめに A∨〜A, B∨〜B, C∨〜Cを加えてから分析を始めること。 最終的に○のついた枝ごとにアトム(A,B,C)かその否定を拾って連言で結び、それからそれらを選言で結ぶこと (その際、重なっている情報は省略してよい)。
  • p.35 の問題2も基本的に問題1とすることは同じだが、 問題1のようにはじめに A∨〜A などを加える必要はない。

2008/05/20

• 命題論理への証明中心アプローチ1：ゲンツェンの自然演繹の推論規則と定理の証明の 具体例を解説しました。
• 今日提出してもらった宿題は採点済みです。 2008年度論理学演習成績をチェック。 皆さんの答案から分析的反証法を理解していることがよくわかりました。
• 今回の宿題は p.43 問題1, p.48 問題2 です。 仮定の消える推論規則に注意して取り組んでください。

2008/05/27

• 命題論理への証明中心アプローチ：ゲンツェンの自然演繹（続） とヒルベルト流公理系の導入を行いました。
• 昨日提出してもらった宿題を採点しました。 2008年度論理学演習成績をチェック。 今回の宿題をする上での注意を書いておきます。
  • (∨消)を使うときは式の順番を気にすること。 A∨B, ..., A, ..., C, B, ..., C, C の順に規則で要求されている式が 出ているかに注意すること。 また、(∨消)と書く場合に五つの異なる番号が出ているかに注意すること。
  • どの規則を適用したらよいかわからなくなったら、 式の意味をよく考えて、何かの式を仮定してみること。 Try and Error を繰り返してみてその中から最善のやり方を見出すこと。
  • 規則の適用に少しでも疑問を持ったら、授業でも説明した 仮定を左側に中カッコに括って書く表記で仮定を確かめてみること！
  • 推論規則の使い方や解答の仕方について 不明な点や疑問点があれば教師に質問すること。 誤解したまま解答を書くよりはよっぽどマシ。 聞くは一時の恥、聞かぬは一生の恥！
  • ある式Bの下に、同じ式Bを出したい場合は〜Bを仮定して、 矛盾を導いて(〜〜消)を使う、などすること。
• 今回出した宿題のうち、 p.59の中級（(2),(3),(13),(14),(15),(16)以外）には 前回やった問題が二題含まれているが、 復習をかねてやっておくこと(サービス問題)。(2008/05/31)

2008/06/03

• 命題論理への証明中心アプローチ2：ヒルベルト流公理系（仮定からの演繹）の説明を行いました。 授業中に余談で話した Graham Priest 先生の情報はここ。 Graham Priest 先生の研究している論理には、Paraconsistent Logic （矛盾許容型論理）という名前がついています。
• 昨日提出してもらった宿題を採点しました。 2008年度論理学演習成績をチェック。 今回は全体的に非常に良くできていました。この調子でがんばりましょう。 念のため、(∨消)の使い方には再度注意しておくこと。
• 今回の宿題はテキスト p. 59 の（問題）です。 ヒルベルト流の公理系の公理の形をじっくりみてみて取り組みましょう。

2008/06/10

• 命題論理への証明中心アプローチ2：数学的帰納法の説明を行いました。
• 次週、演繹定理を実際に証明しますが、その証明のエッセンスは 今日の簡単な具体例で説明したように、 演繹の列の書き換えの手続きを証明中で構成する、ということです。 次週の証明が理解できるように数学的帰納法についてよく復習しておきましょう。
• 今日提出してもらった宿題を採点しました。 2008年度論理学演習成績をチェック。 今回も全体的に良くできています。念のため、各公理がどのような形の論理式を許すのか、 再度注意しておきましょう。
• 今回の宿題は、テキスト p. 51 の(III)上級の(1)から(8)全て、です。

2008/06/17

• ヒルベルト流公理系での演繹定理の（メタ）証明を行いました。
• 今回の宿題は、p.66 の問題1（上） (T3), (T4), (T5), (T6), p.66 の問題1（下） の (T9), (T10) です。(T10) は角括弧内の式 A⊃(B⊃〜(A⊃〜B)) を示すように。 取り組む際の注意は、授業でも説明したように、示すべき事柄を導くために 必要なことは何かを考える、ということです。
• 昨日提出してもらった宿題を採点しました。 2008年度論理学演習成績をチェック。 いくつかコメントを述べます。
  • (6) では A∨Bに (∨消) を使うことが必要になります。 そのため、使わなかった人はどこかに間違いがあります。
  • 何人かの人が、すでに消えた仮定に依存する式を、仮定が消えた後で使って しまっていました。このような間違いを防ぐには、適用に不安を感じた時に必ず 仮定の集合のチェックを行っておくこと。
  • 排中律を証明してから使うのは悪いことではないが、 排中律を導くための証明は略さないこと!

2008/06/24

• 命題論理への二つのアプローチの橋渡し：健全性定理の証明を行いました。
• 今回の宿題は、p.66 の問題1(下)(T11), (T12), (T13), (T14), p.67 の問題2, 問題3 です。
• 提出してもらった宿題を採点しました。 2008年度論理学演習成績をチェック。 コメントは、式の形に注意せよ!ということ。 たとえば、A⊃〜(B⊃A)はA1の公理の一例にはなりません。 なぜなら、これはA1の公理型である A ⊃(〜B⊃A)とは全く形が異なりますし、 また、A⊃〜(B⊃A) はトートロジーではないが、A ⊃(〜B⊃A)はトートロジー である、といったように意味も違うからです。

2008/07/01

• 命題論理への二つのアプローチの橋渡し：完全性定理の概略を説明しました。
• 今回の宿題はこちら。 授業で答え合わせをしたような形式でヒルベルトタイプのメタ証明を行うこと。 宿題のヒント：
  • 問2はテキストp.74の記述にヒントがあります。
  • 問3(1)はテキスト p.73の補助定理3の証明、 問3(2)はテキスト p.73の補助定理1の証明、がそれぞれヒントです。
• 提出してもらった宿題を採点しました。 2008年度論理学演習成績をチェック。 予告どおりp.67 問1(13)が正解であった人には二倍の20点をつけてあります。

2008/07/08

• 命題論理への二つのアプローチの橋渡し：完全性定理の証明を終え、 述語論理のフォーマリズムについて説明しました。
• 命題論理の完全性定理の証明の箇所でスキップした補助定理に ついての補足はこちら。確認しておいて下さい。
• 提出してもらった宿題を採点しました。 2008年度論理学演習成績をチェックしてみてください。 全体的に良くできていました。
• ほぼ三ヶ月あまりも夏休みになります。 前期で理解のあまかった点など再度復習しておきましょう。 以前理解できていた箇所も三ヶ月もたてばきれいさっぱり頭から消え去ります。 定期的にこれまでやった練習問題を再度解いてみることで トレーニングを積んでおきましょう。 例えば、一日に一題づつ練習問題を解くなど（そんなに時間はかからないはず）。 述語論理に入ると格段に難しくなるので 命題論理の部分の理解を完全（式の形をみてトートロジー（ないし定理）かそうでないかの 見当がつけられるくらいに）にしておきましょう。 もちろん疑問点が生じたときは いつでもメールで質問してもらってかまいません。
• 今回の宿題は、テキスト p.81問題（(7)を除く）です。 宿題を解答するに当たっては内井惣七名誉教授のページ： A Common Mistake にも注意しておくこと。

2008/10/07

• 後期開始日
• 述語論理への真理中心アプローチ：述語論理のモデル導入を行いました。
• 宿題を採点しました。2008年度論理学演習成績をチェック。量化子の位置で迷う人がいるかも知れないので、その点をフォローします。 ∀x∃y(P(x)⊃Q(y)& L(x,y)) と ∀x(P(x)⊃∃y[Q(y)& L(x,y)]) は同じ「意味」になります。また、∃x∃y(P(x)& Q(y)& L(x,y)) と ∃x(P(x)& ∃y[Q(y)& L(x,y)])も同じ「意味」です。ですので、どちらで解答を書いても構いません。しかし問題はこの同じ「意味」であることをどうやって示すかです。これは次回に学ぶ妥当性概念を使えば証明できるようになります（二つの式が同値≡であることが妥当になる）。
• 今回の宿題は、テキスト p.85 問題(a)と、p.87 の問題の(1)--(3)の問題文を記号式に翻訳すること、です。宿題をする際のヒントを挙げます。
  • p.85 問題(a)の(1)および(3)では「人間b」や「動物a」の扱い方に注意すること。例えば「動物aが人間ではない」といったとき、「a が動物である」ということが含意されているのか、それとも、「a が動物だったら」ということが意味されているのか。慎重に検討すること。
  • p.85, p. 87 のそれぞれには「いかなるPはQではない」という形式の日本語がありますが、これは「すべてのPについて(Qでない)」という意味なので、 記号式に直すときに気を付けてください。
  • p. 87の問題では、「A。B。ゆえに、C」というのを、A, B, C のそれぞれの部分を記号式に直した上で、[(Aの記号化)& (Bの記号化)]⊃(Cの記号化) という形に直しておいてください。

2008/10/14

• 述語論理への真理中心アプローチ：述語論理のモデルの厳密な定義（確認）、 述語論理への真理中心アプローチ：述語論理での分析的反証法（導入）を行いました。
• 宿題を採点しました。2008年度論理学演習成績をチェック。 自由変項（a,b,c）には束縛をかける必要はありません（束縛から自由という意味で自由変項）。
• 今回の宿題は、p.85 の問題(b), p.87 の問題, p.92 の問題1 です。注意を以下に記します。
  • p.85 の問題(b)とp.92 の問題1はモデルを作るだけではなく、作ったモデルで各式が真になることも、 モデルでの真理の定義(テキストpp.89-90)に照らして確認すること(これが授業で言っていた「正当化」)。
  • 真理条件の適用は水も漏らさぬよう必ず一ステップづつ行うこと。
  • V(x) を使う全称記号、存在記号の真理条件が分かりにくい、という人は、例えば、 「どの V(x) の値についても [V(x)∈V(N) あるいは V(x)∈V(A)]」や 「ある V(x) の値について V(x)∈V(N)」といった表現を、V(x)が出てくるまで分析してから、 V(x)の出てくる箇所を次のように置き換えてもよい： 「どの e∈D の値についても [e∈V(N) あるいは e∈V(A)]」、「ある e の値について e∈V(N)」。
  • p.92 の問題1に解答する場合は個体領域の集合を自由に決めてよい。 余裕があれば、禁欲的に（空集合でない限り）どれだけ小さい個体領域で解答ができるかを考えてみましょう。

2008/10/21

• 述語論理への真理中心アプローチ：述語論理での分析的反証法（続）を行いました。
• 今日提出してもらった宿題を採点しました。2008年度論理学演習成績をチェック。 宿題に対するコメントを記します。今回の宿題を解くときにも参考にしてください。
  • 「V(∀xA(x)) = F」となるのは「V(x) のある値につき V(A(x)) = F」となる場合であり、 その場合に限ります(テキスト p.90, (8)(b) の「それ以外」とはこれを指す。10/14に配ったプリントの裏面の第一パラグラフも参照)。 「V(x) のすべて値につき V(A(x)) = F」としてはならない。 ∀x が連言の一般化だと思えばおかしいことに納得できるはず(2008/10/25)。
  • 「V(∀x∀y(F(x,y)∨F(y,x)))=T」を分析するときは必ず外から分析して 「全てのV(x),全てのV(y) の値につき、(V(F(x,y))=T or V(F(y,x))=T)」とすること。 これを「全てのV(x),全てのV(y) の値につきV(F(x,y)) = T、あるいは、全てのV(x),全てのV(y) の値につきV(F(y,x)) = T」 と分析するのは間違い。この違いは、(i)「すべての人間は男性か女性である」と(ii)「すべての人間は男性である、あるいは、すべての人間は女性である」 の違いと同じで、上で挙げた間違いを犯した人は、(i)を(ii)と同じ意味だとみなしていることになってしまう。 このようにわからなくなったら具体的な例を入れて自分の推論が正しいかチェックしてみること。
• 今回の宿題はp.92 の問題2とp.95 の問題 (1)--(12)を、分析的反証法を使って解いてください。 以下に注意を記します：
  • (∀真)の一度の適用は、ひとつだけの自由変項（例えばa）に適用すること。 複数個の自由変項に適用したい場合は複数回(∀真)を適用すること。
  • p.92 の問題2は妥当であることを示すために、元の式の否定から出発して、すべての枝分かれで×がつくことを確認すれば十分。
  • p.95 の問題は(i)すべての枝分かれで×がついた場合は、妥当と結論付け、 (ii)すべての規則を適用し尽くしても×が出ず、ひとつの枝に○がついた場合は、 その枝に出現しているアトム（P(a,b)とか〜F(b)）の情報からモデルを作り(その際、 元の式に出現する記号にはすべて意味を与えておくこと(2008/10/25))、その上で 前回の宿題（p.85 の問題(b)、p.92 の問題1）でやったように元の式が偽になることを正当化しておくこと。 （p.95 の問題中の A, B, C はアトムとみなしてよい (2008/10/25)）
  • 分析的反証法が終結しない場合は、(i)終結しない旨の説明と(ii)元の式を偽にするモデルを作って、 (iii)そのモデルの下で偽になることをチェックすること。

2008/10/28

• 述語論理への証明中心アプローチその1：述語論理への自然演繹の拡張の導入を行いました。
• 前回の宿題を採点しました。2008年度論理学演習成績をチェック。 コメントは以下の通り。
  • 式の分析は外側から！：∀x〜∃y C(x,y) のような形の式があった場合は内側の〜∃y C(x,y)から分析してはならない。 まずは一番外側の∀xから分析すること。また、∀xB(x)∨A(a) のような形の式の内側の∀xB(x)にいきなり（∀真）を適用してはならない。 （∨真）で枝分かれさせてから分析すること。
  • 枝分かれをキチンとすること！：（∨真）（ないし（& 偽）など）を繰り返し適用する必要がある場合は、 箒状に枝が分かれるように分析すること。
  • ∃xA(x)が偽となる真理条件：V(∃xA(x)) = F となるのは、すべてのV(x)の値につきV(A(x)) = F となる場合でありその場合に限ります。 「あるV(x) の値につきV(A(x)) = F」とはならないので要注意。「白いカラスが存在する」が偽になるのは、どんなカラスを見ても白くない場合であり、 近所で一匹の黒いカラスを見かけるだけでは不十分ということ。
  • いつ分析が終結するか：○をつける場合に気をつけないといけないのは、(∀真)規則を適用しつくしたか、ということ。 適用しつくしていないのに○をつけてはならない。分析した式の集合中の自由変項がどれだけあるかに注意しましょう。
• 今回の宿題は、p.104 の問題1(1)---(5)です。(∀入)規則の使い方に気をつけましょう。 不安な人は仮定の集合を書いて、自分の適用が正しいかをチェックしておくこと。 授業で「a is fresh in 1」と書いたのは、「自由変項 a が番号1の式に出現してしない」という意味です。
• タルスキの写真が見たい、という人は、Alfred Tarski @ MacTutor History of Mathematics archive へ。

2008/11/4

• 述語論理への証明中心アプローチその1：述語論理への自然演繹の拡張(続)と述語論理への証明中心アプローチその2：述語論理でのヒルベルト流公理系の導入を行いました。
• 前回の宿題を採点しました。2008年度論理学演習成績をチェック。 コメントは以下の通り。
  • 自由変項の取り方にかかわる条件（「a is fresh in 1」）が必要になるのは、（∃消）や（∀入）を後で使いたいという下心のある場合のみ! 例えば、今回の提出してもらったp.104 の問題1(1)では、（∀消）を使った場合にわざわざ「b is fresh in 1」と断ってしまうと、逆に、元の式が ∀xQ(x,b)⊃Q(b,b)という形の時に証明が通らないことになってしまうので注意が必要。
  • 自由変項の取り方にかかわる条件は　"a is fresh" と断るだけでなく、どこを睨んでどのような a をとってきたのかもきちんと書きましょう。
• 今回の宿題は、問題1(p.105)の(6)---(10) と、問題2(p.105)のプリントで配った改変版です。 また、以前のこの page の記録や自分の答案を見直して、命題論理で以前にした間違いを犯さないように気をつけましょう。

2008/11/11

• 述語論理への証明中心アプローチその2：述語論理でのヒルベルト流公理系の説明を行いました。
• 前回の宿題を採点しました。2008年度論理学演習成績をチェック。 コメントは以下の通り。
  • 全体的によくできていました。問題2の難しかった二問ができた人にはそれぞれ15点づつ点数を付けてあります。
  • （∃消）規則を使う際の自由変項についての条件が足りないケースがよくありました。模範解答で見せたように、 どことどこの式に対して fresh な自由変項を考えないといけないかに注意しましょう。
• 今回の宿題は、p.108 の問題1とp.108の問題2のプリントで配った改変版です。宿題に対する注意は以下の通り。
  • ヒルベルト流の公理系の証明をするには、「これをいうためには何が言えたら十分だろうか」を考える初めの段取りが大事です。
  • 今回の授業でも質問がありましたが、たとえ 〜A∨BとA⊃Bが命題論理の公理系で同値になることが分かっていても、∀x(〜P(x)∨Q(x)) と ∀x(P(x)⊃Q(x)) が述語論理の公理系で同値になることを前提してはいけません。また、これを命題論理で証明できること、すなわち S と書いてはなりません。使いたい場合は、きちんと公理系内の定理（|-の意味）になることを示しましょう。 （以下 11/17 補足）ただし、∨や& や∃の略記を⊃と〜と∀を使った元の表記に直すのはどの段階でしてもかまいません。
  • R2規則をあとで使いたい場合は、自由変項に関する条件を当の自由変項を導入した時点で「b is fresh in ---」のような形で必ず書いておくこと。
  • まだ述語論理の演繹定理は使ってはいけません。
  • （11/17 補足）「S」と書いてよいのは、形からトートロジーとわかるもの、です。たとえば、命題論理のヒルベルトタイプの公理系で証明した(T1)--(T14)や、 また自然演繹で証明したpp.49-51の論理式など。それ以外では、(A⊃〜B)⊃(B⊃〜A)など。 「形から判断してトートロジーになる」という部分に関しては正当化はいりません。 「形から判断してトートロジーになる」の部分を敷衍すれば、述語論理のアトムP(x)や∀xA(x)の形の式を命題論理のアトムとみなしたときに、トートロジーになる、ということ。 例えば、∀x〜〜P(x)⊃∀xP(x)は、「∀x〜〜P(x)」と「∀xP(x)」のそれぞれを別のアトム C, D と考えねばならず、C⊃Dとなるので、S と書いてはいけない。しかし、〜〜∀xP(x)⊃∀xP(x)だと、「∀xP(x)」を一つのアトム C と考えて、〜〜C⊃Cとなるので、Sと書いてよい。

2008/11/18

• 述語論理への証明中心アプローチその2：述語論理でのヒルベルト流公理系での演繹定理の説明を行いました。
• 前回の宿題を採点しました。2008年度論理学演習成績をチェック。コメントは以下の通り。
  • 問題1の(T17)：この問題では∀x(A(x)& B(x))⊃∀xB(x) を証明する必要があります。これを(T15)と引用してはいけません。 (T15)∀x(A(x)& B(x))⊃∀xA(x) とほぼ同様の仕方で証明しましょう。
  • R2の使い方：A⊃B(a)からA⊃∀xB(x)を導くのがR2（ただし x は A（と∀xB(x) に出現しない）です。 これを(i) A⊃〜B(a)からA⊃〜∀xB(x)を導く規則と考えたり、(ii)A⊃B(a) から B(a) ⊃∀xB(x)を導く規則とみなしてはいけません。 (i) は実際間違った推論ではありませんが、R2の使い方としては間違いです。(ii) を認めてしまうと、 次のような奇妙な主張が定理になってしまいます： A として a が出現しない矛盾 C& 〜C をとる。Bとしては犬(ポチ)を考える。犬(-) はもちろん「-が犬である」という一項述語。 すると、矛盾からは何でも言えるので、(C& 〜C)⊃犬(ポチ)が言える。ここでa はC& 〜Cに出現しないようにとったので、 (ii)を使って 犬(ポチ)⊃∀x犬(x) が証明できる。 もう一段階敷衍すれば、これはポチというたったひとつの個体が犬であることがわかっただけで、すべての個体が犬だ、 と結論づけることができてしまい、ナンセンス！
  • (A4) と (T16) の使い方: T16 を (P(a)⊃Q(a))⊃(∃xP(x)⊃∃xQ(x)) と使うのは間違い。正しい適用例なら、 定理のはずで（次回に学ぶ健全性によれば）妥当のはずだが、分析的反証法で反例が構成できてしまう。 同じように (A4) を 〜∀xP(x)⊃〜P(a)のような形で使うのもおかしい。これは対偶をとれば上の「R2の使い方」の箇所の最後で説明したナンセンスな例が 導けると言っているに等しい。参考：Be sensitive to the Form!.
  • 上の二つの例を見るだけでもわかりますが、不安なケースでは、 これは本当に定理や規則の適用例になっているのか、と懐疑的になること。 疑いを持ったら、(i)具体例（日本語でも簡単な算数の例でも）を入れて妙な帰結が出てこないかをチェックする、 (ii)定理の場合は必要なら述語論理の分析的反証法でチェックをしてみる、という労力を惜しまないように。 このような習慣をつけるようにするのもトレーニングの一環です。
• 今回の宿題は、テキスト p.110 の問題1と問題2です。問題1については以前配ったプリントの改変版で解いてください。 授業で説明していた演繹定理を使った証明のサンプルはこちら。 今回の答え合わせやこれを参考に解いてみてください。 問題1を解く際は、Sとしてどのような命題論理の定理（トートロジー）を念頭に置いているのかに気を配りましょう。 使えるトートロジーかどうか不安なら、分析的反証法でチェックしてみること。問題2はR2 をうまく使うのがポイントです。 質問はいつでもどうぞ。

2008/11/25

• NF の後片付けのため休講。

2008/12/2

• 述語論理への二つのアプローチの橋渡し：健全性と完全性定理を説明しました。
• 前回の宿題を採点しました。2008年度論理学演習成績をチェック。 長かった宿題もこれでおしまいです。みなさんどうもおつかれさまでした。コメントは以下の通りです。
  • カッコをきちんとつけよう: たとえば、A⊃B⊃Cをカッコをキチンと書かないと、 (A⊃B)⊃Cの意味で書いていたのに、いつの間にか A⊃(B⊃C) にすり替わっていた、ということが起こり得ます。 また、演繹定理を A |- B⊃C から |- A ⊃ (B⊃C) を導くために使ってもかまいませんが、 A |- B⊃C から |- (A⊃B)⊃C を導くためには使ってはいけません。この例ではわずか二文字分ですが、 カッコは間違いや思い込みを防いでくれる憎めない記号です。
  • 問題2は、うまくもってきた定理の式に b が出現しないことを断わっておきましょう。

2008/12/9

• 完全性定理の説明の続きとテューリングマシン・停止問題の概観を行いました。
• 次回は年明けの1/6です。スライドで余った決定問題の箇所は次回は扱いません。 しかし、質問があれば受け付けます。

2009/1/6

• 論理学演習の最終回で一階述語論理での等号の取り扱いを、モデル理論と証明論の両側面から説明しました。
• 今日の授業は自由参加にしましたが、今回の授業の資料がほしいという人は までメールすること。
• 授業の資料の練習問題を解いたが見てほしい、という人は上記アドレスにメールをして私にアポイントメントをとってください。
• 2008年度論理学演習成績にこれまでの成績の総合合計とAver.を掲載しました。

Katsuhiko SANO

Last Revised: 2011/2/3.