boolstuff - Disjunctive Normal Form boolean expression C++ library
g++ prog.cpp -lboolstuff
boolstuff is a C++ library that contains an algorithm to convert a
boolean expression binary tree into the Disjunctive Normal Form. The NOT
operator is supported. A C API covers most of the library's functionality.
The Disjunctive Normal Form is an ORing of ANDed terms. In other words, if the
OR is considered an additive operation and the AND a multiplicative operation,
then the DNF is a sum of products.
For example, the DNF of the expression
a&(b|c) is
a&b|a&c
The DNF eliminates parentheses and provides a normalized form of the original
expression. This normalized form is easier to execute.
The DNF produced by BoolStuff is devoid of any "useless" terms, which
are always false (e.g.,
x&y&!x), but the terms that form the
DNF are not necessarily simplified (e.g.,
x&y&x). When
executing an expression in DNF, it is recommended to obtain the list of terms
and then to obtain the set of variables used in each term. In the case of the
term
x&y&x, the set will only contain
x once.
The library's source archive comes with an example program (in the 'examples'
subdirectory) and with two testing programs (in the src/boolstuff
subdirectory).
This program is free software; you may redistribute it under the terms of the
GNU General Public License. This program has absolutely no warranty.
Pierre Sarrazin
See the BoolStuff Home Page:
http://sarrazip.com/dev/boolstuff.html
Comments are welcome.
Version 0.1.x is an unstable development version. The programming interface of
the library and the command-line options of the accompanying commands are not
necessarily fixed. The documentation has not been reviewed for completeness.
George Boole (1815-1864) is an English mathematician who helped establish modern
symbolic logic and whose algebra of logic, now called Boolean algebra, is
basic to the design of digital computer circuits.