Como estão os primeiros implicados de fórmulas de chifre definidos?

Question

Estou confuso sobre a definição de prime implica em fórmulas de chifre.

Por exemplo, no papel de kira 2012 Na página 109 é declarado:

Agora no papel de Boros 2010 na página 82 A seguinte definição é usado:

Meu objetivo é decidir se uma fórmula de chifre é primo ou não em tempo polinomial. Para que eu quero assumir a definição usada em Kira 2012.

Como posso provar que as duas definições acima para as primeiras implicações de fórmulas de chifre são equivalentes?

edit: O que eu tenho até agora é que, se assumirmos a definição de Kiras e, por exemplo, uma cláusula $ c=NEG X_1 \ Vee \ Neg X_2 \ Vee X_3 $ de Fórmula < span class="contêiner matemática"> $ F $ e $ c $ é primo então $ f \ Rightarrow C $ . Se alguém negligencia um literal em c, recebemos $ c_1=NEG X_1 \ Vee \ Neg X_2 $ e obviamente $ c_1 \ $ Rightarrow C $ . Portanto, como $ c $ é primo então por kiras Definition Nenhuma outra sub-cláusula adequada de $ c $ é um implicante então $ f \ nightarrow c_1 $ . Negligenciando mais literais em $ c_1 $ para obter $ c_2 $ vai dar $ C_2 \ rightarrow c_1 \ rightarrow c $ . Em seguida, por definição de $ c $ Deve ser que $ f \ nrightarrow c_2 \ rightarrow c_1 $ e nós obter que todas as subpas cláusulas de $ c_1 $ não são primo se verificarmos que $ c_1 $ não é melhor. Portanto, para verificar se uma fórmula $ F $ é primo Nós consideramos cada cláusula $ c $ e negligência Literais de $ c $ uma vez e verifique se a nova cláusula não é primo. Se uma cláusula é primo, segue que F não é primo.

Eu acho que a equivalência para a outra direção é similarmente. Assumir a definição de Boros. Então, se considerarmos a cláusula $ c $ e soltar um literal arbitrário, obtemos $ c_1 $ que não é Um implicado se $ c $ é primo assim $ f \ nrightarrow c_1 $ . Mais uma vez temos oviosamente $ c_1 \ rightarrow C $ e caindo mais literais arbitrários em $ c_1 $ para obter $ c_2 $ Observamos $ f \ nightarrow c_2 \ rightarrow c_1 $ (caso contrário $ f \ rightarrow c_2 \ rightarrow c_1 $ O que está errado desde $ c_1 $ não é implicado). Desde que, deixando literais, podemos produzir sub-cláusulas arbitrárias, pode-se seguir que também todas as sub-cláusulas adequadas de c não podem ser primo de outra forma $ f \ rightarrow c_2 \ righttarrow c_1 $ que é uma contradição. E Kiras Definição segue.

é o meu raciocínio correto?

Answer 1

Esta equivalência é uma ideia um pouco folclore em papéis sobre os primeiros implícitos. Uma pequena prova é apresentado na secção "Definições" do este papel . A ideia por trás da equivalência é que, se $ c $ não é um implicante primo para $ \ varphi $ , em seguida, há um subconjunto adequado $ c '$ de $ c $ (identificando cláusulas com o conjunto de Literais que eles forçam) tal que $ c '$ é um implicante de $ \ varphi $ . Mas se este for o caso, então você pode preencher $ c '$ com os literais em $ c \ setminus c' $ até que tenha tamanho $ | c | - 1 $ , e assim, você obtém um implicante que é $ c $ menos um literal você "caiu". A outra direção da equivalência é trivial: se nenhum subconjunto adequado de $ c $ é um implicante, depois soltando qualquer literal de $ C $ dá-lhe algo que não é um implicante.

Eu não vejo a relação com fórmulas de chifre, pois a equivalência é sobre definições para primeiros implicantes de qualquer fórmula.