jbool_expressions is a simple open-source library for creating and manipulating boolean expressions in java.
A basic propositional expression is built out of the types And
, Or
, Not
, Variable
and Literal
. All of these extend the base type Expression. For example,
Expression<String> expr = And.of(
Variable.of("A"),
Variable.of("B"),
Or.of(Variable.of("C"), Not.of(Variable.of("C"))));
System.out.println(expr);
We see the expression is what we expect:
((!C | C) & A & B)
Of course, this expression contains a useless term (either C or (! C) is always true.) We can simplify the expression, and see that the extra term is simplified out:
Expression<String> simplified = RuleSet.simplify(expr);
System.out.println(expr);
outputs:
(A & B)
We can assign a value to one of the variables, and see that the expression is simplified after assigning "A" a value:
Expression<String> halfAssigned = RuleSet.assign(simplified, Collections.singletonMap("A", true));
System.out.println(halfAssigned);
outputs:
B
We can assign the last variable, and see that the expression resolves to a literal "true".
Expression<String> resolved = RuleSet.assign(halfAssigned, Collections.singletonMap("B", true));
System.out.println(resolved);
outputs:
true
All expressions are immutable (we got a new expression back each time we performed an operation), so we can see that the original expression is unmodified:
System.out.println(expr);
outputs:
((!C | C) & A & B)
Alternatively, we could have provided our expression as a String in prefix notation and parsed it. We can verify that this expression is identical to the one we built manually:
Expression<String> parsedExpression = RuleSet.simplify(ExprParser.parse("( ( (! C) | C) & A & B)"));
System.out.println(parsedExpression);
System.out.println(parsedExpression.equals(simplified));
output:
(A & B)
true
We can also convert expressions to sum-of-products form instead of just simplifying them. For example:
Expression<String> nonStandard = ExprParser.parse("((A | B) & (C | D))");
System.out.println(nonStandard);
Expression<String> sopForm = RuleSet.toDNF(nonStandard);
System.out.println(sopForm);
output:
((A | B) & (C | D))
((A & C) | (A & D) | (B & C) | (B & D))
Likewise, we can convert an expression to product-of-sums form. For example:
Expression<String> nonStandard = ExprParser.parse("((A & B) | (C & D))");
System.out.println(nonStandard);
Expression<String> posForm = RuleSet.toCNF(nonStandard);
System.out.println(posForm);
output:
((A & B) | (C & D))
((A | C) & (A | D) & (B | C) & (B | D))
All of these examples can also be found in ExampleRunner
The current simplification rules define fairly simple and fast optimizations, and is defined in RuleSet. I'm happy to add more sophisticated rules (let me know about them via a PR or issue). The current rules include:
Literal removal:
(false & A) => false
(true & A) => A
(false | A) => A
(true | A) => true
Negation simplification:
(!!A ) => A
(A & !A) => false
(A | !A) => true
And / Or de-duplication and flattening:
(A & A & (B & C)) => (A & B & C)
(A | A | (B | C)) => (A | B | C)
Child expression simplification:
(A | B) & (A | B | C) => (A | B)
((A & B) | (A & B & C)) => (A & B)
Additional rules for converting to sum-of-products form:
Propagating &:
( A & ( C | D)) => ((A & C) | (A & D))
De Morgan's law:
(! ( A | B)) => ( (! A) & (! B))
jbool_expressions is available via maven central (check out Maven central for the latest version โ the version below may not be the most recent):
<dependency>
<groupId>com.bpodgursky</groupId>
<artifactId>jbool_expressions</artifactId>
<version>1.23</version>
</dependency>
Snapshot builds of jbool_expressions are also published to sonatype:
<repository>
<id>oss.sonatype.org-snapshot</id>
<url>http://oss.sonatype.org/content/repositories/snapshots</url>
<releases>
<enabled>false</enabled>
</releases>
<snapshots>
<enabled>true</enabled>
</snapshots>
</repository>
<dependency>
<groupId>com.bpodgursky</groupId>
<artifactId>jbool_expressions</artifactId>
<version>1.24-SNAPSHOT</version>
</dependency>
jbool_expressions is built with Maven. To build from source,
> mvn package
generates a snapshot jar target/jbool_expressions-1.0-SNAPSHOT.jar.
To run the test suite locally,
> mvn test
jbool_expressions is very much in-development, and is in no way, shape, or form guaranteed to be stable or bug-free. Bugs, suggestions, or pull requests are all very welcome.
Copyright 2013 Ben Podgursky
Licensed under the Apache License, Version 2.0