Logical matrix

In algebraic logic, a logical matrix is a semantic structure consisting of an algebra \mathbf{A} and a non-empty subset D of its carrier set A, where the elements of D are designated values that represent the acceptable or "true" truth values for formulas in a given logic.^[1] Logical matrices generalize the truth-table semantics of classical propositional logic to arbitrary algebraic structures, enabling the modeling of logical consequence relations in a precise algebraic framework.^[1] A set of formulas \Gamma entails a formula \phi in a logic \mathbf{L} if, for every logical matrix \langle \mathbf{A}, D \rangle that models \mathbf{L}, any valuation sending all elements of \Gamma to designated elements in D also sends \phi to D.^[1] This approach connects syntactic deduction to algebraic properties, such as filters and congruences, and is particularly powerful for protoalgebraic logics where reduced matrices (obtained via the Leibniz operator \mathbf{\Omega}_{\mathbf{A}}(D)) capture the logic's full semantics.^[1] The concept of logical matrices originated with Alfred Tarski in the 1920s, though it built on implicit ideas in Jan Łukasiewicz's work on many-valued logics, and was further formalized by figures like Jerzy Łoś and Roman Suszko in the mid-20th century.^[1] They form the foundation of matrix semantics, which applies to a wide range of non-classical logics, including intuitionistic, modal, and paraconsistent systems, by associating each logic with a class of such matrices that validate its theorems and rules.^[1] In practice, the Lindenbaum matrix—derived from the free algebra of the logic quotiented by its equivalence relation—provides a canonical model, ensuring every propositional logic admits a complete matrix semantics.^[1]

Fundamentals

Definition

A logical matrix is an m \times n matrix A = (a_{ij}) whose entries a_{ij} belong to the two-element Boolean algebra \{0, 1\}, equipped with operations such as meet (\wedge), join (\vee), and complement (\neg). This is a special case of more general matrices over Boolean algebras B, where matrix operations use the algebraic operations of B (such as intersection for meet and union for join) rather than standard arithmetic, distinguishing them from real-valued matrices that rely on addition and multiplication over the reals.^[2] In this structure, $0 acts as the zero element, $1 as the unit, \wedge corresponds to logical AND (intersection), \vee to logical OR (union), and \neg to logical NOT (complement).^[2] This yields a binary or (0,1)-matrix, often termed a logical matrix in contexts involving binary relations.^[2] More generally, matrices over any Boolean algebra B, such as the power set algebra \beta_k of subsets of a k-element set (with \cap as meet, \cup as join, and set complement as negation) or algebras of intervals over the reals ordered by inclusion, can be considered, though the term "logical matrix" is typically reserved for the {0,1} case.^[3] The dimensions m and n typically reflect the sizes of the domain and codomain sets in applications like relation representation.^[2]

Relation Representation

A logical matrix provides a standard way to encode a binary relation R \subseteq X \times Y between finite sets X and Y, where |X| = m and |Y| = n. Assuming fixed enumerations X = \{x_1, \dots, x_m\} and Y = \{y_1, \dots, y_n\}, the corresponding m \times n logical matrix A = [a_{ij}] is defined such that a_{ij} = 1 if (x_i, y_j) \in R and a_{ij} = 0 otherwise.^[4] This construction yields a bijection between the set of all binary relations R \subseteq X \times Y and the set of all m \times n matrices over \{0,1\}, as each possible relation corresponds uniquely to a choice of entries in the matrix based on membership in R.^[5] The original relation can be recovered from the matrix by determining that (x_i, y_j) \in [R](/page/R) if and only if a_{ij} = 1.^[4] When X and Y have different cardinalities, the resulting logical matrices are rectangular (non-square), reflecting the asymmetry in the dimensions of the Cartesian product X \times Y.^[6]

Examples

Basic Example

A fundamental example of a logical matrix is the two-valued matrix for classical propositional logic. The algebra \mathbf{A} is the Boolean algebra with carrier set A = \{0, 1\}, where 0 represents falsehood and 1 truth. The operations are defined as follows: conjunction \land by \min(x, y) or xy, disjunction \lor by \max(x, y) or x + y - xy, and negation \lnot by $1 - x. The set of designated values is D = \{1\}.^[1] In this matrix \langle \mathbf{A}, D \rangle, a formula is valid if every valuation (homomorphism from the formula algebra to \mathbf{A}) maps it to 1 whenever the premises are mapped to 1. This captures the truth-table semantics of classical logic, where tautologies always evaluate to 1. For instance, the formula p \lor \lnot p evaluates to 1 for any assignment to p. To verify, consider the truth table implicit in the operations: for p \land q, the values are 1 only if both are 1, matching classical AND.

Further Examples

