Ones And Zeros

Ones and Zeros\ Understanding Boolean Algebra, Digital Circuits, and the Logic of Sets \ \ By John R. Gregg \ John Wiley & Sons\ ISBN: 0-7803-3426-4 \ \ \ Chapter One\ Number Systems and Counting \ The focus of this book is the branch of mathematical logic known as Boolean algebra or Boolean logic. Although we will spend considerable time exploring Boolean algebra in its various forms, first we should spend time thinking about numbers and the ways in which we represent them by using symbols.\ 0.1 NUMBERS: SOME BACKGROUND\ A numeral is a single symbol that represents a quantity or number. A number system is a way of assigning combinations of numerals to different quantities. The act of assigning combinations of numerals to different quantities through the use of a number system is called counting. Human beings happen to have 10 fingers, five on each hand, which has resulted in the use of the base 10 or decimal number system by most cultures. In fact, the word digit comes from the Latin digitus, meaning finger.\ The decimal system has 10 numerals: 0, 1,2, 3, 4, 5, 6, 7, 8, and 9. We can express any number we want by using different combinations of these 10 numerals within the base 10 number system. Some cultures, notably the Mayas, Celts, and Aztecs, developed base 20 number systems probably from originally using both fingers and toes to count. The Sumerians and the Babylonians, for reasons lost in the mists of time, developed a base 60 number system to which we still owe our practice of dividing the hour into 60 minutes, the minute into 60 seconds, and the circle into 360°.\ The most direct ancestor of our particular number system, with its rather abstract but indispensable notion of zero, and its use of the position of a given digit to determine the quantity represented by that digit, was developed in India more than a thousand years ago. During the great flourishing of Islam, it slowly spread throughout the Arab world before making its way to Europe. The great popularizer of the Hindu-Arabic number system in Europe was Leonardo of Pisa, a well-traveled mathematician whose 1202 publication Liber Abaci brought Europe out of the mathematical dark age of the Roman numeral.\ 0.2 THE DECIMAL SYSTEM: A CLOSER LOOK\ If your niece shows you a jar full of pebbles that she gathered at the beach and tells you that she counted them and that there are exactly 608 pebbles in the jar, what exactly is the relationship between the sequence of numerals "608" and the number of pebbles in the jar? How do we make this connection?\ The number 608 has three digit positions or numeral slots: the 100s position (which contains a six), the 10s position (which contains a zero), and the ones position (which contains an eight). Every base 10 number consists of numerals in such slots or digit positions. The total value represented by a given numeral in a number is determined by two things: the value of the numeral itself and the value assigned to the position that the numeral occupies in the number. To get the total value carried in each position, we multiply the numeral in the position by the value of the position itself. To get the value of the entire number, we add up the total values for all the positions. Thus, for the number 608,\ (6 × 100) + (0 × 10) + (8 × 1) = 600 + 0 + 8 = 608.\ Table 0.1 shows the relationship between each digit position and the value we assign it. Each position represents exactly 10 times more than the position to its right and exactly one-tenth the value of the position to its left. Another way of saying this is that the positions represent successive powers of 10. If we count the positions from right to left beginning with zero (not one), each position carries a value equal to 10 raised to the power of the position number. Stated more mathematically, each position carries the value [10.sup.x] where x is the number of the position. For example, position 2 is the [10.sup.2] or 100s position. Position 17 would be the [10.sub.17] or 100,000,000,000,000,000's position.\ In any number the digit in the leftmost position is called the most significant digit because it carries the most value in the number. The rightmost digit is called the least significant digit because it carries the least value in the number.\ Look at our example number 608 again. What about the 0 in the 10s position? It is tempting to say that there are no 10s in 608 but that is not really true; there are 60 tens (plus one-eighth of a 10, if you want to get picky). What the 0 in the 10s position really indicates is that there are no leftover 10s that cannot be lumped together into a hundred or a thousand, etc.\ Likewise, the 6 in the 100s position means that there are six 100s left over that cannot be lumped together into a thousand (or some even higher power of 10). If the number were 908, there would be nine 100s that could not be lumped together into a thousand. However, if we were to add another hundred to 908, we would have 10 hundreds, which would be an even thousand with no 100s left over, or 1008.\ Because each digit position only holds the leftover numbers that could not be lumped together into a higher power of 10, each digit only needs to hold at most nine. Nine is as full as a digit can get before it "flips over" into the next digit position.\ The numeral 0 is somewhat different from the rest of the base 10 numerals, 1 through 9. It does not actually represent any value. It represents nothing, which is different than saying that it does not represent anything. It is sometimes called a place holder because it occupies space in a number without adding any value to it. Yet without the lowly 0, how could the 1 in 1,000,000 occupy the millions position?\ Another property of 0 is that it invisibly occupies all digit positions to the left of the most significant digit of a number; we just do not write them all out for convenience's sake. Thus, 4 is the same as 0000000004. All those 0s mean that there are no 10s, no 100s, no 1000s, etc. When we do choose to write the meaningless 0s in the front of a number, they are sometimes called padding zeros. Sometimes padding zeros are necessary when filling out forms (e.g., month of birth: 03).\ 0.3 OTHER BASES\ What if people had only seven fingers? There would only be seven digits: 0, 1, 2, 3, 4, 5, and 6 but no 7, 8, or 9. We would count in base 7, in which a digit "flips over" into the next higher position when it reaches six not nine. If you had a car with a base 7 odometer, as you drove it would climb mile after mile toward 666666, at which point it would flip back to 000000. Counting in base 7 works as shown in Table 0.2.\ The digit positions in base 7 do not represent the same values that they do in base 10. In base 10, each digit position represents a value 10 times as great as that represented in the position to its right. In base 7 each digit position represents a value seven times as great as that represented by the position to its right and one-seventh as great as that of the position to its left. That is, digit positions represent successively greater powers of seven. There is a ones position at the far right, followed by a sevens position, followed by a 49s ([7.sup.2]) position, followed by a 343s ([7.sup.3]) position, and so forth. The values assigned to each of the first five base 7 digit positions are shown in Table 0.3.\ EXERCISE 0.1\ A. Write out (in base 10) the values assigned to the first five digit positions of the following bases, beginning with the least significant digit position (zero) and working toward the most significant digit position (four):\ 1. 9 2. 5 3. 4 4. 3 5. 2\ 0.4 CONVERTING FROM BASE 7 TO BASE 10\ If we have a number in base 7 e.g., 4625, how do we know how big it is? Because we are not used to working in the base 7 number system, for it to mean anything to us we must be able to convert it to base 10.\ To convert a number from base 7 to base 10, we multiply the numeral in each digit position by that digit position's value then add the resulting products together. For example, to find the base 10 representation of the base 7 number 4625, we note that there is a four in the 343s position, a six in the 49s position, a two in the sevens position, and a five in the ones position, as shown in Table 0.4.\ Based on this observation, we calculate:\ (4 × [7.sup.3]) + (6 × [7.sup.2]) + (2 × [7.sup.1]) + (5 × [7.sub.0]) = 4 × 343 + 6 × 49 + (2 × 7) + (5 × 1) - 1372 + 294 + 14 + 5 - 1685.\ To avoid confusion in places where confusion is likely, we will put a subscript on numbers indicating their base. Thus, [4625.sub.7] = [1685.sub.10]. Naturally, the subscripted number itself, indicating the base, is in base 10.\ Consider for a moment the quantity [25.sub.10]. It represents the same quantity that [34.sub.7] does. To illustrate this, look at Figures 0.1 and 0.2. Each contains the same number of chili peppers, but in each group the chili peppers are arranged differently to reflect the different ways of looking at the same quantity depending on the number system being used.\ Figure 0.1 represents 25 chili peppers grouped in a way that makes sense in base 10: two groups of 10 chili peppers each and one group of five chili peppers left over. Figure 0.2 shows the same number of chili peppers but grouped in a way that reflects a base 7 method of counting them: three groups of seven chili peppers each and one group of four chili peppers left over.\ 0.5 CONVERTING FROM BASE 10 TO BASE 7\ To convert a number from base 10, which we are used to, to another base (e.g., base 7), we need to rearrange the number from groupings of powers of 10 to powers of 7. We do not draw out chili peppers and move them around as we did in the last example. We regroup the number mathematically using division.\ Recall that each digit in a base 7 number can be thought of as "leftover," quantities that were left over after forming groups of greater powers of seven. This concept of "leftovers" is the same as the concept of remainders in long division. To find the base 7 representation of a number whose base 10 representation is known to us, we keep dividing the number by 7 according to the normal rules of long division. The remainder that results from each division gives us one more digit in our base 7 number, working right to left, from the least significant digit to the most significant digit.\ For example, to find out what [967.sub.10] is in base 7, first we divide 967 by seven: 967 ÷ 7 = 138, with a remainder of one. (If we had 967 ball bearings and we tried to form them on the ground in neat groups of seven, there would be one left over.) Thus, there is a one in the ones column of our base 7 number. Next, we take the quotient we got before, 138, and divide it by 7. This is equivalent to grouping the groups of seven ball bearings we had before into groups of seven, making groups of 49 ball bearings each: 138 ÷ 7 = 19, with a remainder of five. Thus, there are five groups of seven ball bearings that do not fit evenly into any of the groups of 49 ball bearings. Therefore, the digit in the sevens position in the base 7 number is five. To find the digit in the 49s position, we again divide our quotient by 7: 19 ÷ 1 = 2, with a remainder of five, therefore a five occupies the 49s position in our base 7 number. Finally, 2 ÷ 7 = 0 with a remainder of two, so a two occupies the 343s position in the base 7 number. Now we are done because our number has melted away to zero, and we have nothing more to divide by seven: [967.sub.10] = [255.sub.17]. We can check this result by reconverting [255.sub.17] into base 10:\ (2 × [7.sup.3]) + (5 × [7.sup.2]) 4- (5 × [7.sup.1]) + (1 × [7.sup.0]) = (2 × 343) + (5 × 49) + (5 × 7) 4 (1 × 1) = 686 + 245 + 35 + 1 = 967.\ Now let us consider base 5, in which the only digits are 0, 1,2, 3, and 4 and the digit positions have values of successive powers of five, as shown in Table 0.5.\ To convert a base 5 number to base 10, we follow the same method we used for base 7: multiply each numeral by the value its digit position represents. For example, to convert [413.sub.5] to base 10, we calculate as follows:\ ([4 × 5.sup.2]) 4 (1 × [5.sup.1]) + (3 × [5.sup.0]) = (4 × 25) + (1 × 5) + (3 × 1) = 100 + 5 + 3 - [108.sub.10].\ To convert back to base 5, we use the same sequence of steps for converting base 10 to base 7:\ [108.sub.10] ÷ 5 = 21, remainder 3 (3 in l's position) [21.sub.10] ÷ 5 = 4, remainder 1 (1 in 5's position) 4 ÷ 5 = 0, remainder 4 (4 in 25s position)\ The two methods for converting from base 10 to another base and back again are general and can be applied to any base. Such a distinct sequence of steps is called an algorithm.\ What is the smallest base we could have? Because any number system has digits 0 through one less than the base of the number system itself, we could not really have a base 1 because it would only have one digit, 0. With only one symbol, we could not use our method of using the digit position to impart value to a numeral because we would have no place holder. However, we can have a base 2 with digits 0 and 1. The base 2 or binary number system would be extremely unwieldy to use when balancing your checkbook, for example, but it has some interesting properties that make it of crucial concern for the rest of this book.\ On the other hand, could we have a base greater than 10? We could, but only if we invent new digits to represent single-digit numbers greater than nine. By convention, people who need to use such number systems (and there are more of them than you might think) usually use letters to represent these digits. Accordingly, counting in base 16 works as shown in Table 0.6.\ The base 16 or hexadecimal number system has 1610 digits: 0 through F ([F.sub.16] = [15.sub.10]).\ EXERCISE 0.2\ A. Count from one to [20.sub.10] in the following bases:\ 1. 8 2. 6 3. 5 4. 3 5. 2\ B. Convert the following numbers to their base 10 equivalents:\ 6. [3124.sub.7] 7. [12332.sub.4] 8. [15366.sub.9] 9. [4000.sub.5] 10. [7122.sub.8] 11. [77.sub.8] 12. [333.sub.4] 13. [111111.sub.2]\ C. Convert the following base 10 numbers to the indicated base:\ 14. [413.sub.10] to base 5 15. [128.sub.10] to base 8 16. [3000.sub.10] to base 6 17. [963.sub.10] to base 3 18. [67.sub.10] to base 2\ D. Perform the indicated base conversions:\ 19. [54.sub.8] to base 5 20. [312.sub.4] to base 7 21. [520.sub.6] to base 7 22. [12212.sub.3] to base 9 23. [100.sub.8] to base 2 24. What generalizations can you draw about converting a number from one base to a power of that base, e.g., from base 3 to base 9 ([3.sup.2]) or from base 2 to base 4 ([2.sup.2]) or base 8 ([2.sub.3])?\ 0.6 ADDITION IN OTHER BASES\ Adding numbers in other bases is much like adding numbers in base 10. Care must be taken, however, because it is easy to forget that you are working in another base. For instance, in base 6, 4 + 3 does not equal 7, as it does in base 10 because there is no numeral 7 in the base 6 number system. In base 6,4 + 3 = 11; a one in the sixes position and a one in the ones position, [11.sub.6] = [7.sub.10].\ What about adding multidigit numbers? The familiar rules of carrying apply. To perform the following addition in base 4:\ 32113 + 11323\ We begin with the first column and add the numbers in it together: [3.sub.4] + [3.sub.4] = [12.sub.4]. We would then drop the 2 into the first column of the sum and carry the 1:\ 1 32113 + 11323 2\ Next, we add the numbers in the second column, including the carry: [1.sub.4] + [1.sub.4] + [2.sub.4] = [10.sub.4]. We drop the 0 and carry the 1. We continue in this vein until we have\ 1111 32113 + 11323 110102\ We can check that [32113.sub.4] + [11323.sub.4] = [110102.sub.4] by converting all three numbers to base 10 performing the addition on the first two numbers in base 10 and making sure that the sum we get is equal to the third number.\ (Continues...)\ \ \ \ \ Excerpted from Ones and Zeros by John R. Gregg Excerpted by permission.\ All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.\ Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site. \ \

Before We BeginCh. 0Number Systems and Counting1Ch. 1The Basic Functions of Boolean Algebra: and, or, and not22Ch. 2Combinational Logic37Ch. 3The Algebra of Sets and Venn Diagrams59Ch. 4Other Boolean Functions77Ch. 5Realizing any Boolean Function with and, or, and not101Ch. 6More Digital Circuits126Ch. 7Laws of Boolean Algebra150Ch. 8Boolean Logic173App. ACounting in Base 2203App. BPowers of 2204App. CSummary of Boolean Functions205Further Reading213Answers to Exercises219Index277About the Author281

\ BooknewsExplains, in lay terms, Boolean algebra, the surprisingly simple system of mathematical logic used in digital computer circuitry. Anecdotal in style and often funny, material traces the development of this system, shedding light on the process of mathematical invention and scientific discovery. Includes exercises and solutions, and real- world examples of digital circuit design. For students and general readers interested in science, technology, and mathematics. Annotation c. by Book News, Inc., Portland, Or.\ \ \ \ \ Zentralbaltt MATHUseful for . . . everybody who would like to get an easy to read introduction to the theory and the application of Boolean logic.\ \