Saltar al contenido

¿Cómo convertir a la forma normal conjuntiva?

Te sugerimos que revises esta solución en un entorno controlado antes de pasarlo a producción, saludos.

Solución:

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

Doble negación:

1. $Pleftrightarrow lnot(lnot P)$

Leyes de De Morgan

2. $lnot(Pbigvee Q)leftrightarrow (lnot P) bigwedge (lnot Q)$

3. $lnot(Pbigwedge Q)leftrightarrow (lnot P) bigvee (lnot Q)$

leyes distributivas

4. $(P bigvee (Qbigwedge R))leftrightarrow (P bigvee Q) bigwedge (Pbigvee R)$

5. $(P bigwedge (Qbigvee R))leftrightarrow (P bigwedge Q) bigvee (Pbigwedge 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 4. de nuevo

3. $((((Abigvee C) bigwedge (B bigvee C))bigwedge ((Abigvee D) bigwedge Bbigvee D))) bigvee E)$ que da:

4. $(((Abigvee C) bigwedge (B bigvee C))bigvee E)bigwedge ((Abigvee D) bigwedge Bbigvee D))bigvee E) $

5. $(Abigvee Cbigvee E) bigwedge (B bigvee Cbigvee E)bigwedge (Abigvee Dbigvee E) bigwedge (Bbigvee Dbigvee E)$

Que ahora está en CNF. Puede usar cosas como Wolfram Alpha para verificar esto también si lo desea.

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 fallas. $phi=((acuña b)vee(q cuña r))vee z$ entonces:

$$begin{arrayc a & b & q & r & z & phi\hline 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 1 & 1 \ 0 & 0 & 0 & 1 & 0 & 0 \ endarray$$

Y así sucesivamente, y por cada fila en la que $ phi=0 $ obtienes 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 yvee q vee r vee z)$. la cláusula de la tercera línea es $(x vee yvee q vee bar r vee z)$. No hay cláusula para la segunda línea porque $ phi=1 $.

Para la línea $begin{arrayc0&1&0&1&0&0endarray$ obtienes la cláusula $(x vee bar y vee q vee bar r vee z)$.

Finalmente pones un $cuña $ entre las cláusulas.

Recuerda algo, que te damos el privilegio parafrasear si encontraste tu inconveniente justo a tiempo.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *