Given the expression $E$, is there an assignment of boolean values ($true$ or $false$) that we can give to our variables such that this is evaluated to $true$?

$E = (¬x + z + ¬v) · (¬v + w) ·(¬z + w +v)$

Also, i would like to know how to associate it a graph $G$ to the boolean expression with those values that make the expression $true$.

  • $\begingroup$ Hint: I you let $w$ be true, then two of the factors are already taken care of. And $w$ isn't mentioned in the one that remains, so you have ample opportunity to make that true, too. $\endgroup$ – hmakholm left over Monica Nov 24 '13 at 5:58

We have: $E = (¬x + z + ¬v) · (¬v + w) ·(¬z + w +v)$

Let $\lnot v = T \iff v = F$.

Then the first two factors are true, and for the third factor, it will be true if you put $z = F \iff \lnot z = T$ and/or put $w = T$.

Only one of $\lnot z$ or $w$ needs to be true for the third factor to be true. So the truth of your statement $E$ depends on as few as only two truth-value assignments:

$$(v = F \land z = F)\;\text{ or }\;(v = F \land w = T).$$

In each case, the truth value assignments of the two remaining variables is irrelevant: the two remaining elements can be true or false without changing the truth of the statement.

If you'd like to see all the possible truth value assignments for the variables that make $E$ true, Wolfram Alpha helped to create the following truth-table:

enter image description here

In the right-most column, for each row that evaluates to true (T) (they're highlighted in an awful shade of pink!), simply read off the 9 possible truth-value assignments for the variables associated with that row.

| cite | improve this answer | |
  • $\begingroup$ We are now in your house! :-) +1 $\endgroup$ – Amzoti Nov 25 '13 at 0:27

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.