プログラミングで理解する反射律・対称律・推移律・反対称律

集合論とか離散数学の分野で反射律・対称律・推移律・反対称律というキーワードが登場する。
大学での授業では、とても抽象的に説明がされるので、そもそも何の話をしているのか理解できない、という状態になりがち。

インターネット上を検索すると、それなりの情報が得られるものの、それでもやっぱりよくわからない。

そこで何かわかりやすい説明の方法はないものか・・と考えたものの、
これって文章で説明しようとするからいけないのではないだろうか。

そもそも扱う対象が論理の話なので、プログラミングに例えるのがいいに違いない。

というわけで、以下は「プログラミングで理解する反射律・対称律・推移律・反対称律」。

例題として「二項演算子★は反射律・対称律・推移律・反対称律をそれぞれ満たすか?」という問題を考えてみる。

ここで、演算子★は、anOperation という名前の関数で定義されるとすると、
この関数は2つの引数を取る。
そして、真または偽のどちらかを返すので、戻り値は boolean 型だ。

というわけで、次のように記述できる。

boolean anOperation(x,  y) {
  if(x と y の関係が条件を満たす) { return true }
  else { return false }
}

■ 反射律
さてここで、この二項演算子が反射律を満たすかどうかは、次のように判定できる。

foreach(集合に含まれる要素 a) {
  if(anOperation(a, a) == false) {
    print( anOperation で定義された演算は反射律を満たさない )
    return // 判定終了
  }
}
print( anOperation で定義された演算は反射律を満たす )

つまり、引数として同じものを2つ渡した時に、常に結果が true となる演算子であれば「反射律を満たす」と言える。
この条件は、演算の対象となる集合の要素すべてに対して当てはまる必要があるので、1つでも例外があれば、反射律を満たさないということになる。

■対称律
二項演算子が対称律を満たすかどうかは、次のように判定できる。

foreach(集合に含まれる要素の組み合わせ a, b) {
  if(anOperation(a, b) == true) {
    if(anOperation(b, a) == false) {
      print( anOperation で定義された演算は対称律を満たさない )
      return // 判定終了
    }
  }
}
print( anOperation で定義された演算は対称律を満たす )

つまり、対称律を満たすのであれば、anOperation(a, b) が true なら、anOperation(b, a) も必ず true でなければならない。

■推移律
二項演算子が推移律を満たすかどうかは、次のように判定できる。

foreach(集合に含まれる要素の組み合わせ a, b) {
  if(anOperation(a, b) == true && anOperation(b, c) == true) {
    if(anOperation(a, c) == false) {
      print( anOperation で定義された演算は推移律を満たさない )
      return // 判定終了
    }
  }
}
print( anOperation で定義された演算は推移律を満たす )

つまり、推移律を満たすのであれば、anOperation(a, b) と anOperation(b, c) が true であれば、anOperation(a, c)も必ず true でなければならない。

■反対称律
二項演算子が反対称律を満たすかどうかは、次のように判定できる。

foreach(集合に含まれる要素の組み合わせ a, b) {
  if(anOperation(a, b) == true && anOperation(b, a) == true) {
    if(a != b) {
      print( anOperation で定義された演算は反対称律を満たさない )
      return // 判定終了
    }
  }
}
print( anOperation で定義された演算は反対称律を満たす )

つまり反対称律を満たすのであれば、(anOperation(a, b) == true && anOperation(b, a) == true) であるのは a == b のときだけである。

というわけで、anOperation 関数の中身をいろいろな二項演算に置き換えることで、それが反射律・対称律・推移律・反対称律を満たすか判定できる。


参考
関係演算子のいろいろな性質
『離散構造』4 章(関係) の演習問題の解答例


離散数学―コンピュータサイエンスの基礎数学 (マグロウヒル大学演習)

離散数学―コンピュータサイエンスの基礎数学 (マグロウヒル大学演習)

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)