情報ネットワーク学基礎 1 講義ノート （4 月 16 日） 【1】 氏名： 記号論理学入門 目的 • 数学など厳密な論理が要求される場合の基本 ◦ 論文を読む，書くための基礎体力 ◦ 分かりやすく，正確なプログラムを書くための基礎体力 • 論理とは何か，論理そのものの理解 • 論理は物事を正しく伝えるために必須の言語．納得して使えるようになることを目指す． ◦ 独特な言い回しがあるので，慣れてほしい．日本語（英語）として，正しく使えるように．そのた めには「自分の頭で考えた」日本語（英語）を常に念頭に置きながら学習すること． 概要 §1 命題論理 (propositional logic)：∀, ∃ などを使わない論理 ［例］(p ⇒ q) ∨ r ⇒ q ∧ r §2 述語論理 (predicate logic)：∀, ∃ などを使う論理 ［例］∀x ∃y, p(x) ∧ q(y) ⇒ r(x, y) ※ 適宜，自然言語（日本語・英語）との対応を考える． §1 [1] 命題論理 (propositional logic) 命題とは • 真偽を判定することができる文（式）1 ． ［例題］以下は命題といえるか？ (1) 2 + 5 = 4 である． √ (2) 2 は有理数である． (3) A さんは背が高い. (4) A さんは B さんより背が高い. (5) π は十進法表示したときに 3141592 が現れる. 1 「正しい（真である）文」ではないので，勘違いしないように（常に真である文（トートロジ−，恒真式) については後述）． 1 [2] 記法 基本的な真理関数（truth function） 記号 名称 読み 英語 例 — Simple proposition Negation Conjunction Disjunction Conditional Equivalence — p, q, r, . . . ¬ ∧ ∨ ⇒ ⇔ [3] 真理値 (truth value) 以下では一般に， • 真（true） ：1, T, ⃝ • 偽（false)：0, F, × などで表す．p, q, r, . . . は 0 または 1 を表す変数になる． [4] 真理値表 (truth value table) p 0 0 1 1 q 0 1 0 1 ¬p p∧q p∨q p⇒q p⇔q 注意 1 日常語の「または」と論理の「または」は違う． ［例］このセットには，コーヒーまたは紅茶がサービスでつきます. • 日常語：どちらか一つだけ（排他的選言，または排他的論理和） ；つまりコーヒーか紅茶，どちらかしか 飲めない． • 論理：どちらか一方，両方でもよい（両立的選言） ；コーヒーと紅茶の両方を飲む事ができる． 注意 2 p が「偽」なら p ⇒ q は q の真偽に関係なく真． ［いくつかの解釈］ • 日常語：もし p ならば q である． ◦ 因果的条件（p が q より時間的に先） ［例］宝くじに当選したら食事をごちそうするよ． ◦ 同値（p と q の意味がほぼ同じ） ［例］いい子にしてたらおやつをあげるよ． • 数学： （p ならば q ） ［例］ 「すべての実数 x について，x ≥ 2 ならば x2 ≥ 4 である． 」は正しい．では，x = 0 や x = −2 のと 2 き，命題は真であるか．また， 「すべての実数 x について，x ≥ 4 ならば x ≥ 2 である． 」はどうか． Cf. 対偶は常に真なり． 2 p ⇒ q についての補足 [5] p ⇒ q の真理値表のうち (i) p が真かつ q が真、および (ii) p が真かつ q が偽に対しては、真理値は通常の意 味で与えられる．そこで以下の表１が得られる．これから表１の Ⓢ と ® に入る真理値を他の真理関数との関 係から決定しよう． p 0 0 1 1 表１ q 0 1 0 1 p⇒q Ⓢ ® 0 1 p 0 0 1 1 表２ q 0 1 0 1 q⇒p Ⓢ 0 ® 1 p 0 0 1 1 表３ q 0 1 0 1 p⇒q Ⓢ 1 0 1 q⇒p Ⓢ 0 1 1 (p ⇒ q) ∧ (q ⇒ p) Ⓢ∧Ⓢ 0 0 1 (a) まず p ⇒ q の逆の意味 q ⇒ p を考えよう．表２よりもし ® が 0 だと p ⇒ q と q ⇒ p が全く同じとなっ てしまうので、® は 1 と決まる． (b) 次に (a) の結果を入れた表３を見てみると p ⇒ q と q ⇒ p から (p ⇒ q) ∧ (q ⇒ p) の真理値表を眺める と，この真理値は p ⇔ q つまり同値と同値となることが期待される．これより Ⓢ が 1 と決定され，さきに導 入した真理値表と同じとなる． 命題論理の論理式 (well formed formula: wff ) [6] • p, q, r, . . .：式 • A, B が式なら， ［例］A = ¬p ∨ q ◦ 式の否定：¬(A) ◦ 式同士の連言：(A) ∧ (B) ◦ 式同士の選言：(A) ∨ (B) ◦ 式から式への含意：(A) ⇒ (B) ◦ 式同士の同値：(A) ⇔ (B) も式である 2 ． 注意 3 記号の強弱に注意． (1) ¬ (2) ∧, ∨ (3) ⇒ (4) ⇔ の順に弱くなる. ルールとしては, 括弧をはずすと一意的に決まらない場合ははずせない. 具体的には, i) （）内が要素式または否定記号が一番外側についた論理式の場合には（）を省略する. ［例］¬(¬(A)) は ¬¬(A) と書く. ii) 同じ強弱間の記号 ∧, ∨ が並ぶ場合についてははずせない. iii) (A) ⇔ (B) の同値記号の場合は常に（）をはずす. 2 括弧 () がついているのは，A, B が式だから． 3 これらはあくまで, 慣習なので他の流儀もある. ［例］(¬(p) ∨ ((q) ∧ (r))) ⇒ (p ∨ q) は ¬p ∨ (q ∧ r) ⇒ p ∨ q と書いて良いが，これ以上は括弧を外すことが 出来ない． ［例題］以下の式 に括弧（）を入れると何通りにあらわせるか. (1) p ∨ q ⇒ r (2) ¬p ∧ q ∨ r (3) ¬p ∧ ¬q ⇒ r [7] トートロジー (恒真命題，tautology) 定義：命題変数の真理値が何であっても常に真理値が 1 になる式 3 ． ［トートロジーの例］ (1) p ⇒ p (一般には (A) ⇒ (A)) (同一律, law of identity) p 0 1 p p⇒p (2) p ∨ ¬p (排中律, law of the excluded middle) p 0 1 ¬p p ∨ ¬p (3) p ⇔ ¬¬p (二重否定, law of double negation) p 0 1 ¬p ¬(¬p) p ⇔ ¬¬p (4) ¬(p ∧ ¬p) (矛盾律, law of contradiction) p 0 1 (5) (6) (7) ¬p p ∧ (¬p) ¬(p ∧ ¬p) i) p ∧ p ⇔ p (巾等律１, idempotent law) ii) p ∨ p ⇔ p (巾等律２, idempotent law) i) p ∧ q ⇔ q ∧ p (交換律１, commutation law) ii) p ∨ q ⇔ q ∨ p (交換律２, commutation law) i) p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r (結合律１, associative law) ii) p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r (結合律２, associative law) 3 命題変数の真理値が何であっても常に真理値が 0 になる式は矛盾命題 (矛盾式, contradictory wff) というが，トートロジーを否 定すればよいのでここでは議論しない．日常では通常, トートロジーを同義語反復の意味で使用するが，ここでの定義は違う． 4 (8) i) ¬(p ∧ q) ⇔ ¬p ∨ ¬q p 0 0 1 1 q 0 1 0 1 (ド・モルガンの法則 1, de Morgan’s law）4 p∧q ¬(p ∧ q) ¬p ii) ¬(p ∨ q) ⇔ ¬p ∧ ¬q ¬q ¬p ∨ ¬q ¬(p ∧ q) ⇔ ¬p ∨ ¬q (ド・モルガンの法則 2, de Morgan’s law) ［例題］真理値表を使わずに (8)–ii) を示せ． (9) p ⇒ q ⇔ ¬p ∨ q (10) (p ⇔ q) ⇔ (p ⇒ q) ∧ (q ⇒ p) (必要十分条件, necessary and sufficient condition) (11) p ⇒ q ⇔ ¬q ⇒ ¬p (12) (対偶, law of contraposition) i) p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r) (分配法則 1, distributive law) ii) p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) (分配法則 2, distributive law) (13) 三段論法 (syllogism) i) p ∧ (p ⇒ q) ⇒ q (前件肯定式, modus ponens) ii) (p ⇒ q) ∧ (q ⇒ r) ⇒ (p ⇒ r) (推移律, transitive law) iii) ¬p ∧ (p ∨ q) ⇒ q (選言的三段論法, law of disjunctive syllogism) (14) (p ⇒ q) ∧ (q ⇒ r) ⇒ ((p ∨ q) ⇒ r) (15) (16) (17) (構成的両刃論法, law of constructive dilemma) i) p ∧ (p ∨ q) ⇔ p (吸収律１, absorptive law) ii) p ∨ (p ∧ q) ⇔ p (吸収律２, absorptive law) i) p ∧ q ⇒ p (縮小律, law of simplification) ii) p ⇒ p ∨ q (拡大律, law of addition) i) (p ⇒ (q ⇒ r)) ⇒ (p ∧ q ⇒ r) (移入律, law of importation) ii) (p ∧ q ⇒ r) ⇒ (p ⇒ (q ⇒ r)) (移出律, law of exportation) (18) p ⇒ q ∨ ¬q (19) p ∧ ¬p ⇒ q (20) p ⇒ (q ⇒ p) (21) (p ⇒ (q ⇒ r)) ⇒ ((p ⇒ q) ⇒ (p ⇒ r)) (22) ((p ⇒ q) ⇒ p) ⇒ p (23) p ∨ (p ⇒ q) (24) 最後に I をトートロジー, O を矛盾式とするとき A ∧ I ⇔ A, A ∨ I ⇔ I, A ∨ O ⇔ A, A ∧ O ⇔ O 4 Augustus de Morgan, 1806–1871 (英). ド・モルガンの法則と分配法則については以下のより一般の形が成り立ち，よく使用され る．¬(p1 ∧ p2 ∧ · · · ∧ pn ) ⇔ ¬p1 ∨ ¬p2 ∨ · · · ∨ ¬pn , ¬(p1 ∨ p2 ∨ · · · ∨ pn ) ⇔ ¬p1 ∧ ¬p2 ∧ · · · ∧ ¬pn および q ∨ (p1 ∧ p2 ∧ · · · ∧ pn ) ⇔ (q ∨ p1 ) ∧ (q ∨ p2 ) ∧ . . . (q ∨ pn ), q ∧ (p1 ∨ p2 ∨ · · · ∨ pn ) ⇔ (q ∧ p1 ) ∨ (q ∧ p2 ) ∨ . . . (q ∧ pn )．証明は各自試みよ． 5 [8] 演習問題 問題 1 ［トートロジーの例］について，以下の方針でトートロジーであることを確認せよ．ただし，同値変形で示 す場合には以下の注意を守ること． • 証明したいトートロジーより若い番号の式は（証明されたと思って）使って良い．ただし，(24) は使用 してよい． • 各式変形では，どのトートロジーを用いたか，式番号を付記せよ． 問 1-1 (9), (17)–i) を真理値表で示せ． 問 1-2 (11) を同値変形で示せ． 問 1-3 (12)– i) を真理値表で，また (12)– ii) を同値変形で示せ． 問 1-4 (13)–ii), iii) を示せ（方針は問わない）．また, 日本語（英語）の例を作って確かめよ. 問題 2 問 2-1 次の真理値表を与える論理式 A(p, q) を以下の方針で見つけよ. (1) まず p ∨ q, p ∨ ¬q, ¬p ∨ q, ¬p ∨ ¬q の真理値表を調べよ， (2) それらの連言（∧）または選言（∨）による組み合わせを考えて A(p, q) を見つけよ． (3) 次に ¬p ∧ ¬q, ¬p ∧ q, p ∧ ¬q, p ∧ q の真理値表を調べ，それらの連言，選言による組み合わせで A(p, q) が書けるか調べよ． (4) 最後に ¬A(p, q) と得られた解答との関係を考察せよ． p 0 0 1 1 q 0 1 0 1 A(p, q) 0 1 1 0 問 2-2 次の真理値表を与える論理式 A(p, q, r) を問 2-1 を参考にして次の形で書け． (1) A1 ∧ A2 ∧ · · · ∧ An ．ただし，A1 , A2 , . . . , An は p, q, r および ¬p, ¬q, ¬r の選言． (2) A1 ∨ A2 ∨ · · · ∨ An ．ただし，A1 , A2 , . . . , An は p, q, r および ¬p, ¬q, ¬r の連言． p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 6 A(p, q, r) 0 1 0 0 0 1 1 1
© Copyright 2024 ExpyDoc
