Write tautology and implication tests in C, without CUDD's comparison functions.
The unique table keeps one node for each function under the current order, and a negation is a complemented pointer to the same node. So two BDDs compute the same function exactly when they are the same pointer, and a question about a function becomes a question about which node it is. Cudd_ReadOne(dd) returns the constant 1, and Cudd_ReadLogicZero(dd) the constant 0.
Cudd_ReadOne(dd)
Cudd_ReadLogicZero(dd)
Build x0 & x1 | x0 & ~x1 with Cudd_bddAnd, Cudd_Not and Cudd_bddOr. Whatever x1 is, it is 1 exactly when x0 is, so it is the function x0.
x0 & x1 | x0 & ~x1
Cudd_bddAnd
Cudd_Not
Cudd_bddOr
x1
x0
Build (x0 | x1) & (x0 | ~x1) the same way. It too is x0.
(x0 | x1) & (x0 | ~x1)
Both results are therefore the pointer that Cudd_bddIthVar(dd, 0) returns: comparing them with == decides that they are equal, without looking at a single assignment.
Cudd_bddIthVar(dd, 0)
==
Comparing pointers settles a question about every assignment at once, because the diagram is canonical.
Write two helpers. int is_tautology(DdManager *dd, DdNode *f) returns 1 when f is 1 on every input, and 0 otherwise. int implies(DdManager *dd, DdNode *f, DdNode *g) returns 1 when every input that makes f 1 also makes g 1, and 0 otherwise.
int is_tautology(DdManager *dd, DdNode *f)
f
int implies(DdManager *dd, DdNode *f, DdNode *g)
g
Both leave every reference count as they found it. Cudd_bddLeq and Cudd_bddLeqUnless, which answer the second question directly, are not allowed.
Cudd_bddLeq
Cudd_bddLeqUnless
A C file that includes cudd.h and defines both functions with these names and parameters. The check compiles your file with a hidden test program against CUDD 3.0.0, runs it with AddressSanitizer and UndefinedBehaviorSanitizer, and says which test failed.
cudd.h
is_tautology and implies return 1 or 0 as stated.
No reference leaked: Cudd_CheckZeroRef reports 0.
Without Cudd_bddLeq or Cudd_bddLeqUnless.
Watch the conditions: they show whether the file defines both functions and names neither forbidden one; the results are decided when you press Check answer.
Try each function by hand on small cases: x | ~x and x for is_tautology, and x & y with x, then x with x & y, for implies.
x | ~x
x
is_tautology
x & y
implies
If your code builds a new BDD, reference it and release it before you return, so the counts end as they began.
Kata 5.2 of Binary Decision Diagrams with CUDD on formal.org. The site checks the answer when you press Check answer; sign in to keep your progress.