数理論理学 第1回

数理論理学 第1回
茨城大学工学部情報工学科
佐々木 稔
講義の概要
 証明、論理展開
 自然言語文を記号を用いて形式的に表現
 記号操作による推論
 学習目標
 命題論理による推論、証明方法の理解と実践
 1階述語論理による推論、証明方法の理解と実践
教科書、参考書
 「情報の論理数学入門」
 小倉久和、高濱徹行 著
 近代科学社
 2,700円+税
 「情報科学における論理」
 小野寛晰 著
 日本評論社
 3,300円+税
講義予定
第1回
第2回
第3回
第4回
第5回
第6回
第7回
第8回
命題
論理式
命題論理式の解釈
命題論理と公理系
命題論理と推論
三段論法と背理法
中間試験
述語論理とは
第9回述語、変数、量記号
第10回述語論理の論理式
第11回 述語論理の解釈
第12回 冠頭標準形
第13回 スコーレム関数と
スコーレム標準形
第14回 導出と推論
第15回 エルブラン定理と
導出原理
講義資料
 講義資料の配布はしません
 講義資料のダウンロードは可能
 http://sas.cis.ibaraki.ac.jp/logic/
 次回の講義資料
 前の週の金曜日ごろにアップロード予定
評価方法
 以下の項目を総合的に評価





出席(毎時間出す確認問題)
中間試験
期末試験
小テスト
レポート
 中間試験と期末試験の比率
 例年1:3(変化することもあります)
論理学と数理論理学(1)
 論理学とは
 人間の思考をモデル化
 文の真偽のみを着目した表現方法
 問題解決(推論や証明)を行う
 何のために使うのか?
 実世界の現象を論理的な側面から問題解決
 「真偽の定まった複数の文から、関連する文の真偽を
判定する」
 他人の問題解決を理解、整理する
論理学と数理論理学(2)
 数理論理学とは
 論理学をより数学的な理論で確立
 推論の機械化を志向
 数学的扱いを可能にするため、表現規則が存在
 命題論理、述語論理
 命題論理はブール代数と等価
 何のために使うのか?
 論理学と同じ
高校数学「集合と論理」
 命題
 基本的に数式が対象




条件(必要条件、十分条件)
「すべて」と「ある」
否定
逆、裏、対偶
大学での「数理論理学」
 命題論理学
 自然言語文による論理
 三段論法、背理法、帰納的帰結、トートロジー
 述語論理学
 命題から述語へ
 述語論理式の解釈
 述語論理式による推論と導出原理
 より深い論理へと続く…
命題
 真か偽のいずれかの値をとる、自然言語で表
現された文
 命題以外の文は真にも偽にもならない
 命題論理
 命題の真偽の組合せパターンを体系化
命題の例






太陽は西に沈む
今日は晴天である
6は素数である
太陽は恒星である
円周率は実数である
モナ・リザはレオナルド・ダ・ヴィンチが描いた
命題でない例







太陽の沈む方向
今日の天気
最小の素数
太陽は東に沈むかもしれない
明日は雨が降るだろう
21世紀中に世界の人口は倍になる
第二次世界大戦は1939年に始まった
例題
 「日本の首都は東京である」
 「今日はいい天気だ」
基本命題
 命題としてこれ以上分解できない命題






「この花は朝顔である」
「この花は朝顔である」
「今日は木曜日である」
「今日は金曜日である」
「この授業はレポートで成績を付ける」
「この授業は試験で成績を付ける」
複合命題
 基本命題を組み合わせて構成される命題
 「この花は朝顔である。
または、この花は朝顔である。」
 「今日は木曜日か、金曜日である」
 「この授業はレポート、かつ、試験で成績を付け
る」
 「今日も明日も雨は降らない」
 「今日か明日、雨が降る」
命題変数
 命題を変数として表現
 命題の真理値のみを考える
 「真」の場合は “T” (True)
 「偽」の場合は “F” (False)
 基本命題変数
 p, q, r, …(小文字の記号)
 命題変数
 P, Q, R, …(大文字の記号)
 「太陽は西からのぼる」を命題 P とする
 P=F
 「円周率は実数である」を命題 Q とする
 Q=T
 「円周率は有理数である」を命題 R とする
 R=F
 命題 QR という表記は存在しない