how to solve a system of boolean equations

Hi, i would like to know how to solve a system of boolean equations in mathlab. I found examples on how to reduce equations, but i don't know how to solve them

example:

!ab + a!b = 0  
!a!bc + c = 1  
a!c + a = 0

for this, the solution is a=0, b=0, c=1.

EDIT:

This is just an example, the real problem i will want to solve will be a system of 100 equations with 64 variables

note:

ab  means a and b
a+b means a or b
!a  means not a

I tried this, but it doesn't show the solution:

solve({(not a and b) or (a and (not b)) = false, not a and not b and c or c = true, a and not c or a or b = false}, logic)

result is:

piecewise([((a and not b) = false or not a and b) and (c = true or not a and not b and c) and (a or b = false or a and not c), C_], [(a and not b) <> false and (a or not b) or c <> true and (a or b or not c) or not a and b <> false and (not a or c), {}])

[Roger Stafford]

Each of the equations of the form "expression = 1" can be replaced by just "expression" and each of the form "expression = 0" can be replaced by the negation of that expression. The collection of equations could then be replaced by the 'and' of all of these. What you are really asking for, therefore, is either the set of combinations of the variables for which this combined expression is true, or if there are a great many such combinations, perhaps a greatly simplified expression equivalent to it.

Excepting Matt's "brute force" method, which would probably become impractical for as many as 64 variables, Matlab is probably not really suited for this latter kind of problem. There is not to my knowledge a version of the Symbolic Toolbox function 'simplify' which could be used to simplify logical expressions in an effective manner. Designing it would be a major project I suspect.

[Roger Stafford]

" solve({(not a and b) or (a and (not b)) .... " I believe I warned you.

[Walter Roberson]

Material relevant to simplifying logical expressions: http://staff.science.uva.nl/~jesshope/web-site-08123/Downloads/minimising-boolean-eqns.pdf

[Matt J]

Note that equations with zeros on the RHS can be broken up into additional, simpler equations. E.g.,

 !ab + a!b = 0

leads to

!ab=0
a!b=0

or equivalently, using DeMorgan's Law

a + !b=1
!a +  b=1

So, really, you should never have a 0 on the rhs of your equations.

Answer 1

[Alan Weiss]

I am not sure, but perhaps you can reformulate your problem as a binary integer programming problem, and then use the Optimization Toolbox function bintprog to solve the problem.

For suggestions on turning boolean equations into binary integer programming constraints, see this link (there may be better links, it is just the first one I found).

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

Answer 2

[Matt J]

A brute force approach would be to enumerate all possible combinations.

combs=dec2bin(0:7,3)-'0';  %All combinations

a=combs(:,1); b=combs(:,2); c=combs(:,3); 

idx = ((~a.*b +~b.*a) == 0 ) & ((~a.*~b)==1) & ((a.*~b.*c +c)==1);

result = combs(idx,:)

[Roger Stafford]

When dealing with booleans in this extensive manner it would be a lot safer in my opinion to avoid the use of arithmetic operators altogether and use logicals exclusively. For example, if a and b are both true in an 'or' operation, then a+b==1 turns out to be false, whereas a|b would be correct.

[Matt J]

But maybe '+' is supposed to mean actual addition in this context, Roger, rather than logical or. Only the OP knows.

[Andrei]

i updated the question

[Matt J]

If you can perform reductions on the individual equations, you might be able to pre-solve for enough variables to the point where brute force enumeration becomes possible again.

In your example, for instance, the second equation alone readily reduces to c=1,

 !a!bc + c=1
 (!a!b + 1)c=1
  c=1

and similarly the 3rd equation readily reduces to a=0.