ぷよぷよ_多重折返しのパターン列挙

ご覧いただきありがとうございます。

多重折返しの譜面のURLをただひたすらに貼っていきます。

(まだ横3しか作成していませんが…。)

ちなみに、私は初心者なので、あまり下記の譜面を鵜呑みにしないことをおすすめします。

あら探しをするぐらいがちょうどよいでしょう。

あと、編集適当です。ご了承ください。

 

 

 

1. 横3


    1.1. L字合わせ


        1.1.1. 横3
            1.1.1.1. http://www.puyop.com/sim/g3worsAlHtsitJGGrBisyrJHjjyGisyrBJ
            1.1.1.2. http://www.puyop.com/sim/4ggioGkAyHtsitJGGrBisyrJHjjyGisyrBJ
            1.1.1.3. http://www.puyop.com/sim/5z0AJ0BrgytIsBikGsBiryrJHjjyGisyrBJ
            1.1.1.4. http://www.puyop.com/sim/E0orqytJijkBIrBijGsBiryrJHjjyGisyrBJ
            1.1.1.5. http://www.puyop.com/sim/o52ylJiykBtrBijGsBiryrJHjjyGisyrBJ
            1.1.1.6. http://www.puyop.com/sim/20gGoEJiyItsztikGsBiryrJHjjyGisyrBJ
        1.1.2. 横2 
            1.1.2.1. http://www.puyop.com/sim/5sgiJGlABGBqjtJjGsBiryrJHjjyGisyrBJ
            1.1.2.2. http://www.puyop.com/sim/2s05i05JjIyIGByjtJjGsBiryrJHjjyGisyrBJ
        1.1.3. 縦3
            1.1.3.1. http://www.puyop.com/sim/g00B04rwkGzAkqllzllHGsBiryrJHjjyGisyrBJ
            1.1.3.2. http://www.puyop.com/sim/305Jg5jqsrjyllslksGrBisyrJHjjyGisyrBJ
            1.1.3.3. http://www.puyop.com/sim/g40EG0AJoGGikztlItlsGsBiryrJHjjyGisyrBJ
        1.1.4. 縦2 
            1.1.4.1. http://www.puyop.com/sim/g50E4Gw2iqJHlkzlItrzJsBAJIkjyGisyrBJ
            1.1.4.2. http://www.puyop.com/sim/5204rg5rB2iqJHlkzlItrzJsBAJIkjyGisyrBJ
            1.1.4.3. http://www.puyop.com/sim/5204rg5rH2iyJHlkzlItrzJsBAJIkjyGisyrBJ
            1.1.4.4. http://www.puyop.com/sim/5204r55rj2iyJHlkzlItrzJsBAJIkjyGisyrBJ
            1.1.4.5. http://www.puyop.com/sim/5g3rE3ly4JqGjlAjlItrzJsBAJIkjyGisyrBJ
            1.1.4.6. http://www.puyop.com/sim/503rl3ly4JqGjlAjlItrzJsBAJIkjyGisyrBJ
            1.1.4.7. http://www.puyop.com/sim/4g0rEisAqqHlBHliqrzisyAJIkjyGisyrBJ
        1.1.5. 1
            1.1.5.1. http://www.puyop.com/sim/g2yHriytzqkzlJqrzisyAJIkjyGisyrBJ
            1.1.5.2. http://www.puyop.com/sim/20grwHqizlzqkzlJqrzisyAJIkjyGisyrBJ
            1.1.5.3. http://www.puyop.com/sim/q00rwgqiHlzykzlJqrzisyAJIkjyGisyrBJ
            1.1.5.4. http://www.puyop.com/sim/gqwHriyljtkzlIqrzisyAJIkjyGisyrBJ
        1.1.6. 順L字
            1.1.6.1. http://www.puyop.com/sim/g2EEqwwrioszglziJqrzisyAJIkjyGisyrBJ
            1.1.6.2. http://www.puyop.com/sim/2EgqwEriwszjlziJqrzisyAJIkjyGisyrBJ
            1.1.6.3. http://www.puyop.com/sim/2E0qwgriBszjlziJqrzisyAJIkjyGisyrBJ
            1.1.6.4. http://www.puyop.com/sim/g00EqwwriqtjlIziIqrzisyAJIkjyGisyrBJ
            1.1.6.5. http://www.puyop.com/sim/5qwkriqtjlIziIqrzisyAJIkjyGisyrBJ
            1.1.6.6. http://www.puyop.com/sim/gywHAiyBjlIziIqrzisyAJIkjyGisyrBJ
        1.1.7. 逆L字
            1.1.7.1. http://www.puyop.com/sim/w0qE4zrkqislHiAHkIqrzisyAJIkjyGisyrBJ
            1.1.7.2. http://www.puyop.com/sim/yg0AEgyiolHiGHkiqrzisyAJIkjyGisyrBJ
            1.1.7.3. http://www.puyop.com/sim/qwgrEwqiolHiAHlIqrzisyAJIkjyGisyrBJ
            1.1.7.4. http://www.puyop.com/sim/tggrwwtJokziGzliqrzisyAJIkjyGisyrBJ
        1.1.8. 順J型
            1.1.8.1. http://www.puyop.com/sim/5gllEIJwijqAziJqrzisyAJIkjyGisyrBJ
            1.1.8.2. http://www.puyop.com/sim/50ll5IJkijqAziJqrzisyAJIkjyGisyrBJ
            1.1.8.3. http://www.puyop.com/sim/50llgIJHijyAziJqrzisyAJIkjyGisyrBJ
        1.1.9. 逆J字
            1.1.9.1 http://www.puyop.com/sim/50rr0llgIJHijiAzyJqrzisyAJIkjyGisyrBJ


    1.2. 準宇宙32

        1.2.1. 横3
            1.2.1.1. http://www.puyop.com/sim/20grwwqiytztIzilqrHisyAJIkjyGisyrBJ
            1.2.1.2. http://www.puyop.com/sim/200rwkqiytztIzilqrHisyAJIkjyGisyrBJ
            1.2.1.3. http://www.puyop.com/sim/2E0rB0qi0tJkkzzJzilqrHisyAJIkjyGisyrBJ
        1.2.2. 横2 
            1.2.2.1. http://www.puyop.com/sim/g2EErwwqiwszolziJqrjisyAJIkjyGisyrBJ
            1.2.2.2. http://www.puyop.com/sim/2EgrwEqiwszslziJqrjisyAJIkjyGisyrBJ
            1.2.2.3. http://www.puyop.com/sim/2E0rwgqiBszslziJqrjisyAJIkjyGisyrBJ
        1.2.3. 縦3
            1.2.3.1. http://www.puyop.com/sim/520zzkArqqijIzktzktqrHisyAJIkjyGisyrBJ
            1.2.3.2. http://www.puyop.com/sim/50g3yw3rq2ijszjJzktqrHisyAJIkjyGisyrBJ
        1.2.4. 縦2 
            1.2.4.1. http://www.puyop.com/sim/2E02wlJiHIzylzyJqrjisyAJIkjyGisyrBJ
            1.2.4.2. http://www.puyop.com/sim/4E0yw5AijyzylzyJqrjisyAJIkjyGisyrBJ
            1.2.4.3. http://www.puyop.com/sim/qE0rw0qijkzyJzylqrHisyAJIkjyGisyrBJ
        1.2.5. 順L字
            1.2.5.1. http://www.puyop.com/sim/30giGwjrwkioJjgkHiAqrHisyAJIkjyGisyrBJ
            1.2.5.2. http://www.puyop.com/sim/3w03GgArwyioBHkkHiAqrHisyAJIkjyGisyrBJ
            1.2.5.3. http://www.puyop.com/sim/w03G03rg2is5HkkHiAqrHisyAJIkjyGisyrBJ
            1.2.5.4. http://www.puyop.com/sim/3w03GgArwyiwBHjkHiAqrHisyAJIkjyGisyrBJ
            1.2.5.5. http://www.puyop.com/sim/w03G03rg2iA5HjkHiAqrHisyAJIkjyGisyrBJ
        1.2.6. 逆L字
            1.2.6.1. http://www.puyop.com/sim/3w0AGgzrwyiolHiAHkkqrHisyAJIkjyGisyrBJ
            1.2.6.2. http://www.puyop.com/sim/3w0AG0zrlyislHiAHkkqrHisyAJIkjyGisyrBJ
        1.2.7. J字型
            1.2.7.1. http://www.puyop.com/sim/3Gg3rw2iwkHqBHiAqrHisyAJIkjyGisyrBJ
            1.2.7.2. http://www.puyop.com/sim/3G03r42ikkHqBHiAqrHisyAJIkjyGisyrBJ
            1.2.7.3. http://www.puyop.com/sim/3G03rw2ikkHqBHiAqrHisyAJIkjyGisyrBJ
            1.2.7.4. http://www.puyop.com/sim/3G03rg2izkHyBHiAqrHisyAJIkjyGisyrBJ
        1.2.8. 逆J字
            1.2.8.1. http://www.puyop.com/sim/3G03rg2izkHiBHyAqrHisyAJIkjyGisyrBJ


    1.3. 準宇宙2-3

        1.3.1. 逆L字
            1.3.1.1. http://www.puyop.com/sim/gg2tE2iw5Jw3soGsJiyHsiAqrJHjjyGisyrBJ
            1.3.1.2. http://www.puyop.com/sim/g02tg2iE5Jw3ssGsJiyHsiAqrJHjjyGisyrBJ
            1.3.1.3. http://www.puyop.com/sim/g02t02ig5JI3ssGsJiyHsiAqrJHjjyGisyrBJ
            1.3.1.4. http://www.puyop.com/sim/g02t02ig5JI3szGsJiyHsiAqrJHjjyGisyrBJ
            1.3.1.5. http://www.puyop.com/sim/2g00t02i55Jk3szGsJiyHsiAqrJHjjyGisyrBJ
        1.3.2. 横3
            1.3.2.1. http://www.puyop.com/sim/g0oE3EwArwzJoyIJHsijyHsiAqrJHjjyGisyrBJ
            1.3.2.2. http://www.puyop.com/sim/og0EE3rw3Js2IJHsijyHsiAqrJHjjyGisyrBJ
            1.3.2.3. http://www.puyop.com/sim/o00Eg3rB3Js2IJHsijyHsiAqrJHjjyGisyrBJ
            1.3.2.4. http://www.puyop.com/sim/o00Eg3rI3Js2IJHsijyHsiAqrJHjjyGisyrBJ
            1.3.2.5. http://www.puyop.com/sim/o00E53rk3Js2IJHsijyHsiAqrJHjjyGisyrBJ
            1.3.2.6. http://www.puyop.com/sim/o00Eg3rI3Jz2IJHsijyHsiAqrJHjjyGisyrBJ
            1.3.2.7. http://www.puyop.com/sim/g0oE3EoArwzJwyIJHsijyHsiAqrJHjjyGisyrBJ
        1.3.3. J字型
            1.3.3.1. http://www.puyop.com/sim/og3GE3rs2iJlIGrIizyHsiAqrJHjjyGisyrBJ
            1.3.3.2. http://www.puyop.com/sim/3og3GIArzyiJlIGrIizyHsiAqrJHjjyGisyrBJ
            1.3.3.3. http://www.puyop.com/sim/3o0zGlArzyiJlIGrIizyHsiAqrJHjjyGisyrBJ
            1.3.3.4. http://www.puyop.com/sim/o03Gl3rs2iJlIGrIizyHsiAqrJHjjyGisyrBJ
            1.3.3.5. http://www.puyop.com/sim/g0oE3Gw3ro2iJlIGrIizyHsiAqrJHjjyGisyrBJ
            1.3.3.6. http://www.puyop.com/sim/o53G43rj2iJlIGrIizyHsiAqrJHjjyGisyrBJ
        1.3.4. 逆J字
            1.3.4.1. http://www.puyop.com/sim/g00E5qo5JI2iIlsiHsGJyHsiAqrJHjjyGisyrBJ
            1.3.4.2. http://www.puyop.com/sim/g00E5qw5Js2iJlsiHsGJyHsiAqrJHjjyGisyrBJ
            1.3.4.3. http://www.puyop.com/sim/g5qI5Jz2iJlsiHsGJyHsiAqrJHjjyGisyrBJ
            1.3.4.4. http://www.puyop.com/sim/g5qJ5JA2iHlsiHsGJyHsiAqrJHjjyGisyrBJ


    1.4. 名無し

        1.4.1. 横3
            1.4.1.1. http://www.puyop.com/sim/g0gE4tg4Aw5JyHssisJGBrkJslrJHjjyGisyrBJ
            1.4.1.2. http://www.puyop.com/sim/gg4tE4Ai5JAHssisJGBrkJslrJHjjyGisyrBJ
            1.4.1.3. http://www.puyop.com/sim/g4oEslwrAgtJAGkqrkJHBrkJslrJHjjyGisyrBJ
            1.4.1.4. http://www.puyop.com/sim/g4owslgrAwtJIGkqrkJHBrkJslrJHjjyGisyrBJ
        1.4.2. 横2 
            1.4.2.1. http://www.puyop.com/sim/g0oE5jg5Jw3ryGksHkJrBrkJslrJHjjyGisyrBJ
            1.4.2.2. http://www.puyop.com/sim/g0oE5jw5Jg3rAGkqHkJrBrkJslrJHjjyGisyrBJ
            1.4.2.3. http://www.puyop.com/sim/og5jw5Jl3rAGkqHkJrBrkJslrJHjjyGisyrBJ
            1.4.2.4. http://www.puyop.com/sim/g0ow5jg5Jw3rIGkqHkJrBrkJslrJHjjyGisyrBJ
        1.4.3. 1
            1.4.3.1. http://www.puyop.com/sim/og2EEABwIJyrsjikBJBrkJslrJHjjyGisyrBJ
            1.4.3.2. http://www.puyop.com/sim/o02EgABBIJyrsjikBJBrkJslrJHjjyGisyrBJ
            1.4.3.3. http://www.puyop.com/sim/o02EgABIIJyrsjikBJBrkJslrJHjjyGisyrBJ
        1.4.4. 縦2 
            1.4.4.1. http://www.puyop.com/sim/o02EgABGIJkrszikBJBrkJslrJHjjyGisyrBJ
        1.4.5. 縦3
            1.4.5.1. http://www.puyop.com/sim/og2EEABgIJyrszikBJBrkJslrJHjjyGisyrBJ
        1.4.6. 順L字
            1.4.6.1. http://www.puyop.com/sim/g0ow3Gw3rl2iy5IHHIJrBrkJslrJHjjyGisyrBJ
            1.4.6.2. http://www.puyop.com/sim/g0oE3Gw3rk2iy5IHHIJrBrkJslrJHjjyGisyrBJ
            1.4.6.3. http://www.puyop.com/sim/og4GI4Ak2iy5IHHIJrBrkJslrJHjjyGisyrBJ
            1.4.6.4. http://www.puyop.com/sim/g0ow4Gg4AB2is5IGHIJrBrkJslrJHjjyGisyrBJ
        1.4.7. 逆L字
            1.4.7.1. http://www.puyop.com/sim/g0oE4jg4Aw3rsGkJrkGzBrkJslrJHjjyGisyrBJ
            1.4.7.2. http://www.puyop.com/sim/g0oE4jw4Aw3rqGkJrkGzBrkJslrJHjjyGisyrBJ

