Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How can I solve a set of boolean equationst to get a,b,c and d.

Like:

w = a*b*c*d
x = !a*b*d
y = !b*a*d + !c*a*d + !a*b*c + !d*!a*b
z = a*c

w, x, y, z are known.

This example above is very simple to solve via substituation. But what is with complex system of equations?

I have read this question: how to solve system of linear equations of XOR operation? but I have not xor - I have got not, and and or.

share|improve this question

1 Answer 1

It's not true that this example is simple to solve via substitution; in fact it's impossible to solve these equations for $a$, $b$, $c$ and $d$. This is because $15$ different assignments of truth values to $a$ through $d$ lead to $w$ being false (namely all except the one where $a$ through $d$ are all true), and these $15$ assignments cannot be distinguished by the $8$ different assignments to $x$, $y$ and $z$, so necessarily there are assignments to $w$ through $z$ that correspond to more than one assignment to $a$ through $d$. It follows that there's no unique solution of these equations for $a$ through $d$.

As Ilmari explained in the thread you linked to, in $\mathbb F_2$ addition corresponds to XOR and multiplication corresponds to AND. You can express NOT and OR in terms of XOR and AND like this:

$$ \begin{align} \neg a & = 1\oplus a\;,\\ a+b & = \neg((\neg a)\cdot(\neg b))\;. \end{align} $$

The resulting equations over $\mathbb F_2$ won't be linear if variables are connected with AND, since that corresponds to multiplying them. As over any field, non-linear equations over $\mathbb F_2$ may or may not have a unique solution; in this case they don't.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.