如何定义喇叭公式的素数如何？

Question

我对喇叭公式的主要定义感到困惑。

例如在基拉2012年第109页，它已陈述：

现在在 boros 2010 第82页的以下定义用来：

我的目标是决定喇叭公式是素数是否在多项式时间中。为此，我想假设基拉2012中使用的定义。

如何证明上述两个定义对于喇叭公式的主要影响是等同的？

编辑： 到目前为止，我所拥有的是，如果我们假设kiras定义并且例如一个子句 $ c=neg x_1 \ vee \ neg x_2 \ vee x_3 $ 的公式<跨越类=“math-container”> $ f $ 和 $ c $ 是prime that the $ f \ RightRarrow C $ 。如果一个人在c中忽略了一个文字，我们得到 $ c_1=neg x_1 \ vee \ neg x_2 $ 并且显然 $ c_1 \ RightRarrow C $ 。因此，由于<跨度类=“math-container”> $ c $ 是prime，然后由kiras定义没有 $ c $ 的其他适当的子子句是一个含义所以<跨越类=“math-container”> $ f \ nightarrow c_1 $ 。忽略 $ c_1 $ 获取 $ c_2 $ 将给出 $ c_2 \ lightarrow c_1 \ lightarrow c $ 。然后根据 $ c $ 它必须是 $ f \ nightarrow c_2 \ lightarrow c_1 $ 我们获取 $ c_1 $ 如果我们检查 $ c_1 $ ，则不是prime的所有子子句主要的。因此，要检查公式 $ f $ 是prime我们考虑每个子句 $ c $ 并忽略所有 $ c $ 一次的文字并检查新子句是否不是素数。如果一个条款是素数，则遵循f不是素数。

我认为其他方向的等价类似。假设博罗斯的定义。然后，如果我们考虑子句 $ c $ 并且删除任意文字我们得到 $ c_1 $ 哪个不是一个牵引如果 $ c $ 是prime so so $ f \ nightarrow c_1 $ 。我们再次拥有 $ c_1 \ lightarrow c $ 以及在 $ c_1 $ 中删除任何更多任意文字获取 $ c_2 $ 我们注意 $ f \ nightarrow c_2 \ lightarrow c_1 $ （否则 $ f \ lightarrow c_2 \ lightarrow c_1 $ 由于 $ c_1 $ 没有牵引）。由于通过删除文字，我们可以生成任意子子句，可以遵循，也可以遵循C的所有适当的子条款，否则 $ f \ lightarrow c_2 \ lightarrow c_1 $ 这是一个矛盾。和kiras定义遵循。

是我的推理正确吗？

Answer 1

这个等价是关于素涂物的论文中有点民间想法。一个小的证明本文。 等效背后的想法是，如果 $ c $ 不是 $ \ vari $ 的主要突出链然后，有一个适当的子集 $ c'$ $ c $ （用该组识别子句他们强制的文字）这样<跨度类=“math-container”> $ c'$ 是 $ \ vari $ 的含义。但如果是这种情况，那么你可以用 $ c \ setminus c'$ clubly in $ c'$ 。 直到它具有大小 $ | c | - 1 $ ，因此，您获取了一个 $ c $ 减去一个字面形的含义，你是“掉落”。等效的另一个方向是微不足道的：如果没有正确的 $ c $ 是一个突出的，那么丢弃 $ c $ 给你一些不是amblicant的东西。

我没有看到与喇叭公式的关系，因为等价是关于任何公式的主要血管分析的定义。