0
$\begingroup$

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

OP's jpg image inserted directly

  • 0
    @user: I find the picture illegible. Please post in $\LaTeX$: to see how you can right click any example and select Show Source. Put what you find between dollar signs. Your comment before last also is very hard to understand.2011-05-27

2 Answers 2

3

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$

Truth Table

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.

0

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})$

  • 0
    no, I'm in Belarus2011-06-15