計算機基礎論

Size: px

Start display at page:

Download "計算機基礎論"

そうすけさどひら
5 years ago
Views:

1 命題論理 ( 教科書 :3.1~3.5) 藤田聡 ( 広島大学 )

2 ガイドライン命題論理 ( 今週 ) A ならば B であるという形の論理式を用いて推論を行う ( 例 : 否定論理和論理積 ) 事実の集まりから求めたい結論を正しく導けるかを問う ( 参考 : 推理小説 ) 述語論理 ( 次週 ) 命題論理で表現されることに加えてすべての何某についてという表現が許された論理体系すべての整数についてという表現も可

3 今日の授業内容命題がどのようなものかを理解する命題論理で用いられる基本演算子含意について正しく理解する ( 真理値表 ) 逆裏対偶必要十分条件命題的同値という考え方を理解する必要十分という考え方がわかることが重要

4 風が吹くと風が吹くと砂ぼこりが出る砂ぼこりが出ると盲人がふえる盲人は三味線をひくのでそれに張る猫の皮が必要で猫が減る猫が減ると鼠がふえて桶をかじる桶がかじられると桶屋が繁盛する風が吹くと桶屋が儲かる ( 命題論理 )

5 命題 (proposition) とは? 真 (true) か偽 (false) かどちらかであるような言明のこと言明 ( ある事実を述べた文 ; statement) 例 ) 日本の首都は名古屋である例 ) = 例 ) 広島大学にはトイレが 185 箇所ある例 )x+y=z である

6 記法命題を p, q, r, s などの記号であらわす命題の真理値 (truth value) は真 (T) か偽 (F) である命題を取り扱う論理を命題論理 (propositional logic) と呼ぶあるいくつかの命題から新しい命題をつくることを考える ( 論理演算子 :3.2 節 )

7 否定 (negation) いま p を命題とする p を p ではないことを主張する言明であると定義する ( not p と読む ) p が命題であることに注意 p と p の関係は真理値表 (truth table) で表現できる

8 否定 (negation) p T F p F T p の真理値が T のとき p の真理値が F になることを示している真理値表

9 例 p p 今日は水曜日である今日は水曜日ではない今日は水曜日であるのではないでも OK 実際は今日がいつであるかによってこの言明の真理値は変わるため厳密にはこれは命題ではない

10 結合子 (connective) 二つ以上の命題からひとつの命題を作り出すための演算子論理積論理和排他的論理和がある

11 (a) 論理積 (conjunction) いま p,q を命題とする p q を p かつ q であることを主張する言明であると定義する p きょうは金曜日 q きょうは13 日 p q きょうは13 日の金曜日

12 (b) 論理和 (disjunction) いま p,q を命題とする p q を p または q であることを主張する言明であると定義する p きょうは金曜日 q きょうは13 日 p q きょうは13 日または金曜日注意 : 両方とも T であってもよいことに注意つまり 13 日の金曜日は OK

13 (c) 排他的論理和 (exclusive or) いま p,q を命題とする p q を p または q のいずれか一方のみが T であることを主張する言明と定義 p q きょうは金曜日きょうは13 日 p q??? 注意 :13 日の金曜日は NG

14 (d) 含意 (implication) あるいは条件式いま p,q を命題とする p q を p ならば q であることを主張する言明であると定義する p を仮定 (hypothesis) 又は前提 (premise) と呼び q を結論 (conclusion) または帰結 (consequence) と呼ぶ

15 含意真理値表は右の通り p q p q T T T T F F 仮定が F ならば結論によらず T になる! F T T F F T

16 含意をあらわす英文英文で以下のように記述されているのはすべて p q の意味である : if p, (then) q p implies q p is sufficient for q (pはqの十分条件) q is necessary for p (qはpの必要条件)

17 例 p: きょうは 13 日の金曜日 q: きょうは金曜日のとき p q は常に T である ( 確認せよ )

18 例 p: 2+3=6 q: この授業では皆に優がでるのとき p q は常に T である ( 本当か?)

19 逆と対偶 p q に対して q p を逆 (converse) p q を裏 (reverse) q p を対偶 (contrapositive) と言う ( 逆は裏の対偶 : 確認せよ )

