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.

I am doing boolean simplification using Quine-McCluskey which works well.

However, I now need to perform the simplification with some known term combinations.

For example, I want to simplify:

(A+B)C

If I know that:

A+B == true

then this simplifies to:

C

Or if I know that:

BC == false

then it simplifies to

AC

How can I implement this in a fully general way?

share
1  
What do you mean by "implement" ? –  Skydreamer Feb 24 '12 at 22:16
1  
Are you asking about a specific situation or about an algorithm to partially evaluate Boolean expression efficiently? –  Asaf Karagila Feb 24 '12 at 22:17
    
Sorry for not being clear - I am asking for an algorithm that can simplify boolean expressions given a list of terms that are already known. It needs to cope with situations more complex than the examples given in the question. –  Chris Feb 24 '12 at 22:19
    
I have now solved this problem. See below for my answer. –  Chris Feb 28 '12 at 15:51

2 Answers 2

  • "and" and "or" are distributive over each other so you can first expand this and see if any pattern can be improved.
  • You can apply the simple rules such as A AND B = A if B is true.
  • Given they are distributive, you can also factor out propositions : A AND B OR A AND C = A AND(B OR C)
  • There is no perfect algorithm for this kind of problem, you have to change the expressions different ways and see what can be done to improve them.

Hope it helps.

share
    
Thank you for your comment, however I have discovered that there is a solution that fits well with the Quine-McCluskey algorithm. See my answer for details. –  Chris Feb 28 '12 at 15:51

I've discovered a nice solution to this problem.

Quine-McCluskey is able to handle a truth-table where some of the terms are marked as "don't care", which means that the term will never occur, so the minimized expression can return true or false.

For example:

A B result
0 0 0
0 1 don't care
1 0 don't care
1 1 con't care

It can clearly be seen that the above function can be minimized to just return 'false', as that is the only result that we care about.

So to deal with known terms, all that has to be done is set the result to "don't care" for any terms in the truth table where a known term evaluates to false. The Quine-McCluskey algorithm then generates the minimized function taking the known terms into account.

For example, if we have a function of A and B, and we know that A == false, then any line on the truth-table where A is true can be marked as "don't care" because we know it will never occur.

share

This site is currently not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .