証明 Proofs

命題P(p、q、r、…)が真の時、命題Q（p、q、r、…)が真である事が論理的に導ける時、その論理的推論過程を証明(Proof)という。

定理(theorem)は真であることが証明できる命題であり、公理(axiom)は証明の際に真として使うことができる命題である。

定理よりも重要性は低いが他の結果の証明に役立つ補題(lemma)、ある命題から導き出せる結論をcorollaryという。

推論(conjecture)は証明をする際に真と仮定したりする命題のことで、度々偽になることがあるので定理ではない。

<直接証明(Direct Proof)>

pが真である時、必ずqが真でなければならない事を示す事によって、含意(logically imply)p→qが真である事を確立する方法である。

例：

直接証明を使って、「２つの奇数の積は奇数である」事を証明する。

ある奇数を２k＋１とし、もう１つの奇数を２m＋１とする。２つの奇数の積は、

（２k＋１）（２m＋１）＝４km＋２k＋２m＋１＝２（２km＋k＋m）＋１

∴２つの奇数の積は奇数である。

<矛盾を使う証明(Proof by Contradiction)>

もし命題pが真であることが、矛盾qおよび含意¬p→qが真である事によって証明されれば命題pは矛盾を使って証明されるとする。

例：

矛盾を使って「０でない有理数と無理数の積は無理数である」事を証明する。

xを有理数、yを無理数とすると、xはx＝a/bと表すことができる。

ここで、有理数と無理数の積を有理数であると仮定すると、xy＝p/qと表すことが出来るので、xy＝p/q＝(a/b)y

yについて解くと、y＝pb/qa

yは無理数であるが、pb/qaは有理数であるため矛盾が生じる。

∴有理数と無理数の積は無理数である。

ある命題が偽である事を証明するには、反例(counterexample)を挙げれば良い。

例：

「もしaとbが有理数なら、a^bも有理数であるかどうか」を証明する。

a＝２、b＝1/2とすると、a^b＝２^(1/2)＝√２

√２は無理数であるため、この命題の反例である。

∴命題は偽である（aとbが有理数でも、a^bも有理数とは限らない）。

推論 Inference

論法(argument)は、前提(premise)と呼ぶ与えられた命題P1、P2、…、Pnが結論(conclusion)と呼ぶもう１つの命題Qを結果として生み出す主張である。

ある論法が真なら妥当な(valid)論法と呼ばれ、偽ならば誤り(fallacy)と呼ばれる。

例：

S1: ある男が独身ならば彼は不幸である

S2: ある男が不幸ならば彼は若くして死ぬ

ーーーーーーーーーーーーーーーーーーーー

S: 独身は若くして死ぬ

S1、S2は前提、Sは結論。この論法は妥当である事を示す（三段論法）。

<推論>

例：

(1). ¬p∧q                                  Premise

(2). ¬p                                       Simplification using (1)

(3). r → p                                  Premise

(4). ¬r                                        Modus tollens using (2) and (3)

(5). ¬r→s                                   Premise

(6). s                                          Modus ponens using (4) and (5)

(7). s→t                                      Premise

(8). t                                           Modus ponens using (6) and (7)

(1). ∃x(C(x) ∧ ¬B(x))                   Premise

(2). C(a) ∧ ¬B(a)                         Existential instantiation from (1)

(3). C(a)                                      Simplification from (2)

(4). ∀x(C(x) → P(x))                    Premise

(5). C(a) → P(a)                          Universal instantiation from (4)

(6). P(a)                                       Modus ponens from (3) and (5)

(7). ¬B(a)                                    Simplification from (2)

(8). P(a) ∧ ¬B(a)                          Conjunction from (6) and (7)

(9). ∃x(P(x) ∧ ¬B(x))                   Existential generalization from (8)

述語論理、量化 Predicate Logic and Quantifiers

変数にある特定の要素を代入すると真偽が定まる主張を命題関数(propositional function)または述語(predicate)という。

例：

P(x)＝xは動物である…xに犬や木、本などを代入すると真偽が定まる。

P: 述語「は動物である」、x :変数

P(犬)＝犬は動物である…True

P(本)＝本は動物である…False

変数が複数ある場合、P(x1, x2, ..., xn)はn-place predicateまたはn-ary predicateという。

プログラミングの世界において、プログラムは有効なインプットを与えた時に、恒に望んだアウトプットを表示する。この時のある命令が呼び出される前に必ず満たされていなければならない状態を前提条件(preconditions)、その命令の終了後に保証する状態を帰結条件(postconditions)という。

