Chapter 2:

Basic Definitions

• Binary Operators
• AND

z = x • y = x y z=1 if x=1 AND y=1

• OR

z = x + y z=1 if x=1 OR y=1

• NOT

z = x = x’ z=1 if x=0

• Boolean Algebra
• Binary Variables: only ‘0’ and ‘1’ values
• Algebraic Manipulation

*

1

Single Variable Theorem

• ( x’ )’ = x
• A • A = A A + A = A
• A • 0 = 0 A + 1 = 1
• A • A= 0 A+A= 1

Two and Three Variable Laws

• Theorem: DeMorgan
• ( A • B )’ = A’ + B’ ( A + B )’ = A’ • B’

​

*

2

Boolean Algebra

• Commutative Law (قانون التبادل)

AB = BA

A+B = B +A

• Associative (التجميع)

A(BC) = (AB)C

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

• Distributive (التوزيع)

A ( B + C ) = AB + AC

A + BC = ( A + B ) • ( A + C ) You can check out using a truth table

*

3

*

4

*

5

A NAND gate can be used as a NOT gate using either of the following wiring configurations.

a NOR gate

Logic Operators

• AND

​

​

​

• NAND (Not AND)

*

6

Logic Operators

• OR

​

​

​

• NOR (Not OR)

*

7

Logic Operators

• XOR (Exclusive-OR)

​

​

​

• XNOR (Exclusive-NOR)� (Equivalence)

*

8

Logic Operators

• NOT (Inverter)

​

​

​

• Buffer

*

9

Boolean Functions

• Boolean Expression

Example: F = x + y’ z

• Truth Table

All possible combinations�of input variables

• Logic Circuit

*

10

Algebraic Manipulation

• Literal:

A single variable within a term that may be complemented or not.

• Use Boolean Algebra to simplify Boolean functions to produce simpler circuits

Example: Simplify to a minimum number of literals

F = x + x’ y ( 3 Literals)

= x + ( x’ y )

= ( x + x’ ) ( x + y )

= ( 1 ) ( x + y ) = x + y ( 2 Literals)

*

11

Distributive law

Complement of a Function

• DeMorgan’s Theorm

​

​

​

*

12

Standard Forms

• Minterm
• Product (AND function)
• Contains all variables
• Evaluates to ‘1’ for a�specific combination

Example

A = 0 A B C

B = 0 (0) • (0) • (0)

C = 0

*

13

1 • 1 • 1 = 1

Standard Forms

• Maxterm
• Sum (OR function)
• Contains all variables
• Evaluates to ‘0’ for a�specific combination

Example

A = 1 A B C

B = 1 (1) + (1) + (1)

C = 1

*

14

0 + 0 + 0 = 0

Standard Forms

• Truth Table to Boolean Function

*

15

Standard Forms

• Minterms

​

​

​

​

*

16

• Maxterms

• Sum of Products (SOP)

• Product of Sums (POS)

*

17

• Give the standard form using (SOP)?

• Give the standard form using (POS)?

Chapter 3:

Karnaugh Map

• Adjacent Squares
• Number of squares = number of combinations
• Each square represents a minterm
• 2 Variables ⇨ 4 squares
• 3 Variables ⇨ 8 squares
• 4 Variables ⇨ 16 squares
• Each two adjacent squares differ in one variable
• Two adjacent minterms can be combined together

Example: F = x y + x y’

= x ( y + y’ )

= x

*

19

Two-variable Map

*

20

Note: adjacent squares horizontally and vertically NOT diagonally

Two-variable Map

• Example

*

21

Three-variable Map

*

22

Three-variable Map

• Example

*

23

Three-variable Map

• Example

*

24

Three-variable Map

• Example

*

25

Three-variable Map

• Example

*

26

Four-variable Map

*

27

Four-variable Map

• Example

*

28

Four-variable Map

• Exercise 1: Simplify? Given the Boolean function

F = A’C + A’B + A B’C + BC

*

29

• Exercise 2: Simplify? Given the Boolean function

F = A’ B’ C’ + B’ C D’ + A’ B C D’ + A B’ C’

Four-variable Map

• Example

Simplify: F = A’ B’ C’ + B’ C D’ + A’ B C D’ + A B’ C’

*

30

Four-variable Map

• Example

Simplify: F = A’ B’ C’ + B’ C D’ + A’ B C D’ + A B’ C’

*

31

Four-variable Map

• Example

Simplify: F = A’ B’ C’ + B’ C D’ + A’ B C D’ + A B’ C’

*

32

Four-variable Map

• Example

Simplify: F = A’ B’ C’ + B’ C D’ + A’ B C D’ + A B’ C’

*

33

Four-variable Map

• Example

Simplify: F = A’ B’ C’ + B’ C D’ + A’ B C D’ + A B’ C’

*

34

Product of Sums Simplification

*

35

Don’t-Care Condition

• Example

*

36

F

Don’t care what value F may take

Logic�Circuit

A

B

C

Don’t-Care Condition

• Example

*

37

F

A

B

C

Don’t-Care Condition

• Example

*

38

F (w, x, y, z) = ∑(1, 3, 7, 11, 15)

d (w, x, y, z) = ∑(0, 2, 5)

x = 0

x = 1