Binär matris

En binär matris, eller en noll-ett matris, är en matris vars element bara består av 1:or eller 0:or.

Boolska operatorer

De boolska operatorerna ∧ (och) och ∨ (eller) definieras för vanliga boolska variabler b₁ och b₂ genom:

b₁ ∧ b₂ är 1 om både b₁ = 1 och b₂ = 1, annars 0.
b₁ ∨ b₂ är 1 om minst en av b₁ och b₂ är 1, annars 0.

Definition av Boolska operatorer för matriser. Låt $A=[a_{ij}]$ och $B=[b_{ij}]$ vara binära matriser med lika antal rader och kolonner. Då definieras A ∨ B och A ∧ B som $A\lor B=[a_{ij}\lor b_{ij}]$ resp $A\land B=[a_{ij}\land b_{ij}].$

Exempel

Vi har två 1-0 matriser A och B.

A={\begin{bmatrix}1&0&1\\0&1&0\end{bmatrix}}\ \ B={\begin{bmatrix}0&1&0\\1&1&0\end{bmatrix}}

Om vi väljer att förena A och B (A ∨ B)

A\lor B={\begin{bmatrix}1\lor 0&0\lor 1&1\lor 0\\0\lor 1&1\lor 1&0\lor 0\end{bmatrix}}={\begin{bmatrix}1&1&1\\1&1&0\end{bmatrix}}

Om vi väljer att A och B ska mötas (A ∧ B)

A\land B={\begin{bmatrix}1\land 0&0\land 1&1\land 0\\0\land 1&1\land 1&0\land 0\end{bmatrix}}={\begin{bmatrix}0&0&0\\0&1&0\end{bmatrix}}

Boolska produkten

Låt nu A vara en m×k 0-1 matris och b en k×n 0-1 matris. Då definieras den boolska produkten av A och B betecknad A ⊙ B som m×n-matrisen C med $C_{ij}=(a_{i1}\land b_{1j})\lor (a_{i2}\land b_{2j})\lor \dots \lor (a_{ik}\land b_{kj})$