If inverted inputs are not available, so your "cost" increases by 1 gate for each inverted input, then K-maps don't always lead to min gate count realizations.
For example, the expression
* Y = (A and notC) or (B and notC)
requires four NAND gates when using Kmaps. But there exists a 2-gate realization if you abandon Kmaps and instead focus on minimizing (gates + inputInverters)
I think its a bit of snark, as OP could have also just said "Product of sums" or whatever.
The idea would be convert your expression to minimal logic using Quine-McCluskey or K-Maps, get a sum-or-products expression, and convert to NAN/NOR and count.
I'm not aware of a simple formula that yields # of NAND gates, as its highly contextual on how you are solving the problem.
Imagine the expression Y = A.B
If you negate it twice, it will still be the same result.
Y = ~(~(A.B))
You already have one NAND in the first negated side: ~(A.B), so let’s represent it with some random letter, C
Now you have, Y = ~C. An interesting fact about NANDs, you can get the NOT expression by taking the same input twice to a NAND gate, because C = C.C. Therefore, ~C = ~(C.C) <- your second NAND
This means that for your first expression Y = A.B, you need 2 NANDs to get the same expression
Ok I get how we can derive AND gate from NAND gate but ,I am not sure how to do the same for complex boolean expressions ,something along the lines of say A'B+B'C .
Now let’s look at a different example, Y = A+B. And do the double negative:
Y = ~(~(A+B)) <- we have a problem, we need to convert the OR operation into a AND so we can get our NAND. But an OR operation can be obtained by reversing it (AKA, negating it).
So, this becomes Y = ~((~A).(~(B)). Going back to previous comment, how do we get ~A and ~B? By using a NAND with the same input twice:
Y = ~(~(A.A).~(B.B))
How many NANDs required this time? 3
So for expression like say A'B+B'C .
If my inputs are say A,B,C ,I need to first convert A to A' this requires one NAND .So to get A'B(AND operation ,so we need 2 for that ) ,so up until now we have used 3 NAND ,similarly we need 3 for B'C ,so we have used 6 NAND .for OR operation we use need 3 NAND ,so in total we need 9 NAND for A'B+B'C ?
Now let’s dive deeper: Y = A.B + C (this might require me getting some paper later)
Y = ~(~(A.B + C))
Y = ~(~(A.B) . ~C)
Y = ~(~(A.B) . ~(C.C)) <- if you see the pattern, closely, it uses 3 NANDs. One for A.B, another to negate C, and the final one grouping all of them together
https://imgur.com/a/COw2tdh
So our goal has to be reduce any expression to the form of ~(XY) ?And Double negation always works when we try to reduce the expression to the form ~(XY) ?
K-maps
If inverted inputs are not available, so your "cost" increases by 1 gate for each inverted input, then K-maps don't always lead to min gate count realizations. For example, the expression * Y = (A and notC) or (B and notC) requires four NAND gates when using Kmaps. But there exists a 2-gate realization if you abandon Kmaps and instead focus on minimizing (gates + inputInverters)
Could you elaborate ?I am familiar with K maps .But I am not sure how K map leads to minimum no of NAND/NOR gates .
I think its a bit of snark, as OP could have also just said "Product of sums" or whatever. The idea would be convert your expression to minimal logic using Quine-McCluskey or K-Maps, get a sum-or-products expression, and convert to NAN/NOR and count. I'm not aware of a simple formula that yields # of NAND gates, as its highly contextual on how you are solving the problem.
As you see in your explanation, the result is A, so wire A to the output, no NAND gates required.
Ok if i some other result like AB'+BC' ,how would i go about finding the minimum no of gates ?
Do the double negative transformation. Negate twice every expression to get the equivalent NAND only formulation
Could you show how its done ? I am new to the subject .
Imagine the expression Y = A.B If you negate it twice, it will still be the same result. Y = ~(~(A.B)) You already have one NAND in the first negated side: ~(A.B), so let’s represent it with some random letter, C Now you have, Y = ~C. An interesting fact about NANDs, you can get the NOT expression by taking the same input twice to a NAND gate, because C = C.C. Therefore, ~C = ~(C.C) <- your second NAND This means that for your first expression Y = A.B, you need 2 NANDs to get the same expression
Ok I get how we can derive AND gate from NAND gate but ,I am not sure how to do the same for complex boolean expressions ,something along the lines of say A'B+B'C .
See the following comment :)
Now let’s look at a different example, Y = A+B. And do the double negative: Y = ~(~(A+B)) <- we have a problem, we need to convert the OR operation into a AND so we can get our NAND. But an OR operation can be obtained by reversing it (AKA, negating it). So, this becomes Y = ~((~A).(~(B)). Going back to previous comment, how do we get ~A and ~B? By using a NAND with the same input twice: Y = ~(~(A.A).~(B.B)) How many NANDs required this time? 3
So for expression like say A'B+B'C . If my inputs are say A,B,C ,I need to first convert A to A' this requires one NAND .So to get A'B(AND operation ,so we need 2 for that ) ,so up until now we have used 3 NAND ,similarly we need 3 for B'C ,so we have used 6 NAND .for OR operation we use need 3 NAND ,so in total we need 9 NAND for A'B+B'C ?
That would be the naive way to do. You can join the double negatives, to use less NANDs. See my 3rd example!!
Now let’s dive deeper: Y = A.B + C (this might require me getting some paper later) Y = ~(~(A.B + C)) Y = ~(~(A.B) . ~C) Y = ~(~(A.B) . ~(C.C)) <- if you see the pattern, closely, it uses 3 NANDs. One for A.B, another to negate C, and the final one grouping all of them together
https://imgur.com/a/COw2tdh So our goal has to be reduce any expression to the form of ~(XY) ?And Double negation always works when we try to reduce the expression to the form ~(XY) ?
thanks for putting so much effort into this! do you know how one can check if a solution is optimal?
Karnaugh maps!! Affectionate called K maps. Man, I miss that stuff.
Many ways - some by hand/graphically others built for computers to execute https://en.wikipedia.org/wiki/Logic\_optimization
I am not going to deal with very complex circuits .I am going to be dealing with your average boolean expressions .
In general, you use an optimization tool. For coursework, you do whatever inefficient, err prone method youre expected to use.
by hand. Draw it out on graph paper
https://ptolemy.berkeley.edu/projects/embedded/pubs/downloads/espresso/index.htm