NB - A Library for Storage and Manipulation of Nested Boolean Equations

Abstract:

 

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).

 

 

1.0 Introduction

 

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 [5][7]. 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 [4] or boundary representations [1]. Secondly, the boolean equation can be simplified to some simple normal form [3].

 

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 [6]. 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 [2], 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.

 

 

2.0 Equation Storage

 

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.

 

2.1 The Nested Boolean Form

 

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.

 

Figure 1 - Various Forms for Boolean Equation

 

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.

 

 

2.2 Appended Sets for Engineering Efficiency

 

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,

 

( : plate chasis screw;forward_mount_hole screw;aft_mount_hole )

 

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,

 

( & stock top_face ( + hole chamfer );move_to_middle_of_face )

 

In this case a chamfered hole has been created in some other position, and then relocation.

 

 

2.3 Data Structures For Storage

 

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.

 

Figure 2 - Data Structure for Storing Nested Boolean Equations

 

Figure 3 - Data Structure for Storing Sets of Properties

 

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.

 

3.0 Boolean Algebra

 

The basic axioms of Boolean algebra are given below, and illustrate the rich set of tools available for manipulating equations.

 

Figure 4 - Basic Laws of Boolean Algebra

 

 

3.1 Manipulation Operators

 

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.

 

• Idempotent

• Simplify - A + A = A, A * A = A

• Example equation ( & A B A C A A;e )

• 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.

• Possible results,

( & A B C A A;e )

( & A B A C A;e )

( & B A C A A;e )

• Complicate - A = A + A, A = A * A

• Example equation ( + A B C )

• In this expression there are n=3 possible terms to apply the members to.

• Possible results,

( + A A B C )

( + A B B C )

( + A B C C )

• Associative

• Simplify - A + ( B + C) = A + B + C, A * ( B * C) = A * B * C

• Example equation ( & A B ( + C D ) ( & E;x F );y )

• There are n=4 possible candidates for this operation of which two are bracketed, and one of those two has the same sign. The ‘( & E F )’ term can be ‘popped’ because it has the same operation as the parent term.

• Possible result,

( & A B ( + C D ) E;x;y F;y )

• Complicate - A + B + C = A + ( B + C ), A * B * C = A * ( B * C )

• Example equation ( & A;x B ( ~ C ) )

• For this operation it was chosen to allow each possible commutation (see commutative operator). This gives a total n!(n!) possible permutations that are acceptable for this operation.

• Possible results,

( & ( & A;x B ) ( ~ C ) )

( & ( & B A;x ) ( ~ C ) )

( & ( ~ C ) ( & A;x B ) )

( & ( ~ C ) ( & B A;x ) )

( & ( & A;x ( ~ C ) ) B )

( & ( & ( ~ C ) A;x ) B )

( & B ( & A;x ( ~ C ) ) )

( & B ( & ( ~ C ) A;x ) )

( & ( & B ( ~ C ) ) A;x )

( & ( & ( ~ C ) B ) A;x )

( & A;x ( & B ( ~ C ) ) )

( & A;x ( & ( ~ C ) B ) )

• Commutative

• Does not simplify or complicate - A + B = B + A, A * B = B * A

• Example equation ( + A ( & B C ) D )

• There are n! possible acceptable permutations for this operation. In simple words this operation only shuffles the order of the terms in the equation.

• Possible results,

( + A ( & B C ) D )

( + A D ( & B C ) )

( + D A ( & B C ) )

( + D ( & B C )A )

( + ( & B C ) A D )

( + ( & B C ) D A )

• Distributive

• Simplify - ( & A ( + B C ) ) = ( + ( & A B ) ( & A C ) ),

( + A ( & B C ) ) = ( + ( & A B ) ( + A C ) )

• Example equation ( + A ( + B;e C );f ( + D E ) ( & F G ) )

• There is only one possible permutation with this operation.

• Possible result,

( & ( + A F ( + B;e C );f ( + D E ) ) ( + A G ( + B;e C );f ( + D E )))

• Complicate - ( + ( & A B ) ( & A C ) ) = ( & A ( + B C ) ),

( & ( + A B ) ( + A C ) ) = ( + A ( & B C ) )

• Example equation ( & A B ( + C D ) ( + D E ) ( & F G ) )

• Again, this operation will only have one possible permutation for the purpose of simplicity.

• Possible result,

( & A B ( + D ( & C E ) ) ( & F G ) )

• Complement

