計算機科学のブログ

関係 関係の表し方 関係のグラフ 逆関係、倍数と約数、逆関係と等しい場合

情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第5章(関係)、5.2(関係の表し方)、5.2.1(関係のグラフ)の問5.3、4の解答を求めてみる。

問5.3

{ ( 1 , 1 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 3 , 1 ) , ( 3 , 3 ) , ( 4 , 1 ) , ( 4 , 2 ) , ( 4 , 4 ) }

逆関係。

{ ( 1 , 1 ) , ( 1 , 2 ) , ( 2 , 2 ) ( 1 , 3 ) , ( 3 , 3 ) ( 1 , 4 ) , ( 2 , 4 ) , ( 4 , 4 ) }

問 5.4

Q - 1 = { ( x , 1 ) , ( y , 2 ) , ( z , 3 ) }
( x , y , z ) = ( 1 , 2 , 3 ) Q = Q - 1 = { ( 1 , 1 ) , ( 2 , 2 ) , ( 3 , 3 ) }
( 1 , x ) = ( x , 1 ) ( 2 , y ) = ( z , 3 ) ( 3 , z ) = ( y , 2 ) x = 1 , y = 3 , z = 2
( 1 , x ) = ( y , 2 ) ( 2 , y ) = ( x , 1 ) ( 3 , z ) = ( z , 3 ) x = 2 , y = 1 , z = 3
( 1 , x ) = ( y , 2 ) ( 2 , y ) = ( z , 3 ) ( 3 , z ) = ( x , 1 )

なし。

( 1 , x ) = ( z , 3 ) ( 2 , y ) = ( x , 1 ) ( 3 , z ) = ( y , 2 )

なし。

( 1 , x ) = ( z , 3 ) ( 2 , y ) = ( y , 2 ) ( 3 , z ) = ( x , 1 ) x = 3 , y = 2 , z = 1

よって、求めるすべての

( x , y , z )

の組は、

( 1 , 2 , 3 ) ( 1 , 3 , 2 ) ( 2 , 1 , 3 ) ( 3 , 2 , 1 )