<   2018年 01月 ( 12 )   > この月の画像一覧

外延性の公理

公理的集合論の外延性の公理は次のようになる。
外延性の公理 A と B が全く同じ要素を持つのなら A と B は等しい
要素が全く同じなら集合 A と集合 B は等しいのは当然のようだが、この公理を適用すると、{a, a, a} と {a, a} と {a} は同じ集合ということになる。{a,a,a} のどの要素を取ってもそれは {a} の要素だし、{a} の要素は全て {a, a, a} の要素だからだ。
つまり集合では重複した要素は取り除かれる。これは、ものの集まりを考えるときにやや特殊な考え方になる。

Haskell の Data.List モジュールには nub (要点) という関数がある。リストから重複する要素を取り除く関数だ。

Prelude> import Data.List
Prelude Data.List> nub [1,1,2,3,3,3,4,4]
[1,2,3,4]

Python の場合は集合型というデータ型があるので重複した要素の除去は自動的に行われる。

>>> {1,1,2,3,3,3,4,4}
{1, 2, 3, 4}

プログラムを組むときは、リストが重複した要素を持つのは、むしろこちらのほうが普通なので、外延性の公理はリストに制約をかけるものである。

しかし、空集合 {} から対の公理を使って {{}, {}} が作られるがこれは外延性の公理で {{}} と等しいものとされる。空集合のみを要素とする集合 {{}} は外延性の公理がなければ、対の公理だけでは作ることができない。

外延性の公理という制約が、対の公理と組み合わせることによって空集合のみを要素とする集合を作ることができる。対の公理だけではこのような集合を作ることはできないので、制約によって却って表現の拡充が行われることになる。

公理集合論の集合は、一般的に考えるものの集まりよりはかなり制約を受けたものの集まりになるようだ。

[PR]
by tnomura9 | 2018-01-30 11:42 | ラッセルのパラドックス | Comments(0)

公理的集合論の世界

以前の記事『なぜ素朴集合論は矛盾するのか』で素朴集合論の世界を「帰属関係の定義された対象のネットワークの全体」として捉えると、なぜラッセルのパラドックスが起きてしまうのかを述べた。

「集合とはものの集まりというもの」であるという直観的な定義は上のようなネットワークとして捉えることができるように思われる。しかし、このネットワークでは、そのすべての対象の集合を考えたとき、その部分集合の全てをそれらの対象で代表させるということはできないという表現力の不足を招く。このため、集合(対象)としては表せない、ネットワークの対象の集まりであるクラスが発生してしまうのだ。

このようなクラスを発生させない集合だけを集めるために、公理的集合論の公理群が決められ、これこそが集合であり素朴的集合論の集合は欠陥があるとされている。しかし、公理的集合論の集合が一口にどんな集合なのかは、公理を眺めていてもはっきりしない。集合論を学ぶときに、この公理的集合論の指し示す集合が目に見えないのが大きな不満になる。

そこで、公理的集合論の公理群からどのような集合の世界が見えてくるかを考えてみた。矛盾のない真の集合とはどのような形をしているのかを見てみたいと思ったのだ。

Wikipedia から抜粋した公理的集合論である ツェルメロ=フレンケルの公理系 (ZF: Zermelo-Fraenkel) の公理は次のようになる。
外延性の公理 A と B が全く同じ要素を持つのなら A と B は等しい

空集合の公理 要素を持たない集合が存在する

対の公理 任意の要素 x, y に対して、x と y のみを要素とする集合が存在する

和集合の公理 任意の集合 X に対して、X の要素の要素全体からなる集合が存在する

無限公理 空集合を要素とし、任意の要素 x に対して x ∪ {x} を要素に持つ集合が存在する

冪集合公理 任意の集合 X に対して X の部分集合全体の集合が存在する

置換公理 "関数クラス"による集合の像は集合である

正則性公理(基礎の公理) 空でない集合は必ず自分自身と交わらない要素を持つ
どれも抽象的で具体的なイメージを作り辛いが、よく眺めていると、空集合の公理からべき集合の公理まではその定義が再帰的定義であることが分かる。再帰的定義はコンピュータのプログラムではよくあらわれる関数の定義の方法だ。例えば自然数の階乗を求める関数は次のように定義できる。

Prelude> :{
Prelude| let
Prelude| fact 0 = 1
Prelude| fact n = n * fact (n-1)
Prelude| :}
Prelude> fact 5
120

fact n を計算するのにそれ自身の関数 fact を使っている。巡回しているようだが fact 5 を展開してみるとその仕組みが分かる。

fact 5 = 5 * (fact 4) = 5 * 4 * (fact 3) = 5 * 4 * 3 * (fact 2) = 5 * 4 * 3 * 2 * (fact 1) = 5 * 4 * 3 * 2 * 1 * (fact 0) = 5 * 4 * 3 * 2 * 1 * 1 = 120

このように fact n を fact n = n * fact (n-1) という定義によって次々に展開していけば、最後には fact 0 = 1 という固定された値にたどり着くため、それを計算することによって階乗が計算できる。この fact 0 = 1 という定義を base case というが、これがなければ fact n = n * fact (n-1) という recursive case のみでは展開が無限に続くだけなので fact n の値を求めることはできない。

上の空集合の公理~べき集合の公理までが、このような再帰的定義であって、集合の世界を再帰的に定義している。例えば対の公理
対の公理 任意の要素 x, y に対して、x と y のみを要素とする集合が存在する
の場合は、集合の世界に属する対象 x, y をとり、この二つの既知の対象を要素とする集合 z を作る方法を定義している。これは、集合の世界の要素を、集合の世界の要素で定義するため再帰的な定義である。これは上でのべた再帰的定義の recursive case にあたる。

さきに述べたように再帰的定義では base case がなければ無限の再帰を引き起こしてしまうので、base case が必要になる。それでは上の公理群の中で base case といえるのはどの公理だろうか。

それは空集合の公理である。

上の公理のなかで、空集合の公理以外は集合を定義するのに recursive case として再帰的に定義している。すなわち、すでに集合として認められたものから新しい集合を生成するというやり方だ。再帰的定義は生成規則でもある。

ところが、空集合の公理
空集合の公理 要素を持たない集合が存在する
は base case だ。つまり集合を定義するのにほかの集合を必要としない。要素を持たない空集合はそれ自身で集合を定義することができる。言い換えると公理的集合論でア・プリオリに存在するのは空集合のみなのである。公理的集合論の他の集合は全て、この空集合に、ほかの再帰的定義を適用して生成された集合なのである。例えば空集合 {} に対の公理を適用して

{{},{}} = {{}}

という空集合を要素とする集合を作ることができる。つまり公理的集合論で定義される集合とは、空集合を出発点として他の生成規則である再帰的定義を適用して作られる集合の全体なのだ。これは、素朴集合論の定義から直感的にイメージする集合とは少し異なっている。しかし、このようにして作られた集合の集まりの中に、矛盾のない論理や数学が構築できるのだ。

つまり、公理的集合論の世界は一種のコンピュータのデータの世界と考えたほうがいいかもしれない。コンピュータのデータの世界は1と0の記号列からできている世界だが、シミュレーションプログラムを組むことで、森羅万象をその中に表現することができる。公理的集合論の集合もそのようなビットの世界の一種と考えることができる。

不可思議な公理的集合論の集合もこのようにとらえると視覚化できて抽象感が薄らぐのではないだろうか。

[PR]
by tnomura9 | 2018-01-28 08:22 | ラッセルのパラドックス | Comments(0)

Python でシーザー暗号

以前に Haskell でシーザー暗号を作ってみたが、Python でもできるのではないかと思ってやってみた。

>>> chars = [chr(x) for x in range(97,97+26)]
>>> chars
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', '
'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
>>> rotate = lambda n,xs: xs[n:] + xs[:n]
>>> rotate(3, chars)
['d', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', '
't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c']
>>> code = rotate(3, chars)
>>> code
['d', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', '
't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c']
>>> encoder = dict(zip(chars, code))
>>> encoder['c']
'f'
>>> decoder = dict(zip(code, chars))
>>> decoder['f']
'c'
>>> encode = lambda xs: ''.join([encoder[x] for x in xs])
>>> encode('hello')
'khoor'
>>> decode = lambda xs: ''.join([decoder[x] for x in xs])
>>> decode('khoor')
'hello'

上の例はコンソール上で関数チェックをしながらの操作だが、プログラムだけを抜き出すと次のようになる。

>>> chars = [chr(x) for x in range(97,97+26)]
>>> rotate = lambda n,xs: xs[n:] + xs[:n]
>>> code = rotate(3, chars)
>>> encoder = dict(zip(chars, code))
>>> decoder = dict(zip(code, chars))
>>> encode = lambda xs: ''.join([encoder[x] for x in xs])
>>> decode = lambda xs: ''.join([decoder[x] for x in xs])

あまり Python らしくないプログラムかもしれないが、それでもきちんと動くプログラムだ。逆に言うと、リストの内包的定義や、λ記法や、関数オブジェクトを自然に仕様の中に取り込んでいることが分かる。

[PR]
by tnomura9 | 2018-01-22 18:12 | Python | Comments(0)

Python datetime モジュール

Pythonの datetime モジュールを使ってみた。今日の日付と曜日を調べた。

>>> from datetime import date
>>> today = date.today()
>>> today.isoformat()
'2018-01-12'
>>> today.year
2018
>>> today.month
1
>>> today.day
12
>>> today.weekday()
4
>>> weekday = 'Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday'.split(',')
>>> weekday
['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday']
>>> weekday[today.weekday()]
'Friday'

ついでに安室奈美恵の生まれた日の曜日を求めた。

>>> amuro = date(1977,9,20)
>>> weekday[amuro.weekday()]
'Tuesday'

Python 言語の基本的な使い方が分かったら、あとは標準や非標準のモジュールを調べて、問題解決に使う必要がある。しかし、そのためにはプログラミングで解決すべき問題がなければならない。さしあたって解決したい問題がないというのがアマチュアプログラマの弱点だ。

自分が何をやりたいのか。それを解決するためのプログラミング言語以外の知識を持ち合わせているか。そちらのほうを明確にするのが必要なのだ。

[PR]
by tnomura9 | 2018-01-12 12:54 | Python | Comments(0)

Python で木構造を扱う

関数型言語でよく使われるデータ構造にはリスト型以外に木構造がある。Haskell の場合には木構造は代数的データ型で定義する。例えば次のようにノードには左右の木構造を収め、リーフに文字列を収めるデータ構造 Tree を定義する。

Prelude> data Tree = Node Tree Tree | Leaf String deriving Show
Prelude> let a = Node (Leaf "hello") (Node (Leaf "world") (Leaf "."))

この木構造のリーフの値を列挙する go_around 関数は次のように再帰的に定義できる。

Prelude> :{
Prelude| let
Prelude| go_around (Leaf str) = [str]
Prelude| go_around (Node left right) = go_around(left) ++ go_around(right)
Prelude| :}
Prelude> go_around a
["hello","world","."]

Python で木構造を定義するには、ノードとリーフのデータ型をクラスで定義する。Haskell で代数的データ型で定義したところを、Python ではクラスを定義することで木構造のデータ型を作ることになる。代数的データ型のデータがクラスのインスタンスに相当するわけだ。こう考えると、クラスの定義の、新しいデータ型を定義するという一面が明らかになる。あるいは、オブジェクト指向言語のクラスの性質の一部は Haskell の代数的データ型として捉えることができることが分かる。

class Node:
    def __init__(self,left,right):
        self.left = left
        self.right = right

class Leaf:
    def __init__(self,data):
        self.data = data
    def get(self):
        return self.data
def go_around(tree):
    if isinstance(tree, Leaf):
        return [tree.get()]
    else:
        return go_around(tree.left) + go_around(tree.right)

a = Node(Leaf('hello'), Node(Leaf(','), Leaf('world')))
print(go_around(a))

実行例

================== RESTART: C:/Users/****/Desktop/tree.py ==================
['hello', ',', 'world']

このように、Haskell の代数的データ型とPythonのクラス定義の意味合いが同じ事が分かる。どんなプログラム言語であれ、プログラムをデータ構造とアルゴリズムとして捉えるとそれらのプログラム言語の本質をとらえて活用できるような気がする。データ構造とアルゴリズムへのアプローチの仕方に言語の特徴がみられるだけだからだ。
Python という言語の使い方がなんとなくわかった気がするので Python 関係の記事はこれで終わりにする。AI との関連性についてはもう少し沈黙して勉強しないといけない。


[PR]
by tnomura9 | 2018-01-08 15:49 | Python | Comments(0)

list.pop()

Python のリスト型のメソッドの list.pop() と list.append() を使うとスタックが実装できる。スタックを使ったプログラムの例として逆ポーランド記法で記述した整数の電卓を作ってみた。コマンドラインから逆ポーランド記法でスペース区切りで数式を入力すると計算をしてくれる。数値のスタックが動的にどのように推移していくかを見ることができる。

実行例

input expression: 1 2 + 3 *
[1]
[1, 2]
[3]
[3, 3]
[9]
9

プログラム(IDLEを使って作ったが、シェルからも動かせるはず。)

value_stack = []
stack = []

def calc(stack):
    for acc in stack:
        if acc.isdigit():
            value_stack.append(int(acc))
        elif acc == '+':
            a = value_stack.pop()
            b = value_stack.pop()
            value_stack.append(a+b)
        elif acc == '*':
            a = value_stack.pop()
            b = value_stack.pop()
            value_stack.append(a*b)
        print(value_stack)

while True:
    line = input('input expression: ')
    if line == 'quit': break
    stack = line.split(' ')
    calc(stack)
    print(value_stack.pop())


[PR]
by tnomura9 | 2018-01-07 19:04 | Python | Comments(0)

reduce()

Python 3.6 の組み込み関数からは reduce() が削除されていたので作ってみた。

>>> def reduce(f,x,xs):
...     for y in xs:
...         x = f(x,y)
...     return x
...
>>> reduce(lambda x,y: x+y, 0, [1,2,3,4,5])
15
>>> reduce(lambda x,y: x*y, 1, [1,2,3,4,5])
120

これは Haskell の foldl に相当する。f(x,y) = x+y, x =0, xs = [1,2,3,4,5] の場合この関数は次のような計算になる。

reduce(f,0,[1,2,3,4,5]) = (((((0+1)+2)+3)+4)+5)

つまり、リスト [1,2,3,4,5] の要素を先頭からアキュームレータ x に加算していく。Haskell の場合は変数への再代入ができないので、右項の計算式を展開していってリストの最後まで展開していった時点で式の計算を行っている。Python のような手続き型言語は、変数への再代入が可能なので明示的に x をアキュームレータにしてループを回すことで計算できる。

Haskell のリスト関連の関数で、foldr, foldl は難解なほうだが、手続き型の言語と比較することで、その意味がよくわかる。

reduce と foldl のような等価な動作をする関数を関数型と手続き型とで対比することによって、それぞれのコードの意味がよくわかるのが面白い。

[PR]
by tnomura9 | 2018-01-06 19:12 | Python | Comments(0)

Python のリスト処理

Python のリスト処理の組み込み関数には map() と fliter() がある。ネットの記事では reduce() もあるようだが、手元の環境では組み込み関数から除かれているようだ。

map() 関数はリストの要素に同じ関数を適用したリストを作成する。また、filter() 関数はリストの要素のうち特定の条件を満たすものを抜き出したリストを作成する。

>>> list(map(lambda x: x*x, [1,2,3,4,5]))
[1, 4, 9, 16, 25]
>>> list(filter(lambda x: x % 2 == 0, [1,2,3,4,5]))
[2, 4]

これは次のようにリストの内包表記を使うこともできる。処理速度はこちらのほうが速い。ロジックの読みやすさも損なわれていない。

>>> [x*x for x in [1,2,3,4,5]]
[1, 4, 9, 16, 25]
>>> [x for x in [1,2,3,4,5] if x % 2 == 0]
[2, 4]

リストの要素を取り出したり、部分リストを取り出すにはスライス [x : y] を使う。これを利用すると Haskell 風にリストの先頭の要素を取り出す head や、リストの先頭以外の部分を取り出す tail を定義できる。

>>> head = lambda x: x[0]
>>> tail = lambda x: x[1:]
>>> head([1,2,3,4,5])
1
>>> tail([1,2,3,4,5])
[2, 3, 4, 5]

head と tail を利用して Haskell のパターン (x:xs) を利用した再帰的な関数の定義のようなことができる。

>>> def double(x):
...    if x == []: return x
...    else: return [head(x)*2] + double(tail(x))
...
>>> double([1,2,3,4,5])
[2, 4, 6, 8, 10]

何が何でも関数型でプログラムするのは行き過ぎだが、リスト処理をするとループを記述するより見通しのよいプログラムが書ける場合がある。特に内包表記は速度も速いし、map と filter ができることは簡潔に記述できる。ただし入れ子になったループの場合内包表記ではかえって可読性の低いプログラムになってしまうことがある。適材適所が必要だ。

