Transcript Boolean expressions

Fundamentals
•
•
What kind of data do computers work with?
– Deep down inside, it’s all 1s and 0s
What can you do with 1s and 0s?
– Boolean algebra operations
– These operations map directly to hardware circuits
CS231 Fundamentals
1
Computers are binary devices
•
•
•
•
•
Computers use voltages to represent
information
Voltages are usually limited to 2.5-5.0V
to minimize power consumption
This is only enough to represent two
discrete (digital) signals
– Low and High
– 0 and 1
– False and True
Why?
– To account for noise
– To prevent transitional errors
How can we use these two signals to
represent numbers?
CS231 Fundamentals
Good!
Bad!
Volts
5
High
4
3
2
1
Low
0
Volts
5
High
4
3
Medium
2
1
Low
0
2
Decimal review
•
Numbers consist of a bunch of digits, each with a weight
1
100
•
2
1
.
3
1/10
7
1/100
5
Digits
1/1000 Weights
These weights are all powers of the base, which is 10. We can rewrite
this:
1
102
•
6
10
6
101
2
100
.
3
10-1
7
10-2
5
10-3
Digits
Weights
To find the decimal value of a number, multiply each digit by its weight
and sum the products.
(1 x 102) + (6 x 101) + (2 x 100) + (3 x 10-1) + (7 x 10-2) + (5 x 10-3) = 162.375
CS231 Fundamentals
3
Converting binary to decimal
•
We can use the same trick to convert binary, or base 2, numbers to
decimal. This time, the weights are powers of 2.
– Example: 1101.01 in binary
1
23
–
1
22
0
21
1
20
.
0
2-1
1
2-2
Binary digits, or bits
Weights (in base 10)
The decimal value is:
(1 x 23) + (1 x 22) + (0 x 21) + (1 x 20) + (0 x 2-1) + (1 x 2-2) =
8
+
4
+
0
+
1
+
0
+ 0.25 = 13.25
Powers of 2:
20 = 1
24 = 16
21 = 2
25 = 32
22 = 4
26 = 64
23 = 8
27 = 128
28 = 256
29 = 512
210 = 1024
CS231 Fundamentals
Useful abbreviations:
K = 210 = 1,024
M = 220 = 1,048,576
G = 230 = 1,073,741,824
4
Opposite: converting decimal to binary
•
•
•
To convert an integer, keep dividing by 2 until the quotient is 0. Collect
the remainders in reverse order.
To convert a fraction, keep multiplying the fractional part by 2 until it
becomes 0. Collect the integer parts (in forward order).
– This may not terminate!
Example: 162.375:
162 / 2
81 / 2
40 / 2
20 / 2
10 / 2
5/2
2/2
1/2
•
= 81
= 40
= 20
= 10
=5
=2
=1
=0
rem 0
rem 1
rem 0
rem 0
rem 0
rem 1
rem 0
rem 1
0.375 x 2 = 0.750
0.750 x 2 = 1.500
0.500 x 2 = 1.000
So, 162.37510 = 10100010.0112
CS231 Fundamentals
5
Why does this work?
•
•
This works for converting from decimal to any base
Why? Think about converting 162.375 from
decimal to decimal.
162 / 10 = 16
16 / 10 = 1
1 / 10 = 0
•
rem 2
rem 6
rem 1
Each division “strips off” the rightmost digit (the
remainder). The quotient represents the remaining
digits in the number.
0.375 x 10 = 3.750
0.750 x 10 = 7.500
0.500 x 10 = 5.000
•
Similarly, each multiplication “strips off” the
leftmost digit (the integer part). The fraction
represents the remaining digits.
CS231 Fundamentals
6
Base 8 and base 16 are useful too
•
•
•
Octal (base 8) digits range from
0 to 7. Since 8 = 23, one octal
digit is equivalent to 3 binary
digits.
Hexadecimal (base 16) digits are
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C,
D, E, and F. Since 16 = 24, one
hex digit is equivalent to 4 binary
digits.
We typically use octal and hex as
a shorthand for those long messy
binary numbers.
Decimal
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CS231 Fundamentals
Binary
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Octal
0
1
2
3
4
5
6
7
10
11
12
13
14
15
16
17
Hex
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
7
Binary, octal, hexadecimal
•
Converting from octal (or hex) to binary is easy: just replace each octal
(or hex) digit with the equivalent 3 (or 4) bit sequence
261.358 = 2
= 010
6
110
1
001
261.3516 = 2
6
1
= 0010 0110 0001
•
. 3
. 011
58
1012
. 3
516
. 0011 01012
These binary
numbers are not
equivalent!
To convert from binary to octal (or hex): starting from the binary
point, make groups of 3 (or 4) bits. Add 0s to the ends of the number
if needed. Then, just convert each bit group to its corresponding octal
(or hex) digit.
10110100.0010112 =
=
10110100.0010112 =
=
010 110 100 . 001 0112
2
6
4
. 1
38
1011 0100 . 0010 11002
B
4
. 2
C16
CS231 Fundamentals
These numbers
are equivalent!
8
Functions
•
•
A computer takes input and produces output... just like a math function!
We can express math functions in two ways
As an expression
As a function table
f(x,y) = 2x + y
=x+x+y
= 2(x + y/2)
= ...
•
x
y
f(x,y)
0
…
2
…
23
…
0
…
2
…
41
…
0
…
6
…
87
…
We can represent binary functions in two ways too:
– As a Boolean expression
– As a truth table. It shows all possibilities for an expression.
CS231 Fundamentals
9
Basic Boolean operations
•
There are three basic operations. Each can be implemented in hardware
using a primitive logic gate
NOT
(complement)
AND (product)
OR (sum) of
Operation:
on one input
of two inputs
two inputs
Expression:
Truth table:
xy
x+y
x’
x
y
xy
x
y
x+y
x
x’
0
0
0
0
0
0
0
1
0
1
0
0
1
1
1
0
1
0
0
1
0
1
1
1
1
1
1
1
Logic gate:
CS231 Fundamentals
10
Boolean expressions
•
We can use these basic operations to form more complex expressions
and equations
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 variable represents a 1 or 0.
Listing input variables is optional; instead we often write
f = (x + y’)z + x’
–
–
A literal is an occurrence of an input variable or its complement.
The function above has four literals: x, y’, z, and x’.
Without parentheses, the NOT operation has the highest
precedence, followed by AND, and finally OR. Fully parenthesized,
this function is
f(x,y,z) = (((x +(y’))z) + x’)
CS231 Fundamentals
11
Larger circuits
•
We can build circuits for arbitrary expressions, using our basic gates
f(x,y,z) = (x + y’)z + x’
(x + y’)z
y’
(x + y’)
x’
CS231 Fundamentals
12
Truth tables
•
•
•
We can make a truth table too, by evaluating the function for all
possible inputs.
In general, a function with n inputs will have 2n possible inputs.
The inputs are typically listed in binary order.
f(x,y,z) = (x + y’)z + x’
f(0,0,0)
f(0,0,1)
f(0,1,0)
f(0,1,1)
f(1,0,0)
f(1,0,1)
f(1,1,0)
f(1,1,1)
= (0 + 1)0 + 1
= (0 + 1)1 + 1
= (0 + 0)0 + 1
= (0 + 0)1 + 1
= (1 + 1)0 + 0
= (1 + 1)1 + 0
= (1 + 0)0 + 0
= (1 + 0)1 + 0
=1
=1
=1
=1
=0
=1
=0
=1
CS231 Fundamentals
x
y
z
f(x,y,z)
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
1
1
1
0
1
0
1
13
Summary
•
•
•
Summary
– To minimize analog voltage problems, computers are binary devices
– That means we have to think in terms of base 2
– The basic operations on binary values include AND, OR, and NOT
– These can be directly implemented in hardware (eventually we’ll
show how to do useful stuff with these operations)
– Expressions and truth tables are used to design and describe
circuits
We’ve already seen some of the recurring themes of architecture:
– We use 0 and 1 as abstractions for analog voltages
– Gates are also an abstraction of the underlying technology
– We showed how to represent numbers using just these two signals
Next time:
– Using Boolean algebra to simplify expressions
– This in turn will yield a simpler circuit
CS231 Fundamentals
14