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 Answers 3

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$
6
  • $\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
    Commented Sep 20, 2016 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
    Commented Sep 20, 2016 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
    Commented Sep 20, 2016 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$
    – amWhy
    Commented Sep 20, 2016 at 21:29
  • $\begingroup$ Ah gotcha, this all makes sense now. Thank you for your help! $\endgroup$
    – Eques316
    Commented Sep 20, 2016 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$
2
  • $\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$
    – amWhy
    Commented Sep 20, 2016 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$ Commented Sep 20, 2016 at 22:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .