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.
Finding a graph-theoretic representation of expressions in Boole's algebra
graph theory;logic;boolean algebra
A bit of shameless self-promotion, but you might find http://www.sciencedirect.com/science/article/pii/0895717794001669 relevant, as well as the earlier paper I cite there by Frank Harary. 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.