Boolean Algebra

Logic Gates

Pavithran Puthiyapurayil , Maldives

4/30/2018 1
National University
 Basic logic gates
• Not x
x

• And x
y
xy x
y
xyz
z
x x+y+z
• Or x
y
x+y y
z
• Nand x xy
y
• Nor x x+y
y
• Xor x xÅy
y
Pavithran Puthiyapurayil , Maldives
4/30/2018 2
National University
 The AND gate

Pavithran Puthiyapurayil , Maldives

4/30/2018 3
National University
 The OR gate

Pavithran Puthiyapurayil , Maldives

4/30/2018 4
National University
 The NOT gate (or inverter)

Pavithran Puthiyapurayil , Maldives

4/30/2018 5
National University
 A logic buffer gate

Pavithran Puthiyapurayil , Maldives

4/30/2018 6
National University
 The NAND gate

Pavithran Puthiyapurayil , Maldives

4/30/2018 7
National University
 The NOR gate

Pavithran Puthiyapurayil , Maldives

4/30/2018 8
National University
 The Exclusive OR gate

Pavithran Puthiyapurayil , Maldives

4/30/2018 9
National University
 The Exclusive NOR gate

Pavithran Puthiyapurayil , Maldives

4/30/2018 10
National University
 Boolean Algebra
• Boolean Constants
– these are ‘0’ (false) and ‘1’ (true)
• Boolean Variables
– variables that can only take the vales ‘0’ or ‘1’
• Boolean Functions
– each of the logic functions (such as AND, OR and NOT)
are represented by symbols as described above
• Boolean Theorems
– a set of identities and laws – see text for details
Pavithran Puthiyapurayil , Maldives
4/30/2018 11
National University
 Boolean laws

AB  BA A + AB  A
A+B B+ A A( A + B )  A

A(B + C )  AB + BC A +B  AB
A + BC  ( A + B )( A + C ) AB  A +B

A + AB  A + B
A(BC )  ( AB )C A( A + B )  AB
A + (B + C )  ( A + B ) + C

Pavithran Puthiyapurayil , Maldives

4/30/2018 12
National University
 OR Gate
Current flows if either switch is closed
– Logic notation A + B = C

A B C
0 0 0
0 1 1
1 0 1
1 1 1
Pavithran Puthiyapurayil , Maldives
4/30/2018 13
National University
 AND Gate
In order for current to flow, both switches must
be closed
– Logic notation AB = C
(Sometimes AB = C)

A B C
0 0 0
0 1 0
1 0 0
1 1 1
Pavithran Puthiyapurayil , Maldives
4/30/2018 14
National University
 Properties of AND and OR
• Commutation
oA+B=B+A
oAB=BA

Same as

Same as

Pavithran Puthiyapurayil , Maldives

4/30/2018 15
National University
 Commutation Circuit

AB BA

A+B B+A

Pavithran Puthiyapurayil , Maldives

4/30/2018 16
National University
 Properties of AND and OR
• Associative Property
A + (B + C) = (A + B) + C

A  (B  C) = (A  B)  C

Pavithran Puthiyapurayil , Maldives

4/30/2018 17
National University
 Distributive Property
(A + B)  (A + C)

A B C Q
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1
Pavithran Puthiyapurayil , Maldives 1 1 1
4/30/2018 18
National University
 Binary Addition

A B S C(arry)
0 0 0 0
1 0 1 0
0 1 1 0
1 1 0 1

Notice that the carry results are the same as AND

C=AB
Pavithran Puthiyapurayil , Maldives
4/30/2018 19
National University
 Inversion (NOT)

A Q

0 1
Logic: QA
1 0

Pavithran Puthiyapurayil , Maldives

4/30/2018 20
National University
 Circuit for XOR

AÅB  AB + A B
Accumulating our results: Binary addition is the
result of XOR plus AND
Pavithran Puthiyapurayil , Maldives
4/30/2018 21
National University
Converting between circuits and equations

• Find the output of the following circuit

x x+y
y (x+y)y

y y

__
• Answer: (x+y)y
– Or (xy)y
4/30/2018
Pavithran Puthiyapurayil , Maldives
National University
22
Converting between circuits and equations

• Find the output of the following circuit

x
x xy xy
y
y
___
__
• Answer: xy
– Or (xy) ≡ xy
4/30/2018
Pavithran Puthiyapurayil , Maldives
National University
23
Converting between circuits and equations

• Write the circuits for the following Boolean

algebraic expressions
__
a) x+y

x x+y
x
y

Pavithran Puthiyapurayil , Maldives

4/30/2018 24
National University
Converting between circuits and equations

• Write the circuits for the following Boolean

algebraic
_______
expressions
b) (x+y)x

x x+y
x+y (x+y)x
y

Pavithran Puthiyapurayil , Maldives

4/30/2018 25
National University
 Writing xor using and/or/not
• p Å q  (p  q)  ¬(p  q) x y xÅy
____
1 1 0
• x Å y  (x + y)(xy) 1 0 1
0 1 1
0 0 0

x x+y (x+y)(xy)
y
xy xy
Pavithran Puthiyapurayil , Maldives
4/30/2018 26
National University
 Converting decimal numbers to binary
• 53 = 32 + 16 + 4 + 1
= 25 + 24 + 22 + 20
= 1*25 + 1*24 + 0*23 + 1*22 + 0*21 + 1*20
= 110101 in binary
= 00110101 as a full byte in binary

• 211= 128 + 64 + 16 + 2 + 1
= 27 + 26 + 24 + 21 + 20
= 1*27 + 1*26 + 0*25 + 1*24 + 0*23 + 0*22 +
1*21 + 1*20
= 11010011 in binary

