0

Does using Karnaugh Map produce same result as using principles to simplify boolean expression?

Donny Avaris
  • 67
  • Karnaugh maps are "a grid-like representation of a truth table." Successful use of them to simplify boolean expressions depends on insight and "visual inspection". You might consider them as guides to using "principles" (boolean identities) to achieve simplification. – hardmath Oct 24 '16 at 11:36
  • I see.. No wonder I recognize something between them two – Donny Avaris Oct 24 '16 at 11:39
  • It seems a bit strong to say they "produce same result[s]". We can say the map technique is consistent with the application of boolean identities. – hardmath Oct 24 '16 at 11:44

1 Answers1

1

It depends on what the goal is as far as 'simplifying' goes. The Karnaugh map will produce either a statement in DNF (if you focus on the 1's or True's), or CNF (if you focus on the 0's or False's), and often that is the goal of the simplification. But sometimes this statement can be further 'simplified' (e.g in terms of the number of connectives, or length of statement) using algebraic principles. Also, if you have connectives like $\rightarrow$ or XOR, you can sometimes get a much simpler statement than that you get with the Karnaugh map. For example, see what you get from the Karnaugh map if you consider the statement $P \: XOR \: Q \: XOR \: R$!

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • Here is an example. Consider $(P \wedge (Q \vee R)) \vee \neg (P \vee (Q \wedge R))$. If you put this on a Karnaugh map and find an expression for it in DNF or CNF, then that expression will have more connectives, amd be longer than the original statement, even after you do some further DeMorgan's. – Bram28 Oct 24 '16 at 11:14
  • Ah I see.... By the way, is logic gates circuit differs from each person? – Donny Avaris Oct 24 '16 at 11:20
  • @DonnyAvaris What do you mean by logic gate circuits differing? – OFRBG Oct 24 '16 at 11:22
  • If the goal is to produce a logic circuit, then the goal is typically to put the statement into DNF or CNF, since that mostly reduces the number of layers in a logic circuit. But even if the goal is to put a statement into CNF or DNF, different people can get different answers, and thus different logic gates. You can take that very example I gave in my earlier comment and create a Karnaugh map for it, and you will see that there are two ways to get 3 pairs of 1's. – Bram28 Oct 24 '16 at 11:27
  • i mean the way I create a logic gates, let's say different from my friends – Donny Avaris Oct 24 '16 at 11:30
  • Yes. I figured that's what you meant. So see my previous comment: the answer is that your friend may get a different, but equally correct, logic circuit. – Bram28 Oct 24 '16 at 11:40