CODEWITHSUNDEEP
algorithmmathtime-complexityclassificationboolean-expression
sb15
sb15

Reputation: 313

Algorithm to simplify boolean expressions

I want to simplify a very large boolean function of the form :

f(a1,a2,....,an)= (a1+a2+a5).(a2+a7+a11+a23+a34)......(a1+a3+an).

'.' means OR

'+' means AND

there may be 100 such terms ('.' with each other ) value of n may go upto 30.

Is there any feasible algorithm to simplify this?

NOTE: this is not a lab assignment, a small part of my project on rule generation by rough set where f is dissimilarity function.

Upvotes: 4

Views: 2745

Answers (3)

user1952500
user1952500

Reputation: 6781

The well-known ways to do this are:

The second way is most commonly used on a computer. It's tabular and straight-forward. The first way is the best way to do by hand and is more fun, but you can't use it for anything more than 4 variables reliably.

Upvotes: 4

Ian Mercer
Ian Mercer

Reputation: 39307

If you represent the a values as an int or long where a1 has value 2, a2 has value 4, a3 has value 8 etc.:

int a = (a1 ? 2^1 : 0) + (a2 ? 2^2 : 0) + (a3 ? 2^3 : 0) + ...;

(wasting a bit to keep it simple and ignoring the fact that you'd be better off with an a0 = 1)

And you do the same for all of the terms:

long[] terms = ...;
terms[0] = 2^0 + 2^3 + 2^5           // a1+a2+a5
terms[1] = 2^2 + 2^7 + 2^23 + 2^34   // (a2+a7+a11+a23+a34)

Then you can find the result:

foreach(var term in terms)
{
   if (a & term == term) return true;
}
return false;

BUT this only works well for up to n=64. Above that it's messy.

Upvotes: 0

Chris
Chris

Reputation: 959

The typical method is to use boolean algebra to reduce the statement to its simplest form.

If, for example, you have something like:

(A AND B) OR (A AND C)

you can convert it to a more simple form:

A AND (B OR C)

Upvotes: 0

Related Questions