Chapter 3 - Get Logic

Digital Electronics Logic Gates and Boolean Algebra CHAPTER 2

OR Gates •The Boolean expression for the OR operation is:

X=A+B ‘+’ is stand for OR operation

A B

X = A+B

•The expression X = A + B is read as “ X equals A OR B”

OR Operation •The OR operation produce result (o/p) of 1 wherever any i/p is ‘1’, otherwise the result is ‘0’. A B 0 0 0 1 1 0 1 1

X 0 1 1 1

a) Truth Table

A B X b) Timing Diagram

•Application Example: –Intrusion detection & alarm system. Main Door Back Door Window

Master Alarm Circuit

AND Gates • The Boolean expression for the AND operation is:

X=A.B ‘.’ is stand for AND operation

A B

X = A.B

• The expression X = A . B is read as “ X equals A AND B”

AND Operation •The AND operation produce result (o/p) of 1 wherever both i/p is ‘1’, otherwise the result is ‘0’. A B 0 0 0 1 1 0 1 1

X 0 0 0 1

A B X b) Timing Diagram

a) Truth Table

•Application Example: –A seat-belt alarm system. Ignition Switch

Master Alarm Circuit

Seat-Belt

30s

The Inverter (NOT) • Perform on a single i/p variable • The Boolean operation for the NOT operation is:

X=A ‘-’ overbar represent the NOT operation

A

X=A Presence of small circle always denotes inversion

• The expression is read as ‘ X equals NOT A’ or ‘ X equals inverse of A’ or ‘X equals the complement of A’ A = opposite logic value of A

Summary of Boolean Operation

• The rules for the OR, AND & NOT operation may be summarized as follows:

A 0 0 1 1

OR B 0 1 0 1

X 0 1 1 1

A 0 0 1 1

AND B X 0 0 1 0 0 0 1 1

NOT A X 0 1 0 1 0 1 1 0

NOR Gate • Combination of OR and NOT gate NOR=Not-OR A B

X = A+B

A B

X = A+B

Denotes inversion

a) NOR Symbol

A B 0 0 0 1 1 0 1 1

b) Equivalent Circuit

A+B 0 1 1 1

A +B 1 0 0 0

c) Truth Table

NAND Gate

• Combination of AND and NOT gate NAND = Not-AND

A B

X=A.B

A B

a) NAND Symbol

A B A.B 0 0 0 0 1 0 1 0 0 1 1 1

X=A.B

b) Equivalent Circuit

A.B 1 1 1 0

c) Truth Table

Exclusive OR gate (XOR) – The XOR gate has only 2 i/p

A B

X=A+B

– The o/p of an XOR gate is ‘1’ only when the 2 i/p are at opposite logic level. A 0 0 1 1

B 0 1 0 1

A +B 0 1 1 0

a) Truth Table

Exclusive NOR Gate (XNOR) – The XNOR gate has only 2 i/p A B

X=A+B

– The o/p of an XOR gate is ‘1’ only when the 2 i/p are at same logic level A B 0 0 0 1 1 0 1 1

A+B 1 0 0 1

a) Truth Table

Boolean Operations Boolean algebra is the mathematics of digital systems Boolean Addition •

Boolean addition is equivalent to the OR operation 0+0 = 0

• •

0+1 = 1

1+0 = 1

1+1 = 1

•

In Boolean algebra, a sum term is a sum of literals In logic circuits, a sum term is produced by OR operation with no AND operations involved E.g.

•

A sum term is equal to 1 when one or more of the literals in the term is 1

A + B, A + B , A + B + C

Boolean Operations

(cont.)

Boolean Multiplication •

Boolean multiplication is equivalent to the AND operation 0.0 = 0

0.1 = 0

1.0 = 0

1.1 = 1

•

In Boolean algebra, a product term is the product of literals In logic circuits, a product term is produced by AND operation with no OR operations involved E.g.

•

A product term is equal to 1 only if each of the literals in the term is 1

• •

AB, AB , ABC , A BCD

Boolean Theorems Single variable x = 0/1 1. x.0 = 0 2. x.1 = x 3. x.x = x 4. x.x = 0 5. x+0 = x 6. x+1 = 1 7. x+x = x 8. x+x = 1

Boolean Theorems •

