Necesito ayuda para encontrar formas normales disyuntivas y conjuntivas

Question

Necesito encontrar formas normales disyuntivas y conjuntivas equivalentes a $$\phi = \lnot (\lnot(p \land r) (q \land (r \lor s)))$$ e indique qué equivalencias lógicas se utilizan para cada paso.

Esto es lo que he intentado hacer:

1. $\neg \neg(p \land r) \land \neg (q \land (r \lor s)))$ -Ley de Morgan
2. $(p \land r) \land \neg(q \land (r \lor s))$ -Ley de la doble negación
3. $(p \land r) \land \neg((q \land r) \lor (q \land s))$ -Derecho distributivo
4. $(p \land r) \land \neg(q \land r) \land \neg(q \land s))$ -Ley de Morgan

No sé muy bien a dónde ir a partir de aquí o si he dado un paso en falso. Cualquier ayuda será muy apreciada.

Tabla de equivalencias lógicas

Answer 1

$1. ¬ ¬(p ∧ r) ∧ ¬ (q ∧ (r ∨ s))$ -Ley de Morgan

$2. (p ∧ r) ∧ ¬(q ∧ (r ∨ s))$ -Ley de la doble negación

$3. (p ∧ r) ∧ ¬((q ∧ r) ∨ (q ∧ s))$ -Derecho distributivo

$4. (p ∧ r) ∧ ¬(q ∧ r) ∧ ¬(q ∧ s))$ -Ley de Morgan

Dos aplicaciones más de la ley de DeMorgans:

5. $(p\land r)\land (\lnot q \lor \lnot r)\land (\lnot q \lor \lnot s).$

6. $(p)\land (r) \land (\lnot q \lor \lnot r) \land (\lnot q \lor \lnot s)$ por asociatividad de $\land$ .

EDITAR:

Ahora veremos $$r \land(\lnot q \lor \lnot r) \equiv (r\land \lnot q) \lor (r \land \lnot r)$$

$$\equiv (r\land \lnot q) \lor F \equiv (r\land \lnot q)$$

Ahora tenemos $p\land r \land \lnot q \tag 7$ .

Podemos eliminar la cláusula final en $(6)$ que es $ (\lnot q \lor s)$ , puesto que ya hemos establecido que $\lnot q$ (véase 7), sabemos que $\lnot q \lor s$ es cierto, sin tener conocimiento de $s$ .

(7) Esta es la forma más reducida del enunciado original expresado en CNF

Answer 2

Aquí está la forma normal disyuntiva: $$\phi = \lnot (\lnot (p \land r) \lor (q\land(r\lor s)))=\lnot(\lnot p \lor\lnot r \lor (q \land(r\lor s)))=\lnot((\lnot p \lor \lnot r \lor q) \land (\lnot p \lor \lnot r \lor r \lor s)))=p\land r\land\lnot q.$$ Confío en que sepas qué normas he utilizado.

Answer 3

Sea $$\phi = \lnot (\lnot(p \land r) ∨ (q \land (r \lor s)))$$ Para llegar a CNF:

1. $\lnot \lnot(p \land r) \land \lnot (q \land (r \lor s))$ -Ley de Morgan
2. $(p \land r) \land \lnot(q \land (r \lor s))$ -Ley de la doble negación
3. $(p \land r) \land \lnot((q \land r) \lor (q \land s))$ -Derecho distributivo
4. $(p \land r) \land (\lnot(q \land r) \land \lnot(q \land s))$ -Ley de Morgan
5. $(p \land r) \land ((\lnot q \lor \lnot r) \land (\lnot q \lor \lnot s))$ -Ley de Morgan
6. $p \land r \land (\lnot q \lor \lnot r) \land (\lnot q \lor \lnot s)$ -Asociatividad de $\land$
7. $p\land ((r\land \lnot q) \lor (r \land \lnot r))\land (\lnot q \lor \lnot s)$ -Derecho distributivo
8. $p\land (r\land \lnot q) \land (\lnot q \lor \lnot s)$ -Porque $r\land\lnot r=\textrm{F}$ et $A\lor\textrm{F}=A$
9. $p\land r\land \lnot q \land (\lnot q \lor \lnot s)$ -Asociación de $\land$
10. $p\land r\land \lnot q$ -Desde $\lnot s$ no es una posibilidad, puesto que ya tenemos $\lnot q$ ocurriendo en: $(p)\land (r)\land (\lnot q)$

Para llegar a DNF:

1. $\lnot \lnot(p \land r) \land \lnot (q \land (r \lor s))$ -Ley de Morgan
2. $(p \land r) \land \lnot(q \land (r \lor s))$ -Ley de la doble negación
3. $(p \land r) \land \lnot((q \land r) \lor (q \land s))$ -Derecho distributivo
4. $(p \land r) \land (\lnot(q \land r) \land \lnot(q \land s))$ -Ley de Morgan
5. $(p \land r) \land ((\lnot q \lor \lnot r) \land (\lnot q \lor \lnot s))$ -Ley de Morgan
6. $(p \land r) \land ((\lnot q \land \lnot q) \lor (\lnot r \land \lnot q) \lor (\lnot q \land \lnot s) \lor (\lnot r \land \lnot s))$ -Ley distributiva, Asociatividad de la $\lor$
7. $(p \land r) \land (\lnot q \lor (\lnot r \land \lnot q) \lor (\lnot q \land \lnot s) \lor (\lnot r \land \lnot s))$ -Ley indempotente
8. $(p \land r \land \lnot q) \lor (p \land r \land \lnot r \land \lnot q) \lor (p \land r \land \lnot q \land \lnot s) \lor (p \land r \land \lnot r \land \lnot s)$ -Ley distributiva, Asociatividad de la $\land$
9. $(p \land r \land \lnot q) \lor (p \land \textrm{F} \land \lnot q) \lor (p \land r \land \lnot q \land \lnot s) \lor (p \land \textrm{F} \land \lnot s)$ -Porque $r \land \lnot r=\textrm{F}$
10. $(p \land r \land \lnot q) \lor \textrm{F} \lor (p \land r \land \lnot q \land \lnot s) \lor \textrm{F}$ -Porque $A \land \textrm{F}=\textrm{F}$
11. $(p \land r \land \lnot q) \lor (p \land r \land \lnot q \land \lnot s)$
12. $(p \land r \land \lnot q)$ -Porque $A\lor (A\land B)=A$

11 está en DNF, pero podemos ir un poco más allá y obtener 12, que también está en DNF, donde cada uno de los literales $p$ , $r$ et $\lnot q$ se denominan degenerado disyunciones. Podemos pensar en $p \land r \land \lnot q$ como una especie de disyunción trivial: $\lor(p \land r \land \lnot q)$ y por eso 12 es el DNF. De ahí el CNF: $(p)\land(q)\land(\lnot q)$ y DNF: $(p \land r \land \lnot q)$ tienen formas similares, pero pensadas en términos de conjunciones o disyunciones.