Intended Learning Outcomes for Today's Session

1. Recall Boolean Algebra Laws (Again)
2. Recall how to minimise the terms (Again).
3. Explore ​Karnaugh Map method to minimise Boolean Expression.

Note: Slides from 3 - 23 are recap from last week.

Boolean Logic

In Boolean algebra, a variable is a symbol is used to represent an action, a condition, or data. A single variable can only have a value of 1 or 0. ​

The complement represents the inverse of a variable and is indicated with an overbar. Thus, the complement of is .​

​
A literal is a variable or its complement.​

Boolean Addition/Sum

Parallel Switch

Boolean Sum Term

• In Boolean algebra, a sum term is a sum of literals. ​

• In logic circuits, a sum term is produced by an OR operation with no AND operations involved. ​

Some examples of sum terms are:​

• A sum term is equal to when one or more of the literals in the term are . ​

• A sum term is equal to only if each of the literals is .​

Boolean Multiplication

Series Switch

Product Term "MINTERM"

In Boolean algebra, a product term or “minterm” is the product of literals. ​

In logic circuits, a product term is produced by an AND operation with no OR operations involved. Some examples of product terms are ​

A product term is equal to 1 only if each of the literals in the term is 1. A product term is equal to 0 when one or more of the literals are 0.​

Liteals SOP

Standard SOP (SSOP)

When all input variables appear in each product term, the expression is known as a standard Sum of Product (SOP) expression:

Following expression has input variables A, B, C and D , complete set of variables is not present in the first two expression ​

Following is a standard SOP (SSOP) expression​

Output of a digital circuit written as SSOP

1- Basic Rules (Annulment (Null) Law)

2- Basic Rules (Identity Law)

3- Basic Rules (Idempotent Law)

4- Basic Rules (Complement Law)

5- Double Negation

Note we see that a double inversion, cancel each other out!

Boolean Equation :

6- Associative Law

The associative laws are also applied to addition and multiplication. For addition, the associative law states​

When OR’ing more than two variables, the result is the same regardless of the grouping of the variables.​

For multiplication, the associative law states​

When ANDing more than two variables, the result is the same regardless of the grouping of the variables.​

Example:

Z= (A.B).C == A.(B.C)

Z= (A+B)+C == A+(B+C)

7- Commutative Law

The commutative laws are applied to addition and multiplication. For addition, the commutative law states:​

In terms of the result, the order in which variables are ORed makes no difference.​

For multiplication, the commutative law states:​

In terms of the result, the order in which variables are ANDed makes no difference.​

8- Distributive Law

The distributive law is the factoring law. A common variable can be factored from an expression just as in ordinary algebra. That is​

The distributive law can be illustrated with equivalent circuits:​

9- Absotptive (Redundancy ) Law

10- De Morgan's Laws

1- The complement of the product of two variables equals the sum of their complements.

10- De Morgan's Laws (Cont'd)

2- The complement of the sum of two variables equals the product of their complements.

Reduction of Gates

• If we can reduce the number of gate and yet produce the
  same functionality we gain the benefits of:

  • Economy
  • Speed
  • Increased ability

Karnaugh Map (K-map): Introduction

• A specialised format of a truth table facilitating simpler pattern identification

• A graphical technique (Pictorial) for simplifying Boolean expressions

• Suitable for circuit designs involving a maximum of 4 variables

K-MAP: How to be Implement it?

S=A+B

K-MAP: How to be Implement it?

K-Map Minimisation from Truth Table

• Step-1: Create the K-map and fill it:

  • if you have two variables A and B, you'd arrange the cells in a 2x2 grid.
  • If you have three variables (A, B, C), the grid would be 2x4 or 4x2 depending on the layout, etc.

• Step-2: Group adjacent 1s: Look for groups of adjacent 1s (1, 2, 4, 8, etc.) in the K-map. Groups can be rectangular in shape and can wrap around the edges of the K-map.

• Step-3: Create Sum-of-Products (SOP) terms: Use the grouped 1s to generate simplified terms for the Boolean expression. Each group corresponds to a term in the minimized expression.

K-MAP: Example-1

K-MAP: Example-1

S=A

K-MAP: Example-2

K-MAP: Example-2

K-MAP: Example-3

K-MAP: Example-4

K-MAP: Example-4

K-MAP: Example-5: Three literal

K-MAP: Example-5: Three literal

K-MAP: Example-5: Three literal

Rule: The grouping of 1s must be horizontal, vertical rectangle, or square and the number of 1s in a group has to be , where .

S=A+B

Another way of constructing a K-map (90 D).

How to fix it?

Ali change it

Also you can do this:

Note: Always best to create group as larg as possible

Your Turn

Another one of your turn

Solution of 2nd turn

Rolling Group

Summary of Grouping Rules

1. A group must only contain 1s, no Os

2. A group can only be horizontal or vertical, not diagonal

3. A group must contain (1, 2, 4, 8, etc.)

4. Each group should be as large as possible

5. Groups may overlap

6. Groups may wrap around a table

7. Every 1 must be in at least one group

K-MAP with 4 variables/literals

Your Turn: 4 VARs

Solution your turn 4 VARs

K-Map Minimisation from Boolean Expression

Last Week we used the 10 LAWs to minimise the expression, like so:

K-Map Minimisation from Boolean Expression

No of variable= 3, then number of cells =

K-Map Minimisation from Boolean Expression

Your Turn: Minimise the follwing using:

1- Boolean Algerbra Laws

AND

2- K-MAP

Your Turn: Minimise the follwing using:

1- Boolean Algerbra Laws

Your Turn: Minimise the follwing using:

LAB

1. More K-MAP and Boolean Algebric Laws exercises: LINK

2. Assessment-2 (Portofolio-2: Part-1) LINK