DOC PREVIEW
U of I CS 231 - Boolean algebra

This preview shows page 1-2-3-26-27-28 out of 28 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

January 16, 2002 Boolean algebra 1Boolean algebra• Last time we talked about how arbitrary numbers can be representedusing just the two binary values 1 and 0.• Today we’ll interpret voltages as the logical values “true” and “false”instead. We’ll show:– How functions can be defined for expressing computations– How to build circuits that implement our functions in hardware– How Boolean algebra can help simplify expressions, which in turnleads to simpler circuits.January 16, 2002 Boolean algebra 2Boolean values• On Monday we used electrical voltages to representtwo discrete values 1 and 0, from which binary numberscan be formed.• It’s also possible to think of voltages as representingtwo logical values, true and false.• For simplicity, we often still write digits instead:– 1 is true– 0 is false• We will use this interpretation today, along with special operations, todesign functions and hardware for doing arbitrary computations.Volts1.80TrueFalseJanuary 16, 2002 Boolean algebra 3Functions• Computers take inputs and produce outputs, just like functions in math!• Mathematical functions can be expressed in two ways:• We can represent logical functions in two analogous ways too:– A finite, but non-unique Boolean expression.– A truth table, which will turn out to be unique and finite.x y f(x,y)00 0…… …22 6…… …23 41 87…… …f(x,y) = 2x + y= x + x + y= 2(x + y/2)= ...An expression isfinite but not uniqueA function table isunique but infiniteJanuary 16, 2002 Boolean algebra 4Basic Boolean operations• There are three basic operations for logical values.x y xy00 001 010 011 1x y x+y00 001 110 111 1x x’0110AND (product)of two inputsOR (sum) oftwo inputsNOT(complement)on one inputxy, or x•yx + y x’Operation:Expression:Truth table:January 16, 2002 Boolean algebra 5Boolean expressions• We can use these basic operations to form more complex expressions:f(x,y,z) = (x + y’)z + x’• Some terminology and notation:– f is the name of the function.– (x,y,z) are the input variables, each representing 1 or 0. Listing theinputs is optional, but sometimes helpful.– A literal is any occurrence of an input variable or its complement.The function above has four literals: x, y’, z, and x’.• Precedences are important, but not too difficult.– NOT has the highest precedence, followed by AND, and then OR.– Fully parenthesized, the function above would be kind of messy:f(x,y,z) = (((x +(y’))z) + x’)January 16, 2002 Boolean algebra 6Truth tables• A truth table shows all possible inputs and outputs of a function.• Remember that each input variable represents either 1 or 0.– Because there are only a finite number of values (1 and 0), truthtables themselves are finite.– A function with n variables has 2n possible combinations of inputs.• Inputs are listed in binary order—in this example, from 000 to 111.x y z f(x,y,z)000 1001 1010 1011 1100 0101 1110 0111 1f(0,0,0) = (0 + 1)0 + 1 = 1f(0,0,1) = (0 + 1)1 + 1 = 1f(0,1,0) = (0 + 0)0 + 1 = 1f(0,1,1) = (0 + 0)1 + 1 = 1f(1,0,0) = (1 + 1)0 + 0 = 0f(1,0,1) = (1 + 1)1 + 0 = 1f(1,1,0) = (1 + 0)0 + 0 = 0f(1,1,1) = (1 + 0)1 + 0 = 1f(x,y,z) = (x + y’)z + x’January 16, 2002 Boolean algebra 7Primitive logic gates• Each of our basic operations can be implemented in hardware using aprimitive logic gate.– Symbols for each of the logic gates are shown below.– These gates output the product, sum or complement of their inputs.Logic gate:AND (product)of two inputsOR (sum) oftwo inputsNOT(complement)on one inputxy, or x•yx + y x’Operation:Expression:January 16, 2002 Boolean algebra 8Expressions and circuits•Any Boolean expression can be converted into a circuit by combiningbasic gates in a relatively straightforward way.• The diagram below shows the inputs and outputs of each gate.• The precedences are explicit in a circuit. Clearly, we have to make surethat the hardware does operations in the right order!(x + y’)z + x’January 16, 2002 Boolean algebra 9Simplifying circuits• The expression and circuit on the previous page are actually equivalentto the simplified ones below:x’ + z• Simpler hardware is always better!– In many cases, the simpler circuit is also faster.– Less hardware means smaller size, which also reduces costs.– Simpler circuits draw less power.• How do we know this circuit is the same as the one on the last page?January 16, 2002 Boolean algebra 10Boolean algebra is special• Boolean algebra gives us a way to simplify Boolean functions, much likeregular algebra allows us to simplify mathematical functions.• The AND and OR operations are similar to multiplication and addition:– AND is the same as multiplication for the values 0 and 1– OR is almost the same as addition, except for 1 + 1.• But there are important differences to watch out for, too.– Boolean algebra uses are only two values.– OR is not quite the same as addition, and NOT is a new operation.x y xy00 001 010 011 1x y x+y00 001 110 111 1January 16, 2002 Boolean algebra 11Formal definition of Boolean algebra• A Boolean algebra requires:– A set of values B, which contains at least two elements 0 and 1– Two 2-argument operations + and •– A one-argument operation '• The values and operations must satisfy the axioms below.1. x + 0 = x 2. x • 1 = x3. x + 1 = 1 4. x • 0 = 05. x + x = x 6. x • x = x7. x + x’ = 1 8. x • x’ = 09. (x’)’ = x10. x + y = y + x 11. xy = yx Commutative12. x + (y + z) = (x + y) + z 13. x(yz) = (xy)z Associative14. x(y + z) = xy + xz 15. x + yz = (x + y)(x + z) Distributive16. (x + y)’ = x’y’ 17. (xy)’ = x’ + y’ DeMorgan’sJanuary 16, 2002 Boolean algebra 12Satisfying the axioms• The operations we chose do satisfy all of the axioms. We can show thisby looking at the definitions of our operations.• For example, the axiom x + x’ = 1 is satisfied, because:– We have only two possible values for x: 0 and 1.– The complement of these values are 1 and 0, respectively.– 0 + 1 = 1, and 1 + 0 = 1.x y xy00 001 010 011 1x y x+y00 001 110 111 1x x’0110x x’ x+x’01 110 1January 16, 2002 Boolean algebra 13Proofs with truth tables• We can always prove equivalences using truth tables, to explicitly showthat two expressions always produce the same results.• Let’s use truth tables to prove DeMorgan’s law, (x + y)’ = x’y’.– The columns on the left in each table are the inputs. We have


View Full Document

U of I CS 231 - Boolean algebra

Documents in this Course
Counters

Counters

23 pages

Latches

Latches

22 pages

Lecture

Lecture

33 pages

Lecture

Lecture

16 pages

Lecture

Lecture

4 pages

Datapaths

Datapaths

30 pages

Lecture

Lecture

6 pages

Registers

Registers

17 pages

Datapaths

Datapaths

28 pages

Decoders

Decoders

20 pages

Load more
Download Boolean algebra
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Boolean algebra and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Boolean algebra 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?