# Finding a graph-theoretic representation of expressions in Boole's algebra

I just read "Boole's Algebra Isn't Boolean Algebra" by Theodore Halperin (behind a paywall here). I don't have a strong background in abstract algebra, so, frankly, the paper is a bit over my head but the gist of it is as follows: the algebra developed by Boole in the 19th century has some strange properties. Boole interprets every term in an expression as representing a set and restricts the domain of valid expressions on the basis of relationships between the underlying sets. In particular, he asserts that the expression $x + y$ is valid iff $x$ and $y$ represent disjoint sets, and $x - y$ is valid iff the intersection of $x$ and $y$ is nonempty. He also defines an operation $w = \frac x y$ such that $w$ has many solutions. Halperin goes to great lengths to construct a commutative ring that satisfies Boole's constraints.

I think that there might be a nice, intuitive, graph-theoretic interpretation of Boole's algebra where we can say something like "Given a complex expression in Boole's algebra, $\Phi = \{\phi_1, \phi_2\, \dots, \phi_n\}$, we can construct a (di)graph $G$ such that $\Phi$ is valid if and only if $G$ has some property $P$."

For example, to test if $X + Y$ is valid, we could do something like the following:

Let $G$ be a graph. Let $V(G) = X \cup Y \cup \{v_X, v_Y\}$, i.e. make a vertex for every element of the underlying set, plus a vertex for each term in the expression. Then define

$$E(G) = \{uv_X \mid u \in X \} \cup \{uv_Y \mid u \in Y \}$$

and let $\partial(G)$ be the set of all valid bonds formed by subsets of $V(G)$. It follows that $X + Y$ is valid if and only if $|\partial(G)| = 2$.

From there, I'm not sure how to go about forming graphs for complex expressions like $\frac {y(x + z)} {z^2 + 1}$ by composing simpler graphs. I imagine that there is literature about representing Boolean algebra on graphs, but I haven't been able to find it.

Does anyone have an elegant interpretation? Or a pointer to relevant literature that might get me started?

EDIT: I can't find the article for free anywhere, but wikipedia touches on the issues:

In places, Boole talks of terms being interpreted by sets, but he also recognises terms that cannot always be so interpreted, such as the term 2AB...Such terms he classes uninterpretable terms...uninterpretable terms cannot be the ultimate result of equational manipulations from meaningful starting formulae.

Halperin's paper shows that his algebra is isomorphic to "a commutative ring with unit having no additive or multiplicative nilpotents." I think, for that reason, that it will require heavier machinery to represent than normal Boolean logic operations.

• You may want to check reductions from SAT to graph problems; they routinely use gadgets that encode satisfiability into graphs. – Raphael Apr 24 '14 at 20:43
• havent read article & it would be nice if the info were somewhere open. however, sketch of answer: presumably everything boole talked about is convertible to the standard basis of AND,OR,NOT functionally complete circuits. – vzn Apr 25 '14 at 14:59
• Boole's algebra doesn't obey "1 + 1 = 1", he says that 1 + 1 is undefined. I can't think of how I would encode a test for whether or not x and y are disjoint in a circuit. – Patrick Collins Apr 25 '14 at 19:01
• @vzn I edited with some more info to make the issues clearer. Circuits might work but it's definitely not trivial. – Patrick Collins Apr 25 '14 at 19:15
• ok not totally sure this is answerable (interpretable terms seems a crux: is question somehow asking to interpret uninterpretable terms? also where do they come from? etc) but sounds more like a tcs.se question, try flagging for mod attn after a wk or so of no answer – vzn Apr 25 '14 at 20:23

Those papers present the idea that a boolean function can be represented as a hypercube in which the vertices represent combinations of truth values. That is, rather than construct a graph with a vertex for each boolean variable X, Y etc, construct a graph where one vertex represents the tuple <X=0,Y=0>, one represents <X=0,Y=1> etc.