例：

xとyの値を入れ替えるプログラミングについて、

temp := x

x := y

y := temp

この時、preconditionはP(x, y)＝"x = a and y = b, where a and b are the values of x and y before running the program"

postconditionはQ(x, y)＝"x = b and y = a"

述語と量化を扱う論理分野をpredicate calculusという。この量化(quantification)を使って、命題関数が真になる領域を議論することができる。この領域を定義域(domain/discourse/universe of discourse)という。

量子化の記号として、

全称記号∀(universal quantifier)は英語のall（全ての）、any（任意の）の頭文字を記号化したもの。

存在記号∃(existential quantifier)は英語のexist（存在する）の頭文字を記号化したもの。

存在記号の中でも要素がただ一つに決まる時、uniqueness quantifierと呼び、∃!で表す。

例：

∀xP(x)…全てのxに対してP(x)は真である。

P(x)＝"x＋１＞x、定義域は実数全体"の時、∀xP(x)は真である。

∃xP(x)…ある要素xが存在してP(x)を真として満たしている。

P(x)＝"x＞３、定義域を実数全体"とした時、x＝４はP(x)を満たすがx＝０は満たさない。よって∃xP(x)は真である。

P(x)＝"xー１＝０、定義域は実数全体"の時、xはただ一つ（x＝１）に決まる。∃!P(x)。

優先順位として、量子化記号、論理記号の順に計算する。

ド・モルガンの法則は量化にも使われる。

¬∃xP(x) ≡ ∀x¬P(x)、¬∀xP(x) ≡ ∃x¬P(x)

量化記号は組み合わせることもできる。

順序は外側から内側へ。順序が変わると意味が変わってしまう。

例：

∀y∃y（x＋y＝０）…全てのxに対して、x＋y＝０を満たすyが存在する。

Q(x, y): x＋y＝０の時、

∃x∀xQ(x, y)…あるyに対して全てのxはQ(x, y)を満たす…まずyを選ぶ。y＝１の時、x＝ー１なら命題を満たすが、x≠−１の時命題を満たさない。よって∃x∀xQ(x, y)は偽である。

∀x∃yQ(x, y)…全てのxに対してあるyはQ(x, y)を満たす…xは定義域内ならなんでも良い。x＝１の時、y＝ー１、x＝０の時、y＝０のように、全てのxに対してQ(x, y)を満たすyがそれぞれ存在する。よって∀x∃yQ(x, y)は真である。

論理 Logic

<Propositional Calculus/Propositional Logic>

真か偽(True or False)か、どちらか一方に明確に定まる主張を命題(Proposition)という。

例：

命題: Washington, D.C., is the capital of the U.S.A. …真(True)

命題: 2 + 2 = 3 …偽(False)

What time is it? …真か偽か分からないので命題ではない

命題を英小文字p, q, r, ... (propositional variable/statement variable)などを使って表す。

また、命題の真偽を真理値(Truth value)といい、真の時はT、偽の時はFを使って表す。

例：

p = 犬は動物である…T

q = Tronto is the capital of Canada. …F

<論理式（Compound Propositions）>

いくつかの命題が∧、∨、¬(connective operators)によって結びつけられている命題を論理式(compound propositions)という。

• 論理否定(negation)

命題pについて、命題pの否定を¬pと表す。

p = 犬は動物である　…T

¬p = 犬は動物ではない　…F

• 連言、論理積(conjunction)

命題p、qについて、p∧qで表される。

It is true when both p and q are true and is false otherwise.

p＝犬は動物である　…T、q＝バラは植物である　…T

p∧q＝犬は動物であり、バラは植物である　…T

r＝犬は動物ではない　…F、s＝バラは植物である　…T

r∧s＝犬は動物ではなく、バラは植物である　…F

t＝犬は動物ではない　…F、u＝バラは植物ではない　…F

t∧u＝犬は動物でなく、バラは植物でない　…F

• 選言、論理和(disjunction)

命題p、qについて、p∨qで表される（inclusive or）。

It is false when both p and q are false and is true otherwise.

p＝Students who have taken calculus…T、q＝Students who have taken CS…T

p∨q＝Students who have taken calculus or CS can take this class…T

対し、exclusive orはp⊕qと表される。

It is true when exactly one of p and q is true and false otherwise.

p＝Students who have taken calculus…T、q＝Students who have taken CS…T

p⊕q＝Students who have taken calculus or CS, but not both, can take this class…F

• 条件命題(conditional statement)

命題p、qに対して「もしpならばqである(If p, then q)」という命題（十分条件）。p→qと表される。

pを条件(hypothesis/premise)、qを結論(conclusion/consequence)という。

It is false when p is true and q is false, and true otherwise.

p＝ You get 100% on the final…F、q＝ You get an A…T

p→q＝ If you get 100% on the final, then you will get and A…T

期末で100点を取れなくても、他の要因でAを取れる可能性がある。

「pはqの必要十分条件である(p if and only if)」という形の命題を重条件文(biconditional statement/bi-implications)といい、p⇔qと表される。

It is true when p and q have the same truth values, and is false otherwise.

p＝ You can take the flight…F、q＝ You buy a ticktet…F

p⇔q＝ You can take the flight if and only if you buy a ticket…T

論理式の優先順位は一に否定、二に∨、∧、最後に→、⇔となる。

<真理表(Truth Table)>

命題の真偽を表に表したものを真理表(truth table)という。

＜逆、裏、対偶＞

命題p→qを基準にして、

q→pを逆(converse)、¬p→¬qを裏(inverse)、¬q→¬pを対偶(contrapositive)という。

例：

The home team wins whenever it is raining.＝If it is raining, then the home team wins.

p＝It is raining、q＝ The home team wins

逆(converse)は、

If the home team wins, then it is raining.

裏(inverse)は、

If it is not raining, then the home team does not win.

対偶(contrapositive)は、

If the home team does not win, then it is not raining.＝ original statement

２つの論理式の真偽が完全に一致する時、同値(equivalent)という。

例：

真理表より、p→qと¬q→¬pは同値である。先の例からも同値であることが分かる。

<恒真命題、矛盾命題>

命題が、それを構成している命題の真偽にかかわらず恒に真である時、恒真命題(tautology)といい、恒に偽である時、矛盾命題(contradiction)という。

恒真命題、矛盾命題のどちらでもない条件命題をcontingencyという。

また、pとqの重条件p⇔qが恒真命題の時、pとqはlogically equivalentといい、p≡qと表される。

例：

p∨¬pはtautology、(p∧q)∧¬pはcontradiction。

<ド・モルガンの法則(De Morgan Laws)>

¬(p∧q) ≡ ¬p∨¬q

¬(p∨q) ≡ ¬p∧¬q

<Logical Equivalences>

• ベキ等律(Idempotent laws)

p∨p ≡ p、p∧p ≡ p

• 交換律(Commutative laws)

p∨q ≡ q∨p、p∧q ≡ q∧p

• 結合律(Associative laws)

(p∨q)∨r ≡ p∨(q∨r)、(p∧q)∧r ≡ p∧(q∧r)

• 分配律(Distributive laws)

p∨(q∧r) ≡ (p∨q)∧(p∨r)、p∧(q∨r) ≡(p∧q)∨(p∧r)

• Absorption laws

p∨(p∧q) ≡ p、p∧(p∨q) ≡ p

論理式がある真理値割り当ての際に真となる時、その論理式は充足可能(satisfiable)といい（恒真命題も充足可能である）、また真理値割り当ての際に恒に偽となる時、その論理式は充足不能(unsatisfiable)という（矛盾命題）。

<コンピュータのお話　Bitについて>

コンピュータはビットを使って情報を表す。

ビットは０か１の値でこれを二進数(binary)と呼ぶ。

ビットは０か１かの二つしかないため、これを使って真理値(True or False)を表すことができる。１をT(Truth)、０をF(False)とする。プログラミングの際、０がFalse valueとなるのはこのためである。

ある変数の値がTrueかFalseかのどちらかである時、その変数をブール変数(Boolean variable)という。よって、ブール変数はビットを使って表すことができる。

ビットの演算は論理式に対応している。

リスト Lists

どこのサイト見てもどの本読んでもサラッとしか解説が書かれてない。

誰でも分かると思うなよ、こちとら人の倍以上時間かけないと理解できないんだよ（自慢できない）。

ってわけで自分なりにまとめてみる。

変数に一つの値しかバインド（格納）出来ないのなら、リストを使えば複数の値をバインド出来る。別に数字じゃなくても、'meow'みたいな感じでクオーテーションで囲めば文字列も入れられる（囲まないと NameError : name 'meow' is not defined みたいな感じでエラーになる）。

>>> list = [1, 100, 'set', 'meow', [2, 3], 9]  # リストの中に更にリストを作る事もできる。

>>> blank = [  ]          # 空のリストも作れる。

