3

プログラミングで数学の素養がちょっぴり役に立った話

381
1
$$$$

概要

プログラミングでわからないことについて調べていると,多くのソースコード例が見つかるが,それが正しいことまで説明されているとは限らない.本稿では,2つの配列に含まれる要素が同じであることの判定方法が適切かどうかを,対応する命題を証明することで確かめる.

考える問題

JavaScriptを触っていて,次のようなことをしたい場面が出てきました.

2つの配列に含まれる要素が同じかどうか判定したい

配列は,数学的には有限数列と似たようなものです.本記事では,配列に関する深い知識は不要ですので,とりあえず

  • 配列は[1, 2, 3]のように表す
  • array = [1, 2, 3]とするとき,array[0] = 1, array[1] = 2, array[2] = 3である

というくらいの認識で大丈夫です.

また,2つの配列に含まれる要素が同じということについて,具体例を用いて確認しておきましょう.なお,簡単のため,[1, 1, 1] のように同一の要素が複数個含まれる配列は考えないものとします.

2つの配列に含まれる要素が同じ
  • [1, 2, 3][1, 2, 3]:同じ
  • [1, 2, 3][2, 1, 3]:同じ
  • [1, 2, 3][1, 2, 4]:同じでない
  • [1, 2, 3][1, 2]:同じでない

2つの配列に含まれる要素が同じことの判定方法を軽く調べてみたところ,以下のような方法が見つかりました.

      const array1 = [1, 2, 3];
const array2 = [2, 1, 3];

// array1とarray2に含まれる要素は同じなので,以下の結果はtrueとなる
console.log(
    array1.length === array2.length
    &&
    array1.every(element => array2.includes(element))
);
    

何をしているかというと

  • 2つの配列の要素の数が同じであり(&&の前),
  • かつ(&&),
  • 一方の配列のすべての要素が,もう一方の配列に含まれる(&&の後)

ことを確かめています.
さて,この方法で,2つの配列に含まれる要素が同じかどうか判定できていると言えるでしょうか.

証明

先ほどの方法が正しいことを,ある1つの命題を証明することで確かめてみましょう.

  • 集合$A$の要素の個数を$|A|$で表す.
  • 集合$A,B$に対して$B\setminus A=\{x\mid x\in B\text{ かつ }x\notin A\}$と定める.

先ほどの

  • 2つの配列の要素の数が同じであり,
  • 一方の配列のすべての要素が,もう一方の配列に含まれる

を,結論も含めて数学的な主張に直すと,次のようになります.

有限集合$A, B$$|A|=|B|$かつ$A\subset B$を満たすならば$A=B$である.

早速証明してみましょう.

$A\subset B$より$A\cap B=A$であるから,
$$ |B| =|A\cap B|+|B\setminus A| =|A|+|B\setminus A|\tag{1} $$
である.さらに,$(1)$$|A|=|B|$より$|B\setminus A|=0$,すなわち$B\setminus A=\varnothing$である.従って
$$ B=(A\cap B)\cup(B\setminus A)=A\cup\varnothing=A $$
となり,結論を得る.

というわけで,前節で述べた方法が正しいことがわかりました.

まとめ

今回証明した命題はシンプルな主張ではありますが,

  • 出くわした問題に対して適切な命題を与え,
  • それを証明することにより問題を解決する

ことは,数学を学んでいたからこそできたことだと思います.数学ができることはそれだけで強みになりますので,いま数学を学んでいる方も,これから学ぶ予定の方も,自分のペースでじっくり楽しんでください.

投稿日:20211130

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

電気魚
電気魚
21
20510

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中