Chapter2
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Chapter2 as PDF for free.
More details
- Words: 4,713
- Pages: 44
Logic Elements Switch, Gate, Boolean Algebra Sukree Sinthupinyo Department of Computer Science Thammasat University
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 1/44
Switches ● Electric Circuit ● Electric Circuit ● Physical Switches: Relay ● Physical Switches: Transistor Logic Gates Gate-Level Circuits
Switches
Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 2/44
Electric Circuit
Switches
■
● Electric Circuit ● Electric Circuit ● Physical Switches: Relay ● Physical Switches: Transistor
■
Logic Gates Gate-Level Circuits Boolean Algebra
■
Sukree Sinthupinyo, December 12, 2006
Most familiar example of a switch: device that controls the flow of current through an electric circuit A light fixture L is to be connected to the electric power supply P S and to a manual switch S2 ◆ Turning S2 on and off turns the light on and off A circuit breaker S1 is to be installed near the entry point of the power supply. ◆ Turning S1 off will turn L off, independently of S2
Logic Elements - p. 3/44
Electric Circuit
Switches ● Electric Circuit ● Electric Circuit ● Physical Switches: Relay ● Physical Switches: Transistor Logic Gates Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 4/44
Physical Switches: Relay
Switches
■
● Electric Circuit ● Electric Circuit ● Physical Switches: Relay ● Physical Switches: Transistor Logic Gates
■
Gate-Level Circuits Boolean Algebra
■
Sukree Sinthupinyo, December 12, 2006
Electromechanical Relay contains an electromagnet that consists of a wire coil wrapped around a magnetizable iron core Input variable x of the relay is an electric current applied to the coil Activate by an electric x = 1
Logic Elements - p. 5/44
Physical Switches: Transistor
Switches
■
● Electric Circuit ● Electric Circuit ● Physical Switches: Relay ● Physical Switches: Transistor
■
Logic Gates
■
Gate-Level Circuits Boolean Algebra
■
Sukree Sinthupinyo, December 12, 2006
This particular transistor is of a type known as metal-oxide semiconductor-MOS Input variable x is an electric voltage {VL , VH } Output variable z is an electric current that takes the binary values {IL , IH } It’s more practical when dealing with MOS transistor circuits to treat x and z as binary voltages that assume the same set of values {VL , VH }
Logic Elements - p. 6/44
Switches Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate
Logic Gates
● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate ● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 7/44
A General Definition
Switches
■
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate
In general, a logic gate G is a switching circuit characterized by the following parameters: ◆ A set of n binary input signals or variables X = (x1 , x2 , . . . , xn ), where each xi is 0 or 1, and n ranges from 1 to 10 or so ◆ A single binary output signal z ◆ A function f from X to z that may be expressed as
● NOR Gate
z = f (X) = f (x1 , x2 , . . . , xn )
● EXCLUSIVE-OR Gate ● XOR Gate ● XOR Gate Gate-Level Circuits
◆
and is one of about six basic types
Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 8/44
Single-Input Gates
Switches
■
Buffer ◆ Output z is 1 whenever the input x is 1; z is 0 whenever x is 0 z=x
■
Inverter or NOT gate ◆ Output z is 0 whenever the input x is 1; z is 1 whenever x is 0 zN OT = x ¯
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate ● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 9/44
Single-Input Gates
Switches Logic Gates ● A General Definition ● Single-Input Gates
x
z
x
z
● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate
Buffer
Inverter
● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate ● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 10/44
Single-Input Gates
Switches
■
Buffer
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate
Input x 0 1
Output z 0 1
Input x 0 1
Output z 1 0
● Or Gate ● NAND and NOR Gate ● NAND Gate
■
● NOR Gate ● EXCLUSIVE-OR Gate ● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Inverter or NOT gate
Logic Elements - p. 11/44
And Gate
Switches
■
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates
■
● Single-Input Gates ● And Gate ● And Gate ● Or Gate
■
● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate
The output of And Gate is 1 if and only if x1 is 1 and x2 is 1 and . . . xn is 1. In other word, z is 0 if at least one input is 0: it is 1 if all inputs are 1. It can be interprested as the multiplication of a set of 1-bit numbers; a 0 among the input values makes the result (product) 0
● EXCLUSIVE-OR Gate ● XOR Gate ● XOR Gate
zAN D (x1 , x2 , . . . , xn ) = x1 x2 . . . xn
Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 12/44
And Gate
Switches
■
Truth table
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate
x1 0 0 0 0
x2 0 0 0 0
1 1
1 1
● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Input . . . xn−1 ... 0 ... 0 ... 1 ... 1 ... ... 1 ... 1
xn 0 1 0 1
Output z 0 0 0 0
0 1
0 1
x1 x2 xn Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 13/44
Or Gate
Switches
■
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates
■
● Single-Input Gates ● And Gate ● And Gate ● Or Gate
■
● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate ● XOR Gate
The output of Or Gate is 1 if and only if x1 is 1 or x2 is 1 or . . . xn is 1. In other word, z is 1 if at least one input is 1: it is 0 if all inputs are 0. It can be interprested as the summation of a set of 1-bit numbers; a 0 among the input values makes the result (sum) 0 zOR (x1 , x2 , . . . , xn ) = x1 + x2 · · · + xn
● XOR Gate Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 14/44
Or Gate
Switches
■
Truth table
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate
x1 0 0 0 0
x2 0 0 0 0
1 1
1 1
● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Input . . . xn−1 ... 0 ... 0 ... 1 ... 1 ... ... 1 ... 1
xn 0 1 0 1
Output z 0 1 1 1
0 1
1 1
x1 x2 xn Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 15/44
NAND and NOR Gate
Switches
■
Append NOT to AND and OR, respectively.
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate
zN AN D (x1 , x2 , . . . , xn ) = x1 x2 . . . xn zN OR (x1 , x2 , . . . , xn ) = x1 + x2 + · · · + xn
● And Gate ● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate ● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 16/44
NAND Gate
Switches
■
Truth table
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate
x1 0 0 0 0
x2 0 0 0 0
1 1
1 1
● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Input . . . xn−1 ... 0 ... 0 ... 1 ... 1 ... ... 1 ... 1
xn 0 1 0 1
Output z 1 1 1 1
0 1
1 0
x1 x2 xn Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 17/44
NOR Gate
Switches
■
Truth table
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate
x1 0 0 0 0
x2 0 0 0 0
1 1
1 1
● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Input . . . xn−1 ... 0 ... 0 ... 1 ... 1 ... ... 1 ... 1
xn 0 1 0 1
Output z 1 0 0 0
0 1
0 0
x1 x2 xn Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 18/44
EXCLUSIVE-OR Gate
Switches
■
Logic Gates ● A General Definition
EXCLUSIVE-OR is easily specified in terms of the parity of the number of 1s among the n input variables:
● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate
if and odd number of inputs are 1
● Or Gate ● NAND and NOR Gate ● NAND Gate
zXOR (x1 , x2 , . . . , xn ) = 1
● NOR Gate ● EXCLUSIVE-OR Gate ● XOR Gate
otherwise
● XOR Gate Gate-Level Circuits
zXOR (x1 , x2 , . . . , xn ) = 0
Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 19/44
XOR Gate
Switches
■
Truth table
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate
x1 0 0 0 0
x2 0 0 0 0
1 1
1 1
● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Input . . . xn−1 ... 0 ... 0 ... 1 ... 1 ... ... 1 ... 1
xn 0 1 0 1
Output z 0 1 1 0
0 1
1 0
Logic Elements - p. 20/44
XOR Gate
Switches
■
Logic Gates ● A General Definition
XOR zXOR (x1 , x2 , . . . , xn ) = x1 ⊕ x2 ⊕ · · · ⊕ xn
● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate
x1 x2
● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate
xn
● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 21/44
Switches Logic Gates Gate-Level Circuits ● Combinational Circuits ● Gate-level design for a full adder ● Full adder ● Gate-level design for a full adder ● Fan-in and Fan-out
Gate-Level Circuits
● Meeting Fan-in and Fan-out ● Meeting Fan-in and Fan-out Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 22/44
Combinational Circuits
Switches
■
Logic Gates Gate-Level Circuits ● Combinational Circuits
■
● Gate-level design for a full adder ● Full adder ● Gate-level design for a full adder ● Fan-in and Fan-out ● Meeting Fan-in and Fan-out ● Meeting Fan-in and Fan-out Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Combinational Circuits are obtained by connecting two or more gates, if their time-dependent behavior is ignored. An n-input, m-output combinational circuit N is a multigate circuit that realizes a set of m ≥ 1 functions: F = (f1 (X), f2 (X), . . . , fm (X) where X = (x1 , x2 , . . . , xn ) and each fi is a binary function of the form fi : X → zi for 1 ≥ i ≥ m
Logic Elements - p. 23/44
Gate-level design for a full adder
Switches
■
Logic Gates
■
Gate-Level Circuits ● Combinational Circuits
■
● Gate-level design for a full adder ● Full adder ● Gate-level design for a full adder ● Fan-in and Fan-out
Three-input, two-output combinational circuit F (X) = (f1 (x1 , x2 , x3 ), f2 (x1 , x2 , x3 )) This full adder consists of three AND gates, an OR gate, and an EXCLUSIVE-OR gate. x1
y1
x2
y2
x3
y3
● Meeting Fan-in and Fan-out ● Meeting Fan-in and Fan-out Boolean Algebra
f1 (carry)
f2 (sum)
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 24/44
Full adder
Switches
■
We can define these five equations:
Logic Gates Gate-Level Circuits ● Combinational Circuits ● Gate-level design for a full adder ● Full adder ● Gate-level design for a full adder ● Fan-in and Fan-out ● Meeting Fan-in and Fan-out ● Meeting Fan-in and Fan-out
f1 y1 y2 y3
= y1 + y2 + y3 = x1 x2 = x2 x3 = x1 x3
f2 = x1 ⊕ x2 ⊕ x3
Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 25/44
Gate-level design for a full adder
Switches
■
Truth table
Logic Gates Gate-Level Circuits ● Combinational Circuits ● Gate-level design for a full adder ● Full adder ● Gate-level design for a full adder ● Fan-in and Fan-out ● Meeting Fan-in and Fan-out ● Meeting Fan-in and Fan-out Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
x1 0 0 0 0 1 1 1 1
Input x2 0 0 1 1 0 0 1 1
x3 0 1 0 1 0 1 0 1
Output f1 f2 0 0 0 1 0 1 1 0 0 1 1 0 1 0 1 1
Logic Elements - p. 26/44
Fan-in and Fan-out
Switches
■
Logic Gates Gate-Level Circuits ● Combinational Circuits ● Gate-level design for a full adder ● Full adder ● Gate-level design for a full adder ● Fan-in and Fan-out ● Meeting Fan-in and Fan-out ● Meeting Fan-in and Fan-out
■
Boolean Algebra
■
Sukree Sinthupinyo, December 12, 2006
A physical device can absorb or produce only certain amount of energy without failing ◆ This places an upper bound on the number of input sources that may supply isgnals to a gate G. ◆ And also palce the maximum number of output devices that may be supplied with signals by G’s output line. The number of input lines connected from other gates of G is termed its fan-in. The number of output lines connected to other gates is termed its fan-out.
Logic Elements - p. 27/44
Meeting Fan-in and Fan-out
Switches Logic Gates Gate-Level Circuits ● Combinational Circuits ● Gate-level design for a full adder ● Full adder ● Gate-level design for a full adder ● Fan-in and Fan-out ● Meeting Fan-in and Fan-out ● Meeting Fan-in and Fan-out Boolean Algebra
Figure 1: Increasing fan-in
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 28/44
Meeting Fan-in and Fan-out
Switches Logic Gates Gate-Level Circuits ● Combinational Circuits ● Gate-level design for a full adder ● Full adder ● Gate-level design for a full adder ● Fan-in and Fan-out ● Meeting Fan-in and Fan-out ● Meeting Fan-in and Fan-out Boolean Algebra
1 1 1 1 Figure 2: Decreasing fan-in Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 29/44
Switches Logic Gates Gate-Level Circuits Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
Boolean Algebra
of of of of of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 30/44
Basic Operations
Switches
■
Logic Gates
■
Gate-Level Circuits
■ Boolean Algebra
¯0 = 1 and ¯1 = 0 0 · 0 = 0, 0 · 1 = 0, 1 · 0 = 0, 1 · 1 = 1 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 1
● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of of of of of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 31/44
Boolean Expressions
■
Switches Logic Gates Gate-Level Circuits
■
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of
■
of of
■
of of of
Boolean expressions are formed by application of basic operations to one or more variables or constants. The simplest consists of a single constant or variable, such as 0, X, or Y¯ More complicated using AND or OR, or by complementing another expression. Examples of expressions are: ¯ +C AB A(C + D) + BC
of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 32/44
Axioms&Theorems of Boolean algebra
■
Switches
Identity
Logic Gates
X +0=X
Gate-Level Circuits
X ·1=X
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of
■
Null
of
X +1=1
of
X ·0=0
of of of
■
of
● Formal Proofs ● Well-Formed Expression
Idempotency X +X =X X ·X =X
● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 33/44
Axioms&Theorems of Boolean algebra
■
Switches
Involution law
Logic Gates
¯ =X X
Gate-Level Circuits
(X ′ )′ = X
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of
■
Complementariy
of
¯ =1 X +X ¯ =0 X ·X
of of of of
■
Commutativity
of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
X +Y =Y +X X ·Y =Y ·X
Logic Elements - p. 34/44
Axioms&Theorems of Boolean algebra
■
Switches
Associativity
Logic Gates
(X + Y ) + Z = X + (Y + Z)
Gate-Level Circuits
(X · Y ) · Z = X · (Y · Z)
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of
■
Distributivity
of of of
X · (Y + Z) = (X · Y ) + (X · Z) X + (Y · Z) = (X + Y ) · (X + Z)
of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 35/44
Axioms&Theorems of Boolean algebra
■
Switches
Uniting
Logic Gates
(X · Y ) + (X · Y ′ ) = X · (Y + Y ′ )
Gate-Level Circuits
=X ·1
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of
=X
of of of of of
(X + Y ) · (X + Y ′ ) = X + (Y · Y ′ ) =X +0 =X
of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 36/44
Axioms&Theorems of Boolean algebra
■
Switches
Absorption
Logic Gates
X +X ·Y =X
Gate-Level Circuits
X · (X + Y ) = X
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of of of of
(X + Y ′ ) · Y = X · Y (X · Y ′ ) + Y = X + Y
of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 37/44
Axioms&Theorems of Boolean algebra
■
Switches
Factoring
Logic Gates
(X + Y ) · (X ′ + Z) = X · Z + X ′ · Y
Gate-Level Circuits
X · Y + X ′ · Z = (X + Z) · (X ′ + Y )
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of
■
Concensus
of of of
X · Y + Y · Z + X′ · Z = X · Y + X′ · Z (X + Y ) · (Y + Z) · (X ′ + Z) = (X + Y ) · (X ′ + Z)
of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 38/44
Axioms&Theorems of Boolean algebra
■
Switches
de Morgan’s
Logic Gates
(X + Y + . . . )′ = (X ′ · Y ′ . . . )
Gate-Level Circuits
(X · Y · . . . )′ = (X ′ + Y ′ + . . . )
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of of of of of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 39/44
Informal Proofs
■
Switches Logic Gates Gate-Level Circuits
■
We can interpret the theorems into terms of logic circuits or set theory. For example: A · A = A and A + A = A
Boolean Algebra
b=a
● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of
a
b=a a
of of
c=a
c=a
of of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 40/44
Formal Proofs
■
Switches
A+A=A
Logic Gates
A+A=A
Gate-Level Circuits
(A + A) · 1 = A
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of of
(A + A) · (A + A′ ) = A A · A + A · A′ + A · A + A · A′ = A
of of of of
A+0+A+0=A A+0=A A=A
of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 41/44
Well-Formed Expression
■
Switches Logic Gates Gate-Level Circuits Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of of of of of
Let β be a Boolean algebra with element set K and operator set θ = {+, ·, ′} ◆ The simplest valid or well-formed (WF) Boolean expression on β is a single variable or constant symbol, where a constant is any member of K. ◆ We can construct general WF expressions by repeated application of the following recursive rule: ■ If E1 , E2 , . . . , Ek are WF boolean expressions, then so are all expressions of the form (E1 + E2 + · · · + Ek ), (E1 E2 . . . Ek ), (E¯1 )
of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 42/44
Fully Parenthesized WF: FPWF
■
Switches Logic Gates
FPWF is WFs that use parentheses to define the scope of each AN D, OR, and N OT operations.
Gate-Level Circuits Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of of of of of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 43/44
Axioms&Theorems of Boolean algebra
■
Switches Logic Gates Gate-Level Circuits Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of of
Duality ◆ Dual of a Boolean expression is derived by replacing · by +, + by ·, 0 by 1, and 1 by 0, and leaving variables unchanged ◆ Any theorem that can be proven is thus also proven for its dual! ◆ Meta-theorem (a theorem about theorems)
of of of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 44/44
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 1/44
Switches ● Electric Circuit ● Electric Circuit ● Physical Switches: Relay ● Physical Switches: Transistor Logic Gates Gate-Level Circuits
Switches
Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 2/44
Electric Circuit
Switches
■
● Electric Circuit ● Electric Circuit ● Physical Switches: Relay ● Physical Switches: Transistor
■
Logic Gates Gate-Level Circuits Boolean Algebra
■
Sukree Sinthupinyo, December 12, 2006
Most familiar example of a switch: device that controls the flow of current through an electric circuit A light fixture L is to be connected to the electric power supply P S and to a manual switch S2 ◆ Turning S2 on and off turns the light on and off A circuit breaker S1 is to be installed near the entry point of the power supply. ◆ Turning S1 off will turn L off, independently of S2
Logic Elements - p. 3/44
Electric Circuit
Switches ● Electric Circuit ● Electric Circuit ● Physical Switches: Relay ● Physical Switches: Transistor Logic Gates Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 4/44
Physical Switches: Relay
Switches
■
● Electric Circuit ● Electric Circuit ● Physical Switches: Relay ● Physical Switches: Transistor Logic Gates
■
Gate-Level Circuits Boolean Algebra
■
Sukree Sinthupinyo, December 12, 2006
Electromechanical Relay contains an electromagnet that consists of a wire coil wrapped around a magnetizable iron core Input variable x of the relay is an electric current applied to the coil Activate by an electric x = 1
Logic Elements - p. 5/44
Physical Switches: Transistor
Switches
■
● Electric Circuit ● Electric Circuit ● Physical Switches: Relay ● Physical Switches: Transistor
■
Logic Gates
■
Gate-Level Circuits Boolean Algebra
■
Sukree Sinthupinyo, December 12, 2006
This particular transistor is of a type known as metal-oxide semiconductor-MOS Input variable x is an electric voltage {VL , VH } Output variable z is an electric current that takes the binary values {IL , IH } It’s more practical when dealing with MOS transistor circuits to treat x and z as binary voltages that assume the same set of values {VL , VH }
Logic Elements - p. 6/44
Switches Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate
Logic Gates
● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate ● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 7/44
A General Definition
Switches
■
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate
In general, a logic gate G is a switching circuit characterized by the following parameters: ◆ A set of n binary input signals or variables X = (x1 , x2 , . . . , xn ), where each xi is 0 or 1, and n ranges from 1 to 10 or so ◆ A single binary output signal z ◆ A function f from X to z that may be expressed as
● NOR Gate
z = f (X) = f (x1 , x2 , . . . , xn )
● EXCLUSIVE-OR Gate ● XOR Gate ● XOR Gate Gate-Level Circuits
◆
and is one of about six basic types
Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 8/44
Single-Input Gates
Switches
■
Buffer ◆ Output z is 1 whenever the input x is 1; z is 0 whenever x is 0 z=x
■
Inverter or NOT gate ◆ Output z is 0 whenever the input x is 1; z is 1 whenever x is 0 zN OT = x ¯
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate ● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 9/44
Single-Input Gates
Switches Logic Gates ● A General Definition ● Single-Input Gates
x
z
x
z
● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate
Buffer
Inverter
● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate ● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 10/44
Single-Input Gates
Switches
■
Buffer
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate
Input x 0 1
Output z 0 1
Input x 0 1
Output z 1 0
● Or Gate ● NAND and NOR Gate ● NAND Gate
■
● NOR Gate ● EXCLUSIVE-OR Gate ● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Inverter or NOT gate
Logic Elements - p. 11/44
And Gate
Switches
■
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates
■
● Single-Input Gates ● And Gate ● And Gate ● Or Gate
■
● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate
The output of And Gate is 1 if and only if x1 is 1 and x2 is 1 and . . . xn is 1. In other word, z is 0 if at least one input is 0: it is 1 if all inputs are 1. It can be interprested as the multiplication of a set of 1-bit numbers; a 0 among the input values makes the result (product) 0
● EXCLUSIVE-OR Gate ● XOR Gate ● XOR Gate
zAN D (x1 , x2 , . . . , xn ) = x1 x2 . . . xn
Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 12/44
And Gate
Switches
■
Truth table
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate
x1 0 0 0 0
x2 0 0 0 0
1 1
1 1
● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Input . . . xn−1 ... 0 ... 0 ... 1 ... 1 ... ... 1 ... 1
xn 0 1 0 1
Output z 0 0 0 0
0 1
0 1
x1 x2 xn Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 13/44
Or Gate
Switches
■
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates
■
● Single-Input Gates ● And Gate ● And Gate ● Or Gate
■
● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate ● XOR Gate
The output of Or Gate is 1 if and only if x1 is 1 or x2 is 1 or . . . xn is 1. In other word, z is 1 if at least one input is 1: it is 0 if all inputs are 0. It can be interprested as the summation of a set of 1-bit numbers; a 0 among the input values makes the result (sum) 0 zOR (x1 , x2 , . . . , xn ) = x1 + x2 · · · + xn
● XOR Gate Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 14/44
Or Gate
Switches
■
Truth table
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate
x1 0 0 0 0
x2 0 0 0 0
1 1
1 1
● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Input . . . xn−1 ... 0 ... 0 ... 1 ... 1 ... ... 1 ... 1
xn 0 1 0 1
Output z 0 1 1 1
0 1
1 1
x1 x2 xn Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 15/44
NAND and NOR Gate
Switches
■
Append NOT to AND and OR, respectively.
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate
zN AN D (x1 , x2 , . . . , xn ) = x1 x2 . . . xn zN OR (x1 , x2 , . . . , xn ) = x1 + x2 + · · · + xn
● And Gate ● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate ● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 16/44
NAND Gate
Switches
■
Truth table
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate
x1 0 0 0 0
x2 0 0 0 0
1 1
1 1
● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Input . . . xn−1 ... 0 ... 0 ... 1 ... 1 ... ... 1 ... 1
xn 0 1 0 1
Output z 1 1 1 1
0 1
1 0
x1 x2 xn Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 17/44
NOR Gate
Switches
■
Truth table
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate
x1 0 0 0 0
x2 0 0 0 0
1 1
1 1
● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Input . . . xn−1 ... 0 ... 0 ... 1 ... 1 ... ... 1 ... 1
xn 0 1 0 1
Output z 1 0 0 0
0 1
0 0
x1 x2 xn Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 18/44
EXCLUSIVE-OR Gate
Switches
■
Logic Gates ● A General Definition
EXCLUSIVE-OR is easily specified in terms of the parity of the number of 1s among the n input variables:
● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate
if and odd number of inputs are 1
● Or Gate ● NAND and NOR Gate ● NAND Gate
zXOR (x1 , x2 , . . . , xn ) = 1
● NOR Gate ● EXCLUSIVE-OR Gate ● XOR Gate
otherwise
● XOR Gate Gate-Level Circuits
zXOR (x1 , x2 , . . . , xn ) = 0
Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 19/44
XOR Gate
Switches
■
Truth table
Logic Gates ● A General Definition ● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate ● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate
x1 0 0 0 0
x2 0 0 0 0
1 1
1 1
● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Input . . . xn−1 ... 0 ... 0 ... 1 ... 1 ... ... 1 ... 1
xn 0 1 0 1
Output z 0 1 1 0
0 1
1 0
Logic Elements - p. 20/44
XOR Gate
Switches
■
Logic Gates ● A General Definition
XOR zXOR (x1 , x2 , . . . , xn ) = x1 ⊕ x2 ⊕ · · · ⊕ xn
● Single-Input Gates ● Single-Input Gates ● Single-Input Gates ● And Gate ● And Gate ● Or Gate
x1 x2
● Or Gate ● NAND and NOR Gate ● NAND Gate ● NOR Gate ● EXCLUSIVE-OR Gate
xn
● XOR Gate ● XOR Gate Gate-Level Circuits Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 21/44
Switches Logic Gates Gate-Level Circuits ● Combinational Circuits ● Gate-level design for a full adder ● Full adder ● Gate-level design for a full adder ● Fan-in and Fan-out
Gate-Level Circuits
● Meeting Fan-in and Fan-out ● Meeting Fan-in and Fan-out Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 22/44
Combinational Circuits
Switches
■
Logic Gates Gate-Level Circuits ● Combinational Circuits
■
● Gate-level design for a full adder ● Full adder ● Gate-level design for a full adder ● Fan-in and Fan-out ● Meeting Fan-in and Fan-out ● Meeting Fan-in and Fan-out Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Combinational Circuits are obtained by connecting two or more gates, if their time-dependent behavior is ignored. An n-input, m-output combinational circuit N is a multigate circuit that realizes a set of m ≥ 1 functions: F = (f1 (X), f2 (X), . . . , fm (X) where X = (x1 , x2 , . . . , xn ) and each fi is a binary function of the form fi : X → zi for 1 ≥ i ≥ m
Logic Elements - p. 23/44
Gate-level design for a full adder
Switches
■
Logic Gates
■
Gate-Level Circuits ● Combinational Circuits
■
● Gate-level design for a full adder ● Full adder ● Gate-level design for a full adder ● Fan-in and Fan-out
Three-input, two-output combinational circuit F (X) = (f1 (x1 , x2 , x3 ), f2 (x1 , x2 , x3 )) This full adder consists of three AND gates, an OR gate, and an EXCLUSIVE-OR gate. x1
y1
x2
y2
x3
y3
● Meeting Fan-in and Fan-out ● Meeting Fan-in and Fan-out Boolean Algebra
f1 (carry)
f2 (sum)
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 24/44
Full adder
Switches
■
We can define these five equations:
Logic Gates Gate-Level Circuits ● Combinational Circuits ● Gate-level design for a full adder ● Full adder ● Gate-level design for a full adder ● Fan-in and Fan-out ● Meeting Fan-in and Fan-out ● Meeting Fan-in and Fan-out
f1 y1 y2 y3
= y1 + y2 + y3 = x1 x2 = x2 x3 = x1 x3
f2 = x1 ⊕ x2 ⊕ x3
Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 25/44
Gate-level design for a full adder
Switches
■
Truth table
Logic Gates Gate-Level Circuits ● Combinational Circuits ● Gate-level design for a full adder ● Full adder ● Gate-level design for a full adder ● Fan-in and Fan-out ● Meeting Fan-in and Fan-out ● Meeting Fan-in and Fan-out Boolean Algebra
Sukree Sinthupinyo, December 12, 2006
x1 0 0 0 0 1 1 1 1
Input x2 0 0 1 1 0 0 1 1
x3 0 1 0 1 0 1 0 1
Output f1 f2 0 0 0 1 0 1 1 0 0 1 1 0 1 0 1 1
Logic Elements - p. 26/44
Fan-in and Fan-out
Switches
■
Logic Gates Gate-Level Circuits ● Combinational Circuits ● Gate-level design for a full adder ● Full adder ● Gate-level design for a full adder ● Fan-in and Fan-out ● Meeting Fan-in and Fan-out ● Meeting Fan-in and Fan-out
■
Boolean Algebra
■
Sukree Sinthupinyo, December 12, 2006
A physical device can absorb or produce only certain amount of energy without failing ◆ This places an upper bound on the number of input sources that may supply isgnals to a gate G. ◆ And also palce the maximum number of output devices that may be supplied with signals by G’s output line. The number of input lines connected from other gates of G is termed its fan-in. The number of output lines connected to other gates is termed its fan-out.
Logic Elements - p. 27/44
Meeting Fan-in and Fan-out
Switches Logic Gates Gate-Level Circuits ● Combinational Circuits ● Gate-level design for a full adder ● Full adder ● Gate-level design for a full adder ● Fan-in and Fan-out ● Meeting Fan-in and Fan-out ● Meeting Fan-in and Fan-out Boolean Algebra
Figure 1: Increasing fan-in
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 28/44
Meeting Fan-in and Fan-out
Switches Logic Gates Gate-Level Circuits ● Combinational Circuits ● Gate-level design for a full adder ● Full adder ● Gate-level design for a full adder ● Fan-in and Fan-out ● Meeting Fan-in and Fan-out ● Meeting Fan-in and Fan-out Boolean Algebra
1 1 1 1 Figure 2: Decreasing fan-in Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 29/44
Switches Logic Gates Gate-Level Circuits Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
Boolean Algebra
of of of of of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 30/44
Basic Operations
Switches
■
Logic Gates
■
Gate-Level Circuits
■ Boolean Algebra
¯0 = 1 and ¯1 = 0 0 · 0 = 0, 0 · 1 = 0, 1 · 0 = 0, 1 · 1 = 1 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 1
● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of of of of of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 31/44
Boolean Expressions
■
Switches Logic Gates Gate-Level Circuits
■
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of
■
of of
■
of of of
Boolean expressions are formed by application of basic operations to one or more variables or constants. The simplest consists of a single constant or variable, such as 0, X, or Y¯ More complicated using AND or OR, or by complementing another expression. Examples of expressions are: ¯ +C AB A(C + D) + BC
of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 32/44
Axioms&Theorems of Boolean algebra
■
Switches
Identity
Logic Gates
X +0=X
Gate-Level Circuits
X ·1=X
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of
■
Null
of
X +1=1
of
X ·0=0
of of of
■
of
● Formal Proofs ● Well-Formed Expression
Idempotency X +X =X X ·X =X
● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 33/44
Axioms&Theorems of Boolean algebra
■
Switches
Involution law
Logic Gates
¯ =X X
Gate-Level Circuits
(X ′ )′ = X
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of
■
Complementariy
of
¯ =1 X +X ¯ =0 X ·X
of of of of
■
Commutativity
of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
X +Y =Y +X X ·Y =Y ·X
Logic Elements - p. 34/44
Axioms&Theorems of Boolean algebra
■
Switches
Associativity
Logic Gates
(X + Y ) + Z = X + (Y + Z)
Gate-Level Circuits
(X · Y ) · Z = X · (Y · Z)
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of
■
Distributivity
of of of
X · (Y + Z) = (X · Y ) + (X · Z) X + (Y · Z) = (X + Y ) · (X + Z)
of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 35/44
Axioms&Theorems of Boolean algebra
■
Switches
Uniting
Logic Gates
(X · Y ) + (X · Y ′ ) = X · (Y + Y ′ )
Gate-Level Circuits
=X ·1
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of
=X
of of of of of
(X + Y ) · (X + Y ′ ) = X + (Y · Y ′ ) =X +0 =X
of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 36/44
Axioms&Theorems of Boolean algebra
■
Switches
Absorption
Logic Gates
X +X ·Y =X
Gate-Level Circuits
X · (X + Y ) = X
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of of of of
(X + Y ′ ) · Y = X · Y (X · Y ′ ) + Y = X + Y
of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 37/44
Axioms&Theorems of Boolean algebra
■
Switches
Factoring
Logic Gates
(X + Y ) · (X ′ + Z) = X · Z + X ′ · Y
Gate-Level Circuits
X · Y + X ′ · Z = (X + Z) · (X ′ + Y )
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of
■
Concensus
of of of
X · Y + Y · Z + X′ · Z = X · Y + X′ · Z (X + Y ) · (Y + Z) · (X ′ + Z) = (X + Y ) · (X ′ + Z)
of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 38/44
Axioms&Theorems of Boolean algebra
■
Switches
de Morgan’s
Logic Gates
(X + Y + . . . )′ = (X ′ · Y ′ . . . )
Gate-Level Circuits
(X · Y · . . . )′ = (X ′ + Y ′ + . . . )
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of of of of of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 39/44
Informal Proofs
■
Switches Logic Gates Gate-Level Circuits
■
We can interpret the theorems into terms of logic circuits or set theory. For example: A · A = A and A + A = A
Boolean Algebra
b=a
● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of
a
b=a a
of of
c=a
c=a
of of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 40/44
Formal Proofs
■
Switches
A+A=A
Logic Gates
A+A=A
Gate-Level Circuits
(A + A) · 1 = A
Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of of
(A + A) · (A + A′ ) = A A · A + A · A′ + A · A + A · A′ = A
of of of of
A+0+A+0=A A+0=A A=A
of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 41/44
Well-Formed Expression
■
Switches Logic Gates Gate-Level Circuits Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of of of of of
Let β be a Boolean algebra with element set K and operator set θ = {+, ·, ′} ◆ The simplest valid or well-formed (WF) Boolean expression on β is a single variable or constant symbol, where a constant is any member of K. ◆ We can construct general WF expressions by repeated application of the following recursive rule: ■ If E1 , E2 , . . . , Ek are WF boolean expressions, then so are all expressions of the form (E1 + E2 + · · · + Ek ), (E1 E2 . . . Ek ), (E¯1 )
of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 42/44
Fully Parenthesized WF: FPWF
■
Switches Logic Gates
FPWF is WFs that use parentheses to define the scope of each AN D, OR, and N OT operations.
Gate-Level Circuits Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of of of of of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 43/44
Axioms&Theorems of Boolean algebra
■
Switches Logic Gates Gate-Level Circuits Boolean Algebra ● Basic Operations ● Boolean Expressions ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Axioms&Theorems Boolean algebra ● Informal Proofs
of of
Duality ◆ Dual of a Boolean expression is derived by replacing · by +, + by ·, 0 by 1, and 1 by 0, and leaving variables unchanged ◆ Any theorem that can be proven is thus also proven for its dual! ◆ Meta-theorem (a theorem about theorems)
of of of of of
● Formal Proofs ● Well-Formed Expression ● Fully Parenthesized WF: FPWF ● Axioms&Theorems of Boolean algebra
Sukree Sinthupinyo, December 12, 2006
Logic Elements - p. 44/44
