数理論理学第2回.pptVIP

* * * * * * * * * 数理論理学　第8回 茨城大学工学部情報工学科 佐々木　稔 前回までのあらすじ 命題論理と推論 三段論法 論理的帰結 背理法 クラスによる三段論法の表現 配布資料は以下からダウンロードできます http://sas.cis.ibaraki.ac.jp/logic/ 前回の問題1 以下の前提から命題変数を記号で表し、論理式を導きなさい。また、これらの前提から得られる結論を導き出しなさい． 死刑を怖れる者がいるならば、死刑に犯罪抑止力がある。 死刑に犯罪抑止力があるならば、死刑は正義である。 誤審が防止できていないならば、死刑は正義ではない。 P:「死刑を怖れる者がいる」 Q:「死刑に犯罪抑止力がある」 R:「死刑は正義である」 S:「誤審は防止できている」 死刑を怖れる者がいるならば、死刑に犯罪抑止力がある。 P?Q 死刑に犯罪抑止力があるならば、死刑は正義である。 Q?R 誤審が防止できていないならば、死刑は正義ではない。 ～S?～R 対偶を取って、R?S 三段論法により、 P?S 「死者を怖れる者がいるならば、誤審は防止できている」 前回の問題2 次の論証から命題変数を抜き出し、ベン図を用いて関係を図示せよ。また、この論証が妥当かどうか判定せよ。 「彼の言うことはすべてナンセンスだ。ナンセンスはすべて卑劣だ。彼の言うことはすべて卑劣だ。」 P:「彼の言うこと」 Q:「ナンセンスである」 R:「卑劣である」 P Q R 妥当である 今週のお題 述語論理 命題論理の復習 命題を記号として表現 ブール代数と同様の演算が可能 演算を繰り返して推論を行う 肯定式 否定式 三段論法 背理法 三段論法の復習 前提1：「人間はいつか死ぬ」 前提2：「ソクラテスは人間である」 結論：「ソクラテスはいつか死ぬ」 命題記号での記述 命題 P ：「人間はいつか死ぬ」 命題 Q ：「ソクラテスは人間である」 結論 R ：「ソクラテスはいつか死ぬ」 すべて基本命題（原子命題）で表すしかない (P∧Q)?R 恒真式ではないが、論証は正しい 命題論理の問題点 「ソクラテス」以外でも論証は正しい 命題：「X は Y である」 命題：「Y は Z である」 結論：「X は Z である」 命題論理の問題点 妥当な論証をすべて表記できない 命題の内部構造をより詳細に分析する 述語論理 命題にある固体に着目 「固体について何を述べているか」 例 「すべての日本人は人間である。」 「すべての固体について、その固体が日本人ならば人間である。」 「何を述べるか」の部分を固定する 述語 述語 述語 個体間の関係や性質を表す 例 「太陽は西に沈む」 「太陽」と「西」が「沈む」という関係で結ばれる 「６は素数である」 「素数である」という性質が「６」に含まれる 関数の形で表記し、真偽を返す 沈む（太陽, 西）、素数（6）、人間（日本人） 述語の変数 固体定数 述語の引数が特定の値 a, b, c, ??? 固体変数 述語の引数が任意の固体定数の代表 x, y, z, ??? 固体定数と固体変数 沈む（太陽, 西） a:「太陽」、b:「西」 沈む（a, b） 沈む（x, y） 素数（6） c:「6」 素数（ c ） 素数（ x ） 2項述語 1項述語 述語記号 述語記号 述語そのものを記号で表現 P, Q, R, ??? 例 沈む（太陽, 西） P:「沈む」、a:「太陽」、b:「西」 P (a, b) 引数が任意の値の場合、 P (x, y) 述語論理と命題論理の違い 文の内部構造を表現できる 例 「鯨は哺乳類である」 「鯨は水棲動物である」 「鯨は水棲の哺乳類である」 鯨?哺乳類 鯨?水棲動物 鯨?哺乳類∧水棲動物 哺乳類(鯨) 水棲動物(鯨) 哺乳類(鯨)∧水棲動物(鯨) 命題論理 述語論理 高階述語 変数は述語であってもよい 引数に述語がない述語論理 第1階述語論理 引数に述語が1つ存在する述語論理 第2階述語論理 引数に述語が(n-1)個存在する述語論理 第n階述語論理 この授業では第1階述語論理を対象とする 高階述語の例 「x は y の父親である」 父親(x, y) 「z は w を知っている」 知っている(z, w) 「z は x が y の父親であることを知っている」 知っている(z, 父親(x, y)) 練習問題 次の文を述語を用いて論理式で表現しなさい。 x が y 以下で、y が z 以下ならば、x は z 以下である。(「x が y 以下である」を P(x, y) とする) 花子と桃子は姉妹ではない。(「x と y は姉妹である」を Q(x, y) とする) Bob は情報工学科所属であれば、機