Basic Boolean law:

Boolean function and Expression

Boolean algebra deals with binary variables and logic operations. A Boolean function is described by an algebraic expression called a Boolean expression, which consists of binary variables, the constants 0 and 1, and the logic operation symbols.

Ex:- F(A,B,C,D) = A + BC̅ + ADC

Various ways to represent a given function

• Sum of Products form
• Product of Sums form

1. Sum of Product (SOP) Form:

• This is also called disjunctive canonical form (DCF) or Expanded Sum of Products Form or Canonical Sum of Products form.
• In this form, the function is the sum of a number of product terms, where each product term contains all variables of the function either in complemented or uncomplemented form.
• This can also be derived from the truth table by finding the sum of all the terms that correspond to those combinations for which f assumes the value 1. Example:

 f(A,B,C) = A̅B + B̅C
                                          = A̅B(C + C̅) + B̅C(A + A̅)
                                                = A̅BC + A̅BC̅ + AB̅C + A̅B̅C

• The product term, which contains all the variables of the functions either in complemented or uncomplemented form, is called a minterm.
• the minterm is denoted as m₀, m₁, m₂, …
• Another way of representing the function in canonical SOP form is by showing the sum of minterms for which the function equals 1.

For example:
       f(A,B,C)=m1+m2+m3+m6​
        (or)
       f(A,B,C)=Σm(1,2,3,6)
       Where Σm represents the sum of all the minterms.

2. Product of Sum (POS) Form

• This form is also called the Conjunctive Canonical Form, or Expanded product of sum Form, or Canonical product of Sum Form.
• This is by considering the combinations for which f = 0
• Each term is the sum of all the variables.

• The function f(A,B,C)=(A’+B’)(A+B)
                                         =(A’+B’+CC’)(A+B+CC’)
  = (A’+B’+C)(A’+B’+C’)(A+B+C’)(A+B+C)

• The sum term, which contains each of the n variables in either complemented or uncomplemented form, is called a maxterm.
• Maxterm is represented as M₀, M₁, M₂, …

     Example:
                       f(A,B,C)=M0.M1.M7​
                                       or
                        f(A,B,C)=∏M(0,1,7)

SOP standard form

The Complement of a function expressed as the sum of minterms equals the sum of minterms missing from the original function.
Example:-
f(A,B,C)=Σm(0,2,6,7)
f(A,B,C)’= Σm(1,3,4,5) = m1+m2+m3+m4+m5
f = (m1+m3+m4+m5)’ =m1′ . m3′. m4′  . m5′
= M1  M2  M3  M4  M5
= ∏M(1, 3, 4, 5)

K-map(Karnought map):

in digital electronics, a K-map (Karnaugh map) is a graphical method used to simplify Boolean algebra expressions. It consists of a grid where each cell represents a minterm or maxterm of the Boolean function, based on the input variables. By grouping adjacent cells that contain 1s (for SOP) or 0s (for POS) in powers of 2, redundant terms can be eliminated to derive a minimized expression. This technique is particularly useful for functions with up to 4 or 6 variables, making circuit design more efficient.

Two-variable K-map

A two-variable Karnaugh map (K-map) is a graphical tool used to simplify Boolean algebra expressions for two variables, typically labeled A and B.
It consists of a 2×2 grid (4 cells) representing all possible combinations of the two variables: 00, 01, 10, and 11. Each cell corresponds to a minterm of the Boolean function.

SOP Form:-

• The variable K-map has $=4$ squares. These squares are called cells.
• A ‘1’ is placed in any square that indicates that the corresponding minterm is included in the output expression, and a 0 or no entry in any square indicates that the corresponding minterm does not appear in the expression for output.

POS Form:
Each sum term in the standard POS expression is called a Maxterm. A function in two variables (A, B) has 4 possible maxterms: A + B, A + B̅, A̅ + B, and A̅ + B̅. They are represented as M0, M1, M2, and M3 respectively.

 3-variable K-map

A 3-variable K-map (Karnaugh Map) is a graphical tool used to simplify Boolean algebra expressions with three variables (for example, A, B, and C). It consists of 8 cells, because each variable has 2 possible values (0 or 1) and 2³ = 8. A three-variable K Map may be represented as

Here, A, B, and C are the three variables of the given Boolean function. The K-map helps to visually group adjacent 1s (for SOP) or 0s (for POS) to form larger groups, which simplifies the Boolean expression by combining terms.

4-variable K-map

