高校生に伝えたいほんとうの情報科学

論理の話

論理とは、だれもが当然正しいと認める推論、たとえば「ニワトリは鳥である」「鳥は卵から生まれる」から、「ニワトリは卵から生まれる」を導くような推論の体系であり、論理「学」とはそのような体系を学問として取り扱う分野です。

あまり意識していなかったかもしれませんが、中学校や高校で習う数学の「証明」も、整数や幾何学など個々の対象に関する「公理」(「三角形の内角の和は180度である」など)と、「論理」(Aが成り立ち、「AならばB」が成り立つならばBが成り立つ、などのだれもが正しいと認める推論)の組み合わせで成り立っています。

では、なぜ論理の話が「情報科学科」の紹介ページに登場するのでしょうか? それは、情報科学で扱う「計算」と「プログラム」が、「論理」と切っても切れない密接な関係にあるからです。プログラムというのは、コンピューターに何らかの仕事(計算)をさせるために計算手順を書いたものです。実はこれが、論理の世界の「証明」と対応するのです。

これだけでは何のことかわからないと思うので、もう少し説明しましょう。今、ある性質A(x)を満たすxを入力として受け取り、B(x,y)を満たすyを出力するプログラムPを書いたとしましょう。(A, Bといっても抽象的すぎてピンとこない人は、たとえば A(x) として「xは2以上の整数である」、B(x,y) として「yはxの素因数の列である」を考えてください。そうするとPは、素因数分解をするプログラム、ということになります。)

そのプログラムPが正しいとすると、Pは、A(x)を満たすどんなxに対してもB(x,y)を満たすyを見つける方法を与えていることになります。少し見方を変えると、Pは「A(x)を満たすいかなるxに対しても、B(x,y)を満たすyが存在する」ことの証拠を示していると考えることができます。

逆に、「A(x)を満たすいかなるxに対しても、B(x,y)を満たすyが存在する」という主張の証明をよく読めば、xからyを計算する手順がわかったりします。一見ぜんぜん違う職業であるプログラマーと数学者は、実は同じような職業と見ることできる(?)かもしれませんね。

上のような対応関係を使うと、数学の証明をコンピューター上で記述して機械的に検証することもできます。何年か前に話題になった4色定理(平面上の地図は、必ず4色で塗り分けられる、という定理)のコンピューター上での証明も、その原理に基づいています。

論理学は、ほかにもいろいろな場面で情報科学に登場します。論理学を極めることが情報科学を極めることにつながり、またその逆もしかり。論理とのつながりを通して情報科学という学問の奥深さを垣間見ることができます。

4色定理:
どんな地図でも、4色あれば隣り合う領域が異なる色になるように塗り分けられる。

PAGETOP