graphand

Graphand is a graph-based representation of boolean expressions designed to capture shared subexpressions within a single compact DAG. It is used in theoretical and practical contexts where evaluating or storing large logical formulas benefits from subexpression sharing, such as circuit design, knowledge representation, and query optimization in graph-processing systems.

Formally, a graphand is a directed acyclic graph G = (V, E) whose nodes V are labeled with one of the symbols AND, OR, NOT, or VAR, where VAR nodes carry propositional symbols. Each internal node combines its child subgraphs according to its label: AND and OR take two or more operands, NOT takes a single operand. Leaves are VAR nodes representing atomic propositions. Because the graph is acyclic and shares identical subgraphs, the same subformula can have multiple parents without duplication of effort.

Semantics of a graphand align with standard boolean logic. Evaluation proceeds in topological order, computing the truth values of internal nodes from their children for a given variable assignment. The DAG structure enables sharing of equivalent subexpressions, reducing memory usage and potentially speeding up repeated evaluations.

Relation to other formalisms: graphand is closely related to expression DAGs and to reduced ordered binary decision diagrams (BDDs) but is not by itself a canonical form. Its efficiency depends on effective subgraph hashing and the degree of sharing.

Applications include logic synthesis, symbolic computation, query optimization, and compact representation of complex boolean conditions in graph databases or knowledge bases.