20 逆と対偶高いところから落ちると怪我をする逆 : 怪我をしたのは高いところから落ちたからだ裏 : 高いところから落ちないと怪我をすることはない対偶 : 怪我をしていないのであればその人は高いところから落ちていないけがをする原因はほかにもある

21 対偶の真理値表 p q p q p q q p T T T F F T T F F F T F F T T T F T F F T T T T

22 必要十分条件ちなみに (p q) (q p) は p if and only if q p is necessary and sufficient for q (pはqの必要十分条件) などと書かれる (p qとも書く)

23 p q の真理値表 p q p q q p (p q) (q p) T T T T T T F F T F F T T F F F F T T T

24 同値 p q は p と q の真理値が等しいときに T したがって (p q) ( q p) は p, q の真理値によらずつねに T このことからのことを同等あるいは同値 (equivalent) と呼ぶ

25 例 p q p q p q (p q) (p q) T T T T T T F T F F F T T F F F F F F T

26 命題的同値とは? (propositional Equivalence) 複合命題 (compound proposition) がそれを構成する命題の真理値にかかわらず常に真となるときこれを恒真 ( 命題 )(tautology) であるという逆に常に偽であるとき矛盾 (contradiction) であるという複合命題 p q が恒真であるとき p は q に論理的に同値 (logically equivalent) と呼び, このとき p q と表記する

27 例 p p p p 恒真命題矛盾 ( p q) ( q p) 恒真命題

28 例 p q (p q) p q T T F F T F F F F T F F F F T T

29 例したがって (p q) p q は恒真であるからこれら 2 つの命題は論理的に同値であり (p q) p q ドモルガンの法則 (de Morgan s law) (p q) p q

30 恒真であることの意味 1 p q 1 q n r ならば p r したがって p の真理値を r に単純化して得ることができる 2 rが恒真ならばrは正しい推論を示しているたとえば (p q) ( q p) は恒真であるが p qから q pを推論することができる

31 例分配則 p (q r) (p q) (p r) p (q r) (p q) (p r) p,q,r のすべての組み合わせに対して真理値表をチェックすること!!

32 恒真かどうかの判定方法任意に与えられた命題の真理値表は計算できるしたがって与えられた命題が恒真かどうかは真理値表をつかっても判定できる具体的には,p T が示せれば恒真 p F が示せれば矛盾

33 背理法による証明 p q T を証明するために, p q F を証明している p q p q (p q) に注意すると, (p q) T (p q) F

34 述語論理 ~ 述語と限定作用素 ~ ( 教科書 :3.9~3.11) 藤田聡 ( 広島大学 )

35 これまでのまとめ (1) 命題論理 (propositional logic) について述べた命題変数 (propositional variable) と呼ばれる任意の命題をあらわす変数だけを素論理式とし結合子だけによってつくられる論理式だけが考察の対象であった特にどのような論理式が恒真であるかに興味があった

36 これまでのまとめ (2) 論理式の真理値表は容易に計算できるため論理式 F の恒真性は容易にチェックできるもうひとつの方法としてで結ばれた関係をたどり F T を導くことによっても式 F の恒真性がチェックできる変数という概念を新たに導入述語論理

37 述語 (predicate) とは? 命題関数 (propositional Function) あるいは値域 { T, F } をもつ関数のこと命題論理で使っていた p とか q などの記号はある命題を表す変数 ( 命題変数 ) であった

38 例 1 以下のものは述語である 1) p(x): x > 3 2) q(x,y): x = y + 4 3) R(x,y): 2 = 1 + 3

39 例 1 1) p(x): x > 3 p(2): 2>3 は値 F をとる命題 p(4): 4>3 は値 T をとる別の命題

40 例 1 2) q(x,y): x = y + 4 q(1,2): 1 = 2+4 は値 F をとる命題 q(5,1): 5 = 1+4 は値 T をとる命題

41 例 1 3) R(x,y): 2 = R(x,y) は x,y に関わらず値 F をとる定数命題関数

42 限定作用素 (quantifier) とは? (a) 全称限定作用素 (Universal quantifier) (b) 存在限定作用素 (Existential quantifier) 二種類の限定作用素があるがこれらは否定演算を介することで本質的に同じものであることが理解できる

43 (a) 全称限定作用素 (Universal quantifier) x p(x): x がとりうるすべての値について p(x) は値 T をとるという命題 x を束縛変数 (binding variable) と呼ぶ p(x) の領域 (domain) あるいは x の世界 (universe) などと呼ぶ

44 例 2 この教室の学生はすべて 18 歳以上であるという文を記述しよう p(x): 学生 xは18 歳以上である q(x): 学生 xはこの教室に居る x(q(x) p(x)) ただしxの世界はすべての学生の全体

45 例 2 18 歳以上の学生

46 例 3 x を実数とする p(x): x+1>x とすると xp(x) は T q(x): x>2 とすると xq(x) は F

47 (b) 存在限定作用素 (Existential quantifier) x p(x): ある x に対して p(x) が T を返すという命題

48 例 4 この教室の学生の中に女性がいるという文を記述する p(x): 学生 x は女性である q(x): 学生 x はこの教室に居る x(p(x) q(x)) なぜ x(p(x) q(x)) とかけないか?

49 例 5 x を実数とする p(x): x>x+1 とすると xp(x) は F q(x): x>2 とすると xq(x) は T

50 世界が有限の場合 x の世界が有限集合 {x 1,x 2,, x n } ならば xp(x)=p(x 1 ) p(x 2 ) p(x n ) xp(x)= p(x 1 ) p(x 2 ) p(x n )

51 例 6 論理推論の表現 1) すべてのライオンは獰猛である 2) あるライオンはコーヒーを飲まない 3) ある獰猛な動物はコーヒーを飲まない

52 例 6 p(x): q(x): R(x): x はライオンである x は獰猛である x はコーヒーを飲む 1) x(p(x) q(x)) 2) x(p(x) R(x)) 3) x(q(x) R(x))

53 例 6 1) x(p(x) q(x)) 2) x(p(x) R(x)) 3) x(q(x) R(x)) 1) と 2) がともに T ならば 3) も T 我々の目標はこのような推論を行うための体系を求めること (x の世界が有限ならすべての x についてチェックすれば OK)

54 束縛変数の拡張について n 変数述語 p(x 1,, x n ) も自然に考えられる束縛変数を複数にすることもできる

55 例 7 x,y を実数とする p(x,y): x 2 =y x p(x,y) は y の関数である y<0 ならば x p(x,y)=f y 0 ならば x p(x,y)=t x が束縛変数なのに対し y は自由変数 (free variable) と呼ばれる

56 例 7 p(x,y): x 2 =y のとき x p(x,y) は y の値によらず F をとることに注意せよ ( これも y の関数ではある )

57 例 8 x,y を整数とする p(x,y): x+y=0 y x p(x,y) は y( x p(x,y)) のことである x p(x,y) を y の関数 q(y) とみなし y q(y) を考えれば OK

58 例 8 p(x,y): x+y=0 y=0のとき y=-1のとき y=1のとき y=-2のとき x(x+0=0) F x(x-1=0) F x(x+1=0) F x(x-2=0) F

59 例 8 したがって y x p(x,y) F 一方

60 例 8 x y p(x,y) は x( y p(x,y)) のことである R(x)= y p(x,y) とみなして x R(x) について調べれば OK

61 例 8 p(x,y): x+y=0 x=0のとき x=-1のとき x=1のとき x=-2のとき y(0+y=0) T y(-1+y=0) T y(1+y=0) T y(-2+y=0) T

62 例 8 したがって x y p(x,y) T つまり一般には x y p(x,y) と y x p(x,y) は論理的に等価ではない

63 例 9 以下のことを証明しよう y x p(x,y) x y p(x,y) T y x p(x,y) が T ならば x y p(x,y) も T であることを示せば OK

64 例 9 y x p(x,y) が T だからある y 1 に対して x p(x,y 1 ) が T そこで任意に x 1 を固定したときに y p(x 1,y) は T すなわち x y p(x,y) は T

65 例 10 q(x,y,z): x+y=z とする x y z q(x,y,z) を調べるどのような x どのような y に対しても x+y=z を満たす z は存在するしたがってこの命題は真

66 例 10 q(x,y,z): x+y=z とする z x y q(x,y,z) を調べるこの命題はある z が存在しどのような x どのような y に対しても x+ y=z を満たすことを主張しているこの命題は偽

