# Need help with finding disjunctive and conjunctive normal forms

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

$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:

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

2. $(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

• Thanks for your response. From 6, I think the next step would involve $(r) \land ( \neg q \lor \neg r)$ being reduced to $r \land \neg q$ After that, the r's would combine due to absorption law. I'm just not sure what happened to the s. – Eques316 Sep 20 '16 at 4:54
• I used a truth table to find $r \land \neg q$ but I'm not supposed to use truth tables so I'll need to figure out the logical equivalent to use for this step. – Eques316 Sep 20 '16 at 5:07
• Thanks for the edit. I didn't realize that the identity law could be applied to the $(r \land \neg q) \lor (r \land \neg r)$. So (7) would also be the DNF because it only contains AND's? – Eques316 Sep 20 '16 at 21:17
• Exactly! But if we had, another proposition with, say 6 distinct variables, and reduced to, e.g..$(a \lor \lnot b) \land (c \lor d) \land (\lnot e \lor f)$, that would also be reduced CNF, because the clauses are each conjoined by $\land$. – Namaste Sep 20 '16 at 21:29
• Ah gotcha, this all makes sense now. Thank you for your help! – Eques316 Sep 20 '16 at 22:09

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.

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.

• Your CNF is not reduced enough; $p \land r \land (\lnot q \lor \lnot r) \land (\lnot q \lor \lnot s) \equiv [(p) \land (r) \land (\lnot q)]$. It so happens, in fact that CNF and DNF. In terms of DNF, we can view it simply one disjunct: $(p\land r \land \lnot q)$ – Namaste Sep 20 '16 at 22:14
• @amWhy Cheers, I was just noting that. Since the DNF is all $\land$s it cannot be any other way. – Daniel Buck Sep 20 '16 at 22:20