命題論理 ( 教科書 :3.1~3.5) 藤田 聡 ( 広島大学 )
ガイドライン 命題論理 ( 今週 ) A ならば B である という形の論理式を用いて推論を行う ( 例 : 否定 論理和 論理積 ) 事実の集まりから 求めたい結論を正しく導けるかを問う ( 参考 : 推理小説 ) 述語論理 ( 次週 ) 命題論理で表現されることに加えて すべての何某について という表現が許された論理体系 すべての整数について という表現も可
今日の授業内容 命題 がどのようなものかを理解する 命題論理で用いられる基本演算子 含意について正しく理解する ( 真理値表 ) 逆 裏 対偶 必要十分条件 命題的同値 という考え方を理解する 必要十分 という考え方がわかることが重要
風が吹くと 風が吹くと砂ぼこりが出る 砂ぼこりが出ると盲人がふえる 盲人は三味線をひくのでそれに張る猫の皮が必要で猫が減る 猫が減ると 鼠がふえて桶をかじる 桶がかじられると桶屋が繁盛する 風が吹くと桶屋が儲かる ( 命題論理 )
命題 (proposition) とは? 真 (true) か偽 (false) かどちらかであるような言明のこと 言明 ( ある事実を述べた文 ; statement) 例 ) 日本の首都は名古屋である 例 )5342 263 = 1404946 例 ) 広島大学にはトイレが 185 箇所ある 例 )x+y=z である
記法 命題を p, q, r, s などの記号であらわす 命題の真理値 (truth value) は真 (T) か偽 (F) である 命題を取り扱う論理を命題論理 (propositional logic) と呼ぶ あるいくつかの命題から新しい命題をつくることを考える ( 論理演算子 :3.2 節 )
否定 (negation) いま p を命題とする p を p ではない ことを主張する言明であると定義する ( not p と読む ) p が命題であることに注意 p と p の関係は真理値表 (truth table) で表現できる
否定 (negation) p T F p F T p の真理値が T のとき p の真理値が F になることを示している 真理値表
例 p p 今日は水曜日である今日は水曜日ではない 今日は水曜日である のではない でも OK 実際は 今日 がいつであるかによってこの言明の真理値は変わるため 厳密にはこれは 命題 ではない
結合子 (connective) 二つ以上の命題からひとつの命題を作り出すための演算子 論理積 論理和 排他的論理和がある
(a) 論理積 (conjunction) いま p,q を命題とする p q を p かつ q であることを主張する言明であると定義する p きょうは金曜日 q きょうは13 日 p q きょうは13 日の金曜日
(b) 論理和 (disjunction) いま p,q を命題とする p q を p または q であることを主張する言明であると定義する p きょうは金曜日 q きょうは13 日 p q きょうは13 日または金曜日 注意 : 両方とも T であってもよいことに注意 つまり 13 日の金曜日は OK
(c) 排他的論理和 (exclusive or) いま p,q を命題とする p q を p または q のいずれか一方のみが T であることを主張する言明と定義 p q きょうは金曜日きょうは13 日 p q??? 注意 :13 日の金曜日は NG
(d) 含意 (implication) あるいは条件式 いま p,q を命題とする p q を p ならば q であることを主張する言明であると定義する p を仮定 (hypothesis) 又は前提 (premise) と呼び q を結論 (conclusion) または帰結 (consequence) と呼ぶ
含意 真理値表は右の通り p q p q T T T T F F 仮定が F ならば結論によらず T になる! F T T F F T
含意をあらわす英文 英文で以下のように記述されているのはすべて p q の意味である : if p, (then) q p implies q p is sufficient for q (pはqの十分条件) q is necessary for p (qはpの必要条件)
例 p: きょうは 13 日の金曜日 q: きょうは金曜日 のとき p q は常に T である ( 確認せよ )
例 p: 2+3=6 q: この授業では皆に 優 がでる のとき p q は常に T である ( 本当か?)
逆と対偶 p q に対して q p を逆 (converse) p q を裏 (reverse) q p を対偶 (contrapositive) と言う ( 逆は裏の対偶 : 確認せよ )
逆と対偶 高いところから落ちると怪我をする 逆 : 怪我をしたのは 高いところから落ちたからだ 裏 : 高いところから落ちないと 怪我をすることはない 対偶 : 怪我をしていないのであれば その人は高いところから落ちていない けがをする原因はほかにもある
対偶の真理値表 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
必要十分条件 ちなみに (p q) (q p) は p if and only if q p is necessary and sufficient for q (pはqの必要十分条件) などと書かれる (p qとも書く)
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
同値 p q は p と q の真理値が等しいときに T したがって (p q) ( q p) は p, q の真理値によらずつねに T このことから のことを 同等 あるいは同値 (equivalent) と呼ぶ
例 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
命題的同値とは? (propositional Equivalence) 複合命題 (compound proposition) がそれを構成する命題の真理値にかかわらず常に真となるとき これを恒真 ( 命題 )(tautology) であるという 逆に常に偽であるとき矛盾 (contradiction) であるという 複合命題 p q が恒真であるとき p は q に論理的に同値 (logically equivalent) と呼び, このとき p q と表記する
例 p p p p 恒真命題 矛盾 ( p q) ( q p) 恒真命題
例 p q (p q) p q T T F F T F F F F T F F F F T T
例 したがって (p q) p q は恒真であるから これら 2 つの命題は論理的に同値であり (p q) p q ドモルガンの法則 (de Morgan s law) (p q) p q
恒真であることの意味 1 p q 1 q n r ならば p r したがって p の真理値を r に単純化して得ることができる 2 rが恒真ならばrは正しい推論を示している たとえば (p q) ( q p) は恒真であるが p qから q pを推論することができる
例 分配則 p (q r) (p q) (p r) p (q r) (p q) (p r) p,q,r のすべての組み合わせに対して 真理値表をチェックすること!!
恒真かどうかの判定方法 任意に与えられた命題の真理値表は計算できる したがって与えられた命題が恒真かどうかは真理値表をつかっても判定できる 具体的には,p T が示せれば恒真 p F が示せれば矛盾
背理法による証明 p q T を証明するために, p q F を証明している p q p q (p q) に注意すると, (p q) T (p q) F
述語論理 ~ 述語と限定作用素 ~ ( 教科書 :3.9~3.11) 藤田 聡 ( 広島大学 )
これまでのまとめ (1) 命題論理 (propositional logic) について述べた 命題変数 (propositional variable) と呼ばれる任意の命題をあらわす変数だけを素論理式とし 結合子だけによってつくられる論理式だけが考察の対象であった 特に どのような論理式が恒真であるかに興味があった
これまでのまとめ (2) 論理式の真理値表は容易に計算できるため 論理式 F の恒真性は容易にチェックできる もうひとつの方法として で結ばれた関係をたどり F T を導くことによっても式 F の恒真性がチェックできる 変数 という概念を新たに導入 述語論理
述語 (predicate) とは? 命題関数 (propositional Function) あるいは値域 { T, F } をもつ関数 のこと 命題論理で使っていた p とか q などの記号は ある命題を表す変数 ( 命題変数 ) であった
例 1 以下のものは述語である 1) p(x): x > 3 2) q(x,y): x = y + 4 3) R(x,y): 2 = 1 + 3
例 1 1) p(x): x > 3 p(2): 2>3 は値 F をとる命題 p(4): 4>3 は値 T をとる別の命題
例 1 2) q(x,y): x = y + 4 q(1,2): 1 = 2+4 は値 F をとる命題 q(5,1): 5 = 1+4 は値 T をとる命題
例 1 3) R(x,y): 2 = 1 + 3 R(x,y) は x,y に関わらず値 F をとる定数命題関数
限定作用素 (quantifier) とは? (a) 全称限定作用素 (Universal quantifier) (b) 存在限定作用素 (Existential quantifier) 二種類の限定作用素があるが これらは否定演算を介することで本質的に同じものであることが理解できる
(a) 全称限定作用素 (Universal quantifier) x p(x): x がとりうるすべての値について p(x) は値 T をとる という命題 x を束縛変数 (binding variable) と呼ぶ p(x) の領域 (domain) あるいは x の世界 (universe) などと呼ぶ
例 2 この教室の学生はすべて 18 歳以上である という文を記述しよう p(x): 学生 xは18 歳以上である q(x): 学生 xはこの教室に居る x(q(x) p(x)) ただしxの世界はすべての学生の全体
例 2 18 歳以上の学生
例 3 x を実数とする p(x): x+1>x とすると xp(x) は T q(x): x>2 とすると xq(x) は F
(b) 存在限定作用素 (Existential quantifier) x p(x): ある x に対して p(x) が T を返す という命題
例 4 この教室の学生の中に女性がいる という文を記述する p(x): 学生 x は女性である q(x): 学生 x はこの教室に居る x(p(x) q(x)) なぜ x(p(x) q(x)) とかけないか?
例 5 x を実数とする p(x): x>x+1 とすると xp(x) は F q(x): x>2 とすると xq(x) は T
世界が有限の場合 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 )
例 6 論理推論の表現 1) すべてのライオンは獰猛である 2) あるライオンはコーヒーを飲まない 3) ある獰猛な動物はコーヒーを飲まない
例 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))
例 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)
束縛変数の拡張について n 変数述語 p(x 1,, x n ) も自然に考えられる 束縛変数を複数にすることもできる
例 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) と呼ばれる
例 7 p(x,y): x 2 =y のとき x p(x,y) は y の値によらず F をとることに注意せよ ( これも y の関数ではある )
例 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
例 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
例 8 したがって y x p(x,y) F 一方
例 8 x y p(x,y) は x( y p(x,y)) のことである R(x)= y p(x,y) とみなして x R(x) について調べれば OK
例 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
例 8 したがって x y p(x,y) T つまり一般には x y p(x,y) と y x p(x,y) は 論理的に等価ではない
例 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
例 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
例 10 q(x,y,z): x+y=z とする x y z q(x,y,z) を調べる どのような x どのような y に対しても x+y=z を満たす z は存在する したがってこの命題は真
例 10 q(x,y,z): x+y=z とする z x y q(x,y,z) を調べる この命題は ある z が存在し どのような x どのような y に対しても x+ y=z を満たす ことを主張している この命題は偽
xp(x) とその否定 x p(x) は 任意の x について p(x) が成立する ことを主張している x p(x) は 任意の x について p(x) が成立することはない つまりある x が存在して p(x) が成立しないことがあることを主張している この主張は x p(x) で表現されるしたがって
x p(x) x p(x) 同様に x p(x) x p(x)
例 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)
例 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)
証明手法 ( 教科書 :3.7) 藤田 聡 ( 広島大学 )
数学的推論 (Mathematical Reasoning) ここでの目的は 以下の 2 点に答えることである 1. 数学的議論が正しいのはどの場合か 2. 数学的議論を構成するための手法は何か 特に 定理と呼ばれる言明に興味がある 定理 (theorem) とは 正しいことが証明 (proof) できる言明 (statement) のこと では証明とは何か?
証明 (proof) とは? 言明の列 S 0,S 1,S 2, S i :1 公理 (axiom) あるいは 仮定や既に得られている定理等 (postlude) 2S 0,S 1,S 2,,S i-1 : から新たに導かれる言明 どういう風に? ( 推論規則 )
用語の使い分け 補題 (lemma) ほかの定理を導くための定理 系 (corollary) 定理から簡単に導かれる別の定理
推論規則 (rule of inference) (p (p q)) q (modus ponens と呼ばれる ) または図式的に p p q q
例 きょう雪が降ればスキーにいく きょうは雪である きょうスキーにいく
例 p: きょう雪である q: きょうスキーにいく ((p q) p) q S0: p q S1: p S2: q 新しい言明を作り出している!
正当 (valid) な議論 これらの推論規則を用いて構成された議論は正当 (valid) であるという では 誤った推論にはどのようなものがあるか?
例誤った推論の例 (1) この本のすべての問題を解いたならば, 離散数学をマスターできる あなたは離散数学をマスターした したがって あなたはこの本のすべての問題を解いた どこがどうおかしいでしょうか?
例 ( つづき ) p: q: この本のすべての問題を解いた離散数学をマスターした ((p q) q) p 誤り! 正しくは, ((p q) p) q
例誤った推論の例 (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で割る
例 Indirect proof の例 3n+2 が奇数ならば n も奇数である 対偶を考える すなわち n が偶数ならば 3n+2 も偶数であることを示す n は偶数だから,n=2k とかける よって 3n+2=3 2k+2=2(3k+1) 証明終了
proof by contradiction ( 背理法 ) p を仮定して矛盾を導く あるいは (p q)=p q を T と仮定して矛盾を導く
例 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 も偶数 これは矛盾
proof by cases (p 1 p 2 p n ) q を示すのに (p 1 q) (p 2 q) (p n q) を示す
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 通りだけであることがわかる
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) は偶数
定理と限定作用素 xp(x) の証明 存在性の証明 (existential proof) 1) constructive( 構成的 ) p(a) が T となる a を構成する 2) nonconstructive( 非構成的 )
例 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)
例 15 Nonconstructive proof の例 どのような整数 n に対しても n よりも大きな素数が存在する ( 素数は無限に存在する ) 整数 x=n!+1 を考える x は 2 から n までのどの整数でも割り切れない したがって x が素数であるか, あるいは n 以上の素数が存在して x はその素数で割り切れる
例 前向き推論と後ろ向き推論 互いに異なる実数 a, b に対して (a+b)/2>sqrt(ab) であることを示せ 結論からはじめて その結論が常に成立することを示す ( 推論の向きが後ろ向きなだけで p q を示すのに q p を言おうとしているのではないことに注意
例 前向き推論と後ろ向き推論 (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のときつねに成立
予想 (conjecture) の重要性 いくつかの観測された事実から予想をたてる 予想が正しいかどうかを証明する 予想が正しいことが証明できれば 定理 となる 予想が正しくないことを証明するためには 反例 (counterexample) を示せばよい
予想 定理 の例 いくつかの連続した合成数の列が存在する 24,25,26,27,28 90,91,92,93,94,95,96 そのような列の長さはいくらでも長くできるか? つまり 任意に自然数 n を与えたとき x+1,x+2,,x+n がすべて合成数であるような自然数 x が存在するか ( 証明済み )
予想 反例 の例 ピタゴラスの定理 : 3 2 +4 2 =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
予想 反例 の例 オイラーの予想に対する反例 : 27 5 + 84 5 + 110 5 + 133 5 = 144 5 Lander と partkin によって 1966 年に発見された
未解決の予想の例 3x+1 予想 次のような関数 f(x) を考える :x が偶数のとき f(x)=x/2, x が奇数のとき f(x)=3x+1 このとき どのような x を与えても 関数 f(x) を繰り返し適用することにより いずれは必ず 1 に収束する ( 予想 )
未解決の予想の例 x=13 のとき 次のように推移する : 13 40 (=3 13+1) 20 (=40/2) 10 (=20/2) 5 (=10/2) 16 (=3 5+1) 8 4 2 1 この予想の通りに推移することは x=5.6 10 13 の範囲までは確認されているが どのような自然数 x についても成立するかどうかはわかっていない ( 証明もされていないし反例もみつかっていない )