Aplicar reglas de equivalencia para convertir a CNF

Question

Tengo problemas para ver cómo podría aplicar las reglas de equivalencia mencionadas aquí a la siguiente fórmula para convertirla en forma normal conjuntiva (CNF).

$$(p \wedge q) \vee (\neg p \wedge r)$$

Conozco la solución a través de Wolfram Alpha Pero no veo cómo se pueden aplicar estas reglas para obtener la respuesta. Estas reglas me resultan un poco confusas cuando se trata de la negación de un literal. ¿Podría alguien ayudarme a entender este proceso?

Answer 1

Si miramos aquí se nos da un algoritmo a seguir, y veremos que en cada paso lo único que tenemos que hacer es dar un paso $5$ .

$$(p \wedge q) \vee (\neg p \wedge r) \equiv ((p \wedge q) \vee \neg p) \wedge ((p \wedge q) \vee r) \quad \text{ distribute} \vee \text{ over } \wedge$$ $$\equiv ((p \vee \neg p) \wedge (q \vee \neg p)) \wedge ((p \vee r) \wedge (q \vee r)) \quad \text{ again distribute} \vee \text{ over } \wedge $$ $(p \vee \neg p)$ es una tautología y sabemos que $t \wedge a \equiv a$ para cualquier tautología $t$ para que podamos simplemente "tirar" $(p \vee \neg p)$ . Esto nos deja con:

$$(q \vee \neg p) \wedge ((p \vee r) \wedge (q \vee r)) \equiv (q \vee \neg p) \wedge (p \vee r) \wedge (q \vee r) \quad \text{ since } \wedge \text{ is associative} $$

Esto es en forma normal conjuntiva, aunque no es exactamente lo que da Wolfram.

Answer 2

Esta fórmula está en forma normal disyuntiva (DNF), por lo que si sólo se utilizan esas reglas para convertirla en CNF, costará mucho esfuerzo. Pero hay un truco para convertir DNF a CNF rápidamente.

Denotemos dos nuevas variables A, B tales que:

• $A \to (p \wedge q) = \neg A \vee (p \wedge q) = (\neg A \vee p)\wedge(\neg A \vee q)$
• $B \to (\neg p \wedge r) = \neg B \vee(\neg p \wedge r)= (\neg B \vee \neg p)\wedge(\neg B \vee r)$

Así que su fórmula en CNF es $(A \vee B)$ junto con las restricciones anteriores, lo que significa:

$(A \vee B) \wedge (\neg A \vee p)\wedge(\neg A \vee q) \wedge (\neg B \vee \neg p)\wedge(\neg B \vee r)$

Answer 3

Primero escribe la tabla de verdad:

 p   q   r  (p∧q)  (¬p∧r)  [(p∧q)∨(¬p∧r)]
 0   0   0    0        0           0
 0   0   1    0        1           1
 0   1   0    0        0           0
 0   1   1    0        1           1
 1   0   0    0        0           0
 1   0   1    0        0           0
 1   1   0    1        0           1
 1   1   1    1        0           1

Ahora, ¿cómo se escribe una forma normal disyuntiva a partir de esto? A grandes rasgos, interpreta todos los "0s" como negaciones de las variables, y los "1s" como las variables cuando y sólo cuando la declaración se evalúa a 1, y haz una conjunción n-aria de eso. Luego se hace una disyunción de todo eso. La forma normal de la conjunción consiste en el dual de la forma normal disyuntiva. Puedes mirar las filas en las que la forma de declaración evalúa a 0 en lugar de a 1, y cambiar "OR" por "AND". Escribimos un literal si coincide con 0, y la negación del literal si coincide con 1 para las filas donde tenemos un "0".

La definición de forma normal conjuntiva dice que tienen que calificarse como wffs o formas de enunciado o expresiones significativas. Para ahorrarle a usted y a mí el trabajo de escribir una cadena con muchos paréntesis, en lo sucesivo utilizaré Notación polaca .

Dada una regla informal de desprendimiento, podemos definir los wffs relevantes de la siguiente manera:

1. Todas las letras minúsculas del alfabeto latino se consideran wffs.
2. Si $\alpha$ se califica como wff, entonces también lo hace N $\alpha$ .
3. Si $\alpha$ , $\beta$ se puede calificar como wffs, entonces también lo hace K $\alpha$$ \N -beta$.
4. Si $\alpha$ , $\beta$ se puede considerar como wffs, entonces también lo es A $\alpha$$ \N -beta$.

Así, Kpq representa el wff (en una lengua distinta) por encima de la primera columna que no cae debajo de una variable. KNpr representa el wff sobre la segunda columna que no cae debajo de una variable, y AKpqKNpr representa el wff sobre la tercera columna que no cae debajo de una variable.

AApqr sólo evalúa a 1 cuando una de sus variables toma el valor 1. En caso contrario, se califica como falso. AApNqr sólo se evalúa a 1 cuando Nq se evalúa a 0, y lo mismo ocurre con p y r. Y así sucesivamente, lo que nos permite inferir

KKK AApqr AApNqr AANpqr AANpqNr como forma normal conjuntiva.