HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Do Karnaugh maps yield the simplest solution possible?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thekarnaughsimplestmapspossibleyieldsolution

Problem

I'm learning to use a Karnaugh map, but I'm not sure if I obtained the simplest expression possible. Have a look at this example:

Truth table (inputs are A B C; output is F):

A   B   C   |   F
0   0   0   |   1
0   0   1   |   0
0   1   0   |   1
1   0   0   |   0
0   1   1   |   1
1   0   1   |   1
1   1   0   |   0
1   1   1   |   1


The Karnaugh map looks like this:

AB
--
C|

    00  01  11  10
    --------------
0|  (1  1)  0   (1)
1|  0   (1  1)  (1)


And this yields $\bar{C}\bar{A}+CB+A\bar{B}$. Is there any simpler way of choosing the 1s from the map and getting a simpler result? Are Karnaugh maps guaranteed to always yield the simplest result possible?

Solution

Karnaugh maps do not always give the simplest expression possible, but they do always give the simplest "Sum of Products" expression possible (https://web.archive.org/web/20190920201621/https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.html).

Context

StackExchange Computer Science Q#32462, answer score: 5

Revisions (0)

No revisions yet.