Pavithran Puthiyapurayil , Maldives

4/30/2018 27
National University
 Converting binary numbers to decimal
• What is 10011010 in decimal?
10011010 = 1*27 + 0*26 + 0*25 + 1*24 + 1*23 +
0*22 + 1*21 + 0*20
= 27 + 24 + 23 + 21
= 128 + 16 + 8 + 2
= 154

• What is 00101001 in decimal?

00101001 = 0*27 + 0*26 + 1*25 + 0*24 + 1*23 +
0*22 + 0*21 + 1*20
= 25 + 23 + 20
= 32 + 8 + 1
= 41
Pavithran Puthiyapurayil , Maldives
4/30/2018 28
National University
 A note on binary numbers
• In this slide set we are only dealing with non-
negative numbers
• The book (section 1.5) talks about two’s-
complement binary numbers
– Positive (and zero) two’s-complement binary
numbers is what was presented here
– We won’t be getting into negative two’s-
complmeent numbers

Pavithran Puthiyapurayil , Maldives

4/30/2018 29
National University
 How to add binary numbers
• Consider adding two 1-bit binary numbers x and y
– 0+0 = 0
– 0+1 = 1
– 1+0 = 1 x y Carry Sum
– 1+1 = 10 0 0 0 0
0 1 0 1
1 0 0 1
• Carry is x AND y 1 1 1 0
• Sum is x XOR y
• The circuit to compute this is called a half-adder

Pavithran Puthiyapurayil , Maldives

4/30/2018 30
National University
 The half-adder
x y Carry Sum
• Sum = x XOR y 0 0 0 0
• Carry = x AND y 0 1 0 1
1 0 0 1
1 1 1 0

x x
y y Sum
Sum
Carry
Carry
Pavithran Puthiyapurayil , Maldives
4/30/2018 31
National University
 Using half adders
• We can then use a half-adder to compute the
sum of two Boolean numbers

1 0 0
1 1 0 0
+1 1 1 0
? 0 1 0

Pavithran Puthiyapurayil , Maldives

4/30/2018 32
National University
 How to fix this
• We need to create an adder that can take a carry bit
as an additional input
– Inputs: x, y, carry in x y c carry sum
– Outputs: sum, carry out 1 1 1 1 1
• This is called a full adder 1 1 0 1 0
– Will add x and y with a half-adder 1 0 1 1 0
– Will add the sum of that to the
carry in 1 0 0 0 1
• What about the carry out? 0 1 1 1 0
– It’s 1 if either (or both): 0 1 0 0 1
– x+y = 10
0 0 1 0 1
– x+y = 01 and carry in = 1
0 0 0 0 0
Pavithran Puthiyapurayil , Maldives
4/30/2018 33
National University
 x y c s1 c1 carry sum
The full adder 1 1 1 0 1 1 1
1 1 0 0 1 1 0
1 0 1 1 0 1 0
• The “HA” boxes are
1 0 0 1 0 0 1
half-adders
0 1 1 1 0 1 0
0 1 0 1 0 0 1
0 0 1 0 0 0 1
0 0 0 0 0 0 0

c X HA S
S
s
Y C
C
s1
x X HA S

c
y
Y C

c1
Pavithran Puthiyapurayil , Maldives
4/30/2018 34
National University
 The full adder
• The full circuitry of the full adder

c
s

x
y
c

Pavithran Puthiyapurayil , Maldives

4/30/2018 35
National University
 Adding bigger binary numbers
• Just chain full adders together

x0 X HA S
s0
y0 Y C

x1
C

X
FA S
s1
y1 Y C

x2
C

X
FA S
s2
y2 Y C

x3
C

X
FA S
s3
y3 Y C
c
...

Pavithran Puthiyapurayil , Maldives

4/30/2018 36
National University
 Adding bigger binary numbers
• A half adder has 4 logic gates
• A full adder has two half adders plus a OR gate
– Total of 9 logic gates
• To add n bit binary numbers, you need 1 HA and n-1
FAs
• To add 32 bit binary numbers, you need 1 HA and 31
FAs
– Total of 4+9*31 = 283 logic gates
• To add 64 bit binary numbers, you need 1 HA and 63
FAs
– Total of 4+9*63 = 571 logic gates

Pavithran Puthiyapurayil , Maldives

4/30/2018 37
National University
 More about logic gates
• To implement a logic gate in hardware, you
use a transistor
• Transistors are all enclosed in an “IC”, or
integrated circuit
• The current Intel Pentium IV processors have
55 million transistors!

Pavithran Puthiyapurayil , Maldives

4/30/2018 38
National University
 Flip-flops
• Consider the following circuit:

• What does it do?

Pavithran Puthiyapurayil , Maldives
4/30/2018 39
National University
 Memory
• A flip-flop holds a single bit of memory
– The bit “flip-flops” between the two NAND gates
• In reality, flip-flops are a bit more
complicated
– Have 5 (or so) logic gates (transistors) per flip-flop
• Consider a 1 Gb memory chip
– 1 Gb = 8,589,934,592 bits of memory
– That’s about 43 million transistors!
• In reality, those transistors are split into 9 ICs
of about 5 million transistors each

Pavithran Puthiyapurayil , Maldives

4/30/2018 40
National University
Hexadecimal
• A numerical range from
0-15
– Where A is 10, B is 11, …
and F is 15
• Often written with a ‘0x’
prefix
• So 0x10 is 10 hex, or 16
– 0x100 is 100 hex, or 256
• Binary numbers easily
translate:

Pavithran Puthiyapurayil , Maldives

4/30/2018 41
National University