# Systems of equations in Boolean Algebra

I have to study systems of equations in a Boolean algebra, the matrix is $m\times n$ with $m\neq n$. The Boolean algebra is actually the simplest one, it contains only $0$ and $1$, let us denote it by $\mathbb{B}$. What I need to know is a necessary and sufficient condition for an application from $\mathbb{B}^n$ to $\mathbb{B}^m$ to be one-to-one. I read in the paper "Linear Boolean Equations and Generalized Minterms" by S. Rudeanu (Discrete Math 43 (1983) 241-248) that Löwenheim proved some theorems in a paper written in 1919. Hence my question :

Is there any more recent reference about this subject (systems of equations in Boolean algebra) ? And where can I find a proof of Löwenheim's theorem (that could help to understand) ?

All references I can found in some papers I can find (with difficulty) on the Web are unavailable online, and unavailable in my library.

EDIT: Here is Löwenheim's theorem I mention above: In a Boolean algebra $(\mathbb{B},\cup,.,',0,1)$ (I guess that $.$ is the intersection and $'$ the negation), to each $(b_1,\dots,b_m)\in \mathbb{B}^m$, we can associate the system of equations $$\bigcup_{j=1}^na_{ij}x_j=b_i \ \ \ (i=1,\dots,m).$$ Löwenheim proved in a 1919 paper that the system is consistent (I guess that that means that there is a solution) for a given $(b_1,\dots,b_m)\in \mathbb{B}^m$ if and only if $$b_i\leq \bigcup_{j=1}^n a_{ij} \prod_{h=1,h\neq i}^m (a'_{hj}\cup b_h)\ \ \ (i=1,\dots,m).$$ I guess that $\leq$ means the inclusion (it is not explained in the paper). In the same paper, the author calls $x+y=xy'\cup x'y$ the ring sum which is "xor".

• I may be mistaken, but why do you insist on calling this a Boolean algebra? Why not to stick to and and xor and just do usual linear algebra over $\Bbb F_2$. – Alex Degtyarev Nov 20 '14 at 9:24
• Probably because I am using the terminology in a wrong way: I don't know almost anything in Boolean algebra. I use "or", union and not "xor", for the addition. For me $1+1=1$, and not $0$. – Philippe Gaucher Nov 20 '14 at 9:46
• That's exactly my question: on the one hand, all Boolean operations can be interpreted in terms of "and" and "xor"; on the other hand, the latter are merely the operations in the field $\Bbb F_2$, hence, one can apply college linear algebra to your problem. Then, if absolutely necessary, the obvious answer (the matrix has appropriate rank, or nullity is zero, or, in the square case, $\det\ne0$, etc.) can be translated back to "and" and "or". – Alex Degtyarev Nov 20 '14 at 10:16
• Accidentally, I think your $x+y=xy'\cup x'y$ is "xor" (symmetric difference) for sets. But for just $0$, $1$ it's much simpler, as you can easily see from the truth tables. Anyway, this is just a suggestion, to use the kettle principle. – Alex Degtyarev Nov 20 '14 at 10:21
• It is not a numerical system of equations (I cannot take a computer and ask it to solve it), but I understand what you mean. A round trip between the 2-element Boolean algebra and $\mathbb{F}_2$ could help. Anyway, any reference about the subject is welcome. – Philippe Gaucher Nov 20 '14 at 10:22

Let $A$ be an $m\times n$ Boolean matrix. Then the mapping $v\mapsto Av$ is 1:1 iff $n\leq m$ and some subset of $n$ rows of gives a permutation matrix.

The reason is duality of modules over the Boolean semiring shows that $A$ is 1:1 iff the transpose is onto. Since the standard basis vectors of a free $\mathbb B$-module are join irreducible a Boolean matrix gives an onto map iff each standard basis vector appears as a column.

Added per request for more detail.

A $\mathbb B$-module is the same thing as a join-semilattice $M$. The dual $M^*$ is the set of all join-semilattice homomorphisms $M\to \mathbb B$ with pointwise join. If $M$ is finite, then the dual consists of the mappings $f_m$ with $m\in M$ where $f_m(x)=0$ if $x\leq m$ and $1$ else. Indeed, choose $m$ to be the join of all elements mapping to $0$.

It follows if $N$ is a submodule of $M$ then the restriction $M^*\to N^*$ is surjective. Also the canonical map to the double dual is an ISO for $M$ finite. It now follows a map of finite $\mathbb B$-modules is injective iff the dual map is surjective. For a matrix map the dual is the transpose.

If we view $\mathbb B^n$ as a join semilattice, the basis consists of atoms. It follows a matrix transformation is onto iff each basis vector appears in some column. Dualizing gives the result.

• Could you expand the proof please and/or give some references about e.g. duality of modules over Boolean semiring ? A basic course for a beginner I mean. – Philippe Gaucher Nov 20 '14 at 15:38
• Some of this is discussed in Chapter 9 of my book with John Rhodes, The q-theory of finite semigroups. Either the result you want or its dual might even be there or in my paper with Izhakian and Rhodes on representations of monoids over semirings. I don't have references in front of me. I can try to write something more when I have a better computer than a smartphone – Benjamin Steinberg Nov 20 '14 at 17:45