67 xp(x) とその否定 x p(x) は任意の x について p(x) が成立することを主張している x p(x) は任意の x について p(x) が成立することはないつまりある x が存在して p(x) が成立しないことがあることを主張しているこの主張は x p(x) で表現されるしたがって

68 x p(x) x p(x) 同様に x p(x) x p(x)

69 例 11 以下はすべて等価である x y z q(x,y,z) x y z q(x,y,z) x y z q(x,y,z) x y z q(x,y,z)

70 例 12 以下はすべて等価である ( x y p(x,y) x y p(x,y)) x y p(x,y) x y p(x,y) x y p(x,y) x y p(x,y)

71 証明手法 ( 教科書 :3.7) 藤田聡 ( 広島大学 )

72 数学的推論 (Mathematical Reasoning) ここでの目的は以下の 2 点に答えることである 1. 数学的議論が正しいのはどの場合か 2. 数学的議論を構成するための手法は何か特に定理と呼ばれる言明に興味がある定理 (theorem) とは正しいことが証明 (proof) できる言明 (statement) のことでは証明とは何か?

73 証明 (proof) とは? 言明の列 S 0,S 1,S 2, S i :1 公理 (axiom) あるいは仮定や既に得られている定理等 (postlude) 2S 0,S 1,S 2,,S i-1 : から新たに導かれる言明どういう風に? ( 推論規則 )

74 用語の使い分け補題 (lemma) ほかの定理を導くための定理系 (corollary) 定理から簡単に導かれる別の定理

75 推論規則 (rule of inference) (p (p q)) q (modus ponens と呼ばれる ) または図式的に p p q q

76 例きょう雪が降ればスキーにいくきょうは雪であるきょうスキーにいく

77 例 p: きょう雪である q: きょうスキーにいく ((p q) p) q S0: p q S1: p S2: q 新しい言明を作り出している!

78 正当 (valid) な議論これらの推論規則を用いて構成された議論は正当 (valid) であるというでは誤った推論にはどのようなものがあるか?

79 例誤った推論の例 (1) この本のすべての問題を解いたならば, 離散数学をマスターできるあなたは離散数学をマスターしたしたがってあなたはこの本のすべての問題を解いたどこがどうおかしいでしょうか?

80 例 ( つづき ) p: q: この本のすべての問題を解いた離散数学をマスターした ((p q) q) p 誤り! 正しくは, ((p q) p) q

81 例誤った推論の例 (2) 2 = 1 aとbを等しい正整数とする 1. a=b : 仮定より 2. a 2 = ab : 両辺をa 倍 3. a 2 b 2 = ab b 2 : 両辺からb 2 を引く 4. (a-b)(a+b) = b(a-b) : 因数分解 5. a+b = b : 両辺をa-bで割る 6. 2b = b : a=bより 7. 2 = 1 : 両辺をbで割る

82 例 Indirect proof の例 3n+2 が奇数ならば n も奇数である対偶を考えるすなわち n が偶数ならば 3n+2 も偶数であることを示す n は偶数だから,n=2k とかけるよって 3n+2=3 2k+2=2(3k+1) 証明終了

83 proof by contradiction ( 背理法 ) p を仮定して矛盾を導くあるいは (p q)=p q を T と仮定して矛盾を導く

84 例 proof by contradiction の例 sqrt(2) が無理数 (irrational) であることを示そう sqrt(2) が有理数 a/b であると仮定して矛盾を導く (a と b は互いに素とする ) sqrt(2)=a/b より 2=a 2 /b 2 a 2 =2b 2 より a は偶数 2c であるしたがって 4c 2 =2b 2 より 2c 2 =b 2 すなわち b も偶数これは矛盾

85 proof by cases (p 1 p 2 p n ) q を示すのに (p 1 q) (p 2 q) (p n q) を示す

86 proof by cases の例もし整数 n が 2 でも 3 でも割り切れないとき n 2-1 が 24 で割り切れることを示せ整数 n を 6 で割ったときの余りによって場合わけする :6m+j, j=0,1,2,3,4,5 j=0,2,3,4 のときは n は 2 で割り切れるか 3 で割り切れるので考えるべき場合は 6m+1 と 6m+5 の 2 通りだけであることがわかる

