¿Cómo se definen las implicaciones primas de las fórmulas de cuerno?

Question

Estoy confundido acerca de la definición de implicaciones primas en fórmulas de bocina.

Por ejemplo en el papel de kira 2012 en la página 109 se afirma:

Ahora en el documento de boros 2010 en la página 82 la siguiente definición se utiliza:

Mi objetivo es decidir si una fórmula de bocina es Prime o no en el tiempo polinomial. Para eso quiero asumir la definición utilizada en KIRA 2012.

¿Cómo puedo probar que las dos definiciones anteriores para las implicaciones primas de las fórmulas de cuerno son equivalentes?

Editar: Lo que he tan lejos es que si asumimos la definición de Kiras y, por ejemplo, una cláusula $ c=net x_1 \ vee \ net x_2 \ vee x_3 $ de fórmula < Span Class="Math-contenedor"> $ F $ y $ C $ es Prime entonces $ f \ RudoGarrow C $ . Si se descuida un literal en C obtendramos $ c_1=net x_1 \ vee \ neg x_2 $ y obviamente $ c_1 \ RudoGarrow C $ . Por lo tanto, desde $ C $ es Prime entonces por KIRAS Definición, no hay otra sub-cláusula adecuada de $ C $ es un implicante por lo que $ f \ nrightarrow c_1 $ . Descuidando más literales en $ c_1 $ para obtener $ c_2 $ dará $ C_2 \ rudowarrow c_1 \ rudowarrow c $ . Luego, por definición de $ c $ debe ser ese $ f \ nrightarrow c_2 \ judowarrow c_2 \ judowarrow c_1 $ y nosotros Obtenga que todas las subcláusulas de $ c_1 $ no son primeros si compruebamos que $ c_1 $ no es principal. Por lo tanto, para comprobar si una fórmula $ f $ es primo, consideramos cada cláusula $ c $ y descuide todos Literales de $ C $ una vez y verifique si la nueva cláusula no es primordial. Si una cláusula es Prime, sigue que F no es Prime.

Creo que la equivalencia para la otra dirección es de manera similar. Supongamos la definición de boros. Luego, si consideramos la cláusula $ C $ y suelte un literal arbitrario que obtenemos $ c_1 $ que no es Una implicación si $ C $ es Prime So $ F \ NRIGHTARROW C_1 $ . Nuevamente, tenemos oviosamente $ c_1 \ judowarrow c $ y dejando caer más literales arbitrarios en $ c_1 $ a Obtenga $ c_2 $ Notamos $ f \ ngrightarrow c_2 \ rudotrow c_1 $ (de lo contrario $ F \ Rudotrow C_2 \ Rudotrow C_1 $ que está mal desde $ c_1 $ no es implicado). Dado que al caer literales podemos producir subcláusulas arbitrarias, se puede seguir, también todas las subcláusulas correctas de C no pueden ser Prime de lo contrario $ F \ RUDARLOW C_2 \ RUDARLOW C_2 \ JUGAR> que es una contradicción. Y la definición de kiras sigue.

es mi razonamiento correcto?

Answer 1

Esta equivalencia es una idea algo folclórica en los documentos sobre los primos implicantes. Una pequeña prueba se presenta en la sección "Definiciones" de este documento . La idea detrás de la equivalencia es que, si $ c $ no es un implicante primo para $ \ varphi $ , entonces hay un subconjunto adecuado $ c '$ de $ C $ (identificación de cláusulas con el conjunto de Los literales que forzan) de manera que $ c '$ es un implicante de $ \ varphi $ . Pero si este es el caso, entonces puede rellene $ c '$ con los literales en $ C \ setminus c' $ hasta que tenga el tamaño $ | c | - 1 $ , y por lo tanto, obtiene un implicante que es $ C $ menos exactamente un literal que "cayó". La otra dirección de la equivalencia es trivial: si no hay un subconjunto adecuado de $ c $ es implicante, luego dejando caer cualquier literal de $ C $ le da algo que no es un implicante.

No veo la relación con las fórmulas de bocina, ya que la equivalencia se trata de definiciones de implicantes primordiales de cualquier fórmula.