ブログ「サイバー少年」

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

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

ペアノの公理と特殊な数学的帰納法

今回は、あんまり深く考えないで数学について記事にしようということで、以前の記事で数学的帰納法を使ったときに思ったことを書きます。

あんまり考えて書いていないので、特に新たな発見をしたわけではないのですが、ちょっとしたアイデアとして。


数学的帰納法は、なにも0や1(自然数の最初の数)から始まって1つ後ろの数、その1つ後ろの数というふうにドミノ倒しされるとは限らず、

0や1でない自然数から始まって、1つ後ろでないところの数へとドミノ倒しされることがあります。

数学的帰納法の応用ですね。
我らがWikipediaにも書いてあります。

数学的帰納法 - Wikipedia
https://ja.wikipedia.org/wiki/%E6%95%B0%E5%AD%A6%E7%9A%84%E5%B8%B0%E7%B4%8D%E6%B3%95


そんでもって、数学的帰納法は形式論理で扱うときにどのようになるかというと、自然数に関する公理のひとつとなります。

ペアノの公理というやつで、それの一番最後の公理が数学的帰納法を正当化するための公理となります。

ペアノの公理 - Wikipedia
https://ja.wikipedia.org/wiki/%E3%83%9A%E3%82%A2%E3%83%8E%E3%81%AE%E5%85%AC%E7%90%86


余談ですが、こういうふうに自然数はどんな性質なんだろうと突き詰めて公理を発見するのではなく、自然数とはこういうものなんだという性質を、神ではない我々が定義することができるというのは、なんか数学の面白さのひとつですよね~。

まあ、私が定義できるほど実力はないのですが…。
ただ、こういう公理主義的な考えの上での数学は、自分で作れるという意味でプログラミングと似ていると思います。

続きを読む

tag: 数学 論理学 論理式 自然数 考察 命題 形式 帰納法

[環論] ユークリッド整域で陥った詭弁

今回も環について知っていないと分からない話をします。

群・環・体の勉強で、特別な環であるユークリッド整域について学び始めました。
とりあえず定義だけ読んだのですが、以下のような定義となります。

なお、本に書いてありましたが、普通の定義より強くしているそうです。

任意の整域(A,+,×)に対してa∈Aを非負整数に対応付ける関数H(x)で次のような条件を満たすものが存在する整域をユークリッド整域と呼びます。

1. H(0) = 0かつH(a) = 0ならa = 0 (0は加法の単位元)
2. a ≠ 0かつb ≠ 0なら、H(a×b) >= H(a)かつH(a×b) = H(a)となるのはbが単元のときのみ

3番目の重要そうな条件もあるのですが、ここでは使わないので省略します。
このH(x)をxの高さと呼びます。

そして、a∈Aとb∈Aの公約元xの中で高さが最大になるものを最大公約元と呼びます。
公約元は普通の環でも存在する概念ですが、最大公約元はユークリッド整域でないと存在しない概念ですね。

そして、aとbの最大公約元が単元であるときaとbは互いに素であるといいます。
つまり互いに素であるというのもユークリッド整域でいえる概念なのですが、私はそれに違和感を覚えたわけです。

続きを読む

tag: 数学 勉強 群環体 素数 証明 約数 論理 ユークリッド

一次不定方程式について調べた

前々回の記事「[環論] 素元と既約元の違いってなんなのよ」および、前回記事「数学ネタは人気が出ないのか…」で書いたとおり、
群・環・体の本を読んでいたら不定方程式にぶち当たったので、最近は群・環・体をやらずに不定方程式について調べていました。

群・環・体の本にも予備知識として不定方程式について解説があったので、それを読んだのと、あと不定方程式は高校一年生のときにやりましたから、数Aの教科書をひっぱりだしてきて読んでみました。

覚えてないからな!!

そこで思ったのですが、本によって不定方程式の解法にしても全然、やり方が違いますね。
数学って知識を丸コピするよりか、自分で考える学問ですから考える人が違うと内容もだいぶ違ってしまうんでしょうね。

