Por ejemplo
puede $A \land C$ sea tanto la forma normal conjuntiva como la forma normal disyuntiva de
$(A \lor ((A \land B) \lor (\lnot A \land \lnot B \land \lnot C))) \land C$
Respuestas
¿Demasiados anuncios?
Taroccoesbrocco
Puntos
427
La respuesta corta es: ¡sí!
En efecto, $A \land C$ es a la vez CNF (porque es una conjunción de dos cláusulas disyuntivas, cada una formada por un solo literal) y un DNF (con una sola cláusula conjuntiva).
Para demostrar que $A \land C$ es una CNF y una DNF de $(A \lor ((A \land B) \lor (\lnot A \land \lnot B \land \lnot C))) \land C$ queda por demostrar que $A \land C$ es lógicamente equivalente a $(A \lor ((A \land B) \lor (\lnot A \land \lnot B \land \lnot C))) \land C$ . Para demostrarlo, utilizo equivalencias lógicas enumeradas ici como reglas de reescritura (el uso de la asociatividad se deja implícito):
\begin{align} (A \lor (A \land B) \lor (\lnot A \land \lnot B \land \lnot C)) \land C &\equiv (A \lor (\lnot A \land \lnot B \land \lnot C)) \land C &\text{absortion law} \\ &\equiv (A \lor \lnot A) \land (A \lor \lnot B) \land (A \lor \lnot C) \land C &\text{distributivity law} \\ &\equiv (A \lor \lnot B) \land (A \lor \lnot C) \land C &\text{identity law} \\ &\equiv (A \lor (\lnot B \land \lnot C)) \land C &\text{distributivity law} \\ &\equiv (A\land C) \lor (\lnot B \land \lnot C \land C) &\text{distributivity law} \\ &\equiv A\land C &\text{identity law} \end{align} donde se puede aplicar la primera ley de identidad ya que $A \lor \lnot A$ es una tautología, y la segunda ley de identidad puede aplicarse porque $\lnot B \land \lnot C \land C$ es una contradicción.
Observación . Preste atención a que una CNF de una fórmula dada no es única, y de forma similar para DNF. Por ejemplo, también $A \land C \land (B \lor \lnot B)$ es una CNF de $(A \lor ((A \land B) \lor (\lnot A \land \lnot B \land \lnot C))) \land C$ . Así que, hablando con propiedad, no está claro a qué se refiere cuando habla de el CNF (o el DNF) de una fórmula dada.
Más observaciones interesantes sobre la no unicidad de CNF (o DNF) de una fórmula dada se encuentran en esta pregunta .
Graham Kemp
Puntos
29085
Una forma normal conjuntiva es una conjunción de una secuencia de disyunciones de una secuencia de literales o sus negaciones. Abreviado como: una conjunción de disyunciones de literales o sus negaciones.
Un literal único es una conjunción de una secuencia de un literal. También es una disyunción de una secuencia de un literal.
Así $A\wedge C$ es una conjunción de dos disyunciones de un literal; y también una disyunción de dos conjunciones de un literal. Es decir, es tanto una forma normal conjuntiva como una forma normal disyuntiva.
Ahora bien, ¿es una CNF/DNF para $(A\vee((A\wedge B)\vee(\neg A\wedge\neg B\wedge\neg C)))\wedge C$ ?
Bien, $C$ debe ser verdadera para que se cumpla la afirmación. Si sustituimos $\top$ para $C$ es decir $(A\vee((A\wedge B)\vee(\neg A\wedge\neg B\wedge \bot)))\wedge \top$ que se simplifica a $A$ . Así que $A$ también debe ser verdad. El valor de $B$ es irrelevante.
Por lo tanto $A\wedge C$ es efectivamente un equivalente CNF/DNF de la afirmación.
