Discrete Mathematics for Computer Science

Ordering Relations 195

Solution. Given two words, we will say that the one occurring first in the dictionary is

less than (<) the other. For example,

elephant < tiger

aardvark < ant

and

oz < ozymandias

The first letters of elephant and tiger determine that elephant is less than tiger. In the

second pair of words, the first two letters in the same position that are different are a and n,

which occur in the second letter position. In the third pair of words, the first two letters that

are different in the same position are y and blank. The rule can be thought of most easily

as follows: Think of a word as an infinite string of symbols where all but the first finitely

many are blank. Now, to compare two words, look for the leftmost position at which the

two words contain different letters. For example,

aardvark oz

a n t o z y m a n d i a s

The smaller word of the pair is defined to be the one with the "smaller" symbol in the
position where the two words first differ. What the rule says is that you should look up
both words in a "dictionary" and then designate the first of the two words you come to,
starting from the front of the dictionary, as the smaller word. The described ordering gives
a linear ordering of all the words of a dictionary. 0

Extended ASCII Code

The storage of uppercase and lowercase letters of the alphabet in a computer often is done
by assigning an 8-bit binary code to each. A common computer code is the extended ASCII
code. Special characters and numerals as well as control codes are also assigned codes, but
the focus here is on the idea of what is happening. To be able to sort words, the code for "A'
must be easily recognized as smaller than the code for "B," "C," and so on. The extended
ASCII code for "A" is 01000001; the code for "B" is 01000010. Using the lexicographical
ordering on the bit positions starting at the left, the code for "A' is clearly smaller than the
code for "B":

01000001< "A"' 01000010

< "B"

The complete extended ASCII code assigns 8-bit binary strings to each letter of the alpha-
bet so that

"A" < '"B" < "C", < ... < "1X" < "Y" < "Z"1