3

Consider this map of (A ∧ D) ∨ (B ∧ D) ∨ (A ∧ ¬B ∧ C ∧ D):

Enter image description here

The map is grouped into two sections, both of four squares. Thus producing the simplified expression of (B ∧ D) ∨ (A ∧ D) as shown below.

Enter image description here

This is in following with the rule:

"Groups must contain 1, 2, 4, 8, or in general 2^n cells"

However, if I were to group in such a way that groups contain six cells (not following the 2^n rule):

Enter image description here

This would produce the simplified expression of:

(A ∨ B) ∧ D

I have run this trial a few more times. Even splitting Karnaugh maps where I split possible groups of eight into six and four. I have come to the conclusion that when splitting by six, or any value not of 2^n, the Boolean value between brackets in the expression is ∧ (AND) whereas when using groups of 2^n the splitting boolean value is ∨ (OR).

Thus as groups not in sizes of 2^n produce AND divisions (between brackets), does this mean brackets in boolean expressions cannot be separated by an AND?

And by proxy, is this why Karnaugh maps must be grouped into groups of 2n squares?

Note

Online tools simplify exclusively with OR dividers also: as shown

Enter image description here

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Montresor
  • 806
  • 6
  • 22
  • "Why can't brackets in a Boolean expression be separated by a AND?" who told you this, and in what context? – njzk2 Nov 30 '21 at 19:14
  • 1
    No one told me this. I was originally trying to answer why i could not have groups larger than 2n. If a group is larger than 2n it always causes brackets to be separated by an AND. I have presumed (and such is my question) that this means brackets in simplified boolean expressions cannot be separated by an AND – Montresor Nov 30 '21 at 19:18
  • 1
    I suppose the method is using some simplification to get more easily to a result. But all ands can be turned into ors if needed using De Morgan's: this can be written `not(not D ∨ (not A ∧ not B))` (those are 8 + 2, with OR between them) – njzk2 Nov 30 '21 at 19:25
  • 1
    Interesting hypothesis. I will test further. Indeed i have been ignorant to a certain level of simplification within this process. – Montresor Nov 30 '21 at 19:31
  • Sadly testing has revealed this hypothesis is not linear in all circumstances – Montresor Jan 24 '22 at 13:14
  • what do you mean "not linear"? – njzk2 Jan 25 '22 at 22:14
  • sorry - it is not consistent – Montresor Jan 27 '22 at 19:48
  • I'm fairly confident that the truth table of `not(not D ∨ (not A ∧ not B))` is the same as that of `(B ∧ D) ∨ (A ∧ D)`. If there is a particular set of values for A, B, C, and D that results in a different output, I'd be curious – njzk2 Jan 27 '22 at 22:16
  • It does not work within the karnaugh map – Montresor Feb 03 '22 at 10:47
  • it does. Just invert your table, and it will appears to you. but in any case, Karnaugh is just a method, it's not the only one, and it's not perfect at simplifying boolean expressions. You should be able to build the truth table of both expressions, and simply see that they are exactly equal. Then, learn about https://en.wikipedia.org/wiki/De_Morgan's_laws which will help you understand why – njzk2 Feb 03 '22 at 20:17
  • Thank you i understand that karnaugh is just a method and your information you have provided is very helpful for understanding it and its base theorems better. Thank you very much. It is very interesting what you have said on the matter – Montresor Feb 03 '22 at 21:24
  • 1
    @njzk2 and Montresor not(not D ∨ (not A ∧ not B)) IS the same as that of (B ∧ D) ∨ (A ∧ D). This can be shown as follows: ~(~D + (~A . ~B)) = D . (A + B) per DeMorgan's Theorem, and D . (B + A) = (B . D) + (A . D) per the distributive law. – Andrew Feb 21 '22 at 00:51
  • @Andrew so I keep saying :) – njzk2 Feb 21 '22 at 21:44

1 Answers1

2

