論理マトリックス

論理行列、二値行列、関係行列、ブール行列、または（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の要素数までの範囲をとります。詳細については、添え字付き集合に関する記事を参照してください。

転置​${\displaystyle R^{T}}$論理マトリックスの${\displaystyle R}$二項関係の は、その逆の関係に対応する。^{[ 1 ]}

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

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

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

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

異なる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」を要素ごとに適用することで、ブール代数を形成します。論理行列の補数は、すべてのゼロとイチをそれぞれの反対の要素と入れ替えることで得られます。

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

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

Uのすべての論理行列は、二項関係に対応します。U に対するこれらの列挙された演算と順序付けは、関係の計算に対応し、行列の乗算は関係の合成を表します。^{[ 4 ]}

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

仮定する${\displaystyle (P_{i}),\,i=1,2,\ldots ,m}$そして${\displaystyle (Q_{j}),\,j=1,2,\ldots ,n}$これらは2つの論理ベクトルです。PとQの外積はm × nの長方形関係になります。PとQの外積はm×nの長方形関係になります。

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

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

h をすべて 1 の要素からなるベクトルとする。このとき、v が任意の論理ベクトルであれば、関係R = vh T^はvによって決定される一定の行数を持つ。関係の計算において、このようなRはベクトルと呼ばれる。^{[ 5 ]}具体的な例として、普遍関係がある。${\displaystyle hh^{\operatorname {T} }}$。

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

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

論理行列のすべての 1 を合計するには、行を先に合計するか、列を先に合計するかの 2 つの方法があります。行の合計を加算すると、列の合計を加算した場合と同じになります。インシデンス ジオメトリでは、この行列は、行が「点」に対応し、列が「ブロック」（点で構成される線を一般化したもの）に対応するインシデンス マトリックスとして解釈されます。行の合計は点次数と呼ばれ、列の合計はブロック次数と呼ばれます。点次数の合計はブロック次数の合計に等しくなります。^{[ 6 ]}

この分野における初期の問題は、「与えられた点次数とブロック次数を持つ接続構造の存在に必要な十分条件を見つけること、あるいは行列の言葉で言えば、与えられた行和と列和を持つv  × b型の(0, 1)行列の存在条件を見つけること」であった。^{[ 6 ]}この問題は、ゲイル・ライザーの定理によって解決される。 

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

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