[PR]
by tnomura9 | 2018-01-06 09:04 | Python | Comments(0)

str.format() その2

str.format() メソッドのもう一つの機能は {} の中に記述するデータの書式設定だ。前回の記事で紹介したサイトの引用になるが次のような書式設定が可能だ。書式設定は {} の中に : (コロン)の後に記述する。{0:X} のように format の引数のインデックスと組み合わせることもできる。

左寄せ、センタリング、右寄せ

>>> '{:<10}'.format('hello')
'hello '
>>> '{:^10}'.format('hello')
' hello '
>>> '{:>10}'.format('hello')
' hello'

数値(10進、16進、8進、2進)

>>> 'int: {0:d}; hex: {0:X}; oct: {0:o}; bin: {0:b}'.format(42)
'int: 42; hex: 2A; oct: 52; bin: 101010'

3桁のカンマ区切り

>>> '{:,d}'.format(1234567)
'1,234,567'

固定小数点

>>> '{:.3f}'.format(12.34)
'12.340'

日付フォーマット

>>> d =datetime.datetime.now()
>>> '{:%Y-%m-%d %H:%M:%S}'.format(d)
'2018-01-05 13:11:19'

これだけの知識でも数値計算の書式付きの出力は簡単に記述できる。

>>> for i in range(1,11):
...     print('{0:3} {1:3} {2:5.3f}'.format(i,i*i,math.sqrt(i)))
...
 1   1 1.000
 2   4 1.414
 3   9 1.732
 4  16 2.000
 5  25 2.236
 6  36 2.449
 7  49 2.646
 8  64 2.828
 9  81 3.000
10 100 3.162


[PR]
by tnomura9 | 2018-01-05 13:27 | Python | Comments(0)

str.format()

Python でモニタに出力するときは str.format() 関数で体裁を整えるのが便利だ。format() は 文字列型(str 型)オブジェクトのメソッドだ。出力を表示するテンプレートになる文字列にデータを供給する働きがある。次のサイトを読めば概要がよくわかるが、自分でもいろいろ試してみた。

format関数による文字列フォーマット(新しい形式 / 3.6対応)

format は文字列オブジェクトのメソッドなので、文字列のドット記法になる。つまり文字列中の {} の中に引数を注入する働きがある。format の引数は、文字列でも、数値でも、変数でもよい。データは {} の中に表示される。

>>> 'My name is {}'.format('John')
'My name is John'
>>> 'pi = {}'.format(3.14)
'pi = 3.14'
>>> m = 'Mary'
>>> 'I love {}'.format(m)
'I love Mary'

文字列中の {} の数は複数個でもよい。この場合 format の引数は順番に {} に代入されていく。引数の数が {} より少ない場合はエラーになるが、多すぎる場合は単に無視されるだけだ。

>>> '{} {} {}'.format(0, 1, 2)
'0 1 2'
>>> '{} {} {}'.format(0)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: tuple index out of range
>>> '{} {} {}'.format(0, 1, 2, 3)
'0 1 2'

文字列中の {} は {0}, {1} のようにインデックスをつけることで format() の引数を指定することができる。これを利用すると表示の順番を自由に変えることができる。

>>> '{0} {1}'.format('hello', 'world')
'hello world'
>>> '{0} {0}'.format('hello', 'world')
'hello hello'
>>> '{1} {0}'.format('hello', 'world')
'world hello'

{0[1]}, {0[2]} のようにするとリストやタプルの要素を表示できる。

>>> '{0[0]} {0[1]}'.format([1,2])
'1 2'
>>> '{0[0]} {0[1]}'.format((1,2))
'1 2'

オブジェクトのプロパティも表示できる。

>>> class Person:
...     def __init__(self, name, age):
...         self.name = name
...         self.age = age
...
>>> p = Person('John', 25)
>>> '{0.name} {0.age}'.format(p)
'John 25'

fomat() メソッドで文字列の {} の中にデータを送り込むやり方はまだいろいろあるようだが、とりあえずこれだけ試してみた。

format() メソッドはデータを {} に送り込むだけでなくその時の表示の書式も指定できるがそれはまた別の記事にする。

[PR]
by tnomura9 | 2018-01-04 21:12 | Python | Comments(0)