(B ∧ D) ∨ (A ∧ D) is the correct "sum of products" expression for this Karnaugh map, and (A ∨ B) ∧ D is an equivalent expression (per the "OR distributive law"), but it is no longer in a "sum of products" form.

You did (instead of using the "OR distributive law"): instead of noting (from the top of the Karnaugh map) that the B value does not change for the first 2x2 block and that the A value does not change for the second 2x2 block, you noted further that these two columns of size 2 overlap forming three columns defined by (A ∨ B).

That is fine, but it does not give the "sum of products" (groups of AND'd variables OR'd together), which is what the 2^n rule relates to. Instead you by happenstance ended up with the actual "product of sums" (groups of OR'd variables AND'd together).

The "formal", "graphical", "traditional", "easy", etc. way (which also has a 2^n rule, but for 0s instead of 1s) of getting to your final result is to instead of 1s, circle the 0s, noting again what variable values on the top and/or on the right side do not change, but this time not these values. In your example, the four 0s at the top and the four 0s at the bottom result in the D "sum" (note this "circle" spans from the top to the bottom forming a "logical" circle so-to-speak). The remaining two 0s are combined with the 0 above them and the 0 below them, resulting in the (A ∨ B) "sum" (the idea is to cover all 0s while also selecting the biggest 2^n blocks even if they overlap). (A ∨ B) ∧ D is the "product" of these two "sums". Check out: Minterm vs Maxterm Solution.

The method is "perfect" (as long as the "circles" are as big as possible and nothing is missed). If the "circles" are not as big as possible (but nothing is missed), the result will still be logically correct, but it will use more gates than the minimum.

Andrew
  • 1
  • 4
  • 19
  • That is very interesting about the different laws and techniques used, could you hypothesise or do you know any reasons for why one technique would be used instead of another? – Montresor Feb 20 '22 at 12:59
  • 1
    @Montresor It could depend on the chips being used, the design of the software being written, or simply personal preference. Sometimes both methods are tried, and the cheaper (usually the one with less gates) circuit is used, or the "better" (usually the one with less lines) code is used. – Andrew Feb 20 '22 at 23:51
  • Very interesting i would presume that 'Sum of Products' is a more viable cross board option and thus is the default for general systems and solvers online and within CS exam boards – Montresor Feb 21 '22 at 13:03
  • 1
    for exams, you should know both; also: go over kmaps and race conditions – Andrew Feb 21 '22 at 14:14
  • 1
    Note: The original post of (A ∧ D) ∨ (B ∧ D) ∨ (A ∧ ¬B ∧ C ∧ D) = (A ∧ D) ∨ (B ∧ D); Proof: (A ∧ D) ∨ (A ∧ ¬B ∧ C ∧ D) ∨ (B ∧ D) (associative property) = (A ∧ D) ∨ (A ∧ D ∧ ¬B ∧ C) ∨ (B ∧ D) (associative property) = (X) ∨ (X ∧ ¬B ∧ C) ∨ (B ∧ D) (substitutuion) = (X) ∨ (X ∧ Y) ∨ (B ∧ D) (substitutuion) = (X) ∨ (X ∧ Y) ∨ (B ∧ D) = (X) ∨ (B ∧ D) (OR absorption law) = (A ∧ D) ∨ (B ∧ D) (substitutuion); also can be seen from the Karnaugh map since the (A ∧ ¬B ∧ C ∧ D) block is already contained in the (A ∧ D) block. – Andrew Feb 21 '22 at 14:34
  • 1
    Here is a good link (explains "OR absorption law", for example): *[Laws of Boolean Algebra][3]* [3] https://www.electronics-tutorials.ws/boolean/bool_6.html. – Andrew Feb 21 '22 at 14:37
  • I know that Thank You comments are looked upon with relative distaste on SO but thank you very much for your information, I have been unable to ascertain this answer and level of detail anywhere else – Montresor Feb 21 '22 at 19:18