nigoblog

暫定無職のブログ

数学とプログラミングについて考察 ~ペアノの公理~

数学ガールって本が好きなんですけど、現在5作出ていて第三弾目の「ゲーデル不完全性定理」っていう本を読み直しました。

数学ガール ゲーデルの不完全性定理 (数学ガールシリーズ 3)

数学ガール ゲーデルの不完全性定理 (数学ガールシリーズ 3)

これの2章にペアノの公理の話があるんですが、今回その章を読んだ感想と、プログラミングにその考えを応用してみるとどうなのかって話を考察したので書いていきたいと思います。

  1. ペアノの公理とは
  2. TDDとテストケースについて
  3. ペアノの公理とテストケースの関係
  4. まとめ

このような流れで書いていきます。

ペアノの公理とは

先に示した数学ガールを読んでいただくのが一番手っ取り早いのですが、
Webだと普通にwikipediaがいいですかね。
ペアノの公理 - Wikipedia

数学ガールの文をどこまで引用していいかわからないので簡単にペアノの公理について説明すると、
自然数を定義する公理」
っていう表現が一番正しいかと。
1 + 1 = 2を証明するための公理です。

※ちなみに数学ガールの場合 1, 2, 3, ...をwikipediaの場合 0, 1, 2, ... を自然数としております。

1 + 1 = 2を証明するという言い方はやや語弊がありますが、ペアノの公理を使うと自然数全体の演算が説明つきます。
wikipediaの公理から
公理1では
0 は自然数であるといえ、
公理2では
0 に続きがあるということがいえる。これを後続数といい 0' と表す。
公理3では
0 の続きになるものは0にはならない。つまり0が一番先頭の自然数であると示す。
公理4では
自然数の2つA, Bがあったとき Aの後続数A'とBの後続数B'は一致しない。
つまり異なる自然数の後続数が同じ数ではあってはいけない。ある自然数とその自然数の後続数はそのペアでしか存在しないことを示している。
違う言い方をすると自然数 A, Bがあったとき、A=Bならば A'=B'である。
公理5では
数学的帰納法の話。プログラマ的にいうと関数 f(x) があったとき、x = 0の時にxに対応するリターンがあるならばx = n(自然数)になっても正しい結果が出る事を示している。(この場合はx = 1の方がわかりやすいと思うが。)

ポイントは0の後続数をいきなり1と言わない事。0以外の自然数はまだわかっていないこととしている。

というわけでざっくりペアノの公理についての説明でした。

TDDとテストケースについて

いきなりプログラミングの話になりますが、開発手法の一つにTDDという方法があります。
なんども書いているのでもう一度解説することはありませんが。
TDD(テスト駆動開発)でハノイの塔の実装をしてみる~TDD超入門~ - nigoblog
このとき重要なのはテストケースです。
厳しすぎても意味がないし、浅すぎてもテストに合格したとは言えません。

というわけでここでペアノの公理とテストケースの関係について考えることで最適なテストケースの洗い出しを考えてみましょう!

ペアノの公理とテストケースの関係

ここでfizzbuzzをTDDで開発することを考えます。
fizzbuzzについてはこちらを参考に
テスト駆動開発でFizzBuzz問題を解く - nigoblog
テストケースを考える前にfizzbuzzをもう一度掘り下げてみます。
1. 3の倍数でfizz
2. 5の倍数でbuzz
3. 3の倍数であり5の倍数であるときはfizzbuzz
をそれぞれ返し、具体的には

1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, ... , 13, 14, fizzbuzz, ...

というような数列を作ります。この定義では明示しておりませんが、入力は全て自然数を前提とします。
これをもう少し数学チックに考えてみます。
1. 3nかつ¬5nならばfizzを返す
2. 5nかつ¬3nならばbuzzを返す
3. 15nならばfizzbuzzを返す
4. nは自然数である (n>0)
というわけで入力は自然数であることも明示しました。(¬は否定)
3n, 5n, 15nはそれぞれの係数をスタートとし、その倍数の自然数の集合と見なし、ペアノの公理が満たされているとします。
ここでペアノの公理を利用したテストケースは以下のようになります。
まずは4の自然数以外で例外を出すかどうかのチェック

  • 入力 0 ならば例外
  • 入力値の符号がマイナスならば例外
  • 入力の型がint以外ならば例外

まずはこれで自然数以外をカットすることができました。
つまり入力は自然数限定ということを表しています。
なので数学的帰納法により、

  • 1の時1を返す

これが成り立つということは全ての後続数でも成り立ちます。
また、3nの集合、5nの集合、15nの集合でも同様にテストするので

  • 3, 6でfizzが返る
  • 5, 10でbuzzが返る
  • 15, 30でfizzbuzzが返る

これでペアノの定理5より、全てのケースがテスト出来ている状態と言えます。

まとめ

今回、初めての試みとして数学とプログラミングについての関係を書いてみました。
正直考察がやや甘いところもあるとは思いますが概ね考えたことはかけたかなと思います。

内容の方は、このように数学的帰納法や集合を意識するとテストケースに漏れがなく無駄のないテストケースが書けるのかなと感じております。
もともと集合について読み直すきっかけはデータベースの設計部分だったので、
それに関しても考察できたら書いていこうと思います。

というわけで数学とプログラミングについての考察でした。

参考図書

数学ガール ゲーデルの不完全性定理 (数学ガールシリーズ 3)

数学ガール ゲーデルの不完全性定理 (数学ガールシリーズ 3)

是非読んでみてください。