备注
单击 here 要下载完整的示例代码,请执行以下操作
电路#
将布尔电路转换为等效布尔公式。
在最坏的情况下,布尔电路可以比等效公式以指数形式更具表现力,因为电路可以多次重用子电路,而公式不能多次重用子公式。因此,如果电路很大,以这种方式从布尔电路创建布尔公式可能是不可行的。
import matplotlib.pyplot as plt
import networkx as nx
def circuit_to_formula(circuit):
# Convert the circuit to an equivalent formula.
formula = nx.dag_to_branching(circuit)
# Transfer the operator or variable labels for each node from the
# 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):
# If there are no children, this is a variable node.
label = formula.nodes[root]["label"]
if not formula[root]:
return label
# Otherwise, this is an operator.
children = formula[root]
# If one child, the label must be a NOT operator.
if len(children) == 1:
child = nx.utils.arbitrary_element(children)
return f"{label}({_to_string(formula, child)})"
# NB "left" and "right" here are a little misleading: there is
# no order on the children of a node. That's okay because the
# Boolean AND and OR operators are symmetric. It just means that
# the order of the operands cannot be predicted and hence the
# function does not necessarily behave the same way on every
# 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的否定。
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)
# Convert the circuit to an equivalent formula.
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)))
脚本的总运行时间: (0分0.089秒)