こんな感じでブラケット[ ]の中にカンマで区切っていれる。

要素名は左から順に list[0] = 1, list[1] = 100, list[2] = 'set', list[3] = 'meow', list[4] = [2, 3], list[5] = 9となり、この０、１、２、３、４、５をインデックスという。

試しにインタラクティブモードで打ってみるとこうなるはず。

>>> list[3]

'meow'

負の記号を使って逆から数える事もできる。

そうするとlist[-1] = 9, list[-2] =[2, 3], list[-3] = 'meow', list[-4] = 'set', list[-5] = 100, list[-6] = 1という具合。

このインデックスを使って、格納しているデータの要素を個別に変更する事が出来る。

例えば、'meow'を5000に変えたい場合、

>>> list[3] = 5000

と打てば、'meow'が5000に上書きされる。確認するにはlistと打てば

>>> list

[1, 100, 'set', 5000, [2, 3], 9]

と出るし、または list[3] と打っても確認できる。

>>> list[3]

5000

append()を使えば要素の追加が出来る。

リスト名の後ろに .append(追加する要素)という風に使う。この時、追加される場所は最後の場所になる。

例えば、'python'と入れたい場合、

>>> list.append('python')

そしてlistと入力して確認してみると

>>> list

[1, 100, 'set', 5000, [2, 3], 9, 'python']

となるはず。

要素を削除したい場合は、インデックスを指定して消す方法と、その要素を直接指定して消す方法がある。

インデックスを指定する方法は .pop(インデックス番号)と入力する。[2, 3]を試しに消してみると、

>>> list.pop(4)

[2, 3]

となる。ここでもう一度listと入力すれば[2, 3]が消えている事が分かる。

要素を直接指定して消す場合は .remove(要素)と入力する。'set'を消すなら、

>>> list.remove('set')

これで消えるはず。

ただ、個人的にはremoveの方が使い勝手がいいんじゃないかと…というのも、もしリストの中に同じ要素が入ってた場合、popを使う場合インデックスを一々指定しなきゃなんで…まぁこれは人それぞれなのかな。やってく内にどっちの方がいいのか分かるでしょう。

次に、リストの連結。ここでリストを二つ作っておく。そしてこの二つを次のようにして連結する事ができる。

>>> list1 = [0, 1, 2, 3, 4]

>>> list2 = ['set', 'meow', 'python']

>>> list1 + list2

[0, 1, 2, 3, 4, 'set', 'meow', 'python']

また、スライスという機能を使って、リストの一部を表示する事が出来る。

>>> list1[0:3]

[0, 1, 2]

ブラケット[ ]の中に数字とコロンで位置を指定する。コロンの左側が始まり、右側が終わり。始まりは含んで終わりは含まない点に注意。例の場合、インデックス０の０は含むが、インデックス３の３は含まない為に[0, 1, 2]という風になる。

>>> list1[1:]          # インデックス１から終わりまで

[1, 2, 3, 4]

>>> list1[:2]          # 始めからインデックス２まで

[0, 1]

>>> list1[:]          # 最初から最後まで

[0, 1, 2, 3, 4]

要素を並べ替える方法。.sort()を使うと数字の小さい方から順に、アルファベットはアルファベット順に並べ替えてくれる。

>>> list2.sort()

>>> list2

['meow', 'python', 'set']

.reverse()で今の要素の並び順を逆さまにしてくれる。

>>> list2.reverse()

>>> list2

['set', 'python', 'meow']

最後に、リストの数値に対して新たなリストを作る。list1を使ってみる。

list1の中にある数値の内、2の倍数の数字だけ二乗をしたいとする。この時、[<expression> for <element> in <sequence> if <conditional>]

>>> [i ** 2 for i in list1 if i % 2 == 0]

[0, 4, 16]

この概念を使って、冒頭にちらっと述べた空のリストを使って、新たなリストを作ってみる。

>>> blank = []

>>> for i in list1:

             if i % 2 == 0:

                         blank += [ i ** 2 ]

>>> blank

[0, 4, 16]

おまけで、リストの中の要素数を数える方法。len(リスト名)

>>> len(blank)

3

練習問題１

>>> x = [1, 3, [5, 7], 9]

このとき、要素７を表示するにはどのようにインデックスを入力すれば良いか。

解答

x[2][1]

練習問題２

予想される表示結果は？

>>> [ x**x for x in range(5)]

解答

[0, 1, 4, 9, 16]

>>> ones = [1 for i in ["hi", "bye", "you"]]

>>> ones + [str(i) for i in [6, 3, 8, 4]]