• Simplify - ( ~ ( ~ A ) ) = A

• Example equation ( ~ ( ~ ( & A B );x );y ); z

• Again there is only one possible permutation possible here. If a double negative exists, then it is replaced with the doubly negated term

• Possible results,

( & A B );x;y;z

• Complicate - A = ( ~ ( ~ A ) )

• Example equation ( + A B C;x D )

• In this example there are n=4 possible permutations allowable.

• Possible results,

( + ( ~ ( ~ A ) ) B C;x D )

( + A ( ~ ( ~ B ) ) C;x D )

( + A B ( ~ ( ~ C;x ) ) D )

( + A B C;x ( ~ ( ~ D ) ) )

• DeMorgan’s

• Simplify - ( ~ ( & A B ) ) = ( + ( ~ A ) ( ~ B ) ),

( ~ ( + A B ) ) = ( & ( ~ A ) ( ~ B ) )

• Example equation ( + A B ( ~ ( ~ ( & C;x D );y );z ) )

• There are n=3 possible permutations possible, but only one of these three has the double negative required for this operation to be successful.

• Possible result,

( + A B ( & C;x D );y;z )

• Complicate - ( + ( ~ A ) ( ~ B ) ) = ( ~ ( & A B ) ),

( & ( ~ A ) ( ~ B ) ) = ( ~ ( + A B ) )

• Example equation ( + A B ( ~ C ) ( ~ D;x );y )

• There is only one possible permutation.

• Possible result,

