I recently wrote a very brief introduction to Boolean algebra for the glossary, so I thought it would be worth describing a very simple but important application example. There are two main reasons why I'm interested in Boolean algebra. The first is that in probability theory, the hypotheses we investigate are assumed to be Boolean in character (true or false, with no intermediates allowed). The second is that Boolean algebra is an important branch of logic, and therefore intimately linked to science and rationality.
In an earlier post, I discussed how all transfer of information comes down to a sequence of answers to yes/no questions. In this spirit, therefore, consider the following:
By answering only yes/no type questions, calculate the sum 234 + 111. In other words, if you were a digital computer, how would you perform this calculation?
Expressing numbers by answering yes/no questions
The numbers 234 and 111 are expressed (though I haven't specified it) in the conventional base 10 form. You're probably at the very least dimly aware that to solve this problem, we'll need to convert these numbers to base 2, or binary form.
In base ten, each digit is the answer to a question, 'how many multiples of 10 to the power n are there?', where n is one subtracted from the digit's place in the number. For instance, in 234, the 4 is in the first place and therefore signals how many times 100 appears in the number (once all the higher powers of 10 have been accounted for). Any number greater than 0 raised the power 0 is 1, so 4 times 100 is just 4. Similarly, 3 times 101 is 30, and 2 times 102 is 200. Add them all up, and you get 234.
Actually, in technical circles, what I referred to as the first digit is normally called the zeroth digit - digits are counted the same way Europeans count the floors of a building (Europeans are more logical than Americans!). Therefore, the 3 in 234 is in the first position and the 2 is in the second position. From here on, I'll switch to the standard zero-based indexing. In this nomenclature, the power to which the base is raised is the relevant index, and not 1 subtracted from the index.
Expressing a number in binary uses almost exactly the same scheme, except that now each digit answers a yes/no type question. So if the number (base 10) is 15, we could start by asking 'is it larger than or equal to 24?' The answer is no, so a 0 goes into the left-most (in this case the fourth) digit. Next, 'does it contain 23?' Yes, 23 is 8, and 8 is less than 15, so the next digit is a 1: 01.
Having accounted for those 8, that leaves 7 remaining to be accounted for. Of those remaining 7, is there a 22 present? Yes: 011. And 3 left over. Of those remaining 3, is there a 21 present? Yes: 0111. And there is also a 20 left, so we end up with 01111. That's 15 expressed in binary.
Adding binary numbers
A device that adds together just two binary digits is called a half adder circuit. We'll understand why in a moment. Its inputs are I1 and I2. If I1 is 1 and I2 is 0, then the sum is 1. Similarly, if the values are reversed. If, however, the inputs are I1 = 1, I2 = 1, the sum (in decimal) is 2, which in binary is 10. We can't express this with a single output bit so we need two outputs, which we call 'sum' and 'carry'. In this case, the sum is 0 and the carry is 1.
This half adder circuit is not sufficient to add together strings of more than 1 bit. Suppose we are adding 11 and 01. For thefirst zeroth (right-most) digit, the sum is 0, and the carry is 1. If we use another half adder to add the second first digits, we get 1 again, giving as combined output the string 11. Obviously, the output should be larger than the inputs, when both numbers are non-zero and positive. The reason we fell short is that we did not include the carry from summing the zeroth digit. Thus we need a circuit with three inputs, I1, I2, and carry_in. This new circuit is called a full adder.
We don't need to know physically how such a circuit might be implemented (of course, digital electronics implements all logical operations using networks of transistors), but we do need to work out the logic of its operation. We can do this by drawing up a table.
All possible combinations of the 3 input bits are given in the 3 left-most columns. The fourth column states the standard decimal results when each of these combinations of 0's and 1's are added up. The fifth column converts these decimal results to binary. Finally, the last 2 columns are the zeroth (right-most) and the first digits of this binary result (the sum and carry_out, respectively).
We need two logical expressions. One to give us the 'sum' output bit, and another to yield the 'carry_out' output bit.
Lets start with the sum. There are four cases where this bit is 1, so the logical expression we need is the disjunction (A or B or C... ) of these four cases. Each case is a conjunction of some set of values for each of the 3 input bits. For example, the first case where the sum bit is 1 is "I1 is false and I2 is false and carry_in is true," which I'll denote as I1 I2C.
Denoting disjunction as '+', then the full expression we're after is:
Similarly, for the carry_out bit we have:
To add two strings of binary digits, then, start with I1 and I2 equal to the zeroth (right-most) digits in each string. The initial carry_in is 0. The sum and carry_out bits are calculated according to the above two expressions. For the next step, I1 and I2 are assigned the values of the first digits (next to right-most position) in each of the input strings, and the carry_in is now assigned the carry_out value from the previous step. Finally, the result is the string generated by all the sum bits. We need a cascade of 9 full-adder circuits to perform the required logic.
I made a spreadsheet implementation of this procedure, which can be found here. You don't have write permission for that file, but if you save your own copy, then you shouldn't have any problem experimenting with it.
And that's all we need in order to do logical computations. We can gain some efficiency improvements by applying axioms and theorems of Boolean algebra to simplify the logical expressions we obtain (particularly when we have more complex expressions). This is called Boolean minimization (interestingly enough, this is often most easily done using a computer). But apart from that, the process described here is pretty much all there is to it.
By the way, the answer to the question, 234 + 111:
Actually, in technical circles, what I referred to as the first digit is normally called the zeroth digit - digits are counted the same way Europeans count the floors of a building (Europeans are more logical than Americans!). Therefore, the 3 in 234 is in the first position and the 2 is in the second position. From here on, I'll switch to the standard zero-based indexing. In this nomenclature, the power to which the base is raised is the relevant index, and not 1 subtracted from the index.
Expressing a number in binary uses almost exactly the same scheme, except that now each digit answers a yes/no type question. So if the number (base 10) is 15, we could start by asking 'is it larger than or equal to 24?' The answer is no, so a 0 goes into the left-most (in this case the fourth) digit. Next, 'does it contain 23?' Yes, 23 is 8, and 8 is less than 15, so the next digit is a 1: 01.
Having accounted for those 8, that leaves 7 remaining to be accounted for. Of those remaining 7, is there a 22 present? Yes: 011. And 3 left over. Of those remaining 3, is there a 21 present? Yes: 0111. And there is also a 20 left, so we end up with 01111. That's 15 expressed in binary.
Adding binary numbers
A device that adds together just two binary digits is called a half adder circuit. We'll understand why in a moment. Its inputs are I1 and I2. If I1 is 1 and I2 is 0, then the sum is 1. Similarly, if the values are reversed. If, however, the inputs are I1 = 1, I2 = 1, the sum (in decimal) is 2, which in binary is 10. We can't express this with a single output bit so we need two outputs, which we call 'sum' and 'carry'. In this case, the sum is 0 and the carry is 1.
This half adder circuit is not sufficient to add together strings of more than 1 bit. Suppose we are adding 11 and 01. For the
We don't need to know physically how such a circuit might be implemented (of course, digital electronics implements all logical operations using networks of transistors), but we do need to work out the logic of its operation. We can do this by drawing up a table.
| I1 | I2 | carry_in | decimal result | binary result | sum | carry_out |
| 0 | 0 |
0
| 0 | 0 | 0 | 0 |
| 0 | 0 |
1
| 1 | 1 | 1 | 0 |
| 0 | 1 |
0
| 1 | 1 | 1 | 0 |
| 0 | 1 |
1
| 2 | 10 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 2 | 10 | 0 | 1 |
| 1 | 1 | 0 | 2 | 10 | 0 | 1 |
| 1 | 1 | 1 | 3 | 11 | 1 | 1 |
All possible combinations of the 3 input bits are given in the 3 left-most columns. The fourth column states the standard decimal results when each of these combinations of 0's and 1's are added up. The fifth column converts these decimal results to binary. Finally, the last 2 columns are the zeroth (right-most) and the first digits of this binary result (the sum and carry_out, respectively).
We need two logical expressions. One to give us the 'sum' output bit, and another to yield the 'carry_out' output bit.
Lets start with the sum. There are four cases where this bit is 1, so the logical expression we need is the disjunction (A or B or C... ) of these four cases. Each case is a conjunction of some set of values for each of the 3 input bits. For example, the first case where the sum bit is 1 is "I1 is false and I2 is false and carry_in is true," which I'll denote as I1 I2C.
Denoting disjunction as '+', then the full expression we're after is:
sum = I1I2C + I1I2C + I1I2C + I1I2C
Similarly, for the carry_out bit we have:
carry_out = I1I2C + I1I2C + I1I2C + I1I2C
To add two strings of binary digits, then, start with I1 and I2 equal to the zeroth (right-most) digits in each string. The initial carry_in is 0. The sum and carry_out bits are calculated according to the above two expressions. For the next step, I1 and I2 are assigned the values of the first digits (next to right-most position) in each of the input strings, and the carry_in is now assigned the carry_out value from the previous step. Finally, the result is the string generated by all the sum bits. We need a cascade of 9 full-adder circuits to perform the required logic.
I made a spreadsheet implementation of this procedure, which can be found here. You don't have write permission for that file, but if you save your own copy, then you shouldn't have any problem experimenting with it.
And that's all we need in order to do logical computations. We can gain some efficiency improvements by applying axioms and theorems of Boolean algebra to simplify the logical expressions we obtain (particularly when we have more complex expressions). This is called Boolean minimization (interestingly enough, this is often most easily done using a computer). But apart from that, the process described here is pretty much all there is to it.
By the way, the answer to the question, 234 + 111:
yes, no, yes, no, yes, yes, no, no, yes
(101011001)
(101011001)
No comments:
Post a Comment