电路#

将布尔电路转换为等效的布尔公式。

在最坏情况下,布尔电路的表达能力可能比等效的公式指数级更高,因为电路可以多次重用子电路,而公式不能多次重用子公式。因此,如果电路较大,通过这种方式从布尔电路创建布尔公式可能是不可行的。

import matplotlib.pyplot as plt
import networkx as nx


def circuit_to_formula(circuit):
    # 将电路转换为等效公式。
    formula = nx.dag_to_branching(circuit)
    # 将每个节点的操作符或变量标签进行转移
    # circuit to the formula.
    for v in formula:
        source = formula.nodes[v]["source"]
        formula.nodes[v]["label"] = circuit.nodes[source]["label"]
    return formula


def formula_to_string(formula):
    def _to_string(formula, root):
        # 如果没有子节点,这是一个变量节点。
        label = formula.nodes[root]["label"]
        if not formula[root]:
            return label
        # 否则,这是一个运算符。
        children = formula[root]
        # 如果只有一个子节点,标签必须是NOT运算符。
        if len(children) == 1:
            child = nx.utils.arbitrary_element(children)
            return f"{label}({_to_string(formula, child)})"
        # 注意:这里的“左”和“右”有点误导性:实际上
        # 节点子节点之间没有顺序。这没关系,因为
        # 布尔运算符AND和OR是对称的。这只是意味着
        # 操作数的顺序无法预测,因此
        # 函数在每个平台上不一定表现相同
        # invocation.
        left, right = formula[root]
        left_subformula = _to_string(formula, left)
        right_subformula = _to_string(formula, right)
        return f"({left_subformula} {label} {right_subformula})"

    root = next(v for v, d in formula.in_degree() if d == 0)
    return _to_string(formula, root)

创建一个示例布尔电路。#

这个电路的输出有一个 ∧,下一层有两个 ∨。 第三层有一个变量 x 出现在左边的 ∨ 中,一个 变量 y 出现在左右两个 ∨ 中,以及一个 变量 z 的否定,它作为唯一节点出现 fourth layer.

circuit = nx.DiGraph()
# Layer 0
circuit.add_node(0, label="∧", layer=0)
# Layer 1
circuit.add_node(1, label="∨", layer=1)
circuit.add_node(2, label="∨", layer=1)
circuit.add_edge(0, 1)
circuit.add_edge(0, 2)
# Layer 2
circuit.add_node(3, label="x", layer=2)
circuit.add_node(4, label="y", layer=2)
circuit.add_node(5, label="¬", layer=2)
circuit.add_edge(1, 3)
circuit.add_edge(1, 4)
circuit.add_edge(2, 4)
circuit.add_edge(2, 5)
# Layer 3
circuit.add_node(6, label="z", layer=3)
circuit.add_edge(5, 6)
# 将电路转换为等效公式。
formula = circuit_to_formula(circuit)
print(formula_to_string(formula))


labels = nx.get_node_attributes(circuit, "label")
options = {
    "node_size": 600,
    "alpha": 0.5,
    "node_color": "blue",
    "labels": labels,
    "font_size": 22,
}
plt.figure(figsize=(8, 8))
pos = nx.multipartite_layout(circuit, subset_key="layer")
nx.draw_networkx(circuit, pos, **options)
plt.title(formula_to_string(formula))
plt.axis("equal")
plt.show()
((x ∨ y) ∧ (y ∨ ¬(z)))
((x ∨ y) ∧ (y ∨ ¬(z)))

Total running time of the script: (0 minutes 0.039 seconds)

Gallery generated by Sphinx-Gallery