Matrix (Logik)

In der Prädikatenlogik ist die Matrix einer Formel $F$ diejenige Formel, die man durch Streichen sämtlicher Quantoren aus $F$ erhält. Der Begriff wird vor allem im Zusammenhang mit der Pränexform verwendet, bei der sämtliche Quantoren am Anfang der Formel stehen.

Beispiel

Die Matrix der Formel

$\mathrm{\exists }n\mathrm{\forall }a(a+n=a\wedge \mathrm{\exists }b.a+b=n)$

(Existenz eines neutralen Elements der Addition) ist

$(a+n=a)\wedge (a+b=n)$.

---

A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1)-matrix is a matrix with entries from the Boolean domain B = {0, 1}. Such a matrix can be used to represent a binary relation between a pair of finite sets. It is an important tool in combinatorial mathematics and theoretical computer science.

Matrix representation of a relation

If R is a binary relation between the finite indexed sets X and Y (so ''R'' ⊆ ''X'' ×''Y''), then R can be represented by the logical matrix M whose row and column indices index the elements of X and Y, respectively, such that the entries of M are defined by

$m_{i,j}=\{\begin{array}{cc}1& (x_i,y_j)\in R,\\ 0& (x_i,y_j)\in ̸R.\end{array}$

In order to designate the row and column numbers of the matrix, the sets X and Y are indexed with positive integers: i ranges from 1 to the cardinality (size) of X, and j ranges from 1 to the cardinality of Y. See the article on indexed sets for more detail.

The transpose $R^T$ of the logical matrix $R$ of a binary relation corresponds to the converse relation.

Example

The binary relation R on the set {1, 2, 3, 4}\{\{null}} is defined so that aRb holds if and only if a divides b evenly, with no remainder. For example, 2R4 holds because 2 divides 4 without leaving a remainder, but 3R4 does not hold because when 3 divides 4, there is a remainder of 1. The following set is the set of pairs for which the relation R holds.

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

The corresponding representation as a logical matrix is

$\left(\begin{array}{cccc}1& 1& 1& 1\\ 0& 1& 0& 1\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right),$

which includes a diagonal of ones, since each number divides itself.

See also

• List of matrices
• Binatorix (a binary De Bruijn torus)
• Bit array
• Disjunct matrix
• Redheffer matrix
• Truth table
• Three-valued logic