Digital System�Lecture - 02

Boolean algebra

• Boolean algebra is the category of algebra in which the variable’s values are the truth values, true and false, ordinarily denoted 1 and 0 respectively.
• It is used to analyze and simplify digital circuits or digital gates.
• It is also called Binary Algebra or logical Algebra.

2

Binary Systems

• Computer hardware works with binary numbers, but binary arithmetic is much older than computers
• Ancient Chinese Civilization (3000 BC)
• Ancient Greek Civilization (1000 BC)
• Boolean Algebra (1850)

​

Propositional Logic

• The Ancient Greek philosophers created a system to formalize arguments called propositional logic.
• A proposition is a statement that could be TRUE or FALSE
• Propositions could be compounded into by means of the operators AND, OR and NOT

​

Propositional Calculus Example

Propositions, that may be TRUE or FALSE:

it is raining

the weather forecast is bad

A combined proposition:

it is raining OR the weather forecast is bad

​

​

Propositional Calculus Example

We can equate propositions, for example by writing:

I will take an umbrella = it is raining OR the weather

forecast is bad

or equivalently we can write:

If it is raining OR the weather forecast is bad

Then I will take an umbrella

OR

Rain Bad Weather Forecast Take Umbrella

Diagrammatic representation

• We can think of the umbrella proposition as a result that we calculate from the weather forecast or the fact that it is raining

​

Rain

Bad Weather Forecast

OR

Take Umbrella

Truth Tables

• Since propositions can only take two values, we can express all possible outcomes of the umbrella proposition by a table:

Boolean Algebra

• Propositional logic is too cumbersome to express arguments of any complexity.
• An equivalent, more tractable system of logic was introduced by the English mathematician Boole in 1850.

​

Boolean Algebra

• A Boolean variable has only one of two values: true or false (1 or 0), called logic values.
• A Boolean variable can be a function of other Boolean variables, i.e. Z = F(A, B, C, D…).
• We can also express the function in terms of a Truth Table
• A Truth Table is a tabulated list contains a clear relationship between all possible combination of input variables and the resultant operation.

​

Fundamental Operators - And Operator

Three fundamental operators AND, OR and NOT.

AND Operator

Z = A ∙ B

The AND operation is represented by the symbol “∙”. The truth table or logic table of the AND operation is as follows:

​

​

Fundamental Operators – OR Operator

OR Operator

Z = A + B

The OR operation is represented by the “+” symbol. Note that the OR operation is not related to addition in ordinary arithmetic. The truth table for OR is as follows:

​

​

​

​

Fundamental Operators – NOT Operator

NOT Operator

or Z = A’

• The NOT operation is designated by an overline or an hyphen.
• In words, the above expression is “Z” is equal to a NOT”. The truth table for the NOT operation is as follows:
• The NOT operation is a complement operation.

Fundamentals of Boolean Algebra

• The truth values are replaced by 1 and 0:
• 1 = TRUE
• 0 = FALSE
• Operators are replaced by symbols
• ' = NOT
• + = OR
• • = AND

Precedence

• Further simplification is introduced by introducing a precedence for the evaluation of the operators.
• (The highest precedence operator is evaluated first.)

​

All outcomes can be written as:

AND Operator (•)

OR Operator (+)

NOT '

Boolean Algebra Laws

1) Communicative laws 2) Associative laws

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

AB = BA (AB)C = A(BC)

3) Distributive laws 4) Absorption Law

A∙ (B+C) = (A ∙ B) + (A ∙ C) A∙ (A+B) = A +(A ∙ B)

5) Complement Law

A + = 1

A ∙ = 0

Other useful relationship:

1) A ∙ 1 = A 2) A ∙ 0 = 0 3) A + 1 = 1 4) A + 0 = A

5) A + A = A 6) A ∙ A = A

​

De Morgan’s Theorem

1)

2)

​

• Both forms of the DeMorgan’s Theorem have complement of an entire expression, and the effect of this complementing is to interchange each “+” to a “∙” and each “∙” to a “+” and to complement each variable
• Expression 1) is also described as inputs A and B with a NAND operator
• Expression 2) is also described as inputs A and B with a NOR operator

​

Simplification of Boolean Equation Using DeMorgan’s Theorem

Simplify Y = (A+B) ∙ (A+C)

Y = (A+B) ∙ (A+C)

= A ∙ A + A ∙ C + B ∙ A + B ∙ C

= A + A ∙ C + A ∙ B + B ∙ C

= A ∙ (1+C+B) + B ∙ C – Redundance Law

= A + B ∙ C

​

Sum of Product (SOP) and Product of Sum (POS)

• Product term - is a single variable of the logic product of several variables. The variables may or may not be complemented. e.g. XYZ, Y
• Sum term - is a single variable or the sum of several variables. The variable may or may not be complemented e.g. X+Y,
• Sum of products expression - is a product term of several product terms logically added together e.g.

​

• Product of sums expression - is a sum term or several sum terms logically multiplied together e.g.

​

Conversion of a truth table into SOP and POS

​

​

​

​

• Sum of product solution
• Product of sum solution

Derivation of SOP and POS

Sum of Products expression (Minterm Form)

1) From a truth table

2) The product terms from each row in which the output is a “1” are collected

3) The desired expression is the sum of these products e.g.

Product of Sums expression (Maxterm Form)

1) Form a truth table

2) Construct a column to contain the sum terms

3) The required expression is the product of sums terms from the row in which the output is “0” e.g.

​

Karnaugh Map (K-Map)

• The Karnaugh map provides a formal systematic approach to the problem of minimisation of logic functions. e.g.

​

• In the Karnaugh map, every possible combination of the binary input variables is represented on the map by a square ( or cell).
• For N input variables, we have 2ⁿ square.

​

Layout of Karnaugh Map

Use of K-Map

• In this way, by inspection, it is obvious that terms can be combined and simplified using the theorem. e.g.
• To plot the SOP function on Karnaugh map, a “1” is entered in each square corresponding to a product term in the function.

​

Use of K-Map

• To use the map to form the POS function, a “0” is entered in each cell corresponding to each sum term in the function. Result of simplification should then be in POS form.

​

Representation of Karnaugh Map

• Truth Table vs Karnaugh Map

Truth Table

Karnaugh Map

Use of K-Map

• There is a correspondence between top and bottom rows, and between extreme left and right-hand columns.

​

Simplification using a K-Map

• Simplify

​

​

​

​

​

​

• Solution

Example 1

Example 2

Example 3

Example 4

Example 5

Thanks!

Any questions?

You can find me at:

• minhazularefin21@gmail.com

35