how can i prove that a k-map for n variables gives the most simplified representation of a Boolean function ?
(by simplified i mean we cannot eliminate another variable)
Proof that k-maps give the most minimized result
boolean-algebrakarnaugh map
Related Solutions
Just simply make a truth table that shows values of F for each of the combinations of A, B and C. Then transfer this information to the K-Map format table to do the minimization.
Lets say your five variables are A, B, C, D, E. To "draw" a 5 variable K-map, draw two K-Maps and imagine them stacked on top of one-another.
E=0
!C C
---------- ---------
AB\CD 00 01 11 10
!A { 00 0000 0001 0011 0010 > !B
!A { 01 0100 0101 0111 0110 } B
A < 11 1100 1101 1111 1110 } B
A < 10 1000 1001 1011 1010 > !B
vvvv ---------- vvvv
!D D !D
E=1
!C C
---------- ---------
AB\CD 00 01 11 10
!A { 00 0000 0001 0011 0010 > !B
!A { 01 0100 0101 0111 0110 } B
A < 11 1100 1101 1111 1110 } B
A < 10 1000 1001 1011 1010 > !B
vvvv ---------- vvvv
!D D !D
You see how every grid location (which maps to a min-term) differs from all its neighbors (including wrap-around edge-cases) by exactly one bit? That's more-or-less the whole point of a K-Map representation. Now in a 4-variable K-Map you can "circle" contiguous rectilinear shapes where the output is a "1" so long as their "area" is a power of two (i.e. 1, 2, 4, 8, or 16 terms) in order to achieve a "cover" of the K-map. I believe there are 2^16 possible covers of a 4-variable K-map (i.e. 2^(2^4)).
The only difference in the 5-variable case is "adjacent" also include analogous positions in the two 4-variable maps (sub-spaces), and there are more ways to ways to "circle" a number of cells that is a power of two; that is to say there are "three-dimensional" covers possible.
Hopefully it's clear that "the thing that is constant in a straight line" is what that line identifies, and that the intersections of "the things that are constant" is what makes a particular location a minterm. If you "circle" the upper-left four grid locations in both E=0 and E=1 maps, then E is a don't-care. If you circle the quadrant in just the E=0 map, then the term you are circling must have E in the intersection.
Related Topic
- How to implement a K-Map with negative feedback
- Electrical – simplify A’B’C’+A’B’C+A’BC’+A’BC+ABC into minimal 1st canonical form
- Electrical – Implementing boolean function using OR-NAND and NOR-OR
- Electrical – K-maps, do they completely simplify
- Electrical – Implementing 3 variable boolean function using mux 4 to 1 and inverter
- Electronic – Using don’t cares to reduce a function
Best Answer
How well a karnaugh map can simplify is downto the creator of the map with regards to drawing optimal loops.
How to determine whether what has been drawn (post further boolean reduction) is not really possible with k-maps on their own
One option is the use of Espresso Heuristic Logic reduction via a fantastic piece of software called: Logic friday ( http://www.sontrak.com/ ) Quite often this has reduced some logic of mine even further as I usually forget the odd one or two don't care states
The real question however is ... is this check on reduction for personal/professional use (in which case carry on) or homework? because if it is homework and logicFriday realises a further simplification, you had better be able to realise it via k-maps for the marks