1

I'm learning mathematical logic now and do not understand how to solve boolean equations.

For example, I have an equation like

$$(\bar{z}\implies y)\iff(\bar{z}\lor x )=x\oplus y$$

I'm able to translate it to simple form like:

$$[(\bar{z}\land \bar{y})\land(z\land \bar{x})]\lor[(z\lor y)\land(\bar{z}\lor x )]=(\bar{x}\land y) \lor (x\land\bar{y})$$

and simplify it further. But what should I do next? What is the point of 'solving a boolean equation'? Should I find all possible values of $x,y$ and $z$ that make this equation true? Or should I express $x$ in terms of $y$ and $z$? Or may be something else?

Rick Decker
  • 8,718
akashihi
  • 113
  • The first thing you should do is disambiguate your result by adding parentheses, which I've taken the liberty of doing. – Rick Decker Feb 08 '14 at 18:59
  • Sorry, haven't realised that parentheses are mandatory in that case. Thanks for the correction. – akashihi Feb 08 '14 at 22:09

1 Answers1

0

To solve an equation, whether it is a logical equivalence or not, you find the values of the variables which will make the two sides have the same value. Your proposed alternatives,

Should I find all possible values of $x,y$ and $z$ that make this equation true? Or should I express $x$ in terms of $y$ and $z$?

are both reasonable approaches. For your problem, you can discover, perhaps by using truth tables, that the solutions $(x, y, z)$ are $(T, F, T), (F, T, F), (F, F, T), (F, F, F)$. In many situations, that would be sufficient. You could continue, though, by finding a logical expression which is true if and only if the values of the variables are those I listed above. The usual disjunctive normal form decomposition in your case would give you $$ (x\land\bar{y}\land z)\lor(\bar{x}\land y\land\bar{z})\lor(\bar{x}\land\bar{y}\land z)\lor(\bar{x}\land\bar{y}\land\bar{z}) $$ which you could either leave in this form or simplify further to something like $$ (\bar{x}\land\bar{y})\lor(\bar{x}\land\bar{z})\lor(x\land\bar{y}\land z) $$

Rick Decker
  • 8,718
  • As is understood, i can find DNF for the left part of the equation, but the right side is already simple enough. Is there a way to "move" terms between left and right parts like in usual algebraic equation? – akashihi Feb 08 '14 at 22:16
  • Generally, no. For example, look at the "cancellation" of $b$ in the equality $(a\land b)=(c\land b)$. You might hope that the first equality implied $a=c$, but that's not correct. – Rick Decker Feb 09 '14 at 23:14