Multivariable Theorems 1. x+y = y+x 2. x.y = y.x 3. x+(y+z)= (x+y)+z = x+y+z 4. x(yz) = (xy)z = xyz

a. x(y+z)= xy+xz b. (w+x)(y+z)= wy+xy+wz+xz 5. x+xy = x a. x+xy = x+y b. x+xy = x+y

Boolean Theorems • Rule 1: Anything ANDed with a 0 is equal to 0 • Rule 2: Anything ANDed with a 1 is equal to itself

Boolean Theorems • Rule 3: Anything ANDed with itself is equal to itself

• Rule 4: Anything ANDed with its own complement equals 0

Boolean Theorems • Rule 5: Anything ORed with a 0 is equal to itself

• Rule 6: Anything ORed with a 1 is equal to 1

Boolean Theorems • Rule 7: Anything ORed with itself isequal to itself

• Rule 8: Anything ORed with its own complement equals 1

Boolean Theorems • Rule (extra): Anything complemented twice will return to its original logic level

Boolean Theorems • Commutative law of addition and multiplication: –A+B=B+A – ABC = BCA

Boolean Theorems • Associative law of addition and multiplication – A + (B + C) = (A + B) + C – A(BC) = (AB)C

Boolean Theorems • Distributive law – A(B + C) = AB + AC – (A + B)(C + D) = AC + AD + BC + BD

DeMorgan’s Theorem •

•

•

•

DeMorgan’s Theorems are useful in simplifying expression in which a product or sum of variables is inverted. The two theorems are : 1. ( X + Y ) = Y .X 2. ( X .Y ) = Y + X E.g.: Apply DeMorgan’s Theorems to the following expression: Solution:

AB + C D + EF AB + C D + EF = ( AB )(C D )( EF ) = ( A + B )(C + D )( E + F ) = ( A + B )(C + D )( E + F )

Implications of DeMorgan’s Theorem

Universality of NAND gates and NOR gates NAND gate can be used to perform each of the Boolean operation OR, AND & NOT A

A B

A B

⇒

A

X=A

X = A.B = A.B

⇒

A B

X = A.B

X = A .B = A+B

⇒

A B

X = A+B

X=A.A=A

X = A.B

X=A X=B

OR Gate

Universality of NAND gates and NOR gates NOR gate also can be arranged to implement any of the Boolean operations A

A B

A

⇒

A

X=A

X = A+B = A+B ⇒

A B

X = A+B

⇒

A B

X = A .B

X = A+A = A

X = A+B

X= A

X = A + B = A .B B

X= B

AND Gate

Alternate Logic-Gate Representations

Standard and alternate symbols for various logic gates and inverter.

How to obtain the alternative symbol from standard ones • Invert each input and output of the standard symbol. This is done by adding bubbles (small circles) on input and output lines that do not have bubbles and by removing bubbles that are already there. • Change the operation symbol from AND to OR, or from OR to AND. (In the special case of the INVERTER, the operation symbol is not changed.)

Several points • The equivalences can be extended to gates with any number of inputs. • None of the standard symbols have bubbles on their inputs, and all the alternate symbols do. • The standard and alternate symbols for each gate represent the same physical circuit; there is no difference in the circuits represented by the two symbols. • NAND and NOR gates are inverting gates, and so both the standard and the alternate symbols for each will have a bubble on either the input or the output, AND and OR gates are non-inverting gates, and so the alternate symbols for each will have bubbles on both inputs and output.

Logic-Symbol Interpretation

• Active high/low When an input or output line on a logic circuit symbol has no bubble on it, that line is said to be active-high, otherwise it is active-low.

Interpretation of the two NAND gate symbols

Interpretation of the two OR gate symbols

How to represent the basic logic functions • Logical statements in our own language • Truth tables • Traditional graphic logic symbols • Boolean algebra expressions • Timing diagrams

Summary • Boolean Algebra: a mathematical tool used in the analysis and design of digital circuits • OR, AND, NOT: basic Boolean operations • OR: HIGH output when any input is HIGH • AND: HIGH output only when all inputs are HIGH • NOT: output is the opposite logic level as the input • NOR: OR with its output connected to an INVERTER • NAND: AND with its output connected to an INVERTER • Boolean theorems and rules: to simplify the expression of a logic circuit and can lead to a simpler way of implementing the circuit • NAND, NOR: can be used to implement any of the basic Boolean operations