解答

[1, 1, 1, '6', '3', '8', '4']

練習問題３

i_listの中にある各要素がthisの数字よりも小さいとき that と表示し、大きい時はそのままの数字を表示する関数 if_this_not_that(i_list, this)を書きなさい。

>>> def   if_this_not_that(i_list, this):

        """

        >>> original_list = [1, 2, 3, 4, 5]

        >>> if_this_not_that(original_list, 3)

        that

        that

        that

        4

        5

        """

解答

続：再帰関数 Tree Recursion

前回は再帰関数の基本についてやりました。３つの要素

1. Base case...終了条件

2. Recursive call...再帰表現

3. Solve full problem...２を使って元々の問題を解く

今回もそれに則ってやっていく。

まず、Tree Recursionというのは、基本的に樹形図みたいなもの。

樹形図を書いて、base caseを探して、残りを再帰にしよう的な。その際に、再帰表現が２つ以上になる事が多い（パターンが枝分かれしているから）。

この概念を使うと、フィボナッチ数列を求めるプログラムが簡単に書けるようになる。

まず、フィボナッチ数列というのは、０th＝０、１st＝１として、前の数字と現在の数字を足したものが次の数字になるという数列。つまり、

０、１、１、２、３、５、８、１３、２１、３４、５５、８９、…

という風に増加していく。このn番目の数字が何かを求めるプログラムを書く。

例えば、4番目のフィボナッチ数列を求めたい。この時の樹形図を書くと、

という風になる。フィボナッチ数列の1番目は１、0番目は０なので、この末端の数字を足していくと３となり、フィボナッチ数列4番目の数は３である事がわかる。

この末端のfib(1)とfib(0)をbase caseとして再帰関数でフィボナッチ数列を表す事が出来る（n == 1 の時、 return 1、n == 0 の時、return 0）。

そして出来上がるプログラムがこちら。

この場合のbase caseはn＝０とn＝１の２通り。最後のelse文で再帰表現を二つ使っているのはそのため。

つまり、Tree Recursionの場合も、基本的には終了条件は何か、returnで自身を返しているか、またその表現は終了条件に収束していくかどうかを考えれば良い。

練習問題１

n段の階段がある。この階段を登るとき、１段か２段ずつしか上がらないことにする。この時、何通りの登り方があるかを計算するプログラムを作りなさい。

def   count_stair_ways(n):

        """

        >>> count_stair_ways(7)

        21

        >>> count_stair_ways(3)

        3          # 1+1+1, 1+2, 2+1

        """

解答

練習問題２

先の問題で１段か２段を上がる代わりに、k以内の段数を登ることにする。この時の登り方が何通りあるかを計算するプログラムを作りなさい。

def   count_k(n, k):

        """

        >>> count_k(3, 3).         # 3, 2+1, 1+2, 1+1+1

        4

        >>> count_k(4, 4)

        8

        """

解答

一応これも再帰関数…

練習問題３

パスカルの三角形の(row, column)の位置の数字を求めるプログラムを作りなさい。

def   pascal(row, column):

        """

        >>> pascal(2, 1)

        2

        >>> pascal(4, 2)

        6

        """

解答

このブログについて

UC Berkeleyに編入して数週間、やっぱり勉強内容が難しい。

今まではわからない事があったらググれば大体の事は解決できたけど、大学の内容になるとなかなかネットには初心者に分かるように書いてくれてるとこが少ない。。

ある程度できる事前提で話が書いてある。。。

私は今まで人に教える事で内容を学んできたので、今回ズボラな自分がブログを書くに至ったのも、人にわかりやすく書く事ができれば自分でもよく理解出来るんじゃないかと思ったから。

プログラミングに関しては本当にド素人なので、プロが見たら間違ってるって思う表現もあるかもしれないけどそこは大目に見ていただきたい。

大学では数学とコンピュータサイエンスをやってます。まだ専攻は決めてないけど、コンピュータサイエンスやれたらいいなと。就職有利だしやってみると結構面白いし。試験はかなりエグいけど。

ちなみになんで数学やってるのかというとアメリカ人は数学苦手な人が多いので数学科で応募したら大学入りやすいんじゃないかという思惑があったからです。計算は好きだけど数学自体はそこまで好きじゃないです。数学っていうか証明が嫌い。

そんな感じで更新していきたいと思います。続くかな。。

たまにUC Berkeleyの事も書こうと思うから、Berkeley目指してる人は「こんな感じの学校なんだー」という感じで読んでみてください。