algorithm - 减少 3-SAT 到顶点覆盖？

Question

有人可以以最简单的方式向我解释，如何减少3-SAT到Vertex Cover？我正在按照这里的解释（滚动到第 4 页底部）。我了解拥有两个“小工具”的基本设置：2 节点变量小工具和 3 节点子句小工具。我也将公式理解k = variables + 2 clauses为覆盖所有边缘所需的最小节点数。我不明白的是，这种设置如何证明如果存在 a k-covering，则 CNF 中的布尔表达式是可满足的。具有可满足和不可满足表达式的示例会有所帮助。此外，一旦3-SAT问题转换为 a k-covering，它是否提供了一种方法来识别哪个值（true或false) 应该分配给每个变量以满足布尔表达式？谢谢你的帮助。