Jack, H., "A Library for Storage and Manipulation of Nested Boolean Equations", University of Western Ontario, 1993.
Subroutines for storing and manipulating Boolean equations were developed as part of a system for reasoning on a Boolean algebra representation of a design. The routines were used to store, rearrange, and simplify the expressions. As a result a complete data structure was developed for storing the equations. Most of the axioms of Boolean algebra were also encoded to allow manipulation of the equation. One particular application of these manipulations is to simplify the equation to a conjunctive/disjunctive normal form.
The paper describes the basic data structure, as well as some enhancements for design purposes. In addition, the operators for the Boolean manipulations are presented. Finally, the algorithm for simplifying the Boolean equations is described. The routines have been written in C++, and the author intends to make these commonly available in a library called NB (Nested Boolean).
Boolean logic has many applications, from switching circuit design, to modeling commercial products. In all of these cases the non-uniqueness of the representation is widely recognized . There are two forms of uniqueness, first the form of the equation may vary (equation non-uniqueness), and second the primitives themselves may be different (primitive non-uniqueness).
To overcome the equation non-uniqueness there are two popular approaches that come to mind. First, exhaustively enumerating the equation to derive an unambiguous form, such as truth tables  or boundary representations . Secondly, the boolean equation can be simplified to some simple normal form .
Primitive non-uniqueness is by far a much harder problem. In the simplest case the boolean equation is identical, but primitives can be redundant or unused . Slightly more complicated is the problem of primitives that are oversized. A simple example is a CSG hole that is to cut through a surface, it may be the minimum thickness of the intersecting volume, or it may be made larger for convenience of the designer. The more complicated problems are the result of the selection of different primitives. Two well known approaches are additive, and subtractive construction. In the additive case, primitive shapes are joined to form new parts, in the subtractive case primitive shapes are hewn from a base piece, much as a sculptor would work. Most designers use a combination of both these approaches.
The library presented here was developed to overcome the equation non-uniqueness problem , and it is hoped that in the future the library will be joined with a solid modeler to overcome the primitive non-uniqueness problem.
The major components of this paper focus on describing the Boolean algebra equations, along with some additions provided to allow reuse of modular design segments, as well as simple additions of attributes to the solids. The laws of Boolean algebra are presented, and a structure to allow their application to the data structures. An illustrative application of the functions is given to show how the routines are used, and finally conclusions discuss outstanding problems, and future directions. Two appendices are given to list function names and arguments, and to give instructions for obtaining the source code.
Equations may be stored in a tree form with operators being the nodes, and the leaves being the operands. The depth in the tree determines the scope of the operator. This basic concept has been used here, but in addition brackets have been used whenever possible to clarify operator scope and precedence. This eliminates the need to depend upon convention.
Given a basic Boolean equation ‘A + B & C’ we know that the AND ‘&’ operator takes precedence by convention, but this can be clarified with brackets. If the equation were written ‘( A + ( B & C ) )’, it would be equivalent in meaning. The nested boolean form uses brackets to define the scope of every operator. And, since the operators are individually bracketed, they may be collected as well. This is possible because of the commutativity of the Boolean operators. For example ‘( A + B + C + ( D & E & ( F + G + H ) ) )’ can be rewritten as ‘( + A B ( & D E ( + F G H ) ) )’. This form can be seen to directly correspond to a tree structure in figure 1, whereas the other forms would required at least some interpretation.
The operators that are used in these equations are the basic AND, OR, NOT, and ASSEMBLE, using the symbols ‘&, +, ~, :’ respectively. The ASSEMBLE operator is the only one not considered a common Boolean operator. It is used when parts should coexist separately in a design. A good example of such a condition that requires this is a press fit between two parts. The two parts would overlap if the designs were interpreted by the solid modeler, which is not the actual case in assembly. The two parts would touch along a non-manifold surface that is deformed from the pre-assembly positions and is not easy to determine.
Each of the primitive sets is stored as a list of attributes. These are basically uninterpreted strings that can be whatever form is suitable for the application. In previous work this included statements such as, ‘x_tolerance = 0.5’. Any application that uses these routines is required to interpret the contents. In the case of a solid modeler, some basic primitives, and operations would be required.
The only set member that has been specified is an equation definition. For example, a set called ‘nut’, might contain ‘EQUATION: ( & hex_body threaded_hole )’. The equation contains another set called ‘hex_body’ that in turn will refer to another set. In that set there will be an equation that describes the construction of the 6 sided base. Keeping the equations in this form allows individual sections to be developed and put together after the design process is complete, as is done by human designers.
While a single Boolean equation can represent a full range of products, it is inefficient for a human to cast the equations in this form. A few techniques were developed that enhance design efficiency. Reuse of components is important, for example a typical automobile may contain 100 similar screws. If each of these were to be modeled separately, or copied, the inefficiency would become overwhelming. The better solution is to develop one instance and reuse it in the design. Instances can be created in this method by reusing their set names. But if the set names are used directly, the screw instances would all reappear in the same location. To add properties to existing sets, or equation terms, an append operator has been developed. For example, if a screw were to have two instances, at different positions, it may have an equation such as,
The ‘plate’ and ‘chasis’ would be the two parts to be joined by the screws. The two screws are shown, and would refer to the same item, but the appended sets ‘forward_mount_hole’, and ‘aft_mount_hole’ would contain the respective positions of the holes, and possibly special assembly information. This technique is not limited to use on symbols, it may also be used on terms as well,
The data structures have been set up using linked lists. This allows data structures that will grow dynamically while efficiently using memory space. The basic structures are shown below in Figures 2 and 3. Examples are provided to illustrate their use.
There are other components of the data structures that are not shown, these are used for forward/backwards linking of lists and tracking of unused locations. They would normally be used with this type of data structure, and are therefore omitted for clarity.
When the Boolean operators described in the last section are applied to the nested Boolean form, with appended sets, some additional considerations are required. The following descriptions illustrate how the operators are implemented. The operators described have been divided into complicate/simplify. In general a simplified expression is intended to lead to a disjunctive/conjunctive normal form. In some cases this classification is arbitrary. Please note that the distribution/collection of appended sets has not been fully explored, but rational (and correct) approaches are suggested here.
In this expression there are n=6 terms, and therefore there are (n-1)(n-2)...(1) possible combinations for application. Of this there are only 3 that can be successfully performed in the example equation. This is between the first three ‘A’s. The last ‘A’ is considered different because it has ‘;e’ appended.
The appended sets may create problems during manipulation of the equation. In this work they have been well explored for simplification examples, and are implemented as such. In future work a full set of tools will be developed for dealing with all possible cases.
The user must be able to specify locations in the equation. This is greatly simplified by the nested Boolean form. The basic system is an indexed position. For example, given the equation below, the addresses specify the shown terms.
Use of the NB (Nested Boolean) library has been developed to be modular. The equations can be easily imported and exported in string form. While the equation is stored in the library, it can be manipulated by the Boolean algebra routines, examined by the calling program, or changed by the calling program. The following sections give an example of use for the low level Boolean equation storage, and high level manipulation.
A selected list of many useful function calls are available in the appendix. These will allow the user to work at two different levels. At a low level, the user is responsible for keeping handles and other details. At the higher level the equation can be automatically loaded from a string.
The given program that illustrates the use of the equation manipulation subroutines. An equation was created, a few terms were added and removed, and the equation was printed many times for illustration purposes.
The actual subroutines for manipulation have been implemented based on the previous discussion. The function names used to access these functions are described in the appendix. An example program is given that shows how to manipulate an equation. The equation is loaded, and then the manipulation routines alter its form, and then finally dump it to a string.
The examples show the manipulation of an equation with a simple operator. An example is also given for rationalizing incorrect examples. Finally, an equation is simplified. This program is part of a larger program for testing the software routines.
The NB library was originally developed to support a Computer Aided Process Planning system that reasoned on Boolean algebra. One of the tactics the system would use is equation simplification. The basic mechanism is to start at the equation terms that are the deepest (i.e., most nested). The simplification form of the operators that were described in a previous section are then applied exhaustively. These will lead to small simplifications, until no other simplification is possible. At this point the term is now simplified, and another term at the same depth, or higher up is selected for simplification. This continues up to the root node of the equation. This method is undoubtedly brute force, but it can simplify an equation with 20 terms in less than one second, making it efficient enough for most purposes.
 Requicha, A.A.G., and Vandenbrande, J., “Automated Systems for Process Planning and Part Programming”, Artificial Intelligence: implications for computer integrated manufacturing, IFS Publications Ltd., 1988, pp. 301-326.
An ftp site is being set up, and should be available by early 1995. The basic procedure is to ftp to cobra.megan.ryerson.ca, and look in the directory ‘/pub/software/tools/boolean’. The contents will be a copy of this paper, as well as more complete function descriptions, examples, and the source code. If the software is desired before this time please send email to ‘firstname.lastname@example.org’.