ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

続・集合と写像の勉強まとめ ~ブール代数も~

前回記事「集合と写像の勉強まとめ」で、“関係”というものについてまで書きたかったのですが、
疲れて打ちきってしまったので、今回さっさと書いてしまいます。

また、あのあと“ブール代数”とは何かについても勉強したので、それも書きます。

と言っても、ブール代数の定義を見ただけで、使い方とかはまだなので、何なのかよくわからないままなんですけどね。

さて、この記事は前回記事を読んでいることを前提に書きますので、ご注意ください。




まず前回、直積集合の話をしたときに、集合Xと集合YでX×Yという、異なる集合の直積集合というのを考えていましたが、

X×Xみたいに同じ集合の直積を作ることもありえますね。

そして同じものを掛け算したら累乗の表記になるのと同じようなもので、X×XはX2と書き表せます。

もちろん、Xがn回掛かる直積なら、Xnとなります。


順序対(x,y)と(x',y')が同一である条件は、 x = x' であって y = y' ということです。

つまり、順序対(a,b)と(b,a)は基本的には別物ですが、 a = b である場合は同一です。

X×Xのような、同じ集合の直積では、同じ要素x = x'で(x,x')になるみたいな組み合わせも多いので、同一の順序対が多いですね。


関係

関係というのは、ある集合の要素とある集合の要素の関係ということです。

たとえば、a = bとか、a < bとかは関係です。

ただし厳密にいうと関係ではありません。


集合Xがn回掛かった直積集合Xnにおいて、なんでもいいのでXnの部分集合Rを決めます。

この集合Rを、X上のn項関係といいます。
厳密な意味での関係とは、集合に過ぎません。

たとえば、X2において、Rをx = x'となるような順序対(x,x')だけの集合とします。

そして、X2から適当に取り出した順序対(a,b)が
Rの要素ならa = b、Rの要素でないならa = bじゃない、ということですね。


また、X2において、要素がRに属しているなら1を返す指示関数X2R:X2→{0,1}を、Rに基づいて決定できますね。

この指示関数をX上のn項述語といいます。

最初にイメージしていた関係という言葉の意味は、厳密には述語のことなのです。

a = bならば、X2R((a,b))は1を返す、ようするに真で、
a = bじゃないなら指示関数は0、偽を返します。

指示関数、つまり述語から話が始まって、Rはその述語を満たす要素の集合、
とやったほうがそれっぽいですが、あくまでも数学においては集合から話を始めるそうです。


また、ここまで同じXという集合の要素だけの関係を述べてきましたが、
もちろん異なる集合の直積とその部分集合から、異なる種類の要素における関係を考えることもできます。


また、n項関係の中でもn = 2の二項関係だけに限った話ですが、

二項関係の場合は、二項関係の集合Rに、順序対(a,b)が属することをaRbと書き表すことも可能です。


a = bとかa < bとか書けるのは、Rという名前を=や<に変えたということなのかなと思ったのですが、
それだと=や<は集合になってしまうので、そういうことではないんでしょうか。

そこはよくわかりません。


同値関係、順序

同じ集合Xの要素における二項関係R⊆X2について考えます。

その中で、ある条件を満たす二項関係は特別な名前で呼ばれます。

色々なものがあるようで、それについて語るだけでもだいぶ長くなると思うんですが、私が学んだのは同値関係と順序だけです。


同値関係とは、以下の条件を満たす二項関係Rです。

・反射律:Xの要素aは常にaRa
・対称律:Xの要素a,bは、aRbならbRa、bRaならaRb
・推移律:Xの要素a,b,cは、aRbでbRcなら、aRc

代表的な同値関係は数値におけるイコールですね。

イコールは集合の要素としても同一なわけですが、異なる要素でも同値関係ということはありえます。

ただ、同値関係は上に挙げたようにイコール的な性質を持っています。


順序とは、以下の条件を満たす二項関係Rです。

・反射律:Xの要素aは常にaRa
・推移律:Xの要素a,b,cは、aRbでbRcなら、aRc
・反対称律:Xの要素a,bは、aRbでbRaなら、a = b

順序関係があれば、それに基づいて小さいほうから大きいほうへと、集合の要素を並べられます。

ただし、上は半順序という関係で、aとbのどちらが小さいのか判定不可能という状態を認めるものなので、全部を一列には並べられません。


半順序に

・全順序律:Xの要素a,bは常にaRbまたはbRa

という条件を足すと、全順序にグレードアップして、集合の要素を一列に並べられるようになります。


順序の例は、数値の“以上”とか“以下”ですね。

“より大きい”、“より小さい”も、いかにも順序っぽいですが、実はこれでは推移律しか満たしていないわけですね。

まあでも、推移律はあるし、aがbより大きいかつbがaより大きいなんてのも、
ありえない仕組みになっているので、要素を並べることはできると思うんですが、どうなんでしょうか。

関係とか律とか詳しく勉強したわけではないので、このくらいの予測しか立てられません。


二項関係と写像

集合Xと集合Yの要素間の二項関係R⊆X×Yについてです。

ここで写像f:X→Yがあったとして、Rをf(x) = yとなるような(x,y)の集合とします。

そのようなとき、よく考えてみたら、Rという集合は写像fのグラフとなっています。

写像fのグラフは(x,f(x)=y)の集合だからです。

よって、写像のグラフというのは、二項関係の特別な場合であるともいうことができるのです。


