booleanlogicboolean-expressionkarnaugh-map

Why can't brackets in a simplified Boolean expression be separated by an AND?


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


Solution

  • (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.