ハンティントンの公理系、入門_大学生向け

目次

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とする。
※ここでは否定を簡単に記載できるため「¬()」と表しているが、他のハンティントンの公理の説明では、「(⁻)」を用いていることが多い。
「(⁻)」はわかりづらいだろうから、具体例を下記に記載する。


\overline{A}

3.1.交換律



x+y=y+x...(3.1.1) \\
x \cdot y = y \cdot x...(3.1.2)

3.2.分配律

x+y·z=(x+y)·(x+z)...(3.2.1)
x·(y+z)=x·y+x·z...(3.2.2)

3.3.単位元と零元

x·1=x (単位元)...(3.3.1)
x+0=x(零元)...(3.3.2)

3.4.補元

x+¬x=1...(3.4.1)
x·¬x=0...(3.4.2)

4.ハンティントンの公理系を満たすものの具体例

集合の代数系は(A;∪,∩,¬())である(※)。
※本来は(A;∪,∩,(⁻))だが、書くのが面倒なため、¬()としている。
「(⁻)」はわかりづらいだろうから、具体例を下記に記載する。


\overline{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.1.x+x·y=x

x+x·y=xを示す

x+x·y
=x·1+x·y (∵単位元)
=x·(1+y) (∵分配律)
=x·(1) (∵単位元の性質)
=x·1
=x (∵単位元)

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.

勉強の定義

目次




はじめに

 来てくださってありがとうございます。
 このページではタイトル通り、「勉強の定義」について書いていきます。また、あくまでも個人的な意見です。「勉強の定義」は人それぞれだと考えております。

意識したこと、このページの特徴

 偉そうな言い方にならないように気を付けました。あと、わざと結論を最後に書きました。理由は答えを皆さん自身で考えるということをしやすくするためです。ちなみに、結論がすぐに知りたい方はまとめの欄をご覧ください。

キーワード

 勉強の定義、迷う、目的、手段、記憶、理解、発想、○○(「勉強の定義」の答え)

対象の方

  • 勉強の仕方が分からない
  • Web上や先生、友達から得た、勉強の仕方に関する情報に振り回されている
  • 柔軟に勉強するのが苦手

といった問題に悩まされいる方の役に立てたらと思い、この記事を書きました。自分は高校生のころにそういった問題にぶちあたりました。また、「勉強は得意だが君の意見を聞いてあげよう」という方など、条件に当てはまらない方にも読んでいただけると幸いです。

読み方

 結論をすぐに知りたい方はまとめの章をご覧ください。ご自分で結論を推測したいという方は順番通りにお読みになることをおすすめいたします。



「勉強の定義」を考えるきっかけになったこと

結論はここに書いてあります。このページではこの「勉強の定義」というテーマを考えるきっかけになったことと、結論を出すまでの過程をそのままの順番で書きました。自分が「勉強の定義」を考えるきっかけになったのは受験生、「高校3年」のときです。そのときに抱いた問題点や特徴は以下の通りです。

  • 手段ばかりに注目していた
  • 継続できない
  • 同じ方法、完璧に計画通りにできないとすぐにほかの参考書に乗り換える
  • どうすべきかを自分で考える能力が低かったため、迷うことが多かった。すなわち、行動力、判断力、継続力が低かった
  • やり方を外部(先生や本など)から取り入れることが多かった

この問題を解決するにはどうしたらいいかを考えました。しばらく考えて出てきたのは「勉強の定義」を考えることです。
「勉強の定義」が問題を解決する理由、メリットは以下の通りです。

  • どんな行動も定義にのっとっていれば先に進むことができる
  • 柔軟性がつく。学んだ方法がなぜ効果的なのかを知ることができる。それを知ることで柔軟に方法を変えることが可能。
  • 決断力が身につく。




「勉強の定義」を導くまでの過程

 まず最初に「勉強の定義」として思いついたのは「記憶」、「理解」、「発想」の3つです。勉強をするという行為は結局のところその3つに分解されると考えました。当たり前かもしれませんが、勉強を進めるには勉強する必要があります。ただ、勉強という言葉は分かりにくいため「記憶」、「理解」、「発想」の3つに分解してみました。
さらに考えると「記憶」、「理解」、「発想」の3つを勉強以外のある1つのワードに集約できることに気づきました。この章ではその1つを導くまでの過程を記述していきます。

まず最初に「記憶」について考察していきます。
具体例から考えてみます。具体例として英単語を記憶することを考えます。英単語を記憶するとはどういうことでしょうか。自分は英単語を和訳、もしくは日本の単語を英訳することだと考えました。
一般化すると「AがBであることを記憶している=AからBを思い出せる=AからBを○○できる」となりました。また、○○のところが「記憶」、「理解」、「発想」の3つを集約した言葉です。

次に「理解」について考察していきます。
「記憶」の考察と同じように、具体例から考えてみます。あと、「ならば」を「→」と表記します。具体例として、「x+2=5 ならば(→)x=3」となることを理解するというのはどういうことかを考えていきます。「x+2=5 →x=5-2→x=3」を言えれば理解したといって良いと思います。さらに、「x+2=5 →x=5-2」を理解しているとはどいうことかを考えます。先ほどと同じようにワンクッション置いた形「x+2=5 →x+2-2=5-2→x=5-2」を言えれば理解したといっていいと言えるでしょう。そして、このことは「x+2=5 →x=3」から「x+2=5 →x=5-2→x=3」を○○できると言い換えられます。この○○は「記憶」のときと同じで「記憶」、「理解」、「発想」の3つを集約した言葉です。
一般化すると「A→Cを理解する=A→B→Cを理解する≒A→CからA→B→Cを○○する」となります。また、今回は「A→B」を理解するということにしか言及していませんが、「A=B」を理解するなど、その他の論理構造においても○○するに置き換えられると思います。それらの説明まですると非常に長くなるので割愛します。

最後に「発想」について考察していきます。 具体例として、「理解」と同じように「x+2=5 の方程式を解く」という問題に言及します。その問題を解くには「2を移項する(x=5-2)」という発想をする必要があります。そして、この「発想」という単語も○○に置き換えることができます。
一般化すると
「Aという問題を解くためにBというアイデアを発想する=Aという問題を解決するためにBというアイデアを○○する」
となります。あまり完璧な一般化でないことはご了承ください。



まとめ

 勉強の原則である○○に入る単語が何か分かりますでしょうか。答えは「連想」です。あくまでも持論ですが、自分は「勉強の定義」は「連想」だと考えました。ちなみに、「考える」ということも勉強とのつながりが強いと思いますが、この言葉も「連想する」に置き換えれると考えています。
 次に、この「勉強するとは連想することだ」という結論を役立てる方法について記述します。「どう勉強すればいいか分からない」というように勉強の仕方に迷ったら「とりあえず連想すればいい」と考えることでどう勉強すればいいかを連想できるでしょう。
 以上です。最後まで読んでくださってありがとうございました。



追記

 みなさんは勉強の原則は何だと思いますでしょうか。よろしければご意見をお聞かせください。



参考資料

 特になし

連結グラフ 判定アルゴリズム

目次

はじめに

見に来てくださってありがとうございます。ちなみに初投稿です。
このページでは、タイトル通り、与えられたグラフが「連結グラフ」であるかどうかを判定するアルゴリズムについて説明していきます。

キーワード

グラフ理論、連結グラフ、つながっている、隣接、探索、深さ優先探索(DFS)、頂点、道

対象の方

グラフ理論の基本事項をご存じな方が対象です。具体的には、キーワードにおいて、「深さ優先探索」以外のものをご存じな方となります。また、プログラムは「Python」で書いております。

理解のコツ

アルゴリズムグラフ理論が好きでない方は下記にあるGif画像(動く画像)を中心に御覧になることをおすすめ致します。さらに練習問題も用意致しましたので、よろしければそちらもご覧ください。また閲覧する順番は以下がおすすめです。
1.「直感的な方法」の節でなんとなく理解
2.「練習問題」の章で自分の理解が正しいかを確認
3.「アルゴリズムの詳細」の節でアルゴリズムを厳密に理解する
4.「ソースコード」の章でプログラムを理解する
 

アルゴリズム

直観的な方法

 

f:id:inninzityou:20180228144715g:plain
連結グラフ判定アルゴリズム
※画像の説明:青や赤で括られた頂点は現在注目している(探索中の)ものを表しています。また、頂点の外にある数字は、頂点の番号で、中に書いてあるのはラベル付けの際に利用した数字です。

まず、直観的な方法について説明いたします。また、直観的な方法ですので、曖昧な部分があります。そこは「アルゴリズムの詳細」の方で解決いたします。
深さ優先探索(幅優先探索でも可能)と呼ばれるアルゴリズムを用いて頂点にラベル付け(印をつけること)していく。
すなわち、現在注目している(探索中の)頂点と隣接している頂点の中で、まだ探索していないものを新たに探索しラベル付けする。また、その条件にあてはまらない場合は前に探索した頂点を再び探索する(ここの表現は曖昧)。最終的にすべての頂点がラベル付けされていれば与えられたグラフは連結グラフである。そうでなければ連結グラフではない。
 

アルゴリズムの詳細

前提条件

  • グラフGは無向グラフとする
  • 位数(頂点の数)をp(>=1)
  • サイズ(辺の数)をq(>=0)
  • V(G)={v_0,v_1,v_2,...,v_(p-1)}
  • E(G)={e_0,e_1,e_2,...,e_(q-1)}

Step1. labelに0を代入。
Step2. v_0のラベルをlabelとする。
Step3. v_0に隣接している頂点をvとしStep5へ。隣接している点が存在しなかった場合はStep8へ。
Step4. vに隣接かつ未探索である頂点を新たにvとし、Step5へ。その条件にあてはまる頂点が存在しない場合はStep7へ。
Step5. labelにlabel+1を代入する。
Step6. vのラベルをlabelとし、Step4へ。
Step7. 隣接している頂点の中で現在探索中のラベルより小さい中で一番(ラベルの)番号が近い頂点を選びStep4へ。もし、現在探索中のラベルが0だった場合はStep8へ。
Step8. 全ての頂点がラベル付けされていたらグラフGは連結グラフ。そうでなければ連結グラフではない。

ソースコード

このコードでは「隣接行列」と呼ばれるものを使って、グラフをコードに落とし込んでいます。ご存じない方は「隣接行列」を調べてから、このコードを読むことをおすすめします。

class Graph:
    #グラフを表す

    # 頂点につけるlabelの初期値(ラベリングされていないことを示す値)
    no_labeling_num = -1

    class Vertex:
        # 頂点を表す

        def __init__(self, g, no, label):
            """

            :param g: グラフを表す。またVertexを所有するオブジェクトでもある
            :param no: 頂点にグラフのなかで一意に割り振られた識別用の番号
            :param label: 探索された順番を表す番号。ラベル。
            """
            self.no = no
            self.g = g
            self.label = label

        def __str__(self):
            """
             
            """
            return "no:{0},label:{1}".format(self.no,self.label)

        def adjacentVs(self):
            """ selfと隣接している頂点のリストを返す

            :return:
            """
            result = []
            for c in range(self.g.order):
                if self.g.aDJM[self.no][c] == 1:
                    result.append((self.g.vs[c]))
            return result

        def back_to_previous(self):
            """ 前に探索した頂点を返す(厳密な表現ではない)
            詳細
            ・この頂点に隣接する頂点において、ラベル付けされていない(未探索)なものがないときに、
            次に探索する頂点を返す関数
            ・自身のラベル番号より小さい頂点の中で一番近いものを返す
            ・存在しないときは「None」を返す

            :return:
            """
            result = None
            vs = list(filter(lambda x: self.label > x.label, self.adjacentVs()))
            if vs != []:
                result = vs[0]
                key0 = self.label - result.label
                for v in vs:
                    key1 = self.label - v.label
                    if (key1 < key0):
                        key0 = key1
                        result = v

            return result

    def __init__(self, aDJM):
        """
        
        :param aDJM:隣接行列
        """
        self.aDJM = aDJM
        self.order = len(aDJM)
        self.vs = [Graph.Vertex(self, i, self.no_labeling_num) for i in range(self.order)]

    def no_labelingVs(self, vs):
        """ 渡された頂点リストにおいてlabelingされていない頂点のリストを返す

        :return:
        """
        result = []
        for v in vs:
            if v.label == self.no_labeling_num:
                result.append(v)
        return result

    def isconnected(self):
        """ このグラフが連結グラフであるかどうかを判定する
        
        :return:
        """
        label = 0
        v = self.vs[0]
        v.label = label
        # 最初に探索した頂点が孤立点である場合に対処するための条件
        if v.adjacentVs()==[]:
            v=None
        else:
            v = v.adjacentVs()[0]
            label += 1
            v.label = label
        while (v != None):  # 現在探索中の頂点のラベルが0かつその点に隣接する頂点すべてが探索ずみだったら終了するようにする
            vs = self.no_labelingVs(v.adjacentVs())
            if vs == []:
                v = v.back_to_previous()
            else:
                v = vs[0]
                label += 1
                v.label = label

        return not(self.no_labeling_num in list(map(lambda x:x.label,self.vs)))

# 隣接行列
aDJM = [[0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0],
        [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
        [1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
        [0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
        [1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
        ]

g=Graph(aDJM)

print(g.isconnected())

練習問題

 以下の図において、今回紹介したアルゴリズムに基づいてラベル付けをしてみてください。

f:id:inninzityou:20180306162321p:plain
練習問題1
 
f:id:inninzityou:20180306162522p:plain
練習問題1_解答

解説
 他の手順、解答も存在します。例えば、v_0の次にv_1に注目していますが、v_3、もしくはv_5でも構いません。なお、この解説では、どこに注目し、ラベル付けしたのかということしか書いておりません。詳しい情報は上記の「アルゴリズム」などの項目をご覧ください。

v_0に注目(を探索)
v_0に0とラベル付け(印をつける)

v_1に注目(を探索)
v_1に1とラベル付け(印をつける)

v_2に注目(を探索)
v_2に2とラベル付け(印をつける)

v_1に注目(を探索)

v_0に注目(を探索)

v_3に注目(を探索)
v_3に3とラベル付け(印をつける)

v_4に注目(を探索)
v_4に4とラベル付け(印をつける)

v_3に注目(を探索)

v_0に注目(を探索)

v_5に注目(を探索)
v_5に5とラベル付け(印をつける)

v_0に注目(を探索)
探索終了
すべての頂点がラベル付けされているのでこのグラフは連結グラフである。

f:id:inninzityou:20180306162525p:plain
練習問題2
 
f:id:inninzityou:20180306162528p:plain
練習問題2_解答

解説
v_0に注目(を探索)
v_0に0とラベル付け(印をつける)

v_1に注目(を探索)
v_1に1とラベル付け(印をつける)

v_2に注目(を探索)
v_2に2とラベル付け(印をつける)

v_1に注目(を探索)

v_3に注目(を探索)
v_3に3とラベル付け(印をつける)

v_1に注目(を探索)

v_0に注目(を探索)
探索終了
ラベル付けされていない頂点が存在するので与えられたグラフは連結グラフではない。

追記

 ソースコードについてですが、無理矢理クラスにせず、もっと簡潔に書けば良かったように思えます。書き直すのは面倒なのでお許しください。また、自分は変数を命名するセンスが皆無です。よろしければご教授ください。ちなみに変数の付け方において知っていることは、キャメルケース、スネークケース、クラス名は基本最初が大文字、定数はすべて大文字、Pythonは基本スネークケースなどです。