論理マトリックス

論理行列、二項行列、関係行列、ブール行列、または(0, 1) 行列は、ブール領域B = {0, 1}からのエントリを持つ行列です。このような行列は、一対の有限集合間の二項関係を表すために使用できます。これは、組合せ数学および理論計算機科学における重要なツールです。

R が有限のインデックス付き集合XとYの間の二項関係である場合（つまりR ⊆ X × Y）、R は論理行列Mで表すことができ、その行と列のインデックスはそれぞれXとYの要素をインデックスし、 Mのエントリは次のように定義されます。

${\displaystyle m_{i,j}={\begin{cases}1&(x_{i},y_{j})\in R,\\0&(x_{i},y_{j})\not \in R.\end{cases}}}$

行列の行番号と列番号を指定するために、セットXとY は正の整数でインデックス付けされます。i の範囲は 1 からXの基数(サイズ)までで、j の範囲は 1 からYの基数までです。詳細については、 インデックス付きセットに関する記事を参照してください。

集合{1, 2, 3, 4}上の2 項関係R は、 a がb を余りなく割り切る場合にのみaRb が成立するように定義されます。たとえば、 2 は 4 を余りなく割り切るため 2 R 4 が成立しますが、3 は 4 を 3 で割り切ると 1 の余りがあるため 3 R 4 は成立しません。次の集合は、関係Rが成立するペアの集合です。

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

対応する論理行列表現は

${\displaystyle {\begin{pmatrix}1&1&1&1\\0&1&0&1\\0&0&1&0\\0&0&0&1\end{pmatrix}},}$

各数はそれ自体を割り切るので、対角線上には 1 が含まれます。

• 順列行列は(0, 1) 行列であり、そのすべての列と行にはそれぞれ 1 つの非ゼロ要素が含まれます。
  • コスタス配列は、順列行列の特殊なケースです。
• 組合せ論と有限幾何学における接続行列には、幾何学の点 (または頂点) と線、ブロック設計のブロック、またはグラフのエッジ間の接続を示すものがあります。
• 分散分析における計画行列は、行の合計が一定である (0, 1) 行列です。
• 論理行列はグラフ理論における隣接行列を表すことができます。非対称行列は有向グラフに対応し、対称行列は通常のグラフに対応し、対角線上の 1 は対応する頂点のループに対応します。
• 単純な無向二部グラフの隣接行列は(0, 1) 行列であり、任意の (0, 1) 行列はこのようにして生じます。
• m 個の平方でないn滑らかな数のリストの素因数は、m × π( n ) (0, 1) 行列として記述できます。ここで、π は素数カウント関数であり、j番目の素数がi番目の数を割り切る場合のみ、a _ijは 1 になります。この表現は、二次ふるい因数分解アルゴリズムで役立ちます。
• 2 色のみのピクセルを含むビットマップ イメージは、ゼロが 1 つの色のピクセルを表し、1 が他の色のピクセルを表す (0, 1) 行列として表すことができます。
• バイナリマトリックスは囲碁のゲームルールを確認するために使用することができます。^[1]
• 2x2 論理マトリックスによって変換された 2 ビットの4値ロジックは、遷移システムを形成します。
• 再帰プロットとその変種は、位相空間内でどの点のペアが特定の近傍しきい値よりも近いかを示す行列です。

有限集合上の等式関係の行列表現は単位行列 I、つまり対角要素がすべて 1 で、その他がすべて 0 である行列です。より一般的には、関係R がI ⊆ R を満たす場合、R は反射関係です。

ブール領域を半環と見なすと、加算は論理和に、乗算は論理積に相当し、 2つの関係の合成の行列表現は、これらの関係の行列表現の行列積に等しくなります。この積は^、期待時間O( n2 )で計算できます。^[2]

多くの場合、2 進行列の演算は、モジュラー演算mod 2で定義されます。つまり、要素はガロア体 の要素として扱われます。これらはさまざまな表現で発生し、より制限された特殊形式がいくつかあります。これらは、たとえばXOR 充足可能性に適用されます。 ${\displaystyle {\mathbf {GF}}(2)=\mathbb {Z} _{2}}$

異なるm行n列のバイナリ行列の数は2 ^mnに等しく、したがって有限です。

