Comment les implicats premiers de cornes-formules sont-ils définis?

Question

Je suis confus sur la définition de premiers impliqués dans les formules de corne.

Par exemple dans le papier de Kira 2012 à la page 109 Il est indiqué:

maintenant dans le document de boros 2010 à la page 82 La définition suivante est utilisé:

Mon objectif est de décider si une formule de corne est prime ou non en temps polynomial. Pour cela, je veux assumer la définition utilisée à Kira 2012.

Comment puis-je prouver que les deux définitions ci-dessus pour les principales implications des formules de corne sont équivalentes?

edit: Ce que j'ai jusqu'à présent, c'est que si nous supposons la définition de Kiras et que nous avons par exemple une clause $ c=nee x_1 \ yee \ nee x_2 \ vee x_3 $ de formule < SPAN CLASS="MATH-CONTENEUR"> $ F $ ET $ C $ est APPORTER que $ F \ Rightarrow C $ . Si on néglige un littéral dans C, nous obtenons $ C_1=negn x_1 \ vee \ nee x_2 $ et évidemment $ C_1 \ Rightarrow C $ . Par conséquent, étant donné que $ C $ est la définition de Kiras, aucune autre sous-clause appropriée de $ C $ est un implicateur de sorte que $ f \ nrightarrow c_1 $ . Négliger plus de littéraux dans $ C_1 $ pour obtenir $ C_2 $ donnera $ C_2 \ RightARrow C_1 \ RightARrow C $ . Ensuite par définition de $ C $ il doit s'agir de ce $ f \ nrightarrow c_2 \ rightarrow c_1 $ et nous Obtenez que toutes les sous-clauses de $ C_1 $ ne sont pas primordies si nous vérifions que $ C_1 $ n'est pas premier. Par conséquent, pour vérifier si une formule $ f $ est prime nous considérons chaque clause $ C $ et néglige tous Littéraux de $ C $ Une fois et vérifiez si la nouvelle clause n'est pas prime. Si une clause est prime, il suit que f n'est pas prime.

Je pense que l'équivalence de l'autre direction est similaire. Supposons la définition de Boros. Ensuite, si nous considérons la clause $ C $ et déposer un littéral arbitraire que nous obtenons $ C_1 $ qui n'est pas Un implicate si $ C $ est prime donc $ f \ nrightarrow c_1 $ . Encore une fois, nous avons ovleusement $ C_1 \ Rightarrow C $ et en laissant tomber des littéraux plus arbitraires dans $ C_1 $ à obtenez $ C_2 $ nous notons $ f \ nrightarrow c_2 \ rightarrow c_1 $ (sinon $ F \ RightArrow C_2 \ RightARrow C_1 $ ce qui ne va pas depuis $ C_1 $ n'est pas impliqué). Étant donné que, en supprimant les littéraux, nous pouvons produire des sous-clauses arbitraires on peut suivre que toutes les sous-clauses appropriées de c ne peuvent pas être primordies sinon $ f \ rightarrow c_2 \ rightarrow c_1 $ qui est une contradiction. Et la définition de Kiras suit.

Mon raisonnement est correct?

Answer 1

Cette équivalence est une idée quelque peu sur le folklore dans des papiers sur les implicateurs de choix. Une petite preuve est présentée dans la section « Définitions » de cet article . L'idée de l'équivalence est que, si $ C $ n'est pas un impliciteur préférentiel pour $ \ varphi $ , alors il y a un sous-ensemble approprié $ C '$ de $ C $ (identification des clauses avec l'ensemble de Les littéraux qu'ils forcent) tels que $ C '$ est un impliciteur de $ \ varphi $ . Mais si tel est le cas, vous pouvez remplir $ C '$ avec les littéraux dans $ c \ setminus c' $ jusqu'à ce qu'il ait la taille $ | C | - 1 $ , et ainsi, vous obtenez un implicateur qui est $ C $ moins un littéral que vous avez "abandonné". L'autre sens de l'équivalence est trivial: si aucun sous-ensemble approprié de $ C $ est un impliciteur, puis dépose n'importe quel littéral de $ C $ vous donne quelque chose qui n'est pas un impliciteur.

Je ne vois pas la relation avec les formules de corne, car l'équivalence concerne les définitions des principaux implicateurs de toute formule.