Thanks.Boolean Algebra Reduction - Is There an Algorithm for It?

[Algebra2100]

Hi Everybody,

I have a general question:

Is there any Algorithm that can do Boolean Algebric Reduction ?

Appreciate your help

 

[Defennder]

Karnaugh maps?

 

[Algebra2100]

Can you give me a reference to that algorithm so that i can read about it...Do you have any Visual Basic source or can post link to that algorithm

Can this algorithm for exampe reduce this AUBUCUA to AUBUC As AUA=A

Appreciate your feedback

 

[Algebra2100]

Hi Defennder

I think ur right. I just found about it. But what if you have more than 6 variables ..What if you have a Fault Tree and you want to do Boolean Algebra reduction and you have 30 variables (some of them are repeated)

Let us say you have this equation after solving a Fault Tree and you want to do Boolean reduction and reduce it
(A U B U C U D U F U A U G U H U I U G U K U L U M U B*I U A*F U F*G*H)

Note : A, B, F are repeated variables

Are you still going to use Karnaugh maps? or there is other algorithm

 

[Mastermind_14]

Hi Defennder

I think ur right. I just found about it. But what if you have more than 6 variables ..What if you have a Fault Tree and you want to do Boolean Algebra reduction and you have 30 variables (some of them are repeated)

Let us say you have this equation after solving a Fault Tree and you want to do Boolean reduction and reduce it
(A U B U C U D U F U A U G U H U I U G U K U L U M U B*I U A*F U F*G*H)

Note : A, B, F are repeated variables

Are you still going to use Karnaugh maps? or there is other algorithm

>Karnaugh Maps are not that useful in Boolean logic simplification for more then 8 variables because they are very difficult to visualize and it is even tougher to develop some software to do this job. This is because with each pair of new variables added the amount of complexity is doubled and a new dimension* is added to our problem and for 30 variables we need about 15 dimensions to visualize and program. and the process of simplification starts after you have done the visualization. This is the very same reason why the maximum numbers of Variables that any commercial "Boolean Logic Simplifier Software" can handle is 10.

> with K-Maps there is no problem with repetition of variables in the statement and that is the biggest advantage of it.

>If you have written 4 variables even a thousand times in some boolean expression then too Kmaps will handle it easily with the complexity of just 4 variables.


*dimension is a term i used during my research on developing the algorithm and software of a 8-variable K-Map simplifier software.It is the the dimension of array used to store all information of different sub blocks of K-Maps .So it goes like this

variables dimension
1-2 1
3-4 2
5-6 3
7-8 4
8-10 5

 

[Algebra2100]

Hi Mastermind_14

Thanks for your reply. I still have the same question valid. I am building Fault Tree application and i this fault tree the user is allowed to have repeated basic events. The fault tree can be small and can be big. What i wanted to do is to find an Algorithm that can do Boolean Algebra simplification. Until now i didn't find any algorithm that can do that for me. Any suggestion ?

 

[Mastermind_14]

Hi Mastermind_14

Thanks for your reply. I still have the same question valid. I am building Fault Tree application and i this fault tree the user is allowed to have repeated basic events. The fault tree can be small and can be big. What i wanted to do is to find an Algorithm that can do Boolean Algebra simplification. Until now i didn't find any algorithm that can do that for me. Any suggestion ?

Well As far as I know Karnaugh Map simplification technique is the best method for simplifying boolean Algebra and if you are looking for some new algorithm then i guess you have to develop one on your own. So the alternative solution is that you fix the maximum number of variables that occur in your problem and then use some K-map simplifier (I guess Matlab can help here).

I hope my post helps you reach some decision.

 

[Algebra2100]

Hi Mastermind_14,

What is the name of the Matlab toolbox that can do simplification of boolean Algebra ? Is there is Max. limits for the number of variables ?

Well As far as I know Karnaugh Map simplification technique is the best method for simplifying boolean Algebra and if you are looking for some new algorithm then i guess you have to develop one on your own. So the alternative solution is that you fix the maximum number of variables that occur in your problem and then use some K-map simplifier (I guess Matlab can help here).

I hope my post helps you reach some decision.

 

[Mastermind_14]

I haven't worked a lot on MATLAB (strange for an engineering student isn't it) but I can provide you with a link to a free downloadable K-Map toolbox that can handle 4 variables at max.

http://www.mathworks.com/matlabcentral/fileexchange/6853

If you want more help on this then post a thread about "Matlab and K-Maps" in
"Physics Forums > Other Sciences > Computer Science" or where eever you find it will be best answered.

I hope this solution helps you.

 

[Algebra2100]

Hi Mastermind_14,

Thank you for your reply. Your link is great but yet I can’t use this algorithm to make simplification of Boolean algebra related to Fault Tree. As you may know, you may have 50 basic events or so. So, this algorithm is limited. I did some literature review last week in which I found some researcher talking about Recursive Algorithm. However, I still can’t find code or algorithm that shows how this algorithm works. I wonder if you have any idea about this algorithm or any algorithm other than K-Map cause its really limited and can’t be used to solve fault tree

I haven't worked a lot on MATLAB (strange for an engineering student isn't it) but I can provide you with a link to a free downloadable K-Map toolbox that can handle 4 variables at max.

http://www.mathworks.com/matlabcentral/fileexchange/6853

If you want more help on this then post a thread about "Matlab and K-Maps" in
"Physics Forums > Other Sciences > Computer Science" or where eever you find it will be best answered.

I hope this solution helps you.

 

[Algebra2100]

Did anybody here use Binary Decision Diagram (BDD) or can guide me where to read about it ? I have some papers in using it, but i really can't understand any !

 

[Mastermind_14]

Hi Mastermind_14,

I did some literature review last week in which I found some researcher talking about Recursive Algorithm.

First of all I am sorry for late reply (because of my ongoing exams). Now from what you have mentioned above,it is not clear what kind of "recursive algorithm" he is talking about. Recursive algorithms are used even in Karnaugh Maps (I myself used it) so I cannot comment on the "recursive algorithm" till i get some information on it. Can you please provide me with a link to the place where you learned about it?