Computer Architecture I: Digital Design Dr. Robert D. Kent Lecture 2a Boolean Algebra & Calculus, Basic Gates, Digital Logic Boolean Logic First developed by George Boole (1850s) in a study of 2valued sets and their properties. He aimed to model intelligence and knowledge. Later realized to be of fundamental importance in the design and construction of digital logic devices, namely the computer (Claude Shannon - 1930s). The discovery of the transistor (npn and pnp junctions) and other solid-state microelectronic components (Josephson, Bardeen, Cooper et al) led to manufacture of basic gate devices that realized the various primitive logic operations not, and, or, xor, nand, nor, xnor Boolean Logic We will cover the following points, in order: Definitions and Mathematics Review of basic operations and their truth tables

Boolean postulates Boolean expressions Algebraic Simplification Gate (diagrammatic) representations for circuit layout & design Boolean Logic We emphasize that we are studying two-valued logic bits (0s and 1s) the operations that act on bits the calculus for manipulating the operators and expressions formed from them and the data being operated on Boolean Algebra - Mathematics A Boolean algebra is a system consisting of a set of elements, B, two binary operators (+ and ), parentheses to indicate the nested order of evaluation and an = operator to perform assignment of an expression. The algebra must further obey six fundamental postulates, or axioms: All theorems to be derived depend on the postulates. Postulates, or axioms, are the ground rules that underly everything there is to say (or derive) about a mathematical system Theorems are practical applications of postulates theorems can be proven based on the postulates Boolean Algebra - Mathematics

Postulates: P6: Existence There exist at least two elements x,y in B such that x y P1: Closure: There exists x,y in B such that two independent operations, . (dot) and + (plus) are defined: x + y in B x . y in B P2: Identity: There exist identity elements 0,1 in B relative to the operations + and . , such that for every x in B: 0+x = x+0 = x 1.x = x.1 = x P3: Commutativity: The operations + and . are commutative for all x,y in B: x + y = y + x x.y = y.x Boolean Algebra - Mathematics Postulates: (Continued) P4: Distributivity: Each operation + and . is distributive over the other; that is, for all x,y,z in B: x.(y + z) = x.y + x.Z x + (y.z) = (x+y).(x+z) P5: Complementation: For every element x in B there exists an element ~x, called the complement of x, satisfying: x + ~x = 1 x . ~x = 0

Very useful Theorem: Property of Idempotency: x+x = x x.x = x Boolean Algebra - Mathematics The various postulates satisfy a principle of duality, in that you obtain one form of postulate from the corresponding other one by interchanging the operations + and also the identity elements: Postulate Dual Postulate x+y x 0+x = x+0 = x x+y x+(y x + x THM: 1

y x =x = y+x x z) =(x+y) = 1 x+x (x+z) x x = x , and 1 = x y = y x (y+z) =(x x = 0 x

x = x y ) +( x z) Basic operations There are seven (7) commonly used Boolean, or logic, operations: not and nand or nor eor (xor) enor (xnor) Boolean Algebraic Representation It will be increasingly inconvenient to write out the Boolean operators using words. We therefore adopt the notations: Algebraic

Word form A ( A ) not A AB (A B) A+B A+B A and B A or B A xor B AB A+B A+B A nand B A nor B A xnor B Boolean Algebraic Representation It will be increasingly inconvenient to write out the Boolean operators using words. We therefore adopt the notations: Algebraic Word form

A ( A ) not A AB (A B) A+B A+B A and B A or B A xor B AB A+B A+B A nand B A nor B A xnor B Boolean Algebraic Representation Truth tables for the fundamental logic operations AxB B=0 1

A=0 0 1 1 1 0 (AxB) (A.B) B=0 1 A=0 1 1 1 1

0 B=0 1 A ~A (A) 0 1 1 0 A.B B=0 1 A=0 0 0

1 0 1 B=0 1 B=0 1 (A+B) A=0 1 0 A=0 1 0 A=0

0 1 1 0 1 1 0 0 1 1 1 A+B Theorems & Proof Techniques The circuits inside a computer involve a huge number (millions to billions) of individual data bits, each of which can provide input to an operation. To construct truth tables for such complex circuits is clearly impractical, if not impossible, given the huge number of variable

bits. Further, to prove that a circuit design is correct, or to simplify the expression of a circuit using truth tables is also clearly impractical. Theorems & Proof Techniques The methods of the Boolean Algebra, namely its calculus, provide general and powerful techniques for establishing the correctness of derived equivalent expressions for circuits simplifying the expressions to a more optimal form optimality, here, refers to both simplicity and elegance of expression and provision of more efficient execution in hardware. Theorems & Proof Techniques The cornerstones of Boolean Calculus are: Axioms Algebraic representation Theorems which lead to more complicated and powerful theorems. Proofs are established through the application and re-application of

the prior axioms and theorems, usually also based on the clever use and manipulation of the algebraic representation. Theorems & Proof Techniques REMEMBER! Mathematical proof is a formal and rigorous technique that must be practiced and studied seriously in order to develop into a natural and faithful tool. This is not just a hardware or logic design issue - it also appears in formal software engineering proofs of algorithmic correctness artificial intelligence genetic algorithms and many other places in computer science! Formal Proofs: Theorem 1 T1: The element X is uniquely determined by X, as in P5. Proof: Assume there are two elements X1 and X2, both determined by X. (Note: there can only be two in B)

it follows from P5 that X + X1 = 1 X X 1 = 0 The following steps apply: X 1 = X1 .1 = X1 .(X+X2) = X1 .X + X1 . X2 = X. X1 + X1 . X2 = 0 + X1 . X2 = X. X2 + X1 . X2 Since the original assumption X + was X2 = 1that X1 and X2 were different, we have proven the contradiction, namely that both X X 2 = 0 are identical and therefore X is uniquely determined by X. = X2 .X + X2 . X1 = X2 .(X + X1) = X2 .1 = X 2 So: X1 = X2

QED! Formal Proofs: Theorem 2 T2: For each X in B: (a) X+1=1 (b) X.0=0 Proof of (a): X+1 = 1 . (X + 1) = (X + X) . (X + 1) = X + (X. 1) = X + X =1 QED! X.0 = 0 + (X . 0)

= (X . X) + (X . 0) = X . (X + 0) = X . X =0 QED! Proof of (b): Note the duality in the two proofs. Change + to . and 1s to 0s. Formal Proofs: Idempotent Theorem Idempotent Theorem: For each X in B: (a) X+X=X (b) X.X=X Proof of (a): X+X

Proof of (b): By duality. = (X + X) . 1 = (X + X) . (X + X) = X + (X . X) =X+0 =X QED! Formal Proofs: Involution Theorem Involution Theorem (Double Negation) For each X in B, X = X. Proof: Let X be the complement of X, and X be the complement of X. It follows that: X + X = 1 X + X = 1 X . X = 0 X . X = 0 Then:

X = X + 0 = X + X . X = (X + X) . (X + X) = (X + X) . 1 = (X + X) . (X + X) = X + (X . X) =X+0 =X QED! Formal Proofs: Absorption Theorem Absorption Theorem: For every X, Y in B: (a) X+X.Y=X (b) X . (X + Y) = X Proof of (a): X + X . Y= X . 1 + X . Y = X . (1 + Y) =X.1 =X QED!

Proof of (b): By duality. Formal Proofs: Collapse Theorem Collapse Theorem: For every X, Y in B: (a) X + X . Y = X + Y (b) X . (X + Y) = X . Y Proof of (a): X + X . Y Proof of (b): By duality. = (X + X) . (X + Y) = 1 . (X + Y) = (X + Y) QED! Formal Proofs: De Morgans Theorems De Morgans Theorems: For every X, Y in B:

(a) (X + Y) = X . Y (b) (X . Y) = X + Y Proof of (a): Letting A=(X+Y) and B=X.Y, then (a) states: A = B. If true, then it must follow that: A + A =A+B = (X+Y) + (X.Y) = [(X+Y) + X] . [(X+Y) + Y] = [(X+X) + Y] . [(Y+Y) + X] = [1 + Y] . [1 + X] =1.1 =1 Self-consistent! Proof of (b): By duality. QED Formal Proofs versus Truth Tables All of the previous theorems can be proven using the technique of

proof by exhaustion, based on the use of truth tables. By listing all possible combinations of values (0 and 1) for each variable, its complement and all sub-expressions, one proceeds toward the goal of establishing that each possible expression value on the right and left sides of the theorem relation are equivalent. This is referred to as perfect induction. Boolean Expressions In digital design, circuits are expressed as formulae. 3 literals Examples: variables f(x,y,z) = (x + y) z f(x,y) = xy + xy 4 literals In general, f(x) is a multi-nomial of degree one in each of the

element variables xk in x. The usual goal is to express f(x) in the simplest form possible. Such forms typically involve the minimum number of literals (i.e. variable elements, including complements and repeated elements) They represent hardware designs that are partially or fully optimal. Boolean Expressions When the expression of f is of the form: f = A + BC + DEF SOP it is called a Sum of Products, or Disjunctive Normal Form (DNF). When the expression of f is of the form: f = (A) . (B + D) . (D + E + F) POS it is called a Product of Sums, or Conjunctive Normal Form (CNF). Boolean Expressions - Canonical Forms When the SOP expression of F(A,B,C) involves terms in which all variables appear (some or all may be complemented), it is called a

Sum of Minterms: F(A,B,C) = ABC + ABC + ABC a minterm has all 3 variables When the POS expression of f involves terms in which all variables appear (some or all may be complemented), it is called a Sum of Maxterms: F = (A+B+C) . (A+B+C) . (A+B+C) a maxterm has all 3 variables If f(x) depends on N variables, the maximum number of terms it can have is 2N. Boolean Expressions - Canonical Forms It is usually the case that F(x) is not given a priori. Rather, its boolean value is given for each specific set of x values. These are conveniently expressed in a truth table, as in: K X Y Z 0 1 2 3

4 5 6 7 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 FK 0 1 0 1 0 1

0 1 0 1 0 1 1 0 0 0 The row index value is just the decimal equivalent to the binary sequence of variable values in each row. Boolean Expressions - Canonical Forms It is usually the case that f(x) is not given a priori. Rather, its boolean value is given for each specific set of x values. These are conveniently expressed in a truth table. Example: K X Y Z 0

1 2 3 4 5 6 7 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 FK 0 1

0 1 0 1 0 1 0 1 0 1 1 0 0 0 The minterm canonical form is obtained by collecting all minterms for which FK = 1, namely: F = XYZ + XYZ + XYZ Note: We write the variable name itself when its corresponding entry in the table is 1 - otherwise, we write the complement of the variable. Boolean Expressions - Canonical Forms

This shorthand It is usually the case that f(x) is not given a is priori. notation oftenRather, its the boolean value is given for eachuseful. specificNote set ofthat x values. row values listed in These are conveniently expressedbrackets in a truthare table. the decimal equivalents Example: K X Y Z 0 1 2 3 4 5 6

7 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 FK 0 1 0 1 0 1 0 1

0 1 0 1 1 0 0 0 to the binary sequence of variable The minterm canonical values. form is obtained by collecting all minterms for which FK = 1, namely: F = XYZ + XYZ + XYZ = SUM m(1,3,4) Boolean Expressions - Canonical Forms K X Y Z FK 0 that0f(x)0is not

0 given 0 a priori. Rather, its It is usually the case 1 0 1 1 set of x values. boolean value is given for0 each specific 2 0 1 0 0 These are conveniently expressed 3 0 1 1 in a1truth table. Example: Maxterm 4 Expression 1 0 0 1 5 6 7 1 1 1 0 1

