Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

3.1 Introduction to Boolean Algebra

Discrete Maths

Al Hussein Technical University

Department of Basic Sciences

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Outline

1 Introduction to Boolean Algebra

2 Boolean Algebra Operators

3 Boolean Algebra Laws

4 Boolean Algebra Laws

5 Circuit Simplification

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

What is Boolean Algebra?

Boolean algebra (named in honor of George Boole) involves only

two values
Boolean algebra deals with logical values: TRUE and FALSE.
common names are {F, T}, {LO, HI}, {L, H}, or {0,1}.

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Boolean Operators

Boolean algebra involves three primitive operators.

NOT (A , A′ or ¬A ) — Unary operator the logical negation
(NOT) operator.
The logical disjunction OR (A + B) — Binary operator
The logical conjunction AND (A · B or AB) — Binary operator
That’s all there is to keep track of: two possible values, FALSE and
TRUE, manipulated by three operators, NOT, OR, AND.

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

The NOT Gate (Logical Negation)

The truth table for the NOT Gate

A A
0 1
1 0
Symbol for a NOT gate.

A A

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

The AND Gate Logical Conjunction

The truth table for an AND Gate

A B AB
0 0 0
0 1 0
1 0 0
1 1 1
The symbol for an AND gate.

A
A·B
B

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

The OR Gate Logical Disjunction

The truth table for the OR Gate

A B A+B
0 0 0
0 1 1
1 0 1
1 1 1
The symbol for an OR gate.

A
A+B
B

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Exclusive OR (XOR)
The truth table for an XOR Gate
A B A⊕B
0 0 0
0 1 0
1 0 0
1 1 1

f (A, B) = A ⊕ B = AB + AB

The symbol for an XOR gate.

A
A⊕B
B

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Basic Logic Gates

A B A⊕B A B A·B A B A+B

0 0 1 0 0 1 0 0 1
0 1 0 0 1 1 0 1 0
1 0 0 1 0 1 1 0 0
1 1 1 1 1 0 1 1 0

XNOR NAND NOR

A A A
A⊕B A·B A+B
B B B

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Boolean Algebra Laws

Boolean Algebra Laws

Law AND Form OR Form

Identity Law A·1 = A A+0 = A

Null Law A·0 = 0 A+1 = 1
Idempotent Law A·A = A A+A = A
Inverse Law A·A = 0 A+A = 1

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Boolean Algebra Laws

Law AND Form OR Form

Commutative A · B = B · A A+B =B+A
Associative (A · B) · C = A · (B · C) (A + B) + C = A + (B + C)
Distributive A+(B ·C) = (A+B)·(A+C) A · (B + C) = (A · B) + (A · C)
Absorption A · (A + B) = A A + (A · B) = A
De Morgan’s A·B =A+B A+B =A·B

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Example Circuit Simplification

Example 1. Show the following Boolean Identity: A + AB = A

Soluion

A + AB = A(1 + B)
=A·1
=A

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Count.
A B AB A + AB
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 1

A Output
B

A Output

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Example Circuit Simplification

Example 2.
Show that A + ĀB = A + B Soluion

A + ĀB = (A + Ā) · (A + B)
= 1(·A + B)
=A+B

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Count.
Truth Table and Logic Circuits for A + AB = A + B
A B A AB A + AB A+B
0 0 1 0 0 0
0 1 1 1 1 1
1 0 0 0 1 1
1 1 0 0 1 1

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Example Circuit Simplification

Example 3. Show that (A + B) + (A + C) = A(B + C) Soluion:

Given

(A + B)(A + C) = AA + AC + AB + BC
= A + AC + AB + BC
= A + AB + AC + BC
= A + BC (since A + AB = A, A + AC = A)
A(B + C) = AB + AC
A + BC = A + BC
⇒ (A + B)(A + C) = A(B + C)

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Count.

Truth Table Proof: (A + B)(A + C) = A(B + C)

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

0 0 0 0 0 0 0 0
0 0 1 0 1 0 1 0
0 1 0 1 0 0 1 0
0 1 1 1 1 1 1 0
1 0 0 1 1 1 0 0
1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1

Conclusion: The columns for (A + B)(A + C) and A(B + C) are

identical. Therefore, the identity is true.

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Count.
The Logic Circuit for (A + B)(A + C) & A(B + C)

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Example Circuit Simplification

Example 4. Find the Boolean expression for the output.

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Count.

Soluion

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Example Circuit Simplification

Example 5. Find the Boolean expression for the output of the

following circuits. Show that they are equivalent.

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Circuit Simplification

Soluion

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Count.

AB + A(B + C) + B(B + C) = AB + AB + AC + BB + BC
= AB + AB + AC + B + BC
= AB + AC + B + BC
= B(A + 1 + C) + AC (factor B)
= B(1) + AC (since A + 1 = 1)
= B + AC

Therefore,

AB + A(B + C) + B(B + C) = B + AC

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra
Introduction to Boolean Algebra Boolean Algebra Operators Boolean Algebra Laws Boolean Algebra Laws Circuit S

Thank You!

Discrete Maths Al Hussein Technical University Department of Basic Sciences

3.1 Introduction to Boolean Algebra