ハンティントンの公理系、入門_大学生向け
目次
1.はじめに
1.1.キーワード
論理学, 命題論理, T, F,集合, ハンティントンの公理, 単位元, 補元, 零元, 交換律, 分配律, 結合律,べき等律,二重否定
1.2.対象の方
対象の方は下記の条件に当てはまる方です。深いところは説明しません。
- 命題論理と集合の基本をご存知であることが望ましい（例えば、真理値表、T, F, ∧, ∨,分配律 など）。
- ハンティントンの公理を習い始めた初学生。大学生におすすめ。
- ハンティントンの公理から導かれる性質の証明を知りたい方向け。
2.事前知識（代数系、単位元・零元）
※ここからは何となく「だ・である」口調。
最初に断っておくと、代数系については詳しく知らずとも本記事の内容は理解できる。その上で説明を読んでいてただけると幸いである。
本記事では代数系という単語を次のように用いる。
「ハンティントンの公理系は用いる代数系を(A;+,*,¬())としたとき、次のように表せる。」
とりあえず、代数系(A;+,*,¬())は集合Aと演算子「+,*,¬()」の組み合わせからなるものだと理解していただければ良い。
代数系の例として挙げられるのはRを実数としたときに定義される代数系(R,+,-,*,/)である。
この代数系(R,+,-,*,/)は小学生から習っている四則演算と実数Rの組み合わせのことである。
代数系という言葉を知らずとも、この代数系による集合と演算を理解できていたことから、同じように深く代数系を理解せずとも、本記事のハンティントンの公理系も理解できるはずだ。
また、単位元というのは小学校で習った四則演算の1のように、掛けても値が変わらないものである。例えば、1·6は6というように。
逆に、単位元でないのは、2などである。実際、2·6としたら、6になるのではなく、12になる。
零元は、小学校で習った四則演算の0のように、足しても変わらない要素である。
3.ハンティントンの公理
代数系を(B;+,·,¬())とし、単位元を1、零元を0と表すこととする。
またx,y,z∈Bとする。
※ここでは否定を簡単に記載できるため「¬()」と表しているが、他のハンティントンの公理の説明では、「(⁻)」を用いていることが多い。
「(⁻)」はわかりづらいだろうから、具体例を下記に記載する。
3.1.交換律
3.2.分配律
x+y·z=(x+y)·(x+z)...(3.2.1)
x·(y+z)=x·y+x·z...(3.2.2)
3.4.補元
x+¬x=1...(3.4.1)
x·¬x=0...(3.4.2)
4.ハンティントンの公理系を満たすものの具体例
集合の代数系は(A;∪,∩,¬())である（※）。
※本来は(A;∪,∩,(⁻))だが、書くのが面倒なため、¬()としている。
「(⁻)」はわかりづらいだろうから、具体例を下記に記載する。
この集合の代数系はハンティントンの公理系である。
例えば、A∩U=Aは代数系(A;+,·,¬())におけるA·1=Aに該当する。
これから示すハンティントンの性質を集合に置き換えて考えると理解が深まるであろう。
さらに、ブール代数といったものにも当てはまる。
詳細は省く。理由はもちろん面倒だからである。
5.ハンティントンの性質
※できるだけ自力で証明したい方は最初にこちらを見るとよいだろう。
5.1.双対律
交換律の片方は
x+y=y+x
という等式である。
これの+を·に置き換えると、
x·y=y·x
となる。これは交換律のもう一方の等式である。
分配律も同様である。
さらに単位元において、·を+に、1を0にすると、零元の等式になる。
このように、+と·を入れ替え、さらに1と0を入れ替えても等式が成り立つ性質を双対律という。
この双対律を用いると、下記の等式の証明の記述を二分の一に減らすことができる。
5.2.単位元、零元の性質
5.2.1.単位元の性質
x+1=1となることを示す
x+1
=(x+1)
=(x+1)·1 (∵単位元)
=(x+1)·(x+¬x) (∵補元)
=x+1·¬x (∵分配律)
=x+¬x·1 (∵交換律)
=x+¬x (∵単位元)
=1 (∵補元)
5.2.2.零元の性質
x·0=0を示す。
x·0
=(x·0)
=(x·0)+0 (∵零元)
=x·0+0
=x·0+x·¬x (∵補元)
=x·(0+¬x) (∵分配律)
=x·(¬x+0) (∵交換律)
=x·(¬x) (∵零元)
=x·¬x
=0 (∵補元)
【別解】
単位元と双対律より、
x·0=0が成り立つ。
5.3.べき等律
5.3.1.x+x=x
x+x=xを示す
x+x
=x·1+x (∵単位元)
=x·1+x·1 (∵単位元)
=x·(1+1) (∵分配律)
=x·(1) (∵単位元の性質)
=x·1
=x (∵単位元)
5.3.2.x·x=x
x·x=xを示す
x·x
=(x+0)·x (∵零元)
=(x+0)·(x+0) (∵零元)
=x+0·0 (∵分配律)
=x+0 (∵零元の性質)
=x (∵零元)
【別解】
x+x=xと双対律より、成立。
5.4.吸収律
5.4.2.x·(x+y)=x
x·(x+y)=xを示す
x·(x+y)
=(x+0)·(x+y) (∵零元)
=x+0·y (∵分配律)
=x+y·0 (∵交換律)
=x+0 (∵零元の性質)
=x (∵零元)
【別解】
x+x·y=xと双対律より成立。
5.5.二重否定
¬¬x=xを示す
¬¬x
=¬¬x+0 (∵零元)
=¬¬x+x·¬x (∵補元)
=(¬¬x+x)·(¬¬x+¬x) (∵分配律)
=(¬¬x+x)·(1) (∵補元)
=(¬¬x+x)·(x+¬x) (∵補元)
=(x+¬¬x)·(x+¬x) (∵交換律 )
=x+¬¬x·¬x (∵分配律)
=x+¬(¬x)·(¬x)
=x+(¬x)·¬(¬x) (∵交換律 )
=x+0 (∵補元)
=x (∵零元)
5.6.結合律
5.6.1.(x+y)+z=x+(y+z)
(x+y)+z=x+(y+z)を示す。
以下、この証明において、
(x+y)+z=A
x+(y+z)=B
とする。
大まかな方針を記載する。
【大まかな方針】
(A·B=A…(ア))∧(A·B=B…(イ))を示すことで、
A=Bを示す。
なぜ、(ア)と(イ)が成り立つと、A=Bになるのかを説明する。
A
=A·B (∵(ア))
=B (∵(イ))
まず、下記の等式が成り立つことを示す。
a·((a+b)+c)=a…(10.1.1)
c·((a+b)+c)=c…(10.1.2)
(a+b)·((a+b)+c)=a+b…(10.1.3)
(a+c)·((a+b)+c)=a+c…(10.1.4)
a·((a+b)+c)=a…(10.1.1)
を示す。
a·((a+b)+c)
(D=a+bとおく)
=a·(D+c)
=a·D+a·c (∵分配律)
=a·(a+b)+a·c (∵D=a+b)
=a+a·c (∵吸収律)
=a (∵吸収律)
c·((a+b)+c)=c…(10.1.2)
を示す。
c·((a+b)+c)
(D=a+bとおく。)
=c·(D+c)
=c·(c+D) (∵交換律 )
=c (∵吸収律)
(a+b)·((a+b)+c)=a+b…(10.1.3)
を示す。
(a+b)·((a+b)+c)
(D=a+bとおく。)
=D·(D+c)
=D (∵吸収律)
=a+b (∵D=a+b)
(a+c)·((a+b)+c)=a+c…(10.1.4)
を示す。
(a+c)·((a+b)+c)
(∵A'=(a+b)+cとおく。)
=(a+c)·A
=A'·(a+c) (∵交換律)
=A'·a+A'·c (∵分配律)
=a·A'+c·A' (∵交換律)
=a·((a+b)+c)+c·((a+b)+c) (∵A'=(a+b)+c)
=a+c (∵10.1.1, 10.1.2)
A·B=A…(ア)
を示す。
A·B
=B·A (∵交換律 )
=B·((x+y)+z) (∵A=(x+y)+z)
(D=x+yとおく。)
=B·(D+z)
=B·D+B·z (∵分配律)
=D·B+z·B (∵交換律)
=(x+y)·(x+(y+z))+z·(x+(y+z)) (∵B=x+(y+z))
(E=y+zとおく)
=(y+x)·(x+E)+z·(x+E)
=(y+x)·(E+x)+z·(E+x) (∵交換律 )
=(y+x)·((y+z)+x)+z·((y+z)+x) (∵E=y+z)
=(y+x)·((y+z)+x)+z·((z+y)+x) (∵交換律)
=(y+x)+z·((z+y)+x)
(∵(10.1.4)a=y, b=z, c=xとすると上手く行く)
=(y+x)+z
(∵(10.1.1)a=z, b=y, c=xとすると上手く行く)
=(x+y)+z (∵交換律)
=A (∵A=(x+y)+z)
A·B=B…(イ)
を示す。
A·B
=A·(x+(y+z))
(D=y+zとおく)
=A·(x+D)
=A·x+A·D (∵分配律)
=x·A+D·A (∵交換律)
=x·((x+y)+z)+(y+z)·((x+y)+z) (∵A=(x+y)+z)
=x+(y+z)·((x+y)+z) (∵(10.1.1)a=x, b=y, c=zとすると、上手く行くことが分かる)
=x+(y+z)·((y+x)+z) (∵交換律)
=x+(y+z) (∵(10.1.4)a=y, b=x, c=zとすると上手く行くことが分かる)
=B
よって、(ア)、(イ)、(あ)より、
A=Bが成り立つ。
5.6.2.(x·y)·z=x·(y·z)
(x+y)+z=x+(y+z)と双対律より、成立。
双対律を用いない方法は億劫なため省く。
ハンティントンの性質を証明するコツ
逆順
証明のコツを説明するにあたって、いくつか問題を提示する。
問題1.「x+¬x」を別の形に変換するとどうなるか。
答えは複数あるが一つは「x+¬x=1 (∵補元 )」である。
問題2.「x」を別の形に変換するとどうなるか。
答えのうちの一つは「x=x+0 (∵零元)」である。
問題3.「1」を別の形に変換するとどうなるか。
答えのうちの一つは「1=x+¬x (∵補元)」である。
問題4.「x+0」を別の形に変換するとどうなるか。
答えのうちの一つは「x+0=x (∵零元)」となる。
この中で個人的に困難だと思うのは問題2と問題3である。
では、問題2と問題3の共通点は何か。
それは、当ブログに記したハンティントンの公理の等式の右辺と左辺を逆にしたものという特徴である。
【例】
x =x+0 (問題2)
x+0=x (当ブログの上記に書いた公理の式)
このように、証明のもととする書かれた公式や公理を逆順にも用いることを考えると、証明できる確率があがるはずだ。
これはハンティントン以外の証明でも有効である。
グループ化
再び問題。
問題1.x+yはどのように変換できるか。
答えのうちの一つは、「x+y=(x+y)·1」である。
詳細は下記。
x+y
=(x+y)
(A=x+yとする)
=A
=A·1 (∵単位元)
=(x+y)·1 (∵A=x+y)
問題2.「x·y」を変換するとどうなるか。
答えのうちの一つは「x·y=x·y+0」である。
詳しく説明する。
x·y
=(x·y)
(A=x·yと置く。)
=A
=A+0 (∵零元)
=x·y+0 (∵A=x·y)
このように、グループ化することでどのように変換できるかが分かるようになる。
これも逆順と同じようにハンティントン以外の証明でも活用できる。
s.参考文献
- 情報の論理数学入門...(s.1)
- 小倉久和・高濱徹之, 株式会社 近代科学者, 初版：1991/04/20.