For many-valued logics, consider Łukasiewicz's three-valued logic. The carrier set is A = \{0, \frac{1}{2}, 1\}, with conjunction \land defined as \min(x, y), disjunction \lor as \max(x, y), and implication \to as \min(1, 1 - x + y). The designated set can be D = \{1\} (strong) or D = \{\frac{1}{2}, 1\} (weak), depending on the variant. This matrix models intermediate truth values, useful for vague or uncertain statements.^[7] Another example is the matrix for intuitionistic logic, based on a Heyting algebra \mathbf{A} (e.g., the chain A = \{0 < a < 1\} for a simple finite case). Operations include implication defined as the relative pseudocomplement: x \to y = \max\{z \mid x \land z \leq y\}, with D = \{1\}. Unlike classical logic, excluded middle p \lor \lnot p does not always evaluate to 1, reflecting intuitionistic rejection of proof by contradiction without constructive evidence.^[8] These examples demonstrate how logical matrices adapt algebraic structures to define semantics for non-classical logics, with designated values determining validity.

Properties

Core Properties

Logical matrices provide a semantic framework for propositional logics through their algebraic structure and designated values. A key property is the definition of the consequence relation: for a class of matrices \mathcal{M}, a set of formulas \Gamma entails \phi if, in every matrix \langle \mathbf{A}, D \rangle \in \mathcal{M}, every valuation v: \mathrm{Form} \to A such that v(\gamma) \in D for all \gamma \in \Gamma also satisfies v(\phi) \in D. This ensures that the semantics capture the logic's deductive rules in an algebraically precise manner.^[1] Another fundamental property involves reduced matrices, which eliminate redundancies in the carrier set. A matrix \langle \mathbf{A}, D \rangle is reduced if the Leibniz congruence \mathbf{\Omega}_{\mathbf{A}}(D) = \{(a, b) \in A \times A \mid \forall \phi \in \mathrm{Form}, \, \mathbf{A} \models \phi(a) \leftrightarrow \phi(b) \implies a \in D \iff b \in D\} is the equality relation on A. The reduced form is obtained by quotienting \mathbf{A} by this congruence, and for protoalgebraic logics, the reduced matrices fully determine the semantics.^[1] Logical matrices are particularly useful in protoalgebraic logics, where there exists a set of equivalence formulas \Delta(p, q) such that the Leibniz congruence for any filter coincides with the relation defined by \Delta. This property bridges syntax and semantics, allowing the logic to be characterized by algebraic filters and congruences. Filters in the algebra \mathbf{A} are subsets closed under the logic's operations and containing designated values, playing a role analogous to theories in syntactic terms.^[1]

Lattice Structure

In the context of logical matrices, the underlying algebras \mathbf{A} are often lattice-based, such as Boolean algebras for classical logic or Heyting algebras for intuitionistic logic, where the carrier A forms a lattice under meet and join operations. The set of all congruences on \mathbf{A} forms an algebraic lattice, ordered by inclusion, with the trivial congruence as the bottom element and the full relation as the top; joins and meets correspond to the transitive closures and intersections of relations, respectively. This lattice structure facilitates the study of quotient matrices and semantic equivalences.^[1] Additionally, the collection of filters on \mathbf{A} (upward closed subsets compatible with the designated set D) inherits a lattice structure under intersection (meet) and union-generated filters (join), forming a complete lattice that models the theories of the logic. For example, in classical propositional logic, the filters of the Boolean algebra correspond to the prime filters, yielding the Stone representation. This lattice-theoretic perspective underscores the connections between logical matrices and order theory in algebraic semantics.^[1]

Extensions

Logical Vectors

In the context of Boolean-valued logical matrices used for relation representation, a logical vector can be viewed as an n \times 1 or $1 \times n matrix with entries from the Boolean algebra \{[0](/page/0), [1](/page/1)\}. These arise as rows or columns of such matrices, capturing characteristic functions of subsets or preimages/images under relations.^[9] Operations on logical vectors are component-wise Boolean operations: disjunction \vee (OR), conjunction \wedge (AND), and negation \neg. For example, for vectors a = (1, 0, 1) and b = (0, 1, 1), a \vee b = (1, 1, 1). The Boolean inner product \langle a, b \rangle = \bigvee_{i=1}^n (a_i \wedge b_i) indicates if their supports overlap.^[10]

Row and Column Sums

For logical matrices representing binary relations or directed graphs over the Boolean domain, the cardinal row sum s_i = \sum_j a_{ij} gives the out-degree of element i, and the column sum t_j = \sum_i a_{ij} the in-degree.^[11] In the Boolean semiring (addition \vee, multiplication \wedge), the row sum s_i = \bigvee_j a_{ij} is 1 if the row has at least one 1, indicating existence of relations.^[12] For the matrix

A = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \end{pmatrix},

cardinal row sums are 2, 1, 2 and column sums 2, 2, 1; all Boolean sums are 1, as each row and column has at least one 1. This represents a relation where element 1 relates to 1 and 3, 2 to 2, and 3 to 1 and 2.^[11]^[12] In algebraic logic, extensions of logical matrices include reduced forms using the Leibniz operator \mathbf{\Omega}_{\mathbf{A}}(D) for capturing semantics in protoalgebraic logics.^[1]