nとmが与えられ、Uがすべての論理m × n行列の集合を表すとします。すると、Uは次のように表される 半順序を持ちます。

${\displaystyle \forall A,B\in U,\quad A\leq B\quad {\text{when}}\quad \forall i,j\quad A_{ij}=1\implies B_{ij}=1.}$

実際、U は、2 つの行列間のandおよびor の演算をコンポーネントごとに適用したブール代数を形成します。論理行列の補数は、すべての 0 と 1 をその反対のものと交換することによって得られます。

すべての論理行列A = ( A _ij )には転置行列A ^T = ( A _ji ) があります。Aが、列も行もすべてゼロである論理行列であるとします。この場合、ブール演算を使用した行列積にはm × m単位行列が含まれ、積にはn × n単位行列が含まれます。 ${\displaystyle A^{\operatorname {T} }A}$ ${\displaystyle AA^{\operatorname {T} }}$

数学的構造として、ブール代数U は包含関係によって順序付けられた格子を形成します。さらに、行列の乗算により乗法格子になります。

U内の各論理行列は2項関係に対応する。U に対するこれらの演算と順序付けは関係の計算に対応し、行列の乗算は関係の合成を表す。^[3]

mまたはnが 1 の場合、m × n論理行列 ( m _ij ) は論理ベクトルまたはビット文字列です。m = 1の場合、ベクトルは行ベクトルであり、n = 1 の場合、列ベクトルです。どちらの場合も、1 に等しいインデックスはベクトルの表示から削除されます。

とが2つの論理ベクトルであるとする。PとQの外積はm × nの直交関係となる。${\displaystyle (P_{i}),\,i=1,2,\ldots ,m}$${\displaystyle (Q_{j}),\,j=1,2,\ldots ,n}$

${\displaystyle m_{ij}=P_{i}\land Q_{j}.}$

このような行列の行と列を並べ替えると、すべての1を行列の長方形の部分に組み立てることができます。^[4]

h がすべて 1 のベクトルであるとします。vが任意の論理ベクトルである場合、関係R = vh ^{T は}vによって決定される定数行を持ちます。関係の計算では、このようなR はベクトルと呼ばれます。^[4]特別な例として、普遍的な関係があります。 ${\displaystyle hh^{\operatorname {T}}}$

与えられた関係Rに対して、 Rに含まれる最大の矩形関係はRの概念と呼ばれます。関係は概念に分解し、誘導された概念束に注目することで研究できます。

グループのような構造の表を考えてみましょう。ここで、「不要」は 0 で表され、「必要」は 1 で表され、論理行列を形成します。の要素を計算するには、この行列の行にある論理ベクトルのペアの論理内積を使用する必要があります。 この内積が 0 の場合、行は直交します。 実際、小カテゴリは準グループに直交し、群はマグマに直交します。 その結果、 にはゼロがあり、普遍的な関係にはなりません。 ${\displaystyle R.}$${\displaystyle RR^{\operatorname {T} }}$${\displaystyle RR^{\operatorname {T} }}$

論理行列内のすべての 1 を合計するには、最初に行を合計するか、最初に列を合計するかの 2 つの方法があります。行の合計を加算すると、合計は列の合計を加算したときと同じになります。接続幾何学では、行列は行が「ポイント」に対応し、列が「ブロック」(ポイントで構成される線を一般化したもの) に対応する接続​​行列として解釈されます。行の合計はポイント次数と呼ばれ、列の合計はブロック次数と呼ばれます。ポイント次数の合計はブロック次数の合計に等しくなります。^[5]

この分野における初期の問題は、「与えられた点次数とブロック次数を持つ入射構造が存在するための必要かつ十分な条件を見つけること、または行列言語で言えば、与えられた行と列の合計を持つv  ×  b型の（0、1）行列が存在するための必要かつ十分な条件を見つけること」であった。^{[5]この問題は}、ゲール・ライザー定理によって解決される。

• 行列のリスト
• Binatorix (バイナリ De Bruijn トーラス)
• ビット配列
• 分離行列
• レッドヘッファーマトリックス
• 真理値表
• 3値論理

ウィキメディア・コモンズには、バイナリ行列に関連するメディアがあります。

• 「論理行列」、数学百科事典、EMS Press、2001 [1994]