私は丸コピしか出来ないですが…。


さて、今回はレポートを書く気分で、(一次の)不定方程式について調べて学んだことを記していきたいと思います。

続きを読む

tag: 数学 方程式 勉強 素数 証明 数学的帰納法 学校

[環論] 素元と既約元の違いってなんなのよ

環について知っていないと分からない話を今回はします。

私が群・環・体の勉強に使っている本では、環の章に可換環における素元の定義として

p = abで表せるならaかbのいずれかが単元であるとき、pは素元である
(pは0でも単元でもない)


というふうに書かれていたんですが、インターネットで調べてみたらこれは実は素元の定義ではなく既約元というものの定義だそうです。

まぎらわしいですね。
これは私が読んでいる本が悪いのか。

私が群・環・体の勉強に使っている本は分かりやすい素晴らしい本ですけども、
環の定義として一般的には、乗法について可換であることは公理としませんが、可換環ではなく普通の環が乗法について可換であるとされていたりして、
素元の件も含めてちょっと一般的な定義とズレていますね。


それで、本当の素元の定義とは何かといいますと、

まず可換環においてp | aと書いたときa = xpとなるxが存在するという意味にして、まあ直感的にはpがaを割り切るといえますけども、

p | abであるならp | aまたはp | bであるとき、pは素元である
(pは0でも単元でもない)


ということになります。


しかし、素元と既約元は似ているというか、環よりもう少し条件を強くした代数系においては一致することがあるんですよね。

続きを読む

tag: 数学 群環体 証明 素数 方程式

数理論理学の些細な気づきごと

数理論理学の勉強はもう終わらせてやめましたが、最近ふと気づいてしまったメチャメチャどうでもいい発見があったので、たいしたことではないですから短くまとめます。

すごく小さな発見を、今回は2点ほど用意しております。

(追記ですが、ちっとも短く書けませんでした…)


まず1つ目ですが、xor演算についてです。
数学というより、プログラミングで論理演算をするときに知っとくとためになるかもしれませんね。

xorは、a xor bだったら、どういう意味かといえば、

aとbが両方ともfalseなら結果もfalse、aかbのどちらかだけがtrueなら結果はtrue、aとbが両方ともtrueなら結果はfalse、ですよね。


じゃあ、これがa xor b xor cと3つになったらどうなるでしょうか。
ちなみに左結合、つまり(a xor b) xor cです。

これは、感覚的には2項バージョンの拡張として、a,b,c全てがfalseなら結果はfalse、a,b,cのどれか1つだけがtrueなら結果はtrue、a,b,cのうち2つ以上がtrueなら結果はfalseになる演算だとみなしたいわけですが、そうはならないようなんですね。

反例としては、a,b,cが全てtrueだとしたら結果はfalseになってもらいたいわけですが、a xor bの時点で一回falseになってしまうので、そのfalseとcつまりtrueをxorして、結果はtrueになってしまうと。

ちなみに情報工学ではメジャーな話ですが、x xor trueをかけるとxの反転が得られますから、a xor b xor c xor dのa,b,c,dが全てtrueならa xor b xor c = trueの反転でfalseですね。

偶数個の項なら反例になりませんが奇数個のとき反例になることになります。


また、補足しておくと、ブール代数での話ですが、2項バージョンのときa,bの片方がtrueならtrueというのは、この“片方がtrue”というのが、
「1つだけtrueで残りはfalse」ということなのか、「1つ以上trueがあるが1つ以上falseがある(確実にすべてfalseではないが確実に1つはfalseがある)」ということなのか、という二つの捉え方があって、

これらは2項バージョンにおいては同値ですから違いが曖昧なのですが、3項以上になると違う命題になるので、後者のほうの捉え方も3項以上バージョンでは、また別個に考えられます。

つまり後者の捉え方で、a xor b xor cを、
a,b,c全てがfalseなら結果はfalse、a,b,cのうち1つ以上trueがあって1つ以上falseがあれば結果はtrue、a,b,c全てがtrueなら結果はfalseになる演算だとみなすこともできるわけですね。


