隐藏：BDD 的操作

Question

我正在使用 CUDD C++ 接口 (https://github.com/ivmai/cudd)，但几乎没有关于此库的信息。我想知道如何根据它的值删除一个变量。

例如，我现在将下一个 table 存储在 bdd:

|-----|-----|-----|
|  x1 |  x2 |  y  |
|-----|-----|-----|
|  0  |  0  |  1  |
|-----|-----|-----|
|  0  |  1  |  1  |
|-----|-----|-----|
|  1  |  0  |  1  |
|-----|-----|-----|
|  1  |  1  |  0  |
|-----|-----|-----|

我想根据 x2 的值将前面的 table 拆分为两个单独的 bdd，然后删除该节点：

如果x2 = 0:

|-----|-----|
|  x1 |  y  |
|-----|-----|
|  0  |  1  |
|-----|-----|
|  1  |  1  |
|-----|-----|

如果x2 = 1:

|-----|-----|
|  x1 |  y  |
|-----|-----|
|  0  |  1  |
|-----|-----|
|  1  |  0  |
|-----|-----|

可能吗？

Answer 1

之所以几乎没有关于 CUDD 库的 C++ 接口的文档，是因为它只是 C 函数的包装器，对此有很多文档。

C++ 包装器主要用于摆脱使用 C 接口的代码需要执行的所有 Cudd_Ref(...) 和 Cudd_RecursiveDeref(...) 调用。请注意，如果需要，您也可以使用 C++ 代码中的 C 接口。

要完成您想做的事情，您必须组合 CUDD 提供的布尔运算符，从而获得具有所需属性的新布尔函数。

第一步是将 s 限制为 x=0 和 x=1 的情况：

BDD s0 = s & !x;
BDD s1 = s & x;

如您所见，新的 BDD（还）没有忘记 x 变量的值。您希望它们是 "don't care" w.r.t 到 x 的值。由于您已经知道 x 被限制为 s0 和 s1 中的一个特定值，您可以使用存在抽象运算符：

s0 = s0.ExistAbstract(x);
s1 = s1.ExistAbstract(x);

请注意，x 在这里用作所谓的 立方体 （见下文）。

现在这些就是您想要的 BDD。

立方体解释：如果同时从多个变量中抽象出来，你应该先从所有要抽象出来的变量中计算出这样一个立方体。立方体主要用于表示一组变量。从数理逻辑可知，如果你存在性地或普遍地抽象出多个变量，那么抽象出这些变量的顺序无关紧要。由于 CUDD 中的递归 BDD 操作是在 BDD 对（或三元组）上实现的，因此 CUDD 在内部也将一组变量表示为立方体，因此存在抽象操作只能在（1）BDD 上工作将执行存在抽象，以及 (2) BDD 表示要从中抽象的变量集。作为 BDD 的多维数据集的内部表示不应该与仅使用 CUDD（而不是扩展 CUDD）的开发人员相关，除了表示变量的 BDDD 也可以用作多维数据集。

Answer 2

使用 Cython 绑定到 Python 包 dd 的 CUDD 的方法如下，它使用常量值替换变量 x2。

import dd.cudd as _bdd

bdd = _bdd.BDD()
bdd.declare('x1', 'x2')
# negated conjunction of the variables x1 and x2
u = bdd.add_expr(r'~ (x1 /\ x2)')

let = dict(x2=False)
v = bdd.let(let, u)
assert v == bdd.true, v

let = dict(x2=True)
w = bdd.let(let, u)
w_ = bdd.add_expr('~ x1')
assert w == w_, (w, w_)

通过将 import 语句更改为 import dd.autoref as _bdd，相同的代码在纯 Python 中运行。 dd 的纯 Python 版本可以用 pip install dd 安装。 dd 与模块 dd.cudd 的安装描述为 here。

隐藏：BDD 的操作

CUDD: Manipulation of BDDs

binary

binary-decision-diagram

cudd