3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

$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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Eques316 Sep 20 '16 at 4:54
  • $\begingroup$ 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. $\endgroup$ – Eques316 Sep 20 '16 at 5:07
  • $\begingroup$ 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? $\endgroup$ – Eques316 Sep 20 '16 at 21:17
  • $\begingroup$ 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$. $\endgroup$ – Namaste Sep 20 '16 at 21:29
  • $\begingroup$ Ah gotcha, this all makes sense now. Thank you for your help! $\endgroup$ – Eques316 Sep 20 '16 at 22:09
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$ $\endgroup$ – Namaste Sep 20 '16 at 22:14
  • $\begingroup$ @amWhy Cheers, I was just noting that. Since the DNF is all $\land$s it cannot be any other way. $\endgroup$ – Daniel Buck Sep 20 '16 at 22:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.