F1,F2,…,Fn - rabbit.mns.kyutech.ac.jp

応用数理D （平成２３年度）
各回の目次
１回目の目次
（10月６日）
• シラバスの説明
• 単位などの件
• 命題論理と述語論理のお話
（１）命題変数、ｐやｑと論理記号：∧、∨、￢、⇒。
（２）文「３＋５＝１０ならば、２＝５」は論理的に正しい。
（３）論理的帰結：複数の文（論理式）から、特定の文
（論理式）を結論付ける。
（４）他国語のウェブのページを理解するためには。
（５）命題論理から述語論理へ
（６）論理型プログラム言語
２回目の目次
（10月１３日）
（１）命題論理の論理式
（２）命題論理式の真偽
（３）２つの命題論理式が等しい
（４）命題論理式の書換え
３回目の目次
（10月２０日）
（１）命題論理式の標準形
（２）表で与える論理関数を標準形で記述
（３）論理式の解釈、論理式のモデル、
恒真式、恒偽式、充足可能、
その判定法
（４）論理的帰結と基本定理、具体例
４回目の目次
（10月２７日）
（１）論理的帰結と基本定理、具体例
（２）演習
（３）論理における形式論、意味論
５回目の目次
（１１月１０日）
（１）学会で出張のため、TAに演習を行っ
てもらう
（２）時間内に課題を解いて、提出する
６回目の目次
（１１月１７日）
（１）５回目の課題の解答例
（２）種々の手法による論理的帰結の判定
（A)真偽値表ですべての場合を調べる
（B)完全性定理に基づいて証明する
（C)背理法による（導出による手法）
（３)導出原理による方法
７回目の目次
（１２月１日）
（１）導出法（論理式の恒偽性判定法）
F1∧F2∧…∧Fｎ⇒G（恒真式）
（＊）F1∧F2∧…∧Fｎ∧￢G（恒偽式）
（２） （＊）を節形式に直す。
（＊）の中にΦ∨ｐとψ∨￢ｐ
があれば（＊）＝（＊）∧（Φ∨ψ）。
（３） 逐次追加した式で qと￢ｑが見つかれ
ば充足不能、つまり恒偽
８回目の目次
（１２月８日）
（１）F1:b∧ｃ⇒a、F2:b⇒ｄ、F3：ｆ∧e⇒ｃ
F4:f⇒ｄ、F5：ｆ、F6：e のとき、aは
F1∧Ｆ２∧…∧Ｆ６の論理的帰結？？
（２）定理式の定義とヒルベルトの公理系
（３）Ａ⇒Ａの証明
９回目の目次
（１２月１５日）
（１）⊢ Fｎ と Ｇ⊢ Fｎ
（２）Ｐ⊢ Ｑ⇒Ｐの証明
（３）演繹定理と逆演繹定理
（４）Ａ⇒Ｂ，Ｂ⇒Ｃ ⊢ Ａ⇒Ｃ
（５）Ａ⇒(Ｂ⇒Ｃ), Ｂ ⊢ Ａ⇒Ｃ
（６）⊢ ￢￢Ａ⇒Ａと⊢ Ａ⇒￢￢Ａ
（７）⊢ （￢Ｂ⇒￢Ａ）⇒（Ａ⇒Ｂ）
（８）⊢ （Ａ⇒Ｂ）⇒（￢Ｂ⇒￢Ａ）
１０回目の目次
（１２月２２日）
１．定理の定義、証明の定義、
具体的な証明
２．命題論理の完全性定理
１１回目の目次
（１月１２日）
（１）完全性定理の直観的意味
（２）他国語のウェブのページを理解するためには
論理は言語に依存するものではない
（３）命題論理から述語論理へ
（４）述語論理におけるアルファベット、論理式
（５）述語論理式の解釈
健全性と完全性
がんの治療（目的）とがんの薬の要件（処理方法）
効果を上げるために強い成分にする
＝＞強い成分にすると副作用で髪が抜ける
（薬の完全性は増加、健全性は減少）
副作用を抑えるために成分を弱める
＝＞治療の効果が下がる
（薬の完全性は減少、健全性は増加）
がんだけに作用し、副作用がない薬
(健全で完全な薬）
健全性と完全性 （オッカムの剃刀）
ひげを剃る（目的）とひげ剃り要件（処理方法）
よく剃れるように剃刀を鋭くする
＝＞ひげは剃れる、皮膚も切る
（剃刀の完全性は増加、健全性は減少）
皮膚をけがしないようにすると
＝＞ひげは剃れない
（剃刀の完全性は減少、健全性は増加）
ひげだけを剃り、皮膚を切らない剃刀
(健全で完全な剃刀）
健全性と完全性に関する内容
チキンゲーム
服のサイズ
単位の取り方
政治と議会の過半数
健全性と完全性 （論理的帰結の判定）
論理的帰結・恒真性（目的）と証明手順・公理（処理方法）
QはF1,F2,…,Fnの
論理的帰結？
導出法による
証明手続き
（健全かつ完全）
論理的帰結
恒真式の判定
F1∧F2∧…∧Fn⇒Q
が恒真式
ヒルベルトの公理系
（健全かつ完全）
１２回目の目次
（１月１９日）
（１）述語論理の概要（wikipediaから、再度）
（２）述語論理におけるアルファベット、論理式
（３）述語論理式の解釈
(1) （∀ｘ）P（ｘ） (2)（∃ｘ）￢P（ｘ）
(3) （∀ｘ）（P（ｘ）⇒Q（ｆ（ｘ）,a))
(4) （∀ｘ）P（ｘ）∧ （∃y）￢P(y)は恒偽
(5) （∀ｘ）P（ｘ）⇒ （∃y）P(y)は恒真
(6) Q(a)はF1、F2の論理的帰結
F1:（∀ｘ）（P（ｘ）⇒Q（ｘ）），F2:P(a)
１３回目の目次
（１月２６日）
（１）述語論理式の定義、解釈、恒真式、
恒偽式
（２）述語論理における論理的帰結
（３）述語論理における完全性定理
（４）述語論理に帰納法と数論の公理を
追加すると、完全性定理は成立しない。
不完全性定理が成立。
１４回目の目次
（２月２日）
（１）述語論理式を節形式に書き換える。
（２）単一化（ﾕﾆﾌｨｹｰｼｮﾝ）による導出法
（３）ホーン節に限定した場合の線形導出
（４）論理プログラムの例