BoolStuff

http://sarrazip.com/dev/boolstuff.html

By Pierre Sarrazin*

BoolStuff is a C++ library that supports a few operations on boolean expression binary trees. The main features are:

A command named booldnf that calls this library to convert an expression to the DNF is also provided.

The current version is 0.1.15 (2014-03-01). This version fixes a bug with some expressions whose raw DNF can contain terms of the form a&a. Fixed a bug with the negation of a DNF composed only of useless terms, like (a&!a|a&!a). Version 0.1.14 fixed a bug where some expressions containing large negations would fail an assert statement instead of returning the expected null expression. It alse fixed a bug where some duplicate terms would not be detected because their factors needed to be sorted and simplified themselves to allow that detection. In addition, g++ 4.7.2 compilation errors were fixed (re: swap() function).

BoolStuff is free software distributed under the GNU General Public License. Please note that this means proprietary software linked with this library cannot be distributed legally.

I can be contacted (in French or English) at sarrazip at sarrazip dot com.

Documentation

Screen shot

[boolstuff screen shot - PNG 16k]

Manual pages

There are manual pages for the boolstuff(3) library and for the booldnf(1) command.

Disjunctive Normal Form

The definition of the DNF seems to vary. Dr. Math says that the DNF requires every variable or its complement [to be] represented in every term. However, MathWorld does not obey this requirement, judging from the examples given. My library does not obey it either.

For example, the expression a&(b|c) will be converted to a&b|a&c. There is no c in the first term and no b in the second one.

Examples

The source archive contains a short example and two test programs. They can be studied to learn how to use the library.

Program(s) using BoolStuff

Halevt (HAL events manager) is a "daemon that executes arbitrary commands when a device with certain properties is added to the system and when device properties change." This program is distributed under the GNU GPL.

C API

The library also comes with a C application programming interface. However, it still requires the program to link with libstdc++, the GNU Standard C++ library.

gcc must be used to compile the C source files, but g++ must be used to link the application. One hack to force Automake to do this is something like the following:

myapp_SOURCES = foo.c bar.c baz.c
nodist_myapp_SOURCES = dummy.cpp
# This forces Automake to use g++ to link the application.
# nodist means that Automake must not include this file
# in the distributed source tarball.

dummy.cpp:
        echo 'static void dummy();' > $@
# We generate the dummy C++ source file so we don't have
# to think about it.

CLEANFILES = dummy.cpp
# This tells the 'clean' target to erase the generated file.

Of course, the _CFLAGS and _LDADD variables must also be set to refer to BoolStuff.

Download

Source archive: boolstuff-0.1.15.tar.gz (375 KB)

(See MD5 and SHA1 for this and other files.)

The source archive contains an RPM .spec file, which allows you to build your own RPM by giving the following command:

rpmbuild -ta boolstuff-0.1.15.tar.gz

I wrote a small RPM Building Crash Course (also available in French).

Plugs


* The image is not of me, but of George Boole (1815-1864), 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. The image is taken from Wikipedia and is in the public domain according to that site.

Valid HTML 4.01!

Last update to this page: 2014-03-01 12:58:40 EST5EDT