1 ICT Foundation 命題論理の基礎 Copyright 2010, IT Gatekeeper Project Ohiw a Lab. All rights reserved.

Size: px

Start display at page:

うきえつくとの
4 years ago
Views:

2 2 論理学を学習する理由コンピュータ科学の基礎としてコンピュータに使われている論理回路を理解するための基礎となります今回は基礎的な論理回路を紹介する程度にとどめるプログラミングにも重要な概念大学生の一般常識として更に詳しく学習したい人は関連科目の履修をオススメします色々なことに役に立つツールとして入社試験に多く採用されているSPI(Synthetic Personality Inventory) では論理学の基礎的な問題が出題されている検索エンジンを用いたWebの検索にも論理式の考え方が応用できる

3 3 命題とは何か真偽 ( 真理値 ) が問題となりうるような肯定形の記述文 ( 命令文や疑問文は除く ) のこと鯨は哺乳類だ意味が明瞭なのでアリストテレスは偉い偉いが不明確なので命題の例私は学生である犬は四つ足である昨日学校は休講だったあなたは何歳ですか? 部屋を片付けなさい

4 4 単純命題と複合命題単純命題接続詞や否定詞を含まない肯定形の命題例 : 私は学生である複合命題接続詞 ( かつ, または, ならば, と等しい ) や否定詞 ( でない ) を含む命題例 : 太郎は部屋にいる, かつ, 次郎も部屋にいる今回はと等しいは扱いません

5 5 複合命題の例 1 でない ( 否定 ) 例 : 太郎は部屋にいない太郎は部屋にいる次郎は部屋にいるかつ ( 連言論理積 ) 例 : 太郎は部屋にいる, かつ, 次郎も部屋にいる太郎は部屋にいる次郎は部屋にいる Q

6 6 複合命題の例 2 または ( 選言論理和 ) 例 : 太郎は部屋にいる, または, 次郎も部屋にいる太郎は部屋にいる次郎は部屋にいるならば ( 仮言かげん ) 例 : 太郎は部屋にいる, ならば, 次郎も部屋にいる太郎は部屋にいる次郎は部屋にいる

7 7 選言に関する補足太郎は部屋にいる, または次郎は部屋にいる太郎, 次郎ともに部屋にいる場合, この複合命題は真となる ( 両立的選言 ) 日本語には 2 種類のまたはの使い方があり, 命題論理では通常両立的選言を採用する喫茶店のランチメニューにコーヒーまたは紅茶と記載されている場合, 両方注文することはできない ( 排他的選言 ) 日本国のパスポートは, 日本国籍を持つ者または日本国籍を持つ者と結婚している者に発行されるの場合, 日本国籍を持ち, かつ日本国籍を持つ者と結婚している場合でもパスポートは発行される ( 両立的選言 )

8 8 仮言に関する補足例えば, 明日が国民の祝日ならば, 情報基礎の授業は休講であるという複合命題について, 以下の 4 通りの組み合わせがありうる (1) 明日は国民の祝日なので, 授業が休講になる場合真 (2) 明日は国民の祝日だが, 授業が行われる場合偽 (3) 明日は国民の祝日でないが, 授業が休講になる場合真 (4) 明日は国民の祝日でないが, 授業が行われる場合真冒頭の複合命題は明日が国民の祝日である場合についてのみ授業が休講であると言明しており, 明日が国民の祝日でない場合については何も言明していないこのため,(3)(4) は真となる

9 9 真理値表太郎は部屋にいる, かつ, 次郎も部屋にいるという複合命題について真偽の組み合わせを表にまとめる太郎は部屋にいる次郎は部屋にいる太郎は部屋にいる, かつ, 次郎も部屋にいる真真真真偽偽偽真偽偽偽偽 ( いちいち文章を書くのは大変なので ) 太郎は部屋にいるを P, 次郎は部屋にいるを Q とし, 真を 1, 偽を 0 で表す P Q P かつ Q

10 10 真理関数複合命題の真偽はそれを構成する単純命題の真偽に応じて一通りに決まる P Q P かつ Q 複合命題の真偽は単純命題の真偽の関数になっている真理値表は真理関数を表現している

11 11 基本的な真理関数のまとめ略号一覧 ( これ以外の記法もある ) 否定 : P (Pではない) 連言論理積 (AND):P Q (PとQどちらも) 選言論理和 (OR):P Q (PとQどちらかが) ならば ( 仮言 ):P Q (PならばQ) P Q P P Q P Q P Q

12 演習 1 変換装置 12 0 と 1 の入力を次の規則に基づいて変換し出力する装置 P と Q がある P: 同時に入ってきた信号 X1 と X2 の少なくとも一方が 1 のとき 1 を出力し, 両方とも 0 のときは 0 を出力 Q: 同時に入ってきた信号 X1 と X2 の両方とも 1 のときのみ 1 を出力し, いずれかが 0 のときは 0 を出力する. 装置 P,Q を以下のように繋いだ回路について考える. ある X1 と X2 の値を, それぞれ P,Q に入力した時, 入力値と出力値の正しい組み合わせはどれか ( 複数選択可 ) (X1,X2) (X1,X2) P Q P Y a) (X1,X2,Y)=(1,0,1) b) (X1,X2,Y)=(1,0,0) c) (X1,X2,Y)=(0,1,1) d) (X1,X2,Y)=(0,1,0)

