Need help with finding disjunctive and conjunctive normal forms

Question

I need to find disjunctive and conjunctive normal forms equivalent to $$\phi = \lnot (\lnot(p \land r) ∨ (q \land (r \lor s)))$$ and state which logical equivalences are used for each step.

Here is what I tried to do:

1. $\neg \neg(p \land r) \land \neg (q \land (r \lor s)))$ -De Morgan's law
2. $(p \land r) \land \neg(q \land (r \lor s))$ -Double negation law
3. $(p \land r) \land \neg((q \land r) \lor (q \land s))$ -Distributive law
4. $(p \land r) \land \neg(q \land r) \land \neg(q \land s))$ -De Morgan's law

I'm not really sure where to go from here or if I did a misstep. Any help would be much appreciated.

Table of logical equivalences

Answer 1

$1. ¬ ¬(p ∧ r) ∧ ¬ (q ∧ (r ∨ s))$ -De Morgan's law

$2. (p ∧ r) ∧ ¬(q ∧ (r ∨ s))$ -Double negation law

$3. (p ∧ r) ∧ ¬((q ∧ r) ∨ (q ∧ s))$ -Distributive law

$4. (p ∧ r) ∧ ¬(q ∧ r) ∧ ¬(q ∧ s))$ -De Morgan's law

Two more applications of DeMorgans' law:

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)$ by associativity of $\land$.

EDIT:

Now, we'll look at $$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)$$

We now we have $p\land r \land \lnot q \tag 7$.

We can drop the final clause in $(6)$, which is $ (\lnot q \lor s)$, since we have already established that $\lnot q$ holds (see 7), we know that $\lnot q \lor s$ is true, without having any knowledge of $s$.

(7) This is the most reduced form of the original statement as expressed in CNF

Answer 2

Here's the disjunctive normal form: $$\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.$$ I trust that you can figure out which rules I used.

Answer 3

Let $$\phi = \lnot (\lnot(p \land r) ∨ (q \land (r \lor s)))$$ To get to CNF:

1. $\lnot \lnot(p \land r) \land \lnot (q \land (r \lor s))$ -De Morgan's law
2. $(p \land r) \land \lnot(q \land (r \lor s))$ -Double negation law
3. $(p \land r) \land \lnot((q \land r) \lor (q \land s))$ -Distributive law
4. $(p \land r) \land (\lnot(q \land r) \land \lnot(q \land s))$ -De Morgan's law
5. $(p \land r) \land ((\lnot q \lor \lnot r) \land (\lnot q \lor \lnot s))$ -De Morgan's law
6. $p \land r \land (\lnot q \lor \lnot r) \land (\lnot q \lor \lnot s)$ -Associativity of $\land$
7. $p\land ((r\land \lnot q) \lor (r \land \lnot r))\land (\lnot q \lor \lnot s)$-Distributive law
8. $p\land (r\land \lnot q) \land (\lnot q \lor \lnot s)$-Because $r\land\lnot r=\textrm{F}$, and $A\lor\textrm{F}=A$
9. $p\land r\land \lnot q \land (\lnot q \lor \lnot s)$-Associativty of $\land$
10. $p\land r\land \lnot q$-Since $\lnot s$ is not a possibility, as we already have $\lnot q$ occurring in: $(p)\land (r)\land (\lnot q)$

To get to DNF:

1. $\lnot \lnot(p \land r) \land \lnot (q \land (r \lor s))$ -De Morgan's law
2. $(p \land r) \land \lnot(q \land (r \lor s))$ -Double negation law
3. $(p \land r) \land \lnot((q \land r) \lor (q \land s))$ -Distributive law
4. $(p \land r) \land (\lnot(q \land r) \land \lnot(q \land s))$ -De Morgan's law
5. $(p \land r) \land ((\lnot q \lor \lnot r) \land (\lnot q \lor \lnot s))$ -De Morgan's law
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))$ -Distributive law, Associativity of $\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))$ -Indempotent law
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)$ -Distributive law, Associativity of $\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)$ -Because $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}$ -Because $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)$ -Because $A\lor (A\land B)=A$

11 is in DNF, but we can go one better to get 12, which is also in DNF, where each of the literals $p$, $r$, and $\lnot q$ are termed degenerate disjunctions. We can think of $p \land r \land \lnot q$ as a kind of trivial disjunction: $\lor(p \land r \land \lnot q)$, and so this is why 12 is the DNF. Hence the CNF: $(p)\land(q)\land(\lnot q)$ and DNF: $(p \land r \land \lnot q)$ have similar forms, but thought of in terms of conjunctions or disjunctions.