( ~ ( & ( ~ A ) ( ~ B ) C D;x;y )

 

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.

 

 

3.2 Addressing Terms in the Equation

 

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.

 

Figure 5 - An Example of Addressing Terms in an Equation

 

 

4.0 Application of the Library

 

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.

 

 

4.1 Subroutines for Storage/Recall of Equations

 

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.

 

be_eqn_list *a;

int A, B, C, D, OP0, OP1, OP2;

 

a = new be_eqn_list; // set up an instance of an equation

A = a->number(“A”); // Define symbols for equation

B = a->number(“B”);

C = a->number(“C”);

D = a->number(“D”);

 

// Define Equation Structure ( : A ( & B C ) )

OP0 = a->find_term(“:”); // Find the pointer to the root of the equation

a->append(OP0, POINT_TO_TERM, a->new_term(ASSEMBLE)); // Add a new term

OP1 = a->find_term(“:0:”);

a->append(OP1, POINT_TO_SYMBOL, A);

a->append(OP1, POINT_TO_TERM, a->new_term(AND));

OP2 = a->find_term(“:0:1:”);

a->append(OP2, POINT_TO_SYMBOL, B);

a->append(OP2, POINT_TO_SYMBOL, C);

 

// show some basic operations

a->print(OP0); // print out ( : A ( & B C ) )

a->insert(OP2, 1, POINT_TO_SYMBOL, D);

a->print(OP0); // prints ( : ( & B D C ) )

a->print(OP2); // prints ( & B D C )

a->remove(OP2, 1);

a->print(OP0); // prints ( : A ( & B C ) )

 

// High level use for equation entry

a->insert_string(OP2, 1, “( : R E;one F ( & S;two;three );four )” );

a->print(OP0); // prints ( : A ( & B ( : R E;one F ( & S;two;three );four ) C ) )

a->print(a->find_term(OP2, 1)); // prints ( : R E;one F ( & S;two;three );four )

a->append(OP1, POINT_TO_TERM, a->copy(OP2)); // here a term is copied

delete a;

 

 

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.

 

 

4.2 Subroutines for Manipulation

 

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.

 

ba_expression *a, *b;

 

// Apply a single Boolean operation to an equation

b = new ba_expression;

b->insert_string(b->find_term(“:”), 0, “( + ( ~ A;one ) ( ~ ( ~ B ) );two );three” );

b->print(b->find_term(“:”));

b->demorgan(b->find_term(“:0:”), MAKE_COMPLEX);

b->print(b->find_term(“:”));

b->demorgan(b->find_term(“:0:”), MAKE_SIMPLE);

b->print(b->find_term(“:”));

delete b;

 

// Find and correct small problems in an equation

a = new ba_expression;

a->insert_string(a->find_term(“:”), 0,

“( + ( + W;zed Y;zed ) ( ~ A B;set );one ( : );something;else B ( & C;x );y )”);

a->print(a->find_term(“:”));

a->rationalize();

a->print(a->find_term(“:”));

delete a;

 

// Simplify an expression

a = new ba_expression;

a->insert_string(a->find_term(“:”), 0, “( & A ( + B;e C );f ( + D E ) ( & F G ) )”);

a->print(a->find_term(“:”));

a->ops_distribute(a->find_term(“:”), MAKE_SIMPLE);

a->print(a->find_term(“:”));

delete a;

 

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.

 

 

4.3 How the Equation Simplifier Works

 

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.

 

 

5.0 Conclusion

 

The paper has described a library of functions for storing and manipulating Boolean algebra equations. Some enhancements to the basic Boolean equations were also described that facilitate design.

 

 

References

 

[1] Hoffman, C. M., Geometric and Solid Modeling, Morgan Kaufmann Publishers Inc., 1989.

[2] Jack, H. A Boolean Algebra Approach to High Level Process Planning, Ph.D. thesis at the University of Western Ontario, 1994.

[3] Kakaza and Okino, 1984 - ******Get from file

[4] Mendelson, E., Shaum’s Outline of Theory and Problems of Boolean Algebra and Switching Circuits, McGraw-Hill Book Company, 1989.

[5] 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.

[6] Tilove, R.B., “A Null-Object Detection Algorithm for Constructive Solid Geometry”, Communications of the ACM, July 1984, Vol. 27, No. 7, pp. 684-694.

[7] Woodwark, J.R., “Some Speculations on Feature Recognition”, Computer-Aided Design, Vol.20, No. 4, may 1988, pp. 189-196.

 

 

Appendix A - Basic List of Function Definitions

 

The following list is a sample of available functions that may be used for low level equation storage, recall, and testing.

 

int operation(int op_pnt) - Returns the type of a defined operation

int operation(int op_pnt, int op_type) - Defines the operation for an existing operation

int find_term(char *addr) - Returns the pointer to an address location

int insert(int, int, int, int) - Inserts a new symbol/term in the equation

int new_term(int op_type) - Create a new term

int remove_term(int addr_pnt, int) - Eliminates an old term

int remove(int addr_pnt, int) - Eliminates part of the equation

int copy(int addr_pnt) - Makes a copy of part of the equation

int append(int addr_pnt, int, int) - Adds a new equation segment to the ends an old list

int print(int addr_pnt) - dumps the specified equation segment to the screen

char *dump_string(int addr_pnt) - Same as print, but to a string instead

int insert_string(int, int, char *) - Inserts a string into the existing equation

int count(int) - Returns a count of terms in the equation

int list_terms(int, int*, int*) - provides a list of all terms in an operation

int get_term_parent(int, int*, int*) - Find the parent of a term

int get_symbol_parent(int, int*, int*) - Find the parent of a symbol

int null_term_detect(int addr_pnt) - Detect when a term is empty

 

The sample list of function below are used for manipulating the Boolean equations using the rules of Boolean algebra.

 

int collect(int addr_pnt, int permute) - Groups a set into a new term

int idempotent(int addr_pnt, int permute, int complicate) - A Boolean operation

int commute(int addr_pnt, int permute, int complicate) - A Boolean operation

int commute(int addr_pnt, int complicate) - A Boolean operation

int distribute(int addr_pnt, intcomplicate) - A Boolean operation

int complement(int addr_pnt, int permute, int complicate) - A Boolean operation

int demorgan(int addr_pnt, int complicate) - A Boolean operation

int ops_distribute(int addr_pnt, int complicate) - Complicate or simplify expressions

int rationalize() - Does a sanity check for the equation

int eqn_empty(int addr_pnt) - Checks to see if part of the equation is empty

 

The next sample list of function calls are used to store, and recall function properties.

 

int load_property_sets(char*) - Loads property sets from a file

int copy_set(char*, char*) - Copies a set by name

int append_set(char*, char*) - Appends a set by name

int add_set(char *) - Adds a new set by name

int add_property(int, char*) - Adds a property to a set

int remove_property(int, char*) - Removes a property from a set

int find_property(int, char*) - Finds a property in a set

int find_set(char *) - Finds a numeric reference to a set

int update_property(int, char*, char*) - Replaces an old property in a set

int print() - Prints all the sets

int save_file(char*, char*, char *, char *) - Saves a set to a file

char* property_value(char*, char*) - Returns the value of a property in a set

 

 

Appendix B - How to Get the NB Library

 

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 ‘hjack@megan.ryerson.ca’.