14 14 検索エンジン Web ページを検索するサービスを提供するシステムのこと全文検索型キーワードを入力して検索するキーワードを含むページを検索結果として表示する例 :Google ではキーワードを入力して検索するディレクトリ型キーワードごとに Web ページを分類してある例 :Yahoo ではカテゴリから Web ページを検索できる

15 15 論理式を用いた検索 Google 等の全文検索式の検索サービスでは, 論理式を用いると効率のよい検索を行える Google の検索条件フォーム検索に専用のフォームが用意されている場合もあるが, 論理式で記述すると, 簡単に書ける

16 論理式を用いた検索 1 AND 検索 16 AND 検索 Keyword1 AND Keyword2 のように入力 2 つのキーワードがともに含まれるページが検索できる検索結果を絞り込むときには, キーワードを AND で追加 ( 通常はスペースで AND を表現できるので, と入力する ) 例 : デジタル一眼最安値ソニー Keyword1 Keyword2

17 論理式を用いた検索 2 OR 検索 17 OR 検索 Keyword1 OR Keyword2 のように入力 2つのキーワードのうち少なくともどちらかが含まれるページが検索できる例えば,1 つのものに 2 つ以上の名前があり, その両方を網羅した検索を行いたい場合に利用する例 : 湘南藤沢キャンパス OR SFC Keyword1 Keyword2

18 論理式を用いた検索 3 NOT 検索 18 NOT 検索 Keyword1 NOT Keyword2 のように入力を含むページの中から, が含まれるページを取り除いたページを検索できる正式には,Keyword1 AND NOT Keyword2 と書くが, 通常 AND は省略される Keyword1 Keyword2

20 20 SPI への応用 Synthetic Personality Inventory 採用人事の判断材料として幅広く企業が取り入れている検査能力検査と性格検査をあわせ持った, 高度な個人の資質を総合的に把握する検査のこと能力検査と性格検査があり, 能力検査に命題や推理についての出題がある

21 21 ならばにおける裏逆対偶もともとの命題 :P Q 逆 :Q P 裏 : P Q 対偶 : Q P もともとの命題が真のとき, 対偶だけが常に真である例 : 私がキャンパスにいるならばキャンパスに人がいる

22 22 三段論法前提 1 P Q ソクラテスは人間だ前提 2 Q R 人間は皆死ぬ結論 P R ソクラテスは死ぬ

23 演習 2 SPI の問題例 1 を解いてみよう 23 将棋が好きな人は, 数学が得意であるという命題を真とするとき, 次の内容が正しいものはどれか a) 将棋が好きでない人は, 数学が苦手である b) 将棋が好きな人は, 数学が好きである c) 数学が得意な人は, 将棋が好きである d) 数学が苦手な人は, 将棋が好きではない e) 将棋が好きな人は, 囲碁が好きである各選択肢は将棋が好きな人は, 数学が得意であるの裏逆対偶のどれにあたるか手とり足とり就活 Book SPI 問題集 BEST COLLEGES 就職部著ミネルヴァ出版企画 2006

24 演習 3 SPI の問題例 2 を解いてみよう 24 次のことがいえるとき, これらから確実に分かるのはどれかロマンチストは, 詩人である星が好きな人は, 小鳥や花が好きである花が好きな人は, ロマンチストである a) 小鳥が好きな人は, 花が好きである b) 花が好きな人は, 星が好きである c) 詩人は, 花が好きである d) 小鳥が好きな人は, ロマンチストだ e) 星が好きな人は, 詩人であるヒント : 三段論法の適用, 対偶の変形も使う手とり足とり就活 Book SPI 問題集 BEST COLLEGES 就職部著ミネルヴァ出版企画 2006

25 演習 4 正直者の囚人は誰か当ててみよう 25 ある刑務所に必ず正直に答える者と, 必ず嘘をつく者が居た看守は正直者を選別し恩赦を与える為, 囚人達に誰が嘘つきで誰が正直者か名乗り出ろと問いただしたすると, ある収容房の 3 人組は以下のように答えた A の発言 : B の発言 : B は嘘つきなのです. 私は正直者ですから真実のみを伝えます C が嘘つきだ. 私こそ正直者ですよ Cの発言 : AとBこそ嘘つきだよ. 私? 私は勿論正直者ですとも A,B,C のそれぞれについて, 正直者か嘘つきかどうかを答えよ

26 26 参考図書論理学野矢茂樹著, 東京大学出版会論理学をつくる戸田山和久著, 名古屋大学出版会真理証明計算 : 論理と機械内井惣七著, ミネルヴァ書房

融合規則 ( もっとも簡単な形, 選言的三段論法 ) ll mm ll mm これについては (ll mm) mmが推論の前提部になり mmであるから mmは常に偽となることがわかり ll mmはllと等しくなることがわかる機械的には分配則より (ll mm) mm (ll mm) 0 ll m

融合規則 ( もっとも簡単な形, 選言的三段論法 ) ll mm ll mm これについては (ll mm) mmが推論の前提部になり mmであるから mmは常に偽となることがわかり ll mmはllと等しくなることがわかる機械的には分配則より (ll mm) mm (ll mm) 0 ll m 知識工学 ( 第 5 回 ) 二宮崇 ( ninomiya@cs.ehime-u.ac.jp ) 論理的エージェント (7 章のつづき ) 証明の戦略その 3 ( 融合法 ) 証明の戦略その 1 やその 2 で証明できたときはたしかにKKKK ααとなることがわかるがなかなか証明できないときや証明が本当にできないときには KKKK ααが成り立つのか成り立たないのかわからないまたどのような証明手続きを踏めば証明できるのか定かではない