【电路可满足性问题】
电路可满足性问题(Circuit satisfiability problem)描述为:给定一个电路,需要确定是否存在对输入的赋值使得输出值为1。如果存在这样的赋值,则称这个电路是可满足的。这个赋值也被称为一个满足的赋值。如图5为电路可满足性问题的一个实例。
在这里插入图片描述
图5 电路可满足性问题
图中的左边,从上到下依次是或门、非门。图中的右边是与门。当1和2输入都为1,3输入为0的时候,输出为1。即这个电路是满足的。

0
Posted in 算法设计与分析

Leave a Comment:

电子邮件地址不会被公开。