¿Cómo convertir a la forma normal conjuntiva?

Question

Si tengo una fórmula: $((a \wedge b) \vee (q \wedge r )) \vee z$ ¿Estoy en lo cierto al pensar que la CNF para esta fórmula sería $(a\vee q \vee r \vee z) \wedge (b \vee q \vee r \vee z) $ ? ¿O hay algún otro método que deba seguir?

Answer 1

Para convertir a la forma normal conjuntiva utilizamos las siguientes reglas:

Doble negación:

1. $P\leftrightarrow \lnot(\lnot P)$

Leyes de Morgan

2. $\lnot(P\bigvee Q)\leftrightarrow (\lnot P) \bigwedge (\lnot Q)$

3. $\lnot(P\bigwedge Q)\leftrightarrow (\lnot P) \bigvee (\lnot Q)$

Leyes de distribución

4. $(P \bigvee (Q\bigwedge R))\leftrightarrow (P \bigvee Q) \bigwedge (P\bigvee R)$

5. $(P \bigwedge (Q\bigvee R))\leftrightarrow (P \bigwedge Q) \bigvee (P\bigwedge R)$

Así que ampliemos lo siguiente: (equivalente a la expresión en cuestión)

1. $(((A \bigwedge B) \bigvee (C \bigwedge D)) \bigvee E)$ Ahora usando 4. obtenemos:

2. $((A \bigwedge B) \bigvee C)\bigwedge ((A \bigwedge B) \bigvee D)) \bigvee E$ Y usando el 4. de nuevo

3. $((((A\bigvee C) \bigwedge (B \bigvee C))\bigwedge ((A\bigvee D) \bigwedge B\bigvee D))) \bigvee E)$ que da:

4. $(((A\bigvee C) \bigwedge (B \bigvee C))\bigvee E)\bigwedge ((A\bigvee D) \bigwedge B\bigvee D))\bigvee E) $

5. $(A\bigvee C\bigvee E) \bigwedge (B \bigvee C\bigvee E)\bigwedge (A\bigvee D\bigvee E) \bigwedge (B\bigvee D\bigvee E)$

Que ahora está en CNF. Puedes usar cosas como Wolfram Alpha para comprobar esto también si lo deseas.

Answer 2

Otra posibilidad es hacer una tabla de verdad (Nota, en mi simbología 1=T y 0=F); es más largo pero este método es a prueba de fallos. $\phi=((a\wedge b)\vee(q \wedge r))\vee z$ entonces:

$ a $ $b$ $q$ $r$ $z$ | $\phi$

0 0 0 0 0 | 0

0 0 0 0 1 | 1

0 0 0 1 0 | 0

Y así sucesivamente, y para cada fila en la que $ \phi=0 $ se obtiene una "Cláusula" poniendo el literal en la cláusula si toma 0 en esa fila y su "no" si el literal toma 1.

Por ejemplo, la cláusula de la primera línea es $(x \vee y\vee q \vee r \vee z)$ . la cláusula de la tercera línea es $(x \vee y\vee q \vee \bar r \vee z)$ . No hay cláusula para la segunda línea porque $ \phi=1 $ .

Para la línea (0 1 0 1 0 | 0) se obtiene la cláusula $(x \vee \bar y \vee q \vee \bar r \vee z)$ .

Finalmente se pone un $\wedge $ entre las cláusulas.