2/2/98
- Transition from number 9 to number 2: In music, an octave is a fifth plus a fourth. Similarly, a ninth is a second plus an octave. So in some sense, a ninth is a second.
- Idea of base 2. On this page, we will write all numbers in base 2 in color.
The number 505 is actually 5*10^2 + 0*10^1 + 5*10^0. Similarly, in base 2, we think of the number 11010 as 1*2^4 + 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0 = 16 + 8 + 2 = 26.
Note that binary digits (usually just called "bits") are always either 0 or 1. Though this means that base 2 numbers are much longer than base 10 numbers, arithmetic is much simpler.
Converting a number from base 2 to base 10 is always like the example above. What about converting a number from base 10 to base 2?
One possibility is to work repeatedly with powers of 2. To write 53 in base 2, we first notice that 53 is between 32 (=2^5) and 64 (=2^6). If we next subtract 32 from 53, and get an answer of 21, we notice that this is larger than 16 (=2^4). Subtract 16 from 21, and we get 5. This is smaller than 8 (=2^3), but larger than 4 (=2^2). Subtract 4 from 5, and we get 1. Therefore, we know that 53 = 32 + 16 + 4 + 1 = 110101.
- However, a process of repeated division turns out to be much simpler (though it is harder to understand why it works). Take 53, keep dividing it by 2, and keep track of the remainders:
And then reading the remainders from the bottom to the top, we get 110101 as before.
53 = 2*26 + 1 26 = 2*13 + 0 13 = 2*6 + 1 6 = 2*3 + 0 3 = 2*1 + 1 1 = 2*0 + 1 - Adding numbers in binary is very simple. We only need to remember that 1+1=10. For example,
11011 + 10101 110000 - Multiplication is even simpler, since the only thing to remember is that 1*1=1. For example,
1011 * 101 1011 00 101100 110111 - Division is similar, but too complicated to type neatly.
2/4/98
You will find it helpful to refer to the handout when leafing through these notes.
- Words are arbitrary signs. We can divide a sign into signifier and signified.
- The philosopher Péirce distinguished three different types. Icons have a relationship of similarity between signifier and signified. An example might be a photograph. Indices have a causal relationship between signified and signified. Examples might be smoke as a sign of fire, or footsteps in the snow as a sign of animal activity. Symbols have an arbitrary relationship between signifier and signified. For example, "2" is an arbitrary sign for the concept "two." Technically, therefore, "2" is a "number symbol" and not a number.
Note that many signs overlap these categories. A particularly common example is that of trademarks. The logo for Southern California Electric manages to combine the letters S, C, and E in a way that looks like an electrical cord with a plug. The Finn Air logo is a stylized letter F that looks a bit like an airplane.
- It is precisely the arbitrary nature of words that makes comparative linguistics possible. Similarity of words between various languages demonstrates a common origin precisely because there is no other reason for words to be similar.
For example, gendered forms of "one" in French, Spanish, and Italian show a common origin, because there is no logical reason why "one" should be gendered.
But what about the words for "eight" in those three languages. At first glance, there is little commonality between "huit," "ocho," and "otto." However, in fact there is a commonality here, in which "it" in French relates to "ch" in Spanish and "tt" in Italian. This chart shows many other words with the same pattern.
This is an example of a linguistic correspondence.
English word French Spanish Italian eight huit ocho otto night nuit nocho notte cooked cuit cotto milk lait leche latte done fait hecho fatto
- New vocabulary: A few weeks ago, we talked about the nine primary vowel sounds. Consonants are classified along three major axes.
First, there is the voiced/voiceless question. This is also referred to as "laryngeal activity." For example, "ZZ" is voiced, and "SS" is the unvoiced equivalent sound.
Second, there is the "place of articulation." In other words, where in the aural cavity is the sound made? Possibilities include:
Term Place in aural cavity Example labial lips p dental teeth t velar back of aural cavity k Third, there is the manner of articulation. Plosives are made with an explosive release of air from the mouth; an example of the sound "p." Fricatives are made by gently releasing sound from the mouth. Others in this category are nasals, laterals, trills, and africates.
- Now that we have the vocabulary to discuss sound shifts, let's take an example. Consider the following chart:
The Latin sound [d] turns into the English sound [t], and the Latin sound [t] turns into the English sound [th] (usually written as the Greek letter theta, which isn't available in standard fonts).
Latin English German 2 duo
[d]two
[t]zwei
[ts]3 tres
[t]three
[th]Consider the following chart:
Corresponding sounds in the chart on the left were replaced over time by sounds in the chart on the right. In the old terminology, what happened was described as:
Indo-European Germanic (e.g., English)
voiceless plosives p t k voiced plosives b d g voiced aspirates bh dh gh
f th x p t k b d g
And so A shifts to M, which shifts to T, which shifts to A.
T tenues p t k M mediae b d g A aspirate bh dh gh
f th x A aspirate p t k T tenues b d g M mediae
- Another example is the word for the number 5. In Greek, that is "pente," and in English it is "five." This is an example of a shift from "p" to "f."
- Consider the words for 7. In Latin, we have "septum," in Greek we have "hepta," and in English we have "seven." In this case, we can see a shift from "p" to "v." How does this correspond to the previous example? In fact, in Old English, the word for 7 is "seofon," which does indeed contain the sound "f."
- How about 8? In Greek, we have "okto," in Latin "octo," and in English "eight." The "k" sound changed into "x," (what we usually think of as a guttural "ch"), and then the "gh" part of the word "eight" gradually stopped sounding.
- The Latin word for 10 is "decemb," the Greek word is "deka," and the English word is "ten." Here we see the shift from "d" to "t." How about the "k" sound in the Greek and Latin? It shifted to "x," as shown in the Gothic "taihun," and then gradually vanished.
- This sound shift is called the First Germanic sound shift, or Grimm's Law. The Brothers Grimm, of fairy-tale fame, were the first to publish it, though they didn't discover it.
- One more example: 100 in Latin is "centum," in German "he-katon," and in English "hundred." Here we see the "k" of "centum" and "he-katon" turning into the "h" of hundred.
- This sound shift was repeated again in the Second Germanic sound shift from Low German to (modern) High German.
- Now try taking a look at the Indo-European section of the hand-out. Note that there are strong similarities between Sanskrit, Greek, and Latin. For example, each of those languages has three forms of the word for one.
- But does Armenian deserve to be here? Consider for example the words for 2. In order to see if "erku" is related to "duo," we need to look for other evidence of a shift from "dw" in the rest of Indo-European to "erk" in Armenian. We can find at least three verifications:
These three examples give what is called tertium comparationis, the third verification needed to believe that such a rule might be true.
English Armenian Rest of Indo-European 2 erku dwuo fear erkiwl deos (Greek) long erkar *dwaron
- What lessons can we learn from this?
We need to distinguish when we are taking something on faith, and when we can explain why something works. The explanation usually comes after the realization that something works. For example, we can explain why the staircase method of building magic squares works, but it probably was first figured out inductively.
- There is regularity in linguistic change.
- We need to avoid being convinced by random similarities. Three instances should be found to demonstrate that something systematic is going on.
2/6/98
- The tables for multiplication and addition that were turned in for homework were symmetric about one diagonal because multiplication and addition are commutative. In other words, a+b=b+a and a*b=b*a.
Here are the tables for multiplication and addition in base 2:
Addition + 0 1 0 0 1 1 1 10
Multiplication * 0 1 0 0 0 1 0 1
- There are other types of operations we can consider on these numbers. But first, a small detour: We can identify 1 and 0 with various other ideas. Here's a chart summarizing many of these identifications:
1 TRUE (T) YES (Y) On + 0 FALSE (F) NO (N) Off -
- Other operations are often thought of as acting on T and F. For example, "AND" combines two statements, and the result is TRUE if both are true, and otherwise is FALSE. The symbol for AND is an inverted "v", which is hard to show typographically. Here's the table:
Notice that the result is the same as multiplication, and for that reason AND is sometimes also called "logical multiplication."
Logical AND AND 0=FALSE 1=TRUE 0=FALSE 0 0 1=TRUE 0 1
- Logical OR is true if either of the two statements being combined is true. The symbol for OR is a "v," which is hard to show typographically. The table looks like this:
Logical OR OR 0=FALSE 1=TRUE 0=FALSE 0 1 1=TRUE 1 1
- A related idea is "XOR," in which the result is true if exactly one of the two input statements is true, but false if both of the given statements are true. The symbol for this is a plus-sign with a circle around it, which isn't part of the usual fonts either. Here's the table:
Logical XOR XOR 0=FALSE 1=TRUE 0=FALSE 0 1 1=TRUE 1 0
- Another idea is "negation," written with a tilde (~). It is a "unary operator," meaning that it doesn't combine two statements, but only works with one statement. The table is consequently much simpler:
Logical negation x ~x 0=FALSE 1 1=TRUE 0
- Related to this, we can consider concepts of EVEN and ODD. A number is EVEN if that many stones (pebbles, dots, whatever) can be divided up into two piles containing the same number of objects. A number is ODD if it is not even.
With that in mind, we can easily work out that EVEN+EVEN gives EVEN, since we can just combine the four smaller piles and get two large even piles. Work through the logic, and you also can get EVEN+ODD=ODD, and ODD+ODD=EVEN (this last one is perhaps the trickiest to work through). We can therefore make an addition table for EVEN and ODD:
Notice now that if we replace the word EVEN by 0 and ODD by 1, we get the exact same table that we had for XOR. Here are the two side by side:
+ EVEN ODD EVEN EVEN ODD ODD ODD EVEN
XOR 0=FALSE 1=TRUE 0=FALSE 0 1 1=TRUE 1 0
+ EVEN ODD EVEN EVEN ODD ODD ODD EVEN
- What about multiplication? If we regard multiplication as repeated addition, some of this is easy to work out. Suppose that x and y are even numbers. Then x*y is what happens when we add x to itself y times. Since adding x to itself gives an even number, regardless of how many times we do the addition, we get EVEN*EVEN=EVEN.
How about EVEN*ODD? Again, think of this as x*y, where now x is EVEN and y is ODD. Again, we have to add x to itself a lot of times, and each time we get an EVEN answer. So EVEN*ODD=EVEN, and since multiplication is commutative, we also have ODD*EVEN=EVEN.
Finally, we have to think about ODD*ODD. You can do this concretely, but also a bit more abstractly. Suppose that x is ODD and y is ODD. Then y-1 is EVEN. We know algebraically that x*y is x*(y-1) + x. We just worked out that y-1 is EVEN, so x*(y-1) is EVEN. Therefore, x*(y-1) + x is EVEN+ODD, which is ODD. So ODD*ODD=ODD.
The full multiplication table looks like this:
Notice that this is the same result as multiplication (or logical AND), if we replace EVEN by 0 and ODD by 1. Here are the two side by side:
* EVEN ODD EVEN EVEN EVEN ODD EVEN ODD
* 0 1 0 0 0 1 0 1
* EVEN ODD EVEN EVEN EVEN ODD EVEN ODD
- The class ended with a short discussion of the Josephus problem, which will show up again at the start of next class.
2/9/98
- More about the Josephus problem: Line up n people in a circle. Every other living person commits suicide, starting with person number 2. What is the number of the last person left standing?
If there are 3 people in the circle, then person number 2 kills himself first, followed by person number 1, so person number 3 is the last person left standing. We summarize this by writing J(3)=3.
If there are 8 people in the circle, then person number 1 is the last person left standing (we worked that out in class on Friday). We summarize that by writing J(8)=1.
- Notes on homework assignments: When writing a foreign word, give the transliteration either underscored or in italics, followed usually by a gloss (indicating the meaning) in single or double quotation marks. If there is a pronunciation given (in other words, a transcription), give that in square brackets. For example:
The German word zwei 'two' comes from Old High German and is pronounced [tsvai].Warning: These notes will not always consistently follow that style, because of typographical difficulties working with HTML. That is no excuse for you, since you can either type your homework assignments or handwrite them.
When citing Menninger or Gardner, be sure to give a page reference.
- A bit more about the Latin sound shift from du to b: duenos becomes bonus 'good', duellum becomes bellum 'war'.
- Refer to the hand-out for a discussion of Proto-Indo-European and the languages that it has given birth to. These correspondences were noted over time. There are three possible explanations for a sound correspondence. First, it could be an accident. This is unlikely if there are many examples of the same correspondence. Second, the sound could be borrowed from another language. This is also unlikely, because sounds (unlike words) are seldom borrowed. Third, the correspondence could be genetic, indicating a common ancestry.
Small warning: do not confuse Germanic with German.
Words in Latin that begin with f often correspond to Germanic words beginning with p. But the chart makes clear that the Latin words did not turn into Germanic words. Instead, both came from a common Proto-Indo-European ancestor. Note: We write the ancestor word beginning with an asterisk (*) to indicate that it is a conjectural reconstruction.
So the PIE *pater is a common ancestor for Germanic father, Latin pater, Greek pater, Armenian hayr and Sanskrit pita.
- Remember the First Germanic Sound Shift, or Grimm's Law. Now we talk about the Second Germanic Sound Shift. This took place only in High German (which was spoken in southern Germany, which is higher in altitude than northern Germany, and hence northern German dialects are called Low German). High German was spoken in Austria and Bavaria, for example.
The sounds [p], [t], and [k] became [pf-], [ts], and [kx] respectively (except that this last generally reverted to [k]). These sounds are affricates, which are plosives followed by fricatives.
For example, pipe became pfeife, showing [p] to [pf] shift. We also have water becoming wasser, showing the [t] to [ts] shift, and two becoming zwei as another example of the same shift.
Another part of the same shift had [f], [th] (which should be theta) and [x] becoming [v], [voiced th], and [gamma] respectively. These sounds then become [b], [d], and [g] respectively. What happens here is that voiced fricatives become voiced plosives. For example, seven becomes sieben showing [v] becoming [b], and three becomes drei, showing [th] becoming [d].
- A bit about generalizations to lead into the next class. We saw last time that we could construct addition and multiplication tables for EVEN and ODD. Let's try to generalize these ideas and see what happens.
Call a number 3EVEN if it is a multiple of 3, and 3ODD if it isn't. We will try to construct multiplication and addition tables for 3EVEN and 3ODD next time.
2/11/98
- We can try to construct an addition table for 3EVEN and 3ODD numbers. The same arguments that we used for EVEN and ODD show that 3EVEN+3EVEN=3EVEN, and 3EVEN+3ODD=3ODD.
What about 3ODD+3ODD? We can experiment a bit, and see that 1+2=3 (an example of 3ODD+3ODD=3EVEN), but 2+2=4 (an example of 3ODD+3ODD=3ODD). Therefore, we can't fill in our chart completely; the best we can do is
+ 3EVEN 3ODD 3EVEN 3EVEN 3ODD 3ODD 3ODD 3ODD
or
3EVEN
- We can try to do the same thing for multiplication. The same arguments that we used for EVEN and ODD give us 3EVEN*3EVEN=3EVEN and 3EVEN*3ODD=3EVEN. We know that ODD*ODD=ODD. What happens when we try to mimic the arguments used earlier?
Suppose that x and y are 3ODD numbers. Then x*y is x+x+x...+x added together y times. If we try to analyze this sum, we have to start by talking about x+x. But 3ODD+3ODD can be either 3ODD or 3EVEN. So we can't start copying the result that we used earlier.
The multiplication table actually looks like this:
but we haven't yet given a convincing argument for the entry in the lower-right hand corner.
* 3EVEN 3ODD 3EVEN 3EVEN 3EVEN 3ODD 3EVEN 3ODD
- Remember that we were talking about various operations that we can perform on binary numbers: negation (symbolized by ~), AND, OR, and XOR. Now we expand upon those ideas a bit.
Take the numbers from 0 to 7, write them in binary, and then negate each bit (so that 0 becomes 1, and vice versa). Then write the result back in base 10. Here's what the chart looks like:
Number in base 10 Number in base 2 Negate each bit Convert to base 10 0 000 111 7 1 001 110 6 2 010 101 5 3 011 100 4 4 100 011 3 5 101 010 2 6 110 001 1 7 111 000 0
This is called taking the 2's complement of the number. In a fashion that can be made precise, a computer can regard 0 and 7 as the negative of each other.- We can think of x AND y as the result of putting switches for x and y in series. We can think of x OR y as the result of putting switches for x and y in parallel.
- There are other operations that can be created by conjoining these two. For example, we can define x NAND y as NOT(x AND y), and x NOR y as NOT(x OR y). The symbol for NAND is often an upward arrow, and NOR is often a downward arrow.
- We can build XOR from NOT, AND, and OR. Remember that x XOR y is true if either x or y, but not both, are true. We can check that x XOR y = (NOT x AND y) OR (x AND NOT y):
x y (NOT x) AND y x AND (NOT y) ((NOT x) AND y) OR (x AND (NOT y)) x XOR y 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 1 1 1 0 0 0 0
- A bit about usage: The sentence "Stop and I'll shoot" means "If you stop, then I'll shoot." The sentence "Stop or I'll shoot" means "If you don't stop, then I'll shoot." Clearly, the use of the word "if" is extremely complicated.
- The answer to the Josephus problem looks like this:
Among the observations that we can make are
n J(n) 2 1 3 3 4 1 5 3 6 5 7 7 8 1 9 3 10 5 11 7 12 9 13 11 14 13 15 15 16 1
We can express all of these symbolically rather than in words. We can write that J(n) is always odd, and that J(2^k) = 1, and if J(n)=n, then J(n+1)=1, and that J(n) = J(n-1)+2 usually. Some of these are easier to prove than others.
- The answers are all odd.
- When n is a power of 2, you get 1.
- When J(n) = n, then the next answer is 1.
- The numbers usually go up by 2.
- What about the first one? Well, the first time around the circle, person number 2 commits suicide, then person number 4, and so on. After one circuit of the circle, every even-numbered person is dead. Therefore, J(n) must be odd.
- How about J(2^k)=1? This is hard to argue without graphics. Basically, the idea is that if there are 2^k people in the circle, after one circuit of the circle, there are 2^(k-1) people in the circle, and after 2 go-arounds there are 2^(k-2) people left, and so on. Eventually, the only person left is person number 1.
- The other two can be argued as well, but we leave that for next time.
2/13/98
- Continuing our analysis of the Josephus problem: We can make the following argument about why J(n) is usually 2 more than J(n-1).
Suppose that we have a circle containing n people, and person number 2 kills himself. We now have a circle with n-1 people, but the numbering is not quite what we would like: the next person to kill himself will be person number 4, not person number 2. We can imagine solving the Josephus problem with n-1 people and finding J(n-1), but the problem is that our numbering will be off by 2 (mostly; see below for a small additional complication), so we get that J(n) = J(n-1)+2.
But there's one problem: What happens if J(n-1) = n-1? In that case, the last person left alive will be the person originally numbered 1. (You need to draw a circle and label the circle with numbers to believe this.) So if J(n-1)=n-1, then J(n)=1. And that gives us all the information we need to decide that everything we observed last class is in fact correct.
The problem is that we still need a fast way to figure out J(n); what we have so far is an "inductive solution," meaning that in order to figure out J(41), we first need to figure out J(40), which in turn means that we have to figure out J(39) and so on. That's too slow to be of much use.
Instead, we rely on the fact that J(2^k)=1. If we want to figure out J(n), we write n as 2^k+m. Then we know that J(2^k)=1, and J(n) is m numbers further along in the sequence than J(2^k). Since we are going up by 2 each step, we get that J(n)=2m+1. For example, we can write 41 as 32+9, and then we get right away that J(41)=2*9+1=19.
There is also a fast way to solve this problem if we write the numbers in base 2. The complicated arithmetic formula above about powers of 2 amounts to the following description in base 2: take the first digit of your answer, and shift it to become the last digit. For example, 41=101001. We take the 1 at the front of the number, and shift it to the end, and get 10011. You can check that this is in fact 19.
- How do computers add whole numbers? Remember that we talked last time about how to get computers to compute AND, OR, and NOT, and we built XOR out of those three. But what about addition? Remember the addition table:
How can we do that combining our logical operations?
ADD 0 1 0 0 1 1 1 10
It helps to think of the table as looking like this:
Now focus separately on the first bit and the second bit of the answers, which we will call C (for "carry") and S (for "second bit"):
ADD 0 1 0 00 01 1 01 10
Now we can see that the C chart is in fact AND, and the S chart is in fact XOR. So adding one bit to one bit (which is called a "half-adder") is in fact just two separate operations of AND and XOR.
C 0 1 0 0 0 1 0 1
S 0 1 0 0 1 1 1 0
- Another key fact about 2 is that sqrt(2) is "irrational," i.e., cannot be written as a fraction. The number sqrt(2) occurs naturally as the length of the hypotenuse of an isosceles right triangle with leg 1 (remind yourself of what the Pythagorean theorem says if you don't recall it). There are many tables from many cultures giving approximations to sqrt(2) using the following idea: if a/b is close to sqrt(2), then c/d is closer, where d=a+b and c=b+d. Such a table could look like this:
Numerator Denominator Fraction 3 2 3/2 7 5 8/5 17 12 17/12 41 29 41/29 99 70 99/70
Apparently, though, only Greek mathematicians, soon after the time of Pythagoras (perhaps around 450 BC) proved that sqrt(2) is irrational.
One proof goes like this: Suppose that we can find integers a and b so that a^2 + a^2 = b^2. We can rewrite this as 2a^2=b^2.
Then this says that b^2 is even, and therefore b is even (why?), so write b=2c. Substitute that into the previous equation, divide through by 2, and you get a^2 = 2c^2.
This in turn says that a is even, so we can write a=2d. Substitute that into the previous equation, divide through by 2, and we get 2d^2=c^2.
What's the problem? Well, we started with integers a and b that solved the equation 2x^2=y^2, and now we found smaller integers c and d that solve the same equation. But we can repeat this process forever, getting smaller and smaller integers that solve the same equation.
The problem is that you can't have an infinite sequence of decreasing positive integers. So that's why there are no integers a and b to start with.
2/16/98
- More about the irrationality of the square root of 2. There is a geometric interpretation which is unfortunately not going to appear here on the web. The first reference is to Aristotle's Prior Analytics.
Aristotle's argument is slightly different from the one in the last class. He reasoned as follows:
Suppose that sqrt(2) is a fraction. Write sqrt(2)=a/b. We know that every fraction can be put into lowest terms, so we can suppose that a/b is in lowest terms. In particular, we know that if a fraction is in lowest terms, then either the numerator or denominator (or both) must be odd (because if both are even, then you can divide both the numerator and denominator by 2).Take the equation sqrt(2)=a/b, and square both sides; you get 2=a^2/b^2. Cross-multiply, and you get 2b^2=a^2. This says that a^2 is even, and so a is even. By our previous observation, we know that b must be odd.
Since a is even, we can write a=2c. Substitute that into the equation 2b^2=a^2, and we get 2b^2=4c^2, or b^2=2c^2. But this says that b^2 is even, and so b is even.
We have arrived at a contradiction, and hence we can conclude that sqrt(2) is not a fraction.
- We can turn fractions into binary system "decimals", and vice versa. The process goes exactly the same way as it did for ordinary decimals, and since the layout is close to impossible, it will not be included here.
- Start thinking about constructing 16-by-16 OR and AND tables. How do we AND and OR numbers?
Consider 7 AND 8. Start by writing both in binary, so we are really thinking of 0111 AND 1000. (Write each using 4 bits; in general, you need to write each number with the same number of bits). Then AND the numbers bit by bit. Since 1 AND 0 = 0, we get 0111 AND 1000 = 0000.
On the other hand, 1 OR 0 = 1, so we get 0111 OR 1000 = 1111.
2/18/98
- Suppose that we have a computer which is limited to 4 bits, so it can represent the 16 numbers between 0000 and 1111. If we only want to represent positive numbers, then we already know that these numbers in base 2 are the same as the numbers from 0 to 15 in base 10.
But what happens if we need our computer to represent negative numbers? One solution is to use the last three bits to represent numbers from 000 to 111 (i.e., from 0 to 7), and use the first bit as a "sign bit." We could for example use 0010 as the representation of +2, and 1010 as the representation of -2.
But this turns out to be much harder to implement than one might think. Instead, we use the idea that we agree that 0000 is 0, and then we try to subtract 1 from 0000 to get the representation for -1. When we try to do that, we get the answer 1111. From that point on, there is no problem repeatedly subtracting 1 from each binary number to get the preceding binary number. We end up with
The striking thing is that we can do arithmetic with these numbers without worrying about the sign at all, provided that we ignore all but the last four bits of our answer.
7 0111 6 0110 5 0101 4 0100 3 0011 2 0010 1 0001 0 0000 -1 1111 -2 1110 -3 1101 -4 1100 -5 1011 -6 1010 -7 1001 -8 1000
- Recall our discussion of the half-adder. How does one combine half-adders to get a full-adder?
Remember that the half-adder produces two pieces of information, S and C, from inputs X and Y. C is the "carry bit," which has to get carried to the next column. So a full-adder has to take three inputs, A, B, and C (the carry from the previous column), and produce two outputs, which we will call S (the bit that goes into a particular column) and D (the carry to the next column).
There are 8 possibilities, representing the 8 possible values of A, B, and C:
These can be expressed in formulas as follows (and this is by no means obvious). D will be 1 if 2 or 3 of A, B, and C are 1. That gives the formula
A B C D S 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0
D = ABC + AB(~C) + A(~B)C + (~A)BC where the convention is that we represent AND by multiplication, and OR by addition.
S will be 1 if an odd number of A, B, and C are 1. The formula for S is more complicated:
S = ((~A)B + A(~B))C + ((~A)B + A(~B))(~C). The virtue of these expressions is that they can be gotten from 2 half-adders, one for A and B and one taking the S output of A+B and adding that to C, and one OR that combines the C output of the two half-adders.
- Binary classifications let us classify n items using only log_2 n features, provided that we can correctly come up with enough features to distinguish the items. Examples in class consisted of four shapes, two shaded and two not, and 6 of the 8 cardinal vowels.
- Recall that an idea gets translated into a statement which is transmitted via a medium to the listener, who decodes the statement to get an approximation of the original idea. But there are more complicated features that can come into play.
For example, we can have a message about a message. This is "reported speech." An example is hearsay; Bulgarian even has a "hearsay tense" to distinguish between reported facts and ones that were observed first-hand.
We can also have code about message. This is an example of a shifter, about which more will be said next time.
2/20/98
- Some notes about the mid-term:
- The Second Germanic Sound Shift will not be included on the examination, but the First Germanic Sound Shift is fair game.
- Nothing from either text (Menninger and Gardner) will be on the examination.
- The examination includes material from the entire semester up until today's (February 20) class.
- The answer to the question about AND and OR tables is available. Click here for a quicker-loading but less pretty version, or click here for a lovely but very slow-loading set of pictures.
- Remember last time that we were talking about messages (M) and code (C). M might be the content of what is said, and C is the form.
- But either of these can be applied to either of these, giving a grid. Last time we filled in two entries in the grid:
Recall that Bulgarian has a "hearsay tense," and German uses the subjunctive for things which have been reported but about which the speaker is not certain.
M C M Reported speech (hearsay) C Shifters
A "shifter" is something which is defined by reference to a particular situation. Examples are pronouns and tenses.
What about the remaining two categories? M about C is called "metalanguage." Examples are "This verb is in the third person plural" or "`Dog' means `canine.'"
An example of code about code is proper names. So the entire chart can look like this:
All four can occur in one sentence. Consider:
M C M Reported speech (hearsay) Metalanguage C Shifters Proper names
Jim told me that "flicks" means "movies."In this sentence, the word "Jim" is code about code, the word "me" is a shifter, and the phrase "'flicks' means 'movies'" is metalanguage. The entire sentence is an example of reported speech.
- We are going to focus today on shifters. There are two oppositions in pronouns: I vs. you, and us vs. them.
- Small digression: the word "stereo" is not etymologically a word meaning two, but today it means a sound system with two channels.
- Another digression about stereotypes:
- There are two types of people in the world: those who think that there are two types of people in the world, and those who don't.
- There are three types of people in the world: those who can count, and those who can't.
- Pronouns in English are usually categorized as
Focus just on the singular column. We have three items, so we need two categories to distinguish them. One natural opposition is to think of I/You vs. He/She/It, and take the speaker-listener pair vs. the outside world. How to find another category?
Person Singular Plural I I We II You (singular) You (plural) III He/She/It (singular) They
What is meant by "we"? The notion "first person plural" is not a clearly defined one. Sometimes "we" means "I and you" and sometimes it means "I and He/She/It." The first is called the "inclusive we," and the second is the "non-inclusive we."
It makes sense to continue to differentiate the third-person from the other two, and to use as the second-feature the included/excluded dichotomy.
The chart can look like this:
I II III Feature 1:
Speaker-listener+ + - Feature 2:
Listener- + -
- A note on a relationship between 2 and 5 (which is the next number to talk about): to calculate 5% sales tax, it is simplest to divide by 2 and then shift the decimal point. For example, the sales tax on $14.00 is $0.70, gotten by dividing $14.00 by 2 and then shifting the decimal point one to the left.
- English has many numerical forms, but here are two of the oldest:
For numbers above 2, the etymological relationship between the two columns is clear. What about the word "second"? In German, there is a relationship between "zwei" (two) and "zweit" (second). (But German also uses "ander" to mean "second"; "ander" is cognate to the English word "other.")
Cardinal Numbers Ordinal Numbers One First Two Second Three Third Four Fourth
- The word "second" is not Germanic, but came to English from Latin via French. The Latin word "secundus" is derived from "sequor" meaning "follow" (English "sequence" has the same root), and "secundus" means "following" or "next."
- How about the word "second" meaning a unit of time? This derives from "seconda minuta" (second division of an hour). "Prima minuta" (the first division of an hour) gives the word "minute." The same derivation gives us the words minute and second for dividing degrees of latitude and longitude.
2/23/98
- Pythagorean music theory: the Pythagoreans believed the music can be studied systematically and mathematically.
Take a long string. Suppose that we call the note that it is making C. Divide the string into two equal parts. The resulting note is an octave higher, and is written c.
Divide the string instead into 4 equal parts. The resulting note is an octave higher than c, and two octaves higher than C. It is written c'.
But what if we divide the string into 3 equal parts? The resulting note is called g, and is a fifth higher than c. The ratio of 2:3 in length (or 3:2 in frequency) is called a fifth.
The ratio of c' to g is called a fourth. This is the same as the ratio of f to c. The key idea here is that a fourth and a fifth are complementary intervals: they add to an octave.
- Mathematically, we can think of 5 as either 3+2, or 1+4. Focus first on 3+2, and notice that 3 and 5 are primes that differ by 2. Primes that differ by 2 are called prime pairs, and were studied as far back as Greek mathematicians. The first few prime pairs are 3,5; 5,7; 11,13; 17,19; and so on. It is still unknown whether there are infinitely many prime pairs, but their number certainly dwindles: if we look for prime pairs up to 1000, we will find far fewer than 10 times as many as the number of prime pairs up to 100.
- How to quickly make a list of primes up to 100 (or 1,000)? Use the sieve of Eratosthenes: Make a list of all numbers up to 100. First cross out 1. Then cross out every other number, to take care of the even numbers. Cross out every third number, to take care of multiples of 3. Then cross out every fifth number, to take care of multiples of 5. Repeat until all that you have left are the primes up to 100.
- The other way to look at 5 is as 1+4, and this suggests two different problems. First, we can look at sums of squares:
How can we find a formula to give us the sums of the squares?
1 = 1 5 = 1+4 14 = 1+4+9 30 = 1+4+9+16
- Another question is simpler to state, but harder to answer: we notice that 5=1+4, and 2=1+1, and 10=9+1, and 13=9+4. How can we figure out which numbers are sums of squares?