How to minimise a repetitive boolean expression

Question

Let's say I have the following truth table for a logic gate called 'foo'.

a | b | out |
0 | 0 |  1  |
0 | 1 |  0  |
1 | 0 |  0  |
1 | 1 |  1  |

This resolves to the following boolean expression:

foo = (-a ^ -b) v (a ^ b)

Let's also say I have the following circuit diagram for a logic gate called 'bar'.

          -----        -----
a -------|     |      |     |
         | foo |------|     |
b -------|     |      | foo |------ out
          -----       |     |
c --------------------|     |
                       -----

This resolves to the following boolean expression:

bar = (-((-a ^ -b) v (a ^ b)) ^ -c) v (((-a ^ -b) v (a ^ b)) ^ c)

To find this result, I substituted the boolean expression for 'foo' into itself as 'a'.

Is there a simple, algorithmic way to simplify this boolean expression? It obviously has a lot of repetition and I'd like to get a minimal boolean expression, preferably in CNF or DNF.

possible duplicate of [Any good boolean expression simplifiers out there?](http://stackoverflow.com/questions/14902141/any-good-boolean-expression-simplifiers-out-there) — Leo, Sep 19 '14 at 21:52
But I'm more interested in how it's done, rather than using a tool to do it for me. — Chris, Sep 19 '14 at 21:55
[Here](http://www.allaboutcircuits.com/vol_4/chpt_7/5.html) is some introductory material to get you started. — 500 - Internal Server Error, Sep 19 '14 at 22:10

score 2 · Accepted Answer · answered Mar 15 '16 at 12:48

Expressing the final output as a g function:

f = foo(a,b) = ¬a·¬b + a·b
g = foo(f,c) = ¬f·¬c + f·c
g = foo(foo(a,b),c) = ¬(¬a·¬b + a·b)·¬c + (¬a·¬b + a·b)·c

Assuming the ⋅ operator represents binary conjunction (∧), the + binary disjunction (∨) and the - or the ¬ unary negation, I would apply the laws of Boolean algebra this way:

     ¬(¬a·¬b + a·b)        ·¬c + (¬a·¬b + a·b)·c
     ¬(¬a·¬b + a·b)        ·¬c + ¬a·¬b·c + a·b·c //distributivity of · over +
    (¬(¬a·¬b)·¬(a·b))      ·¬c + ¬a·¬b·c + a·b·c //De Morgan's law
 ((¬¬a + ¬¬b)·(¬a + ¬b))   ·¬c + ¬a·¬b·c + a·b·c //De Morgan's law
     ((a + b)·(¬a + ¬b))   ·¬c + ¬a·¬b·c + a·b·c //double negation law
(a·¬a + a·¬b + b·¬a + b·¬b)·¬c + ¬a·¬b·c + a·b·c //distributivity of · over +
   (0 + a·¬b + b·¬a + 0)   ·¬c + ¬a·¬b·c + a·b·c //complementation: x·¬x = 0
       (a·¬b + b·¬a)       ·¬c + ¬a·¬b·c + a·b·c //identity for +: 0 + x = x
             a·¬b·¬c + b·¬a·¬c + ¬a·¬b·c + a·b·c //distributivity of · over +

             a·¬b·¬c + ¬a·b·¬c + ¬a·¬b·c + a·b·c

The final line is the original expression's minimal DNF. You can also transform it to it's minimal CNF this way:

a·¬b·¬c  + ¬a·b·¬c + ¬a·¬b·c  +  a·b·c
a·¬b·¬c  +  a·b·c  + ¬a·b·¬c  + ¬a·¬b·c          //just permuting
a·(¬b·¬c + b·c)    + ¬a·(b·¬c + ¬b·c)            //distributivity of · over +

//distributivity of + over ·:
(a + ¬a)·(a + (b·¬c + ¬b·c))·((¬b·¬c + b·c) + ¬a)·(¬b·¬c + b·c + b·¬c + ¬b·c)

//complementation: (a + ¬a) = 1
     (1)·(a + (b·¬c + ¬b·c))·((¬b·¬c + b·c) + ¬a)·((¬b·¬c + b·c) + (b·¬c + ¬b·c))

//identity for ·: 1·x = x
         (a + (b·¬c + ¬b·c))·((¬b·¬c + b·c) + ¬a)·(¬b·¬c + b·c + b·¬c + ¬b·c)

//(¬b·¬c + b·c + b·¬c + ¬b·c) = 1 i.e. sum of all b, c combinations; to be sure:
(a + (b·¬c + ¬b·c))·((¬b·¬c + b·c) + ¬a)·(¬b·(¬c + c) + b·(¬c + c)) //distribut.
(a + (b·¬c + ¬b·c))·((¬b·¬c + b·c) + ¬a)·(¬b·(1) + b·(1))      //complementation
(a + (b·¬c + ¬b·c))·((¬b·¬c + b·c) + ¬a)·(¬b + b)              //identity for ·
(a + (b·¬c + ¬b·c))·((¬b·¬c + b·c) + ¬a)·(1)                   //complementation

(a + (b·¬c + ¬b·c)                      )·((¬b·¬c + b·c) + ¬a) //identity for ·
(a + (b + ¬b)·(b + c)·(¬c + ¬b)·(¬c + c))·((¬b·¬c + b·c) + ¬a) //distributivity
(a +      (1)·(b + c)·(¬c + ¬b)·(1)     )·((¬b·¬c + b·c) + ¬a) //complementation
(a +          (b + c)·(¬c + ¬b)         )·((¬b·¬c + b·c) + ¬a) //identity for ·
              ((a + b + c)·(a + ¬c + ¬b))·((¬b·¬c + b·c) + ¬a) //distributivity
//distribut.: ((a + b + c)·(a + ¬c + ¬b))·((¬b+b)·(¬b + c)·(¬c + b)·(¬c+c) + ¬a)
//complem.:   ((a + b + c)·(a + ¬c + ¬b))·(   (1)·(¬b + c)·(¬c + b)·(1)    + ¬a)
//identity:   ((a + b + c)·(a + ¬c + ¬b))·(       (¬b + c)·(¬c + b)        + ¬a)
//distribut.: ((a + b + c)·(a + ¬c + ¬b))·((¬b + c + ¬a)·(¬c + b + ¬a))

                (a + b + c)·(a + ¬b + ¬c)·(¬a + ¬b + c)·(¬a + b + ¬c)

Your function can be simplified to either one of these expressions:

g = a·¬b·¬c + ¬a·b·¬c + ¬a·¬b·c + a·b·c //minimal DNF
g = (a + b + c)·(a + ¬b + ¬c)·(¬a + ¬b + c)·(¬a + b + ¬c) //minimal CNF

score 1 · Answer 2 · answered Oct 03 '14 at 05:59

1

Using De Morgan's laws, you can simplify it further to CNF or DNF.

answered Oct 03 '14 at 05:59

user2351984

11
1

How to minimise a repetitive boolean expression

2 Answers2