さらに、trueでなくfalseの個数に着目した場合、つまりtrueとfalseが出てくる箇所をひっくり返した場合に後者では同値となりますが、前者では違う命題になるので、前者の捉え方のtrueとfalseをひっくり返した捉え方も論理的にはありますが、
まあa xor b xor cを感覚的に捉えるならばfalseの個数で考えるという発想はないと思いますので、この場合は無視しましょう。

だとすれば、上の話での後者の捉え方はどうなのかというのは考えなければなりませんが、このときも前者のときと同様にa,b,cが全てtrueという反例があって、感覚的なものとは違う真理値になります。


感覚的に捉えたものと同じ真理値にしたい場合はどういう論理式を書けばいいのかというと、後者の捉え方の場合は単純に、
(a or b or c) and not (a and b and c)みたいに全ての項をorでつなげたものと、andでつなげたものの否定の論理積をとるだけです。

むしろ、2項の場合はa xor bは(a or b) and not (a and b)と同値なのに、3項以上の場合は同値でなかったことに驚きますね。


前者の捉え方では、2つ以上の項がtrueにならないことを表現するために、あらゆる2つの項の組み合わせについて論理積がtrueにならないことを言わなければならないわけで、

a,b,cなら(a or b or c) and not (a and b) and not (a and c) and not (b and c)みたいに、長いですね。

全ての項をorでつなげたもののあとに、n項ならばnC2個の2つの項の組み合わせの論理積の否定を付けて、論理積でつなげなければなりません。
nandを使えば(a or b or c) and (a nand b) and (a nand c) and (b nand c)みたいに若干、短くなるか…。


というわけで、イメージ通りにやりたい場合はxorでつなげるのでは駄目で、地味に大変な論理式を書かなければならない、という話でした。

そうそう、上記の論理式を書く以外にも、真理値表をもとに論理式の標準形を書くという手段も、一応ありますね。

続きを読む

tag: 数学 論理学 論理式 論理演算 写像 集合 同値 組み合わせ 考察 クソ記事

数学が難しい

前回記事「論理学の勉強コンプリート!!!」で書いたとおり数理論理学の勉強が終わったので、
今は「群・環・体」を図書館で借りた本を読んで勉強してるんですが、なんとも心が折れそうです。

まだ本題には入っておらず、集合と写像についてやったり自然数や整数の性質を学んだりしているページを読んでます。

集合と写像は、去年の十二月にも数理論理学関連で勉強しましたけどね。
まあ置換とか、ちょっぴり新たな概念もありましたけども。


自然数とか整数が難しい!!!

今までやってきた論理学に比べて、こいつらは、かなりワーキングメモリがないと理解できないですね。

集合と写像においてもそうですが、こういう系統のやつは具体的にイメージする対象があって、自分でそれをイメージしないと駄目なものですから。

数理論理学は、なんか上手いこと表現できないですが、とにかく何かをイメージするということはあんまりなかったんですよね。


まあ対象をイメージできないなら、もしくは式を変形するだとか論理的にひとつずつ推論していくことで、形式的に理解するという手立てもあると思いますが、
前回記事で書いたように私には論理を積み重ねる力もたいしてないので、なかなか難しいものがありますね。


このまえ前回記事で

しかし私だってそりゃ書かれてあることを読んで一瞬で理解できるなんてことはほとんどないですが、時間かけたら大抵のものは理解できますよ。

だのなんだのと言っていましたが、なんかもう撤回したい気分ですね。
数学をナメていた…。


整数の性質で、ユークリッドの互除法とか出てきたんですけど、わけわかめって感じでした。
さすがに完全にわからないわけではないですが。

ユークリッドの互除法は、学校でもやらされた気がするんですけどね。
覚えてねえ!


そういえば、集合と写像のページを読んでいて思ったんですが、かなり初歩的な問題だと思いますけど、ちょっと閲覧者の方に数学できる方がいらっしゃればお聞きしたいのですが、

要素数が同じの2つの有限集合A, Bと写像f:A→Bで、fが全射であることとfが単射であることって同値ですよね。

頭のなかで図をイメージすれば、これは正しいような気がするんですが、証明しようと思ったら論理力がなくてできない…。


インターネットで検索すればいくらか似たような問題の証明が出てくるんですけどね。
たとえば、こんなブログ記事が。

よしいずの雑記帳 対等な有限集合における全射と単射の同値性
http://yoshiiz.blog129.fc2.com/blog-entry-694.html


2つの集合が対等であるとは、2つの集合に全単射が存在するという意味だそうですから、有限集合において対等とは、つまり要素数が同じであることと同値だと思うので、これはまさに私が考えている問題の証明だと思うんですが、

読んでもよくわからない…。
イマジネーションが足りないですね。


この他にもQ&Aサイトに写像fの定義域と値域が同じ有限集合の場合において、fが全射であることとfが単射であることの同値性の証明が載ってたりしまして、
その証明を応用するだけでも要素数が同じという条件にまで拡張できると思うんですが、やはりよくわからない…。


数学難しいですね。
まあ分からないことが分かるようになるという喜びが数学の醍醐味なわけですが。

でも分からなさすぎなんだよチクショオオオオオオ!

tag: 数学 勉強 問題 証明 代数学 ワーキングメモリ 集合 写像

形式論理と自然演繹の紹介

論理学の勉強で自然演繹を学んだので、とうとうご紹介したいと思います。

論理学といえば自然演繹、自然演繹といえば論理学ですね。
いや、そんなにでもないか…。


自然演繹を紹介するとは言っても正直なところ、健全性や完全性の証明とかそんな深入りして紹介するのは大規模過ぎて難しいので、
さらっと規則を紹介したり、具体例を示したり、で済まそうと思いますが。

あと、述語論理での扱いも入れたかったのですが、面倒なのと、固有変数条件あたり熱弁して空回りするクソ解説を生産しそうなので、命題論理にとどめておきました。


自然演繹は論理学の形式的証明の方法のひとつで、自然演繹の他には、
ヒルベルト式と呼ばれる矢印だらけの気色の悪い、仕組みは単純だけど使うのが難しいものとか、

シークエント計算という、これはまだ勉強中なのでコメントしづらいんですが、シークエントというものに対してゴニョゴニョしていくものなどがあります。

ちなみに、自然演繹とシークエント計算は、同じゲンツェンという人が発明したそうです。


さて、今回の記事は前編と後編ではなく、ひとつの記事で完結しますが、執筆には2日間かけています。

続きを読む

tag: 数学 論理学 構文論 論理式 証明 命題論理 直観主義 自然演繹 形式 勉強

順序集合を並べるアルゴリズム

たいした内容ではないのですが、また数学のネタです。

今日は脳みそのコンディションが悪いので、読むに耐えないクソ記事になっているかもしれないですが…。

半順序関係が与えられた集合に対して、その半順序関係の情報に基づいて一列に並べるアルゴリズムについて考えていました。

その集合は“有限”の集合であると但し書きしないといけませんね。
なんか全部、有限であることが前提みたいに考えてしまうのは、情報系の人間の悪い癖だと思います。


さてしかし、普通、全順序関係じゃないと一列に並べられないんじゃないかということなのですが、

ここでは任意の元x,yについて、x <= yという順序関係があるとき、yは必ずxの右(上でもいいからとにかく大きい側の方向を定める)に来るという条件を充足するように、半順序集合の全ての元を一列に並べることを、一列に並べることとします。


つまり、大小比較できない二つの元については、どんな順番でもいいから無理やり一列に並べて、
大小比較できる二つの元については確実に、大きい元が大きい側になるように並べるということです。


このような一列を生成するアルゴリズムを、考えたわけなのですが、アルゴリズム自体はクソ簡単なものです。

そもそも私は難しいアルゴリズムを考案できるほどの脳みそがないので…。

続きを読む

tag: 数学 集合 順序 関係 アルゴリズム 計算 帰納法 証明 地図

数学の勉強について雑記…

