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

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个具有not具有属性P

这是您要表达的意思吗？希望更清楚！