1 of 36

Simplification Using

Boolean Algebra

DJM 30073

DIGITAL SYSTEM

​

​

2 of 36

Laws of Boolean Algebra

3 of 36

Boolean Rules��1) A + 0 = A

  • In math if you add 0 you have changed nothing
  • In Boolean Algebra ORing with 0 changes nothing

4 of 36

Boolean Rules��2) A + 1 = 1

  • ORing with 1 must give a 1 since if any input

is 1 an OR gate will give a 1

5 of 36

Boolean Rules ��3) A • 0 = 0

  • In math if 0 is multiplied with anything you

get 0. If you AND anything with 0 you get 0

6 of 36

Boolean Rules��4) A • 1 = A

  • ANDing anything with 1 will yield the anything

7 of 36

Boolean Rules��5) A + A = A

  • ORing with itself will give the same result

8 of 36

Boolean Rules ��6) A + A = 1

  • Either A or A must be 1 so A + A =1

9 of 36

Boolean Rules��7) A • A = A

  • ANDing with itself will give the same result

10 of 36

Boolean Rules��8) A • A = 0

  • In digital Logic 1 =0 and 0 =1, so AA=0 since one of the inputs must be 0.

11 of 36

Boolean Rules� �9) A = A

  • If you not something twice you are back to the beginning

12 of 36

Boolean Rules��10) A + AB = A

Proof:

A + AB = A(1 +B) DISTRIBUTIVE LAW

= A∙1 RULE 2: (1+B)=1

= A RULE 4: A∙1 = A

13 of 36

Boolean Rules ��11) A + AB = A + B

  • If A is 1 the output is 1 , If A is 0 the output is B

Proof:

A + AB = (A + AB) + AB RULE 10

= (AA +AB) + AB RULE 7

= AA + AB + AA +AB RULE 8

= (A + A)(A + B) FACTORING

= 1∙(A + B) RULE 6

= A + B RULE 4

14 of 36

Boolean Rules��12) (A + B)(A + C) = A + BC

PROOF

(A + B)(A +C) = AA + AC +AB +BC DISTRIBUTIVE LAW

= A + AC + AB + BC RULE 7

= A(1 + C) +AB + BC FACTORING

= A.1 + AB + BC RULE 2

= A(1 + B) + BC FACTORING

= A.1 + BC RULE 2

= A + BC RULE 4

15 of 36

PROBLEMS

Using Boolean algebra techniques, simplify this expression:

1. AB + A(B+C) + B(B+C)

2. [ AB (C+BD) + A B ]C

3. A B C + A B C + A B C + ABC + ABC

4. AB + AC + ABC

16 of 36

The Karnaugh Map

17 of 36

The Karnaugh Map

  • Provides a systematic method for simplifying Boolean expressions
  • Produces the simplest SOP or POS expression
  • Similar to a truth table because it presents all of the possible values of input variables

18 of 36

The 3-Variable K-Map

19 of 36

The 4-Variable K-Map

20 of 36

K-Map SOP Minimization

  • A 1 is placed on the K-Map for each product term in the expression.
  • Each 1 is placed in a cell corresponding to the value of a product term

21 of 36

Example:

Map the following standard SOP expression on a K-Map:

Solution:

22 of 36

Example:

Map the following standard SOP expression on a K-Map:

Solution:

23 of 36

Exercise:

Map the following standard SOP expression on a K-Map:

24 of 36

Answer:

25 of 36

K-Map Simplification of SOP Expressions

  • A group must contain either 1, 2, 4, 8 or 16 cells.
  • Each cell in group must be adjacent to one or more cells in that same group but all cells in the group do not have to be adjacent to each other
  • Always include the largest possible number 1s in a group in accordance with rule 1
  • Each 1 on the map must be included in at least one group. The 1s already in a group can be included in another group as long as the overlapping groups include noncommon 1s

To maximize the size of the groups and to minimize the number of groups

26 of 36

Example: Group the 1s in each K-Maps

27 of 36

Determining the minimum SOP Expression from the Map

  • Groups the cells that have 1s. Each group of cells containing 1s create one product term composed of all variables that occur in only one form (either uncomplemented or complemented) within the group. Variable that occurs both uncomplemented and complemented within the group are eliminated. These are called contradictory variables.

28 of 36

Example: Determine the product term for the K-Map below and write the resulting minimum SOP expression

29 of 36

30 of 36

Example: Use a K-Map to minimize the following standard SOP expression

31 of 36

Example: Use a K-Map to minimize the following standard SOP expression

32 of 36

Mapping Directly from a Truth Table

33 of 36

Don’t Care (X) Conditions

  • A situation arises in which input variable combinations are not allowed
  • Don’t care terms either a 1 or a 0 may be assigned to the output

34 of 36

Don’t Care (X) Conditions

Example of the use of “don’t care” conditions to simplify an expression

35 of 36

Exercise: Use K-Map to find the minimum SOP from

1

2

36 of 36

Thank You

“Gagal Setelah Mencuba Seribu Kali Lebih Baik Daripada Tidak Pernah Mencuba. Keperitan dan Kepayahan Adalah Jalan Menuju Kebenaran”