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.
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