A 4-variable K-map (Karnaugh Map) is a graphical method used to simplify Boolean expressions with four variables (for example, A, B, C, and D). It consists of 16 cells, because each variable can be 0 or 1, and 2⁴ = 16. Four four-variable K Map may be represented as

Each cell represents a unique minterm (for SOP) or maxterm (for POS) based on a specific combination of the four variables. The cells are arranged in a 4×4 grid, following Gray code order so that only one variable changes between adjacent cells.

Karnaugh Map Simplification Rules: 

1. We can either group 0’s with 0’s or 1’s with 1’s, but we can not group 0’s and 1’s together.
2. X, representing don’t care, can be grouped with 0’s as well as 1’s.
3. Groups may overlap each other.
4. We can only create a group whose number of cells can be represented in the power of 2.
5. In other words, a group can only contain 2^n, i.e., 1, 2, 4, 8, 16, and so on, number of cells.
6. Groups can be either horizontal or vertical.
7. We can not create groups of diagonal or any other shape.
8. Each group should be as large as possible.
9. Opposite grouping and corner grouping are allowed.
10. The example of corner grouping is shown below.
11. There should be as few groups as possible

Numerical1:Minimize the following Boolean function- F(A, B, C, D) = Σm(0, 1, 2, 5, 7, 8, 9, 10, 13, 15) [SEE 2080]
Solution:
Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map. We fill the cells of the K Map in accordance with the given boolean function.

Thus, minimized Boolean expression is F(A, B, C, D) = BD + C’D + B’D’

Numerical 2 : Minimize the following Boolean function- F(A, B, C, D) = Σm(0, 1, 3, 5, 7, 8, 9, 11, 13, 15)
Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map. We fill the cells of K Map in accordance with the given boolean function.

Thus, the minimized Boolean expression is F(A, B, C, D) = B’C’ + D

Numerical 3 :Minimize the following boolean function- F(A, B, C) = Σm(0, 1, 6, 7) + Σd(3, 5). 
Since the given boolean expression has 3 variables, so we draw a 2 x 4 K Map. We fill the cells of the K Map in accordance with the given boolean function.

Thus, the minimized Boolean expression is :F(A, B, C) = AB + A’B’

Numerical 4 : Minimize the following Boolean function- F(A, B, C) = Σm(1, 2, 5, 7) + Σd(0, 4, 6)
Since the given boolean expression has 3 variables, we draw a 2 x 4 K Map. We fill the cells of the K Map with the given boolean function.

Numerical 5 :Minimize the following Boolean function F(A, B, C) = Σm(0, 1, 6, 7) + Σd(3, 4, 5)
Since the given boolean expression has 3 variables, so we draw a 2 x 4 K Map. We fill the cells of K Map in accordance with the given boolean function.

Thus, the minimized boolean expression is :F(A, B, C) = A + B’

Numerical 6: Minimize the following Boolean function- F(A, B, C, D) = Σm(0, 2, 8, 10, 14) + Σd(5, 15). 
Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map. We fill the cells of K Map in accordance with the given boolean function.

Thus, minimized boolean expression is  F(A, B, C, D) = ACD’ + B’D’

Numerical 7 : Minimize the following Boolean function- F(A, B, C, D) = Σm(3, 4, 5, 7, 9, 13, 14, 15). 
Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map. We fill the cells of K Map in accordance with the given boolean function.

Thus, minimized boolean expression is F(A, B, C, D) = A’BC’ + A’CD + AC’D + ABC

Numerical 8: Consider the following boolean function- F(W, X, Y, Z) = Σm(1, 3, 4, 6, 9, 11, 12, 14)

Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map. We fill the cells of K Map in accordance with the given boolean function.

hus, the minimized boolean expression is F(W, X, Y, Z) = X ⊕ Z

Don’t care condition in K-map:

A K-Map or Karnaugh Map is a graphical tool used to simplify Boolean expressions by arranging cells that represent different combinations of variables in sum or product form. In the K-Map method, there is a useful feature called the don’t care condition, which allows you to mark certain input combinations that do not affect the output. These don’t care conditions, shown as X, make it easier to group cells in the K-Map, helping you get a simpler and more efficient Boolean function. This makes the design of digital circuits easier and cheaper.

Minimize the following 4-variable Boolean expression in SOP form using a K-map. F(A B C D) = ∑m(0,1,4,5,6,10,13) +d⟮2,3⟯

Solution

Compiled by: Er. Basant Kumar Yadav