# Help me to solve with equivalent functions to Disjunctive.normal.form

How I can solve this? I'm really stupid in this logical "math", but if I see example maybe I will understand. Help me with using logical equivalences. Show me please every step; and let's try to convert to DNF.

Edit: Here's the problem (image file inserted here):

-
First, we are not here to do your homework for you. We'd be happy to answer specific questions, but we prefer that you've put some effort into this problem first, and that you show us your work, even if it's not complete. Now: does the "dot" denote conjunction? The over-bar negation? Does $x_1 \bar x_4$ denote $(x_1 \land \lnot x_4)$? –  amWhy May 26 '11 at 20:57
Hint: Can you do anything with the first two terms, ignoring the last? –  Ross Millikan May 26 '11 at 21:56
@amWhy I'm assuming that: $(x_{1} \to x_{2}) \cdot (x_{2} \to \bar{x_3}) \cdot (x_{3} \to x_{1}\bar{x_4})$ Is equal to the more contemporary notation: $(x_{1} \to x_{2}) \land (x_{2} \to \lnot{x_3}) \land (x_{3} \to (x_{1} \land \lnot{x_4}))$. Where $\to$ is the material conditional. –  lewellen May 26 '11 at 22:13
@lewellen: yes, I pretty much assumed the same. Thanks for confirming... –  amWhy May 26 '11 at 22:40
thanks, but I have such solve: ~X1*~X3 V X2*~X3 notx1 and notx3 or x2 and not x3 –  user707895 May 27 '11 at 8:32

Continued original post of mine, below:

In my calculations, I arrived at the same answer that the OP has posted in his comment to lewellen. (Note in particular, that the original solution posted by lewellen is only one possible solution to the expression, though is not equivalent to it.)

The solution to the given problem is, indeed, what the user obtained: $(\lnot x_1 \land \lnot x_3) \lor (x_2 \land \lnot x_3)$, which is in disjunctive normal form. The solution could easily be expressed as $\lnot x_3 \land (\lnot x_1 \lor x_2)$, but of course, this is not disjunctive normal form.

Original problem:

$$(x_{1} \Rightarrow x_{2}) \land (x_{2} \Rightarrow \lnot{x_3}) \land (x_{3} \Rightarrow (x_{1} \land \lnot{x_4}))$$

Note the equivalence: $$(p\rightarrow q) \equiv (\lnot p \lor q)$$ for any $p, q$.

Applying this equivalence to the original problem gets us:

$$(\lnot x_{1} \lor x_{2}) \land (\lnot x_{2} \lor \lnot{x_3}) \land (\lnot x_{3} \lor (x_{1} \land \lnot{x_4}))$$

Observe that $\lnot x_3$ occurs as a disjunct to the second and last conjuncts. From here, we can use distribution:

$$(\lnot x_{1} \lor x_{2}) \land (\lnot{x_3} \lor (\lnot x_{2} \land x_{1} \land \lnot{x_4}))$$

Note that, the above expression, to be true, requires that (A) $(\lnot x_{1} \lor x_{2})$ is true, if the entire expression is to be true. Hence, it follows that the expression (B)$(\lnot x_{2} \land x_{1} \land \lnot x_4)$ cannot be true, since, from (A), either $\lnot x_1$ is true, in which case (B) is false, or else $x_2$ is true, in which case (B) is false.

That leaves us, using distribution, with $$(\lnot x_{1} \lor x_{2}) \land \lnot{x_3} \equiv (\lnot x_1 \land \lnot x_3) \lor (x_2 \land \lnot x_3),$$

which is now in disjunctive normal form.

I will add to this answer, to discuss disjunctive normal form and one way to obtain it. It can be thought of as expressing in the most economical of forms, the minimum number of possible combinations of truth value assignment of variables all in one disjunctive statement. For example,

$$(x_{1} \implies x_{2}) \land (x_{2} \implies \lnot{x_3}) \land (x_{3} \implies (x_{1} \land \lnot{x_4}))$$

holds if and only if:

(1) $x_1$ is false and $x_3$ is false, i.e. $(\lnot x_1 \land \lnot x_3)$ ($x_2$ can be true or false, $x_4$ can be true or false).

OR

(2) $x_2$ is true and $x_3$ is false, i.e. $(x_2 \land \lnot x_3)$ ($x_1$ can be true or false, $x_4$ can be true or false).

Such form can easily be constructed through the use of a truth-table, provided the expression under consideration is not too complicated!