1 1 0 1 0 0 0 The maxterm canonical form is obtained by collecting all maxterms for which FK = 0, namely: F = (X+Y+Z)(X+Y+Z)(X+Y+Z) (X+Y+Z) (X+Y+Z) Boolean Expressions - Canonical Forms K X Y Z FK 0 that0f(x)0is not 0 given 0 a priori. Rather, its It is usually the case 1 0 1 1 set of x values. boolean value is given

for0 each specific 2 0 1 0 0 These are conveniently expressed in a1truth table. 3 0 1 1 In mathematics we encounter Example: 1 0 of 0 terms 1 SUM and 4PRODuct and 5 notations: 1 0 1 we use the 6 7 1 1 1 1

0 1 0 0 Greek capital sigma 0 The maxterm canonical form is obtained by collecting SUM F FK all maxterms for whichK FK = 0, namely: F = (X+Y+Z)(X+Y+Z)(X+Y+Z) (X+Y+Z) PROD FK (X+Y+Z) FK = PROD M(0,2,5,6,7) NOTATION! Greek capital pi SHORTHAND Algebraic Simplification Algebraic simplification is usually applied to canonical minterm

and maxterm expressions. The number of individual terms and variable combinations can be minimized in many cases. The power of algebraic simplification is quite limited and we will need to replace these techniques by other, even more powerful techniques. Gate Representations Gate (diagrammatic) representations are used for circuit layout & design. These gates, or logic devices, are manufactured and used to construct actual microelectronic circuits, such as memories, ALUs, CUs, CPUs, buses and so on. Transistor types: (a) NPN, and (b) PNP with base (B), collector (C) and emitter (E) wires. Gate Representations Each logic operation has its own gate diagram and truth table: X X not (inverter) and / nand or / nor xor / xnor

XY X Y X Y X+Y X Y X X Y Y XY X Y X+Y X Y X

Y Gate Representations Manufacturing of gate level logic devices sometimes benefits the lower cost of production of certain types of gates nand, nor A very powerful property of Boolean Algebra is that all of the basic gate types (boolean operations) can be expressed in terms of just one specific gate nand, nor This implies that an entire computer (except for a few items!) can be constructed from a single gate type. Although true in principle, there are many reasons why a variety of gate types are actually used. Gate Representations Theorem: For each X, Y in B, X + Y = (X . Y) + (X . Y) In words, X xor Y = ( X and ( not Y ) ) or ( ( not X ) and Y ) And, as an equivalent circuit, XY X X Y

X Y X Y Y (XY)+(XY) XY Gate Representations All of the previous theorems can also be re-developed using only the nor gate as the fundamentally primitive gate type. In principle, all gates can be represented in terms of any one gate, with the exception of the not (inverter/complementer) You cannot construct a binary operator from a purely unary one. Gate Representations Example: Express the Inverter (complementer) using only a NAND gate Use the idempotency relationship, namely: X = X.X Now, since the complement of X is just X, it follows that X = (X.X) = not( X and X) = X nand X In diagrammatic form: X

X X X Gate Representations Example: Express the Inverter (complementer) using only a NOR gate Once again, use the idempotency relationship, namely: X = X+X Now, since the complement of X is just X, it follows that X = (X+X) = not( X or X) = X nor X In diagrammatic form: X X X X Gate Representations The circle associated with logic gates corresponds to an inversion (complementation) operation By moving the position of the circle(s), one can often achieve

simple results Example: X X X = (X ) = X X X X Gate Representations Example: De Morgans Theorem (X+Y) = (X).(Y) X Y By manipulating the circles (moving them along lines

and through gates) one can often (X+Y) achieve simplified, or alternative, expressions. X X (X).(Y) Y Y Summary We have considered the Boolean Algebra formal mathematical definition algebraic representation (0 and 1) postulates theorems formal proof techniques Boolean expressions SOP and POS forms

minterms and maxterms Gate diagrams for circuit logic We will now continue to study algebraic simplification, followed by general reduction techniques for simplifying complex boolean expressions.