今回の記事は本当に雑記です。
話を体系的に書くという意識がまったく感じられないものであります。

つまりはクソ記事であるということをご承知ください。


私は最近、数学が好きなので、数学の特に数学基礎論という部分について勉強したり考え事していたりするのですが、

…もしかして自分には数学の才能がないのではないかと思ってしまいますね。


まず数学において重要な、発想力が私は大きく欠如していますね。
だから証明しろとか言われても、どのようにすればいいのかわからない。

答えを見ずに自分の力でなんらかの知見を生み出すことができないのは、数学をやる人間としてどうかという感じですね。

無から何かを探すというのは、すごく考えのフィールドが広すぎて、探索しきれないということですね。

まあ、このフィールドの広さの中で知見を生み出すためには、問題を小さく分割してちょっとずつ考えて、
小さな結論をひとつずつ出していって、最後に大きな結論を出すというのが必要になると思うんですが、

なんか私の場合、大雑把になってしまうということですね…。
たぶん、脳のワーキングメモリが足りないので、細分化しても忘れちゃうんですね。

全体を一気に考えないと頭の中のイメージが崩れてしまうというか。
でも、全体を一気に考えるなんて、大きすぎて出来ないということです。

さらに、有限のものに対してはイメージできるとしても、無限のものはイメージ出来ないので、苦手ですね。

たとえば数学的帰納法とかも、苦手です。


さて一方で、すでに答えが書かれてあるときに、答えを読んで理解する力というのは、まあまあかなと思うのですが、

それでも理解力も足りないと、思ってしまいますね…。

いや、なんというか書かれてあるイメージが、日本語に書き下せる場合と、日本語にできない場合があると思うんです。

日本語で考えられるものであればわりと理解できるんですが、日本語にできないものは苦手ですね。
イメージをイメージのままにして考える力がないんですかねぇ…。

続きを読む

tag: 数学 集合 順序 関係 論理学 述語論理 公理 勉強 偉人 ワーキングメモリ

命題論理の意味論まとめ (後編)

昨日は命題論理について勉強したことのまとめとして、記事「命題論理の意味論まとめ (前編)」を書きましたが、

今回はより話が本格的になってくる後編を書いてまいります。


なお前編で、集合{ T, F }の要素としてのT, Fと、論理式の構成要素としてのT, Fは別物だということに注意しなければならないと触れましたが、

今回はそれを区別するために、論理式の構成要素として使うのはT, Fなんですが、
命題論理で使う集合の{ T, F }のほうは{ 1, 0 }に改めます。

もちろん1が真で0が偽なので、そのように読みかえてください。



前編で言った∨, ∧, ¬の三種類の演算があれば、実は残りの→, ↔は代用可能であるということの、理由については言及しませんでしたが、

まずa→bは、aならばbであり、aでなければあらゆる場合に真ということでしたからaかつb、またはaでないのどちらかで、(a∧b)∨¬aといえます。

つまり代用可能です。

しかしよく考えれば、(a∧b)¬aは満たす条件が排他的ですが、わざわざ排他的にする必要もありません。

つまり、aがなんであれbが真ならばこの演算は真であって、ようするにb∨¬aというふうに、よりスリム化できます。


今、日本語でグダグダと説明しましたが、もちろん厳密にそれを言うためには、前編で触れたように表を用いて確認します。

ただ、今の話のように、演算子の日本語としてのイメージを捉えたうえでわかることというのを考えて、最後に表で確認するという方法は悪くないですね。


まあこの先、それでどんどん法則が増えていって、ほとんど法則とかで同値変形していく感じになって、今後は日本語を使うことなんてほぼないですが…。


なお、a↔bについては、aならばbだしbならばa、ということになるので、これも日本語的に考えて(a→b)∧(b→a)となります。

二つの演算は前述のようにで代用できるので、それをで結んでいるだけなので、結局も三つの演算で代用できることになりますね。

続きを読む

tag: 数学 論理学 法則 標準形 論理式 命題 命題論理 意味論

次のページ

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