$\qquad\qquad\qquad\qquad\qquad\qquad$Truth Table

$\qquad(x_{1} \Rightarrow x_{2}) \land (x_{2} \Rightarrow \lnot{x_3}) \land (x_{3} \Rightarrow (x_{1} \land \lnot{x_4}))$

$\qquad P = x_1$, $Q = x_2$, $R = x_3$, $S = x_4$

The evaluation of the truth value of the entire expression, under the $2^4=16$ possible truth-value assignments for $4$ variables, is given by the column in red.

Note that the expression evaluates as true in the following rows: $2,3,10,11,14,15$. Each of those rows reveal the truth value assignment necessary for the expression to evaluate as true.

-

Even though this is an obvious homework problem, I see value in answering this for people looking for approaches to getting a DNF in the future. So...

Assuming:

$$(x_{1} \Rightarrow x_{2}) \land (x_{2} \Rightarrow \lnot{x_3}) \land (x_{3} \Rightarrow (x_{1} \land \lnot{x_4}))$$

Apply the Material Conditional rewrite: $(x_0 \Rightarrow x_1) \to \lnot (x_0 \land \lnot x_1 )$ (here $\to$ means replace the left hand side with the right hand side)

$$\lnot (x_{1} \land \lnot x_{2}) \land \lnot (x_{2} \land \lnot \lnot{x_3}) \land \lnot (x_{3} \land \lnot (x_{1} \land \lnot{x_4}))$$

Apply De Morgan's rewrite (And): $\lnot (x_0 \land x_1) \to (\lnot x_0) \lor (\lnot x_1)$ and the Double negation rewrite: $\lnot \lnot x_0 \to x_0$

$$(\lnot x_{1} \lor x_{2}) \land (\lnot x_{2} \lor \lnot{x_3}) \land (\lnot x_{3} \lor \lnot \lnot (x_{1} \land \lnot{x_4}))$$

$$(\lnot x_{1} \lor x_{2}) \land (\lnot x_{2} \lor \lnot{x_3}) \land (\lnot x_{3} \lor (x_{1} \land \lnot{x_4}))$$

Apply And/Or rewrite: $x_0 \land (x_0 \lor x_1) \to (x_0 \land x_0) \lor (x_0 \land x_1)$ to get the Conjunctive Normal Form (CNF)

$$(\lnot x_{1} \lor x_{2}) \land (\lnot x_{2} \lor \lnot{x_3}) \land (\lnot x_{3} \lor x_{1}) \land (\lnot x_{3} \lor \lnot{x_4})$$

Apply And/Or rewrite:

$$(\lnot x_{1} \lor x_{2}) \land (\lnot{x_3} \lor (\lnot x_{2} \land x_{1} \land \lnot{x_4}))$$

$\lnot x_{2} \land x_{1} \land \lnot x_4$ cannot be true if $x_1 \lor x_2$ is true

$$(\lnot x_{1} \lor x_{2}) \land (\lnot{x_3})$$

Apply and/or rewrite to get the final DNF of the original expression

$$(\lnot x_{1} \land \lnot{x_3}) \lor (x_{2} \land \lnot{x_3})$$

-
thanks, but I have such solve: ~X1*~X3 V X2*~X3 notx1 and notx3 or x2 and not x3 –  user707895 May 27 '11 at 8:31
Actually, I have what each of you have, conjoined. @lewellen, and/or rewrite is the distributive property; also, you wrote the "rewrite rules" as implications: they are equivalences <--> (iff). I was also hoping to have the OP provide/show more work, ask specific questions, as noted in comments above. Hints are fine, as in your comments, even posting an answer pointing to equivalences OP can use, even using an "external" example to demonstrate how one can reduce to DNF form. But this was clearly marked "homework"; doing the problem for the OP is precisely what I told the OP we DO NOT do here. –  amWhy May 27 '11 at 17:41
@amWhy, I should have explained my notation, → is used as a mapping from one expression to another. I reserved ⇒ for the material conditional (implication). Edited my answer to correct two typos that resulted in the wrong DNF to be derived $(x_1 \land x_2 \land \lnot x_3 \land \lnot x_4)$. –  lewellen May 27 '11 at 20:53
@amWhy - I did indicate in the comments that I had edited my answer. Your answer pointed out that my solution was superfluous but you did not explain why it was wrong. I independently identified where my mistake was. That is why I did not give you credit. If you had pointed out specifically where the issue was, I would have most certainly given you credit and thanked you for your assistance. –  lewellen May 27 '11 at 21:34