SAT解算器中至少有K个编码(共N个)

Question

我知道，给定N中最多k个工具，我可以通过将其更改为N中最多(N-k(个来获得N中至少k个。

但我似乎无法理解这是怎么回事。我可能错过了一些非常琐碎的

例如，如果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则不满意。

也许你的意思是：

N中至少有K是真

相当于

最多N个中的N-K为错误

可以进一步推广为：

N个对象中至少有K个对象具有属性p

相当于：

最多N个对象中的N-K个对象不具有属性p

这是你想要表达的吗？希望更清楚！