# ECE 352 Digital System Fundamentals Boolean Algebra ECE 352 Digital System Fundamentals Boolean Algebra 1 Topics Boolean Algebra Boolean Algebra 2 Boolean Functions

Functional Waveforms Boolean Identities and Manipulations Boolean Algebra Boolean Function Defined by a truth table, which is a complete representation of a Boolean function Same truth table can be implemented using different Boolean functions! If functions have identical truth tables, they are by definition functionally equivalent Different functions with the same truth table may differ in complexity this is why we use logic minimization Can also express the behavior of a Boolean function (or logic circuit) in response to

different input values using a waveform 3 Functional Waveforms Express signal/circuit behavior over time Boolean Algebra 1 is high and 0 is low 4 Given a set of input signals and their values over time, determine resulting output behavior Inputs may not occur in all possible combinations Input combinations may repeat F = AB + C Not definitive like a truth table!

A Can complete from B left to right, but dont C have to if the functionF is combinational Circuits From Boolean Functions Boolean Algebra Functions are implemented using logic gates The circuit inputs are the function variables A literal is a single variable within a term (that may or may not be complemented) The circuit output is the result Each Boolean function can be directly

translated to a gate diagram that produces an output Think how you would read the function out loud... You would use the names of logic functions that each correspond to a gate! If we need more than one output, can create separate functions, separate circuits 5 May be able to share a subset of circuitry Boolean Algebra Boolean Algebra An algebra to work with Boolean values 6

Similar to regular algebra except Boolean variables can only be 0 or 1; constants are only 0 or 1 Has operators, parentheses for precedence, etc. This allows us to manipulate Boolean functions Circuit/logic minimization Identify shared sub-functions (shared circuitry) Verify functionality Transform to use other types of gates or structures etc

Basic Boolean Identities X+1=1 X+0=X Boolean Algebra X+X=X X+ =1 X0 = 0 XX = X X = 0 =X Commutative: X+Y=Y+X

XY = YX Associative: X+(Y+Z) = (X+Y)+Z X(YZ) = (XY)Z Distributive: X(Y+Z) = XY + XZ X + YZ = (X+Y)(X+Z) De Morgans: 7 X1 = X Boolean Algebra

More Algebraic Manipulation Duality Principle: Dual of a circuit/equation: change ANDs to ORs, and change ORs to ANDs Taking the dual of both sides of a Boolean equation results in a valid equation Consensus Theorem: Provides a way to identify and remove a redundant term algebraically 8 Consensus Theorem Boolean Algebra

9 Why Simplify? Boolean Algebra B A C B 10 A C

More complex equation describes more complex circuit More More More More area delay power and heat work to create

Complement of a Function Boolean Algebra The complement of a function is one that has the opposite truth table 11 In the output column, change 0s to 1s and 1s to 0s Use De Morgans Law BEWARE operator precedence and grouping Add parentheses if necessary! Can test if correct by comparing truth tables Complement of a Function

Boolean Algebra = 12 Boolean Algebra ECE 352 Digital System Fundamentals Boolean Algebra 13