# Minimizing number of logic gates

For a boolean function, after drawing K-map we got that function in the form of the sum of products (minimal representation) but problem is that when we implement that minimal representation we use only "AND" and "OR" gates. Is this gate implementation also minimal regarding the number of used logic gates? In other words, for a given minimal function in the sum of products form can we further decrease the number of logic gates using NOR, XOR, etc. instead of ANDs and ORs.

• Sure. An adder implemented with XOR uses less gates than AND and OR. It's likely to be just as many transistors, since the XOR is correspondingly more complex. May 10, 2022 at 20:04
• Minimal SOP is not necessarily minimal from the gates perspective. Even with the same type of gates. For example AB + AC will take 3 gates to implement, while equivalent A(B+C) - only two. May 10, 2022 at 20:10
• And just to stir the "minimal" pot, here's Konrad Zuse's full adder. Note that it only uses two "logic gates." (Those "gates" were the fundamental building block unit.)
– jonk
May 10, 2022 at 20:13
• Thank you all, well, are there certain techniques for reducing, or do we have to look for them? May 10, 2022 at 20:18
• Reducing the boolean function is a good start. Then you might want to compare the SOP vs POS forms. From there I am not aware of any manual formal techniques, just intuition based. Surely, computer tools exist, but I believe these will be heuristic-based for any non-trivial system. May 10, 2022 at 20:22

For a boolean function, after drawing K-map we got that function in the form of the sum of products (minimal representation) but problem is that when we implement that minimal representation we use only "AND" and "OR" gates.

The old PAL/GAL devices were based on AND/OR logic grids, which directly maps SOP.

Is this gate implementation also minimal regarding the number of used logic gates?

No, not at all. For example, $$\Z=A B+B C\$$ would have the following k-map and implementation using SOP AND/OR logic:

But could just as well be implemented as POS OR/AND logic as $$\Z=\left(A+C\right)B\$$:

In other words, for a given minimal function in the sum of products form can we further decrease the number of logic gates using NOR, XOR, etc. instead of ANDs and ORs.

The above shows that it can be reduced even without including NOR, XOR, etc.

But, in general, logic can often also be further reduced using additional options such as XOR, NOR, NAND, etc.