SAT 求解器中 N 编码中的至少 K

Question

我知道如果给定一个至多 k out of N 工具，我可以通过将其更改为至多 (n-k) out of N 来获得至少 K out of N。

但我似乎无法理解这是怎么回事。我可能遗漏了一些非常微不足道的东西

例如，如果 K=2 且 N=6，那么 6 个中至少有 2 个等于 6 个中最多有 4 个

任何帮助将不胜感激

Answer 1

正如您所说，等价性并不正确。所以，不要因为不了解它而难过。为了看，让我们举个例子。假设我们只有布尔值，N=6 和 K=2，赋值：

True False False False False False

这6个变量。声明At most 2 out of 6 are True显然满足这个赋值，但是At least 4 out of 6 are True不满足。

也许你的意思是：

at least K out of N is True

等同于

at most N-K out of N is False

可以进一步概括为：

at least K out of N objects have property P

相当于：

at most N-K out of N objects do not have the property P

这就是你想表达的意思吗？希望这更清楚！