写像のグラフには、ひとつのxに対して対応する順序対(x,y)が一つだけ存在するという特徴がありましたが、
二項関係に、この特徴を足したら、それは写像のグラフとなります。

そして、その集合を関係として述べるなら、xとyがあって、f(x) = yとなる関係だということです。

まあ、XとYの直積集合が一番大きくて、XとYの関係が次に大きくて、次にXからYへの写像のグラフがある、という構図ですね。


あと、n種類の集合の直積からm種類の集合の直積への写像のグラフを、関係と見なしたときに、

n種類の集合の直積と、m種類の集合の直積の間の二項関係だといえばそれまでかもしれませんが、
それぞれの集合をバラバラにして、グラフを二項関係じゃなくて(n+m)項関係と見なすこともできなくはないですね。

場合にもよりますが、そっちのほうが自然です。



n項演算

数の足し算とか割り算とかの四則演算は、名前の通り演算です。
2つの数から1つの数を作るので、2項演算といいます。

数の頭にマイナスを付けて負数を表しますが、あれも1項の演算と見なせます。

数に限らず一般的に、演算とはどういうことでしょうか。

演算とは、集合の複数(もしくはひとつ)の要素から、ひとつの集合の要素を作り出すこと、ようするに順序対からひとつの要素への写像です。

それも普通は、入力も出力も同じ集合の中だけで完結する写像です。

つまり、集合AがあったとしてAn→Aとなる写像を、A上のn項演算といいます。

ただし演算と見なす場合、書き方は写像の名前と括弧じゃなくて、要素の先頭とか、要素と要素の間とか、柔軟な書き方ができます。


ブール代数

ガラッと話が変わって、ブール代数です。

ブール代数というとプログラマにしてみれば馴染みも深い、TrueとFalseのアレねという印象があったんですが、

実はアレはブール代数の一種だっただけで、ブール代数はもっと広い意味でした。

ブール代数というのは、実は二値だとは限りません。


ブール代数のことをブール束とも呼ぶそうですが、ブール束になりそうでなりきれなかった下のグレードに、分配束というものがあります。

まずは分配束について説明します。

集合Lが定義されていて、二項演算つまりL2→Lな二つの写像∨と∧が定義されていて、
これらが下の条件を満たしているとき、Lと∨と∧をセットで分配束と呼びます。

Lの任意の要素x,y,zにおいて

・冪等律: x∧x = x、x∨x = x
・交換律: x∧y = y∧x、x∨y = y∨x
・結合律: (x∧y)∧z = x∧(y∧z)、(x∨y)∨z = x∨(y∨z)
・吸収律: (x∧y)∨x = x、(x∨y)∧x = x
・分配律: (x∨y)∧z = (x∧z)∨(y∧z)、(x∧y)∨z = (x∨z)∧(y∨z)

が成り立っていたら、分配束です。
続いて本命のブール代数です。


分配束で定義されている演算は∨と∧だけでしたが、一項演算つまりL→Lな写像¬を追加します。

また集合Lには、特別枠として二つの異なる要素⊥とTが存在しているとします。

そして、

・x∨T = T、x∧⊥ = ⊥
・x∧T = x、x∨⊥ = x
・x∨¬x = T、x∧¬x = ⊥

という条件が満たされていたら、Lと∨と∧と¬をセットでブール代数と呼びます。

ちなみに¬xのことをxの補要素と呼びます。


条件が色々なサイトで微妙に異なっていてよくわからないんですが、まあ同じものを指しているんだと思います。

なので、減らそうと思えば重複している条件を減らせるかもしれません。


これがブール代数です。
狐につままれた感じですね。

ブール代数というのはこんなよくわからない存在だったわけです。

ではTrueとFalseの二値のアレのほかに、ブール代数であるものはどんなものがあるでしょうか。


実は集合Aの冪集合P(A)というのは、ブール代数なのだそうです。

ブール代数に必要なものは、Lと⊥とTと∨と∧と¬ですが、LをP(A)、⊥をφ、TをAとします。

そして、X∨YはX∪Y、X∧YはX∩Y、¬XはA-Xとします。

A-Xなんて初めて出てきて、説明忘れましたが、差集合です。

Aの要素中から、Xの要素にもなっている要素を取り除いた集合を表します。


こんなような対応をさせたとき、実際に確認してみるとわかりますが、ブール代数の条件を綺麗に満たしています。

よって冪集合というのはブール代数なのです。
ブール代数というのは本当に変な存在ですね。

記事冒頭でも書きましたが、私はブール代数の定義しか勉強してないので、使い方とかはまだよくわかりません。


ちなみに、∨,∧,¬,⊥,TはそれぞれOR,AND,NOT,FALSE,TRUEに結びついているんだなというのはプログラマなら容易に想像できますが、
ブール代数としてのこれらの記号自体にそういう意味はありません。

いわゆる我々の知ってるTRUEとFALSEのブール代数においては、そういう対応になっているだけです。



というわけで、今日もなんやかんやで時間かかりました。

これで、私が見ているサイトの最初の章の部分は全部まとめました。

次の章からもまとめていくのは面倒なので、多分まとめないと思います。

まあ、もっと大きいインターバルで、最後に総合的に大事な部分をつまんで、まとめるぐらいはあるかもしれませんが。

しかし、数学の奥深さに再認識させられて感心しております。

前回記事と今回記事が皆様の学習に役立ったら光栄です。

tag: 数学 論理学 集合 写像 関係 グラフ 述語 演算 ブール代数

コメント

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/436-7e14b998
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。