87 proof by cases の例 n=6m+1 のとき n 2 ー 1=(6m+1) 2 1 = 36m 2 +12m=12m(3m+1) m が偶数の場合も奇数の場合も m(3m+1) は偶数 n=6m+5 のとき n 2 ー 1=(6m+5) 2 1 = 36m 2 +60m+24 =12m(3m+5)+24 m が偶数の場合も奇数の場合も m(3m+5) は偶数

88 定理と限定作用素 xp(x) の証明存在性の証明 (existential proof) 1) constructive( 構成的 ) p(a) が T となる a を構成する 2) nonconstructive( 非構成的 )

89 例 Constructive proof の例任意の n に対してある x が存在して, すべての i(1 i n) に対して x+i は合成数である x=(n+1)!+1 とする任意の i について x+i (n+1)!+(i+1) 0(mod i+1)

90 例 15 Nonconstructive proof の例どのような整数 n に対しても n よりも大きな素数が存在する ( 素数は無限に存在する ) 整数 x=n!+1 を考える x は 2 から n までのどの整数でも割り切れないしたがって x が素数であるか, あるいは n 以上の素数が存在して x はその素数で割り切れる

91 例前向き推論と後ろ向き推論互いに異なる実数 a, b に対して (a+b)/2>sqrt(ab) であることを示せ結論からはじめてその結論が常に成立することを示す ( 推論の向きが後ろ向きなだけで p q を示すのに q p を言おうとしているのではないことに注意

92 例前向き推論と後ろ向き推論 (a+b)/2>sqrt(ab) (a+b) 2 /4 > ab (a+b) 2 > 4ab a 2 +2ab+b 2 > 4ab a 2-2ab+b 2 > 0 (a-b) 2 > 0, これはa bのときつねに成立

93 予想 (conjecture) の重要性いくつかの観測された事実から予想をたてる予想が正しいかどうかを証明する予想が正しいことが証明できれば定理となる予想が正しくないことを証明するためには反例 (counterexample) を示せばよい

94 予想定理の例いくつかの連続した合成数の列が存在する 24,25,26,27,28 90,91,92,93,94,95,96 そのような列の長さはいくらでも長くできるか? つまり任意に自然数 n を与えたとき x+1,x+2,,x+n がすべて合成数であるような自然数 x が存在するか ( 証明済み )

95 予想反例の例ピタゴラスの定理 : =5 2 フェルマーの最終定理 : n>2 かつ xyz 0 のとき x n +y n =z n を満たすような整数 x,y,z は存在しないオイラーの予想 : 3 以上の任意の整数 n に対して n-1 個の自然数の n 乗の和が別の自然数の n 乗になるようなものは存在しない (x 1 ) n +(x 2 ) n + +(x n-1 ) n = y n

96 予想反例の例オイラーの予想に対する反例 : = Lander と partkin によって 1966 年に発見された

97 未解決の予想の例 3x+1 予想次のような関数 f(x) を考える :x が偶数のとき f(x)=x/2, x が奇数のとき f(x)=3x+1 このときどのような x を与えても関数 f(x) を繰り返し適用することによりいずれは必ず 1 に収束する ( 予想 )

98 未解決の予想の例 x=13 のとき次のように推移する : (=3 13+1) 20 (=40/2) 10 (=20/2) 5 (=10/2) 16 (=3 5+1) この予想の通りに推移することは x= の範囲までは確認されているがどのような自然数 x についても成立するかどうかはわかっていない ( 証明もされていないし反例もみつかっていない )

Microsoft PowerPoint - logic ppt [互換モード]

Microsoft PowerPoint - logic ppt [互換モード] 述語論理と ( 全称 ) ( 存在 ) 回の講義の概観 : 命題論理 ( 真理値 ) 2 述語論理 ( モデルと解釈 ) 意味論 semantics 命題論理 ( 公理と推論規則 ) 述語論理 ( 公理と推論規則 ) syntax 構文論 preview 述語論理は命題論理よりも複雑例題 : 次の文は真か偽か? ( 曖昧な文です ) すべての自然数 x に対して x < y を満たすような自然数