20.8.11
Summary
- We discussed forms of data and processes relevant to an electronic till in a supermarket. In particular, we introduced the idea of a sequence of data items.
- A number of fundamental forms of data were introduced. We distinguished two types of number: integers (positive or negative whole numbers, or 0), and real numbers (thought of as decimal numbers and approximated in computers as floating point numbers). Characters may be thought of as symbols that may be entered from a computer keyboard by a single keystroke. Each character is associated with an integer code and we introduced one such encoding called the ASCII code. The Boolean values true and false form another fundamental form of data.
Data may be structured in a collection. Different forms of collection are possible. We looked at two: sets and sequences. In a sequence, the order in which the items appear in the collection is important and an item may appear more than once. In a set, one is only interested in the different items appearing in the collection, and the order in which these items are listed is of no significance, nor is repetition of an item.
The Cartesian product of sets X and Y is written X × Y , and is the set consisting of all ordered pairs (x, y), where x is in X and y is in Y . An ordered pair is also called a 2-tuple. More generally, an n-tuple is an association of n items, each taken from a specified set. An n-tuple is written in round brackets, and is a member of a Cartesian product set combining n component sets. For example, a member of the set Int × Char × Int × SeqOfChar would be a 4-tuple, such as (121, ‘y’, 6, “Qwerty”). - The disjoint union of sets X and Y, written X
Y, consists of all items that come either from X or from Y (where X and Y have nothing in common). This is useful when we want to mix different forms of data in a sequence. - A function is a process that returns a unique value for each permitted input. To give a full description of a function, we give: its signature (name, and input and output sets), a precondition (which may be true), and a postcondition giving its semantics. The semantics should be an unambiguous statement of the relationship between the returned value and the input(s).
If a function has more than one input, then its input set will be a Cartesian product. If a function returns a value that is true or false, then the output set will be Bool. Usually, the semantics of a function are given by a general rule, or possibly by a formula. However, in some cases we need to list the returned value for each possible input. For example, this would be the case for a function returning the price of each barcoded product stocked by a supermarket. - A binary operation is a process, such as addition of integers, that inputs two data items of the same type. A binary operation can be written using infix notation (as in x + y, for example). Addition of integers corresponds to a function with signature Int × Int → Int. We described integer division. Integer division of n by d returns an integer, written DIV (n, d). It also leaves a remainder, denoted by MOD(n, d).
We noted that binary operations are not confined to those on numbers. We described two binary operations on Boolean values that are frequently useful: ∨ (read as “or”) and ∧ (read as “and”). We also introduced the function NOT on Booleans.
Comparisons, such as < or =, are operations returning values in the output set Bool. For example, = Char , a test of whether two characters are identical, corresponds to a function with signature Char × Char → Bool.
Exercises on Section 5
Exercise 12
Give a full description of a function (using the infix notation ×) corresponding to multiplication of integers.Answer
Solution
A suitable description of integer multiplication is given below.function (infix) (x × y on Int) return in Int
pre true.
post The returned value is the result of multiplying x and y.
Exercise 13
With n = 966, evaluate each of:(a) MOD(n, 10);
(b) DIV (n, 10);
(c) MOD(DIV (n, 10), 10).
Answer
Solution
966 = 96 × 10 + 6. So (a) MOD(966, 10) = 6 (the remainder when 966 is divided by 10), and (b) DIV (966,10) = 96. Then (c) MOD(DIV (966, 10), 10) becomes MOD(96, 10). This evaluates to 6, which is the remainder when 96 is divided by 10.Exercise 14
The function LAST is described below.function LAST(s in SeqOfX ) return in X
pre s is not empty.
post The returned value is the last element in s. For example, LAST([1, 2, 3]) = 3.
Consider the expression NOT(LAST(s) = Char LAST (t)).
- (a) What is the value of this expression if s is “the” and t is:
- (i) “same”;
- (ii) “different”?
- (i) “same”;
- (b) Under what circumstances does this expression have the value true?
- (c) Is this expression valid with s = [1,2] and t = [1,8,4,2]?
Answer
Solution
(a) If s = “the” then LAST(s) = ‘e’. (i) With t = “same”, we have LAST(t) = ‘e’, and the given expression becomesNOT(‘e’ =Char ‘e’) = NOT (true) = false.
NOT(‘e’ =Char ‘t’) = NOT (false) = true.
(c) With these values of s and t, the given expression becomes NOT(2 =Char 2). Now =Char compares two characters, and 2 is an integer. So this expression is not valid. (For the given expression to be valid, we need s and t to be sequences of characters, and to be non-empty, so that the precondition of LAST is satisfied.)
Objectives for Section 5
After studying this section you should be able to do the following.
- Recognise and use the terminology: binary operation, infix notation, quotient and remainder (associated with integer division).
- Use the notation for various binary operations introduced in the text, in particular DIV and MOD on integers; and ∧ (and) and ∨ (or) on Boolean values.
- Suggest appropriate signatures and preconditions for functions corresponding to binary operations, including comparisons that return Boolean values.
- Evaluate expressions involving functions and binary operations introduced in the text. Take note of where brackets appear in an expression.
- Recognise an expression that is invalid because it uses a process in a way inconsistent with its signature or precondition.
5.4 Expressions
In computer code, one may want to formulate an expression to achieve some particular purpose, such as to express some condition about the states of variables involved in the code. For example, suppose that you want to express the condition that a sequence s contains at least two members, and that the second member of s is not the space character (with ASCII code 32). This condition holds when the expression below is true.
(SIZE(s) > Int 1) ∧ (NOT(ASC(AT(2,s)) = Int 32))
When writing expressions involving functions and binary operations, there are some points to be careful about. One needs to be careful to use brackets as necessary to ensure that operations are applied in the desired order. This is particularly important in expressions using infix notation. You also need to apply each process in a way that is consistent with its signature. And you must apply each process in a way that is consistent with any precondition that it has. We say that an expression is not valid if it uses a function in a way that is inconsistent with its signature or its precondition. For example, ‘Q’ = Int 32 is not valid, since = Int compares two integers, and ‘Q’ is a character, while PUT(7, “This”, ‘Q’) is not valid, since 7 does not satisfy the precondition of PUT. (The precondition of PUT requires that 7≤ SIZE(“This”), but SIZE(“This”) is 4.)
The functions SIZE and AT were described in Activity 16, and the function ASC was described in Section 4.3. The binary operations = Int , > Int and ∧ are defined earlier in this section.
Notice how important the brackets are in a complicated expression. The order in which the bits of the overall expression are to be evaluated is determined by the way the brackets appear in the expression. We need to follow this carefully in evaluating an expression such as that in Activity 28 (a) (v). A slip in placing one bracket can easily lead to an expression that is not valid, as in (c) above. On the whole, it is good practice when writing computing code to seek to avoid writing complicated expressions. Usually one can split the code into intermediate steps, as indicated by the steps in the evaluation in (a) above.
(SIZE(s) > Int 1) ∧ (NOT(ASC(AT(2,s)) = Int 32))
When writing expressions involving functions and binary operations, there are some points to be careful about. One needs to be careful to use brackets as necessary to ensure that operations are applied in the desired order. This is particularly important in expressions using infix notation. You also need to apply each process in a way that is consistent with its signature. And you must apply each process in a way that is consistent with any precondition that it has. We say that an expression is not valid if it uses a function in a way that is inconsistent with its signature or its precondition. For example, ‘Q’ = Int 32 is not valid, since = Int compares two integers, and ‘Q’ is a character, while PUT(7, “This”, ‘Q’) is not valid, since 7 does not satisfy the precondition of PUT. (The precondition of PUT requires that 7≤ SIZE(“This”), but SIZE(“This”) is 4.)
The functions SIZE and AT were described in Activity 16, and the function ASC was described in Section 4.3. The binary operations = Int , > Int and ∧ are defined earlier in this section.
Activity 28
- (a) With s = “I#am.”, evaluate each of the expressions:
- (i) AT(2, s).
- (ii) ASC(AT(2, s)).
- (iii) ASC(AT(2, s)) = Int 35.
- (iv) NOT(ASC(AT(2, s)) = Int 35).
- (v) (SIZE(s) > Int 3) ∧ (NOT (ASC (AT (2, s)) = Int 35)).
- (i) AT(2, s).
- (b) Let s be a general string. Under what circumstances does the expression in (a) (v) give the value true? Under what circumstances is that expression valid?
- (c) With s = “I#am.”, why is it not possible to evaluate the expression
Discussion
- (a) (i) AT(2, s) = ‘#’.
(ii) ASC(AT(2, s)) = 35.
(iii) ASC(AT(2, s)) = Int 35 becomes 35 = Int 35, which evaluates to true.
(iv) NOT(ASC(AT(2, s)) = Int 35) becomes NOT (true) = false.
(v) We have SIZE(s) = 5 (the number of characters in the string “I#am.”), so (SIZE(s) > Int 3) becomes (5 > Int 3) which is true. So the expression in (v) becomes true ∧ false = false. - (b) The given expression will be true only if each of SIZE(s) > Int 3 and NOT(ASC(AT(2, s)) = Int 35) is true. The first of these is true if the string s contains at least four characters. The second is true if the second character is s is not the character ‘#’. So the expression in (a) (v) will be true if:
the string s contains at least four characters and its second character is not ‘#’.
The precondition of AT requires here that the string s contains at least two characters. The expression in (a) (v) will be valid so long as this is true. (All the other functions in the expression are total. The example in part (a) indicates that the expression is put together in a way that is consistent with the signatures of the functions.) - (c) AT(2,s) = ‘#’. Then AT(2,s) = Int 35 becomes ‘#’ = Int 35. This expression is not valid, since = Int requires two integers as inputs, and ‘#’ is a character. So the given expression is not valid.
5.3 Comparison functions
Another situation where we use infix notation is in writing comparisons, such as x < y, where x and y are numbers. Such a comparison is either true or false. For example, 5 < 9 is true but 5 < 2 is false. To describe a corresponding function, we take the output set to be Bool = {true, false}. Thus the comparison < on integers corresponds to a function, which we can describe as follows.
function (infix) (x < Int y on Int) return in Bool
pre true.
post The returned value is true if x < y and is false otherwise.
Equality is also a comparison function. This is normally written using the infix symbol =. If x and y are numbers, then x = y is true if the numbers x and y are the same and is false if they are not. If one is working with real numbers on a computer, then one needs to be very careful with tests of equality. There will be an element of approximation in the way real numbers are stored, and this may result in a computer reporting real numbers as equal when they are only approximately equal. However, we shall confine our attention to integers, where there is no such problem in deciding whether two numbers are the same.
Sometimes we may wish to test to see whether two characters are the same. (This can be done by comparing their ASCII codes, for example.) A computer will need to work in a different way when comparing two integers for equality from that needed when comparing two characters for equality. These are different processes. Equality of numbers is a function with signature Int × Int → Bool; equality of characters, on the other hand, has signature Char × Char → Bool. Since these are different functions, we will give them different identifiers. We will write = Int for equality of integers and = Char for equality of characters.
function (infix) (x = Int y on Int) return in Bool
pre true.
post The returned value is true if the integers x and y are equal and is false otherwise.
function (infix) (x = Char y on Char) return in Bool
pre true.
post The returned value is true if the characters x and y are the same and is false otherwise.
One could give a binary operation < that compares characters by comparing their ASCII codes. Again, this is a different function from that of comparing integers (which is why we used a subscript Int in the identifier < Int for comparison of integers above).
Note that in mathematics the term binary operation would only be used for a total function whose return type is the same as the type of the inputs.
function (infix) (x < Char y on Char) return in Bool
pre true.
post The returned value is true if ASC(x) < Int ASC (y) and is false otherwise.
In practice, a variety of different comparisons are used on integers (and other forms of data, such as characters), including: > (strictly greater than), ≤ (less than or equal), ≥ (greater then or equal), and ≠ (not equal). Functions may be described for each of these, but we shall not do so here.
function (infix) (x < Int y on Int) return in Bool
pre true.
post The returned value is true if x < y and is false otherwise.
Equality is also a comparison function. This is normally written using the infix symbol =. If x and y are numbers, then x = y is true if the numbers x and y are the same and is false if they are not. If one is working with real numbers on a computer, then one needs to be very careful with tests of equality. There will be an element of approximation in the way real numbers are stored, and this may result in a computer reporting real numbers as equal when they are only approximately equal. However, we shall confine our attention to integers, where there is no such problem in deciding whether two numbers are the same.
Sometimes we may wish to test to see whether two characters are the same. (This can be done by comparing their ASCII codes, for example.) A computer will need to work in a different way when comparing two integers for equality from that needed when comparing two characters for equality. These are different processes. Equality of numbers is a function with signature Int × Int → Bool; equality of characters, on the other hand, has signature Char × Char → Bool. Since these are different functions, we will give them different identifiers. We will write = Int for equality of integers and = Char for equality of characters.
function (infix) (x = Int y on Int) return in Bool
pre true.
post The returned value is true if the integers x and y are equal and is false otherwise.
function (infix) (x = Char y on Char) return in Bool
pre true.
post The returned value is true if the characters x and y are the same and is false otherwise.
One could give a binary operation < that compares characters by comparing their ASCII codes. Again, this is a different function from that of comparing integers (which is why we used a subscript Int in the identifier < Int for comparison of integers above).
Note that in mathematics the term binary operation would only be used for a total function whose return type is the same as the type of the inputs.
Activity 27
Give a full description of an infix function corresponding to < Char comparing two characters by comparing their ASCII codes.
Discussion
A description is given below.function (infix) (x < Char y on Char) return in Bool
pre true.
post The returned value is true if ASC(x) < Int ASC (y) and is false otherwise.
5.2 Operations on Boolean values
The idea of a binary operation, and the use of infix notation, is not confined to numbers. Infix notation may be used for any process with two inputs from the same set. We look now at two binary operations on Boolean values that are often used.
The first of these takes two Boolean values, and returns true if both of the input values are true and returns false otherwise. It is a binary operation, and we shall write it using the infix notation ∧, where the symbol ∧ can be read as “and”. So a ∧ b is true only when a and b are both true. We can describe the function corresponding to this operation as below (The operation ∧ is also known as conjunction).
function (infix) (a ∧ b on Bool) return in Bool
pre true.
post The returned value is true if both a = true and b = true, and is false otherwise.
Alternatively, we could give the semantics of ∧ by listing the returned value in each of four cases, giving the four possible combinations of input values. Using this approach, we could express the postcondition as follows.
post The returned value is c, where
function (infix) (a ∨ b on Bool) return in Bool
pre true.
post The returned value is false if both a = false and b = false, and is true otherwise.
post The returned value is c, where
Another useful process on Boolean values inputs a single Boolean value, and returns the reverse of that value. This process, called negation, is not a binary operation, since it has one input only. We call this function NOT, and we have
function NOT(a in Bool) return in Bool
pre true.
post The returned value is false if a = true and is true if a = false.
(b) (i) Substituting for a and b, we have true ∨ false = true.
(ii) We should evaluate the term in brackets first: true ∨ false = true. Then NOT(true) = false. So NOT(a ∨ b) = false.
(iii) Again, evaluate the term in brackets first: (true ∨ false) = true. Then the given expression becomes true ∧ true which evaluates to true.
The first of these takes two Boolean values, and returns true if both of the input values are true and returns false otherwise. It is a binary operation, and we shall write it using the infix notation ∧, where the symbol ∧ can be read as “and”. So a ∧ b is true only when a and b are both true. We can describe the function corresponding to this operation as below (The operation ∧ is also known as conjunction).
function (infix) (a ∧ b on Bool) return in Bool
pre true.
post The returned value is true if both a = true and b = true, and is false otherwise.
Alternatively, we could give the semantics of ∧ by listing the returned value in each of four cases, giving the four possible combinations of input values. Using this approach, we could express the postcondition as follows.
post The returned value is c, where
- if a = true and b = true then c = true
- if a = true and b = false then c = false
- if a = false and b = true then c = false
- if a = false and b = false then c = false.
function (infix) (a ∨ b on Bool) return in Bool
pre true.
post The returned value is false if both a = false and b = false, and is true otherwise.
Activity 25
Give the semantics of ∨ by listing the returned value in each of four cases, giving the four possible combinations of input values.
Discussion
We can express the postcondition in the description above as follows.post The returned value is c, where
- if a = true and b = true then c = true
- if a = true and b = false then c = true
- if a = false and b = true then c = true
- if a = false and b = false then c = false.
Activity 26
- (a) Give a full description of the function NOT.
- (b) If a = true and b = false, evaluate each of:
- (i) a ∨ b;
- (ii) NOT(a ∨ b);
- (iii) a ∧ (a ∨ b).
- (i) a ∨ b;
Discussion
(a) A description is given below.function NOT(a in Bool) return in Bool
pre true.
post The returned value is false if a = true and is true if a = false.
(b) (i) Substituting for a and b, we have true ∨ false = true.
(ii) We should evaluate the term in brackets first: true ∨ false = true. Then NOT(true) = false. So NOT(a ∨ b) = false.
(iii) Again, evaluate the term in brackets first: (true ∨ false) = true. Then the given expression becomes true ∧ true which evaluates to true.
5.1 Arithmetic operations
Processes such as addition of numbers are called binary operations. (The word “binary” here reflects the fact that a binary operation combines two data items.) A binary operation is a particular form of function. To see this, we need to recognise the appropriate signature.
If you add two integers, then the resulting value is also an integer. So addition of integers takes two integers and returns an integer value. Thus adding integers is a function with signature Int × Int → Int. We can add any two integers, so addition is a total function (that is, has precondition true). We can describe a function, +, corresponding to addition of integers, as below.
function (infix) (x + y on Int) return in Int
pre true.
post The returned value is the result of adding x and y.
Where we use infix notation to write the value returned by a function, we will set out the signature line in the function description in a slightly different way from that used in Section 4, as illustrated above.
function (infix) (x − y on Int) return in Int
pre true.
post The returned value is the result of subtracting y from x.
We saw in Activity 3 that division of one integer by another does not necessarily result in an integer. For example, 2 ÷ 4 = 0.5 and 0.5 is not an integer. This means that we cannot define a function for what we might call “everyday division” that returns an integer value for integer inputs.
Sometimes, we need a form of division of integers that does yield an integer result. For example, suppose our supermarket features a special ‘buy 4, get 1 free’ order on bottles of wine. If a customer comes to the till with nine bottles of wine, then the till needs to calculate how many free bottles they should receive. Now nine bottles of wine contain two lots of four bottles (with one bottle left over). So the customer receives two free bottles of wine. This is an example of integer division. Integer division of 9 by 4 gives the result 2. (Hopefully, the cashier will point out to the customer with 9 bottles of wine that they are entitled to another free bottle!)
As another example, suppose that we want to perform integer division of 29 by 8. Now 3 × 8 = 24, while 4 × 8 = 32. When we perform integer division of 29 by 8 we obtain the result 3. Since 29 − 3 × 8 = 5, dividing 29 by 8 leaves a remainder of 5. Notice that the remainder, 5, satisfies the condition that 0 ≤ 5 < 8.
Integer division has two integers as input. It is a binary operation on Int, so we could use infix notation to write integer division. Now, many programming languages use / as an infix notation for both integer division and for real number division. In such cases, it is vital to appreciate that these are different processes, whose precise behaviour depends upon the type of the values supplied. To emphasise that integer division is not the familiar process of “everyday division”, we will write it as DIV, and use function rather than infix notation to give its values. For example, DIV (29, 8) = 3.
How can we describe integer division in general? To do this, some vocabulary is useful. In writing DIV (29, 8) = 3, the number 8 is called the divisor, and 3 is called the quotient.
We can generalise the equation 29 = 3 × 8 + 5 to give n = q × d + r (where d is the divisor, q is the quotient and r the remainder). The remainder must not be too large. In this example, the remainder 5 is less than 8. In general, the remainder r must be less than the divisor, d. Also, the remainder r is not negative. We can express these conditions on r algebraically as 0 ≤ r < d. So, in general, the quotient, q, is the largest integer by which we can multiply the divisor, d, while leaving a remainder that is not negative. If we subtract (q × d) from n, the resulting remainder needs to be non-negative and less than d.
Integer division has two integers as inputs and returns an integer. So the integer division function has signature DIV : Int × Int → Int. Since we write DIV using function notation, we can describe this function as below.
function DIV (n in Int, d in Int) return in Int
pre d > 0.
post The returned value q is the result of integer division of n by d. It satisfies the condition that if r = n − (q × d), then we have 0 ≤ r < d.
Notice that we only consider the case where the divisor, d, is strictly greater than 0. There is no restriction on the number n that is being divided, though. The examples we have considered so far have n positive.
What do these semantics give if n < 0? As an example, consider n = −29 and d = 8. We have −29 = −4 × 8 + 3 and the semantics give DIV (−29, 8) = −4. (Note that the remainder, r = 3, satisfies the condition 0 ≤ r < d, which is 0 ≤ r < 8 in this case.)
If n = 0, we have DIV (0, d) = 0 for any d that satisfies the precondition.
A second process associated with integer division returns the remainder rather than the quotient. This is again a binary operation. We will write this operation as MOD(n, d). This operation can be described as below.
function MOD(n in Int, d in Int) return in Int
pre d > 0.
post The returned value r is the remainder after integer division of n by d. It satisfies the conditions 0 ≤ r < d and r = n - (q × d), where q is an integer. The remainder MOD(n, d) is sometimes called the value of n modulo d, or more briefly n mod d. Many programming languages use the infix notation n % d for this operation.
If you add two integers, then the resulting value is also an integer. So addition of integers takes two integers and returns an integer value. Thus adding integers is a function with signature Int × Int → Int. We can add any two integers, so addition is a total function (that is, has precondition true). We can describe a function, +, corresponding to addition of integers, as below.
function (infix) (x + y on Int) return in Int
pre true.
post The returned value is the result of adding x and y.
Where we use infix notation to write the value returned by a function, we will set out the signature line in the function description in a slightly different way from that used in Section 4, as illustrated above.
Activity 21
Describe a function, −, corresponding to integer subtraction written using infix notation.
Discussion
Subtraction again combines two integers to produce an integer value. We can subtract any two integers, so this is again a total function.function (infix) (x − y on Int) return in Int
pre true.
post The returned value is the result of subtracting y from x.
Sometimes, we need a form of division of integers that does yield an integer result. For example, suppose our supermarket features a special ‘buy 4, get 1 free’ order on bottles of wine. If a customer comes to the till with nine bottles of wine, then the till needs to calculate how many free bottles they should receive. Now nine bottles of wine contain two lots of four bottles (with one bottle left over). So the customer receives two free bottles of wine. This is an example of integer division. Integer division of 9 by 4 gives the result 2. (Hopefully, the cashier will point out to the customer with 9 bottles of wine that they are entitled to another free bottle!)
As another example, suppose that we want to perform integer division of 29 by 8. Now 3 × 8 = 24, while 4 × 8 = 32. When we perform integer division of 29 by 8 we obtain the result 3. Since 29 − 3 × 8 = 5, dividing 29 by 8 leaves a remainder of 5. Notice that the remainder, 5, satisfies the condition that 0 ≤ 5 < 8.
Integer division has two integers as input. It is a binary operation on Int, so we could use infix notation to write integer division. Now, many programming languages use / as an infix notation for both integer division and for real number division. In such cases, it is vital to appreciate that these are different processes, whose precise behaviour depends upon the type of the values supplied. To emphasise that integer division is not the familiar process of “everyday division”, we will write it as DIV, and use function rather than infix notation to give its values. For example, DIV (29, 8) = 3.
How can we describe integer division in general? To do this, some vocabulary is useful. In writing DIV (29, 8) = 3, the number 8 is called the divisor, and 3 is called the quotient.
We can generalise the equation 29 = 3 × 8 + 5 to give n = q × d + r (where d is the divisor, q is the quotient and r the remainder). The remainder must not be too large. In this example, the remainder 5 is less than 8. In general, the remainder r must be less than the divisor, d. Also, the remainder r is not negative. We can express these conditions on r algebraically as 0 ≤ r < d. So, in general, the quotient, q, is the largest integer by which we can multiply the divisor, d, while leaving a remainder that is not negative. If we subtract (q × d) from n, the resulting remainder needs to be non-negative and less than d.
Integer division has two integers as inputs and returns an integer. So the integer division function has signature DIV : Int × Int → Int. Since we write DIV using function notation, we can describe this function as below.
function DIV (n in Int, d in Int) return in Int
pre d > 0.
post The returned value q is the result of integer division of n by d. It satisfies the condition that if r = n − (q × d), then we have 0 ≤ r < d.
Notice that we only consider the case where the divisor, d, is strictly greater than 0. There is no restriction on the number n that is being divided, though. The examples we have considered so far have n positive.
What do these semantics give if n < 0? As an example, consider n = −29 and d = 8. We have −29 = −4 × 8 + 3 and the semantics give DIV (−29, 8) = −4. (Note that the remainder, r = 3, satisfies the condition 0 ≤ r < d, which is 0 ≤ r < 8 in this case.)
If n = 0, we have DIV (0, d) = 0 for any d that satisfies the precondition.
Activity 22
Give the following values:
- (a) DIV (27,4).
- (b) DIV (32,17).
- (c) DIV (−27, 4).
- (d) DIV (0,6).
- (e) DIV (3,0).
Discussion
- (a) DIV (27,4) = 6, since 27 = 6 × 4 + 3, where 0 ≤ 3 < 4.
- (b) DIV (32,17) = 1, since 32 = 1 × 17 + 15, where 0 ≤ 15 < 17.
- (c) DIV (−27, 4) = −7, since −27 = −7 × 4 + 1, where 0 ≤ 1 < 4.
- (d) DIV (0,6) = 0.
- (e) This is undefined (because of the precondition on DIV ).
function MOD(n in Int, d in Int) return in Int
pre d > 0.
post The returned value r is the remainder after integer division of n by d. It satisfies the conditions 0 ≤ r < d and r = n - (q × d), where q is an integer. The remainder MOD(n, d) is sometimes called the value of n modulo d, or more briefly n mod d. Many programming languages use the infix notation n % d for this operation.
Activity 23
Give the following values:
- (a) MOD(67, 10).
- (b) MOD(55, 5).
- (c) MOD(−27, 4).
Discussion
- (a) MOD(67, 10) = 7 (since 67 = 6 × 10 + 7; the remainder on division of 67 by 10 is 7).
- (b) MOD(55, 5) = 0 (since 55 = 11 × 5 + 0).
- (c) MOD(−27, 4) = 1 because, as noted in Activity 22(c), we have −27 = −7 × 4 + 1.
Activity 24
- (a) Suppose that you buy 335 grams of walnuts at 299 pence per kg, and the price of this purchase is expressed as a whole number of pence by ignoring any fraction. What is the cost of this purchase?
- (b) Now consider a general purchase of this form, of weight grams of a product costing price pence per kilogram. Using the function DIV , give a formula for the cost of such a purchase.
Discussion
- (a) 335 grams is 0.335 kilograms, so this purchase should cost 0.335 × 299 = 100.464 pence, which will be rounded to 100 pence. (Reassuringly, this is the same as the cost given in Figure 2.)
- (b) In general we multiply weight and price, and divide the result by 1000, ignoring any fractional part of the result. So the required value is given by the expression DIV (weight × price,1000).
5 Operations and comparisons: Seeing processes as functions
Addition of numbers is a process that one would expect a computer to be able to perform. Now we write the result of adding the numbers 5 and 2 as 5 + 2, for example. The symbol +, which represents the process of addition, appears between the two numbers being added. This is known as infix notation. Infix notation may be used for processes that combine two data items of the same type. Addition, subtraction and multiplication of numbers are familiar examples. We also use infix notation when writing a comparison of the size of two numbers, such as 5 < 9.
In this section, we shall show that a process such as addition of numbers is a function. Perhaps more surprisingly, a process such as < can also be seen as a function. This perception is a necessary preliminary to seeing how such a process can be implemented by a computer.
In this section, we shall show that a process such as addition of numbers is a function. Perhaps more surprisingly, a process such as < can also be seen as a function. This perception is a necessary preliminary to seeing how such a process can be implemented by a computer.
Exercises on Section 4
Exercise 9
For each of the following functions, give the signature and suggest a suitable precondition.- (a) TOUPPER, which changes a string, containing only lower-case letters, into the corresponding string consisting of upper-case letters. (So, for example, TOUPPER(“word”) = “WORD”.)
- (b) REMOVELAST, which, given a sequence, deletes its last member.
- (c) LAST, which returns the last member of a sequence.
Answer
Solution
- (a) This function inputs a string and outputs a string, therefore it has signature TOUPPER : SeqOfChar → SeqOfChar. It requires a precondition that the input sequence consists entirely of lower-case letters.
- (b) The members of the sequence may come from any set, which we will denote by X. The input is a sequence and the returned value is also a sequence. So the signature is REMOVELAST : SeqOfX → SeqOfX . The input sequence should contain at least one member (otherwise there is no last member to delete), so we need a precondition that the input sequence is not empty.
- (c) This is similar to (a), except that the returned value is an item from X, rather than a sequence. The signature is LAST : SeqOfX → X. We again need the precondition that the input sequence is not empty.
Exercise 10
Suppose that the days of the week are represented by numbers, with Mon-day represented by 1, Tuesday represented by 2, and so on, with Sunday represented by 7. Describe a function TOMORROW2, giving the next day with Days represented in this way.Answer
Solution
You may have given this description.function TOMORROW2(d in Int) return in Int
pre d is in the set {1,2,3,4,5,6,7}.
post The returned value is t, where:
- if d = 1 then t = 2
- if d = 2 then t = 3
- if d = 3 then t = 4
- if d = 4 then t = 5
- if d = 5 then t = 6
- if d = 6 then t = 7
- if d = 7 then t = 1.
function TOMORROW2(d in Int) return in Int
pre 1 ≤ d ≤ 7.
post The returned value is t, where:
t = d + 1 if 1 = d = 6;
t = 1 if d = 7.
Either of these answers is fine.
Exercise 11
- (a) With s = “abcd”, evaluate each of:
- (i) AT(1, s);
- (ii) PUT(2, s, AT(1, s)).
- (i) AT(1, s);
- (b) For a general sequence s, describe how the sequence PUT(2, s, AT(1, s)) is obtained from s.
Answer
Solution
- (a)(i) With s = “abcd”, AT(1,s) = ‘a’.
- (ii) Then PUT(2,s,AT(1,s)) = PUT(2,“abcd”,‘a’) = “aacd”.
- (b) In general, PUT(2,s,AT(1,s)) is formed by replacing the second member of the sequence s with a copy of the first member of s.
Objectives for Section 4
After studying this section you should be able to do the following.
- Recognise and use the terminology: function, signature, domain, semantics, input set, output set, precondition, postcondition.
- Suggest appropriate signatures and preconditions for functions corresponding to a variety of processes on numbers, characters and sequences, including those with more than one input and those that return a Boolean value.
- For given inputs, give the value returned by various functions described in this section, in particular: AT, PUT, SIZE, ASC, CHR, ADDLAST.
4.4 Functions returning true or false
Consider a function, say ISIN , associated with following process.
This function has two inputs, a character and a string (sequence of characters), so we can take the input set to be Char × SeqOfChar. But what is the output set? If the character does appear in the string, then the function can return the value true, and if the character does not appear in the string, then the function can return the value false. So a suitable output set is Bool. Then ISIN has signature Char × SeqOfChar → Bool. We can describe the function ISIN as below.
function ISIN (c in Char, s in SeqOfChar) return in Bool
pre true.
post The returned value is true if the character c appears in the sequence s at least once, and is false if c does not appear at all in s.
(If s is the empty string, then it contains no characters, and ISIN (c, s) will be false whatever the character c is.)
function ISEMPTY (s in SeqOfX ) return in Bool
pre true.
post The returned value is true if the sequence s contains no members, and is false if s contains one or more members.
Given a character and a string, determine whether the character appears in the string.
function ISIN (c in Char, s in SeqOfChar) return in Bool
pre true.
post The returned value is true if the character c appears in the sequence s at least once, and is false if c does not appear at all in s.
(If s is the empty string, then it contains no characters, and ISIN (c, s) will be false whatever the character c is.)
Activity 20
Suggest a description for a function ISEMPTY corresponding to the following process.
Determine whether or not a given sequence is empty.
Discussion
The function will input a sequence (which might contain elements from any set, say X). It can return true if the sequence is empty, and false if it is not empty. So we can use the following description of ISEMPTY.function ISEMPTY (s in SeqOfX ) return in Bool
pre true.
post The returned value is true if the sequence s contains no members, and is false if s contains one or more members.
4.3 Character code functions
Many programming languages provide two functions associated with the character codes (see Table 2). We shall call these functions ASC and CHR. ASC takes a character as input, and returns the integer giving the ASCII code of the input character. CHR returns the character whose ASCII code is the input integer. These functions are described below. We have set a precondition on CHR to conform to our earlier restriction on the set of characters that we will consider in this unit.
function ASC(c in Char) return in Int
pre true.
post The returned value is the ASCII code of c, as given in Table 2.
function CHR(n in Int) return in Char
pre 32 ≤ n ≤ 126.
post The returned value is the character with ASCII code n, as given in Table 2.
As illustrated in Activity 18, the two functions ASC and CHR are closely related. Each reverses the effect of the other. We can express this relationship by writing the two equations below (which hold for every c in Char and for every n in Int satisfying the condition 32 ≤ n ≤ 126).
We say that ASC and CHR are inverse functions.
Not every function can be paired up with an inverse function in this way. For example, the function FIRSTCHAR returns the first character in a string. Now different strings may have the same first character. (“This” and “The” both start with ‘T’, but are different strings.) With input ‘T’, a process attempting to reverse the effect of FIRSTCHAR would not know whether to return “This” or “The” (or “To”, or “Tom”, etc). The function FIRSTCHAR has no inverse function.
function BEFORE(c in Char) return in Char
pre c is a lower-case letter.
post If c lies between ‘b’ and ‘z ’ then the returned value is the letter preceding c in alphabetical order. If c = ‘a’ then the returned value is ‘z’.
function ASC(c in Char) return in Int
pre true.
post The returned value is the ASCII code of c, as given in Table 2.
function CHR(n in Int) return in Char
pre 32 ≤ n ≤ 126.
post The returned value is the character with ASCII code n, as given in Table 2.
Activity 18
Find each of:
- (a) ASC(‘j’);
- (b) CHR(43);
- (c) ASC(CHR(43));
- (d) CHR(ASC(‘j’)).
Discussion
- (a) Referring to Table 2, ASC(‘j’) = 106.
- (b) CHR(43) = ‘+’.
- (c) ASC(CHR(43)) means the result of applying the function ASC to CHR(43). So ASC(CHR(43)) = ASC(‘+’) = 43.
- (d) CHR(ASC(‘j’)) = CHR(106) = ‘j’.
ASC(CHR(n)) = n
CHR(ASC(c)) = c
Not every function can be paired up with an inverse function in this way. For example, the function FIRSTCHAR returns the first character in a string. Now different strings may have the same first character. (“This” and “The” both start with ‘T’, but are different strings.) With input ‘T’, a process attempting to reverse the effect of FIRSTCHAR would not know whether to return “This” or “The” (or “To”, or “Tom”, etc). The function FIRSTCHAR has no inverse function.
Activity 19
A simple cipher replaces each lower-case letter with the next one in alphabetical order. So ‘a’ is replaced by ‘b’, ‘b’ by ‘c’,. . . , ‘t’ by ‘u’, and so on. The letter z ‘ ’ is replaced by ‘a’. The function NEXT, specified below, corresponds to this coding.
function NEXT(c in Char) return in Char
pre c is a lower-case letter.
post If c lies between ‘a’ and ‘y’ then the returned value is the letter following c in alphabetical order. If c = ‘z’ then the returned value is ‘a’.
Does the function NEXT have an inverse function? If it does, describe this inverse function.
function NEXT(c in Char) return in Char
pre c is a lower-case letter.
post If c lies between ‘a’ and ‘y’ then the returned value is the letter following c in alphabetical order. If c = ‘z’ then the returned value is ‘a’.
Does the function NEXT have an inverse function? If it does, describe this inverse function.
Discussion
We can reverse the effect of NEXT by moving each character back one place in alphabetical order. This time, the special case is ‘a’, which must be moved to ‘z’. So NEXT does have an inverse function. If we call it BEFORE, it can be described as below.function BEFORE(c in Char) return in Char
pre c is a lower-case letter.
post If c lies between ‘b’ and ‘z ’ then the returned value is the letter preceding c in alphabetical order. If c = ‘a’ then the returned value is ‘z’.
4.2 Functions defined through cases
In each of the examples considered so far, the function has had its semantics expressed using a formula or a general rule. Some functions have their semantics expressed simply by listing the output for each possible input. For example, let Days be the set of days of the week, and the function TOMORROW have signature Days → Days, and return the day following the input day. If we represent Days using the strings {“Mon”, “Tues”, “Wed”, “Thurs”, “Fri”, “Sat”, “Sun”}, then we can describe the corresponding representation of the function TOMORROW as below.
function TOMORROW1(d in SeqOfChar) return in SeqOfChar
pre d is in the set {“Mon”,“Tues”,“Wed”,“Thurs”,“Fri”,“Sat”,“Sun”}.
post The returned value is t, where:
function CEREALPRICE(c in Char) return in Int
pre c is in the set {‘S’, ‘M’, ‘L’}.
post The returned value is p, where:
function TOMORROW1(d in SeqOfChar) return in SeqOfChar
pre d is in the set {“Mon”,“Tues”,“Wed”,“Thurs”,“Fri”,“Sat”,“Sun”}.
post The returned value is t, where:
- if d = “Mon” then t = “Tues”
- if d = “Tues” then t = “Wed”
- if d = “Wed” then t = “Thurs”
- if d = “Thurs” then t = “Fri”
- if d = “Fri” then t = “Sat”
- if d = “Sat” then t = “Sun”
- if d = “Sun” then t = “Mon”.
Activity 17
Suppose that a particular breakfast cereal is sold in sizes Small, Medium and Large, and that we choose to represent these by the characters ‘S’, ‘M’ and ‘L’. Their respective prices, in pence, are 89 for ‘S’, 119 for ‘M’ and 159 for ‘L’. Describe a function CEREALPRICE that takes a size as input and returns the associated price.
Discussion
We can describe this function as follows.function CEREALPRICE(c in Char) return in Int
pre c is in the set {‘S’, ‘M’, ‘L’}.
post The returned value is p, where:
- if c = ‘S’ then p = 89
- if c = ‘M’ then p = 119
- if c = ‘L’ then p = 159.
4.1 Functions
A function is a process that, when given an input of a specified type, yields a unique output. This is a key idea in providing a precise, mathematical, description of processes in computing.
To describe a particular function, we first give the set from which the input will be drawn and the set from which the output is drawn. This information is called the signature of the function. An example will make this clearer. Example 1(b), on the previous screen, requires an input that is a string, that is, a sequence of characters. The set containing all possible sequences of characters is SeqOfChar. Example 1(b) produces an output that is a character, so this output is in the set Char. We write the signature of this function as SeqOfChar → Char. The set to the left of the arrow is called the input set of the function and the set to the right is called the output set. Some texts use source set rather than input set, and target set rather than output set. It is usual to include an identifier for the function itself in the signature. Suppose we call this function FIRSTCAP. Then its full signature is:
SeqOfChar comprises all sequences of characters, and so includes some sequences that have no upper-case letters.
The second piece of information required in describing a function is any restriction on the input(s). The informal description of FIRSTCAP states only that the first upper-case letter is returned. It does not specify what happens if there is no upper-case letter in the input. Accordingly, a sensible condition on the set of inputs to FIRSTCAP is that the input sequence must contain at least one upper-case letter. This condition on the input value is called the precondition of the function FIRSTCAP.
The third and final piece of information required is the relationship between output and input values. This relationship is referred to as the semantics of the function. The semantics must ensure that there is a unique output for any given input. We can describe the function FIRSTCAP like this:
However, it is not always easy to extract key pieces of information from such a description. We shall usually describe functions using a standard layout, as in the description of FIRSTCAP given below. In exercises, to signal that we want the description of a function to be laid out as below, we will ask for a full description of the function.
function FIRSTCAP(s in SeqOfChar) return in Char
pre s contains at least one upper-case letter.
post The returned value is the first upper-case letter appearing in s.
The signature of the function FIRSTCAP is implicit in the first line of this description. (The signature is FIRSTCAP : SeqOfChar → Char.) This line shows that the function has an input (with identifier s) that comes from SeqOfChar. So its input set is SeqOfChar. The function returns a value in Char. So its output set is Char. We refer to the first line in the full description as the signature line.
The input value s must satisfy the condition given in the line starting pre. This line gives the precondition of the function. The semantics of the function are given in the line starting post. The statement in this line is referred to as the postcondition of the function.
Here, “pre” and “post” are used in the sense of “before” and “after”. Before FIRSTCAP can be applied to a value, that value must satisfy the precondition. After FIRSTCAP has been applied, the returned value will satisfy the postcondition.
Sometimes, we want to refer to the set of input values for which a function is defined. This is called the domain of the function, and is the set of values in the input set that satisfy the precondition of the function.
A function that is defined for all elements in its input set is called a total function. For a total function, no precondition is required on the input value (beyond requiring that it is in the input set). We show this by writing pre true (since the precondition is automatically true).
As another example, consider the process 4.1(d) given earlier. It stated:
A full description of this function is given below. We will give it the identifier FORMULA. The rule for producing an output works for any integer, so we can write true for the precondition.
function FORMULA(x in Int) return in Int
pre true.
post The returned value is x 2 + x.
(a) FIRSTCHAR inputs a string (sequence of characters), and returns a character. So its signature is FIRSTCHAR : SeqOfChar → Char. To have a “first character”, the input sequence needs to contain at least one character, so the function needs a corresponding precondition.
function FIRSTCHAR(s in SeqOfChar) return in Char
pre s contains at least one character.
post The returned value is the first character appearing in s.
The choice of identifier for the input is arbitrary. You may well have used some identifier other than s in your answer.
(b) Note that SUMSEQ inputs a sequence of integers, and returns an integer. A suitable description is given below.
function SUMSEQ(s in SeqOfInt) return in Int
pre true.
post The returned value is the total of the numbers appearing in s. If s contains no members, then the returned value is 0.
You might have chosen to say that the input sequence should not be empty, since the idea of “the total of the numbers” might seem unclear if there are no numbers to add up! That would be fine. We have chosen to regard the “total of no numbers” as 0, and have said so explicitly in the semantics. Sometimes, one needs to make more precise an informal idea of a process. Deciding whether to add a precondition, or to explain what happens in special cases, is the sort of clarification that may be needed.
The value obtained when some function F is applied to an input x is written F(x). So, for example, FIRSTCAP(“a1wQ2*”) means the result of applying the function FIRSTCAP to the string “a1wQ2*”. The value obtained in that case is the first upper-case letter in “a1wQ2*”, and so is ‘Q’.
The example process 1(f), given earlier, was:
For example, if the string “This is a sentence.” and the character ‘s’ are given, then the value returned is 4. This function requires two inputs: a string (a sequence of characters), and a character. We can describe the function as below.
function FIRSTAT(c in Char,t in SeqOfChar) return in Int
pre The character c appears at least once in the sequence t.
post The returned value is the integer n satisfying the condition that the nth character in the sequence t is c, and this is the first occurrence of c in t.
Where a function requires more than one input, the input set is taken to be a Cartesian product of sets, one for each input. For this example, the input set is Char × SeqOfChar. The output set is Int, so the signature of the function is FIRSTAT : Char × SeqOfChar → Int.
We can, for example, apply this function in the form
FIRSTAT(‘s’, “This is a sentence.”). However, we cannot apply it in the form FIRSTAT(“This is a sentence.”, ‘s’). The order of the two inputs given in the signature line in the description of FIRSTAT must be adhered to.
(We could have described a function accepting the inputs in a different order, with the sequence first and the character second. But this would be another function, different from FIRSTAT, just as reversing the order in which two sets are written in a Cartesian product produces a different set.)
Look now at Example 1(e), repeated below.
Given a sequence of items from a set X, and another item from the set X, return the sequence formed by placing the item at the end of the sequence. For example, given the sequence of integers [6,2,5,6] and the integer 1, the value returned is [6,2,5,6,1].
Note that this description is not confined to sequences of numbers. It can be used for sequences with members from any set. This general set is represented here by X. We can describe a function ADDLAST corresponding to this process as below.
function ADDLAST(x in X , s in SeqOfX ) return in SeqOfX
pre true.
post The returned value is formed by placing the item x at the end of the sequence s. For example, ADDLAST(1,[6, 2, 5, 6]) = [6, 2, 5, 6, 1].
(ii) −32 (the third item in the sequence [1, 11, −32, 4]).
(iii) We replace the character at the third place in the string “paan” by the input character ‘i’, to get “pain”.
(iv) The first number gives the position of the item to be changed and the final number is the replacement item. So the value is [1, 3, 2, 4].
(b) SIZE has one input, from SeqOfX , and returns a value in Int. The signature is SIZE : SeqOfX → Int.
The function AT inputs an integer and a sequence and returns a value from X, so the signature is AT : Int × SeqOfX → X.
For the function PUT, the input set is a Cartesian product of three sets, one for each of the three inputs.
The signature is PUT : Int × SeqOfX × X → SeqOfX .
(c) Suitable descriptions are given below.
For SIZE, recall that the number of elements in the empty sequence is 0, so this is a total function.
function SIZE(s in SeqOfX ) return in Int
pre true.
post The returned value is the number of items in the sequence s. If s contains no members then the returned value is 0.
For AT, the semantics only make sense if the integer input gives a position actually in the sequence. So we give a precondition that the input integer is at least 1 (when the first item in the sequence will be returned), and that the input integer is not bigger than the number of items in the sequence. If we use another function in a description, as we use SIZE here in describing AT, then we must describe that function too. SIZE was described above.
function AT(i in Int, s in SeqOfX ) return in X
pre 1≤ i and i≤ SIZE(s).
post The returned value is the ith item in the sequence s.
The function PUT has three inputs, an integer (giving the position of the item to be changed), the sequence to be modified, and the replacement item (from the set X). It requires the same precondition as AT.
function PUT(i in Int, s in SeqOfX , x in X ) return in SeqOfX
pre 1 ≤ i and i ≤ SIZE(s).
post The returned value is the sequence formed by replacing the ith item in s by x.
To describe a particular function, we first give the set from which the input will be drawn and the set from which the output is drawn. This information is called the signature of the function. An example will make this clearer. Example 1(b), on the previous screen, requires an input that is a string, that is, a sequence of characters. The set containing all possible sequences of characters is SeqOfChar. Example 1(b) produces an output that is a character, so this output is in the set Char. We write the signature of this function as SeqOfChar → Char. The set to the left of the arrow is called the input set of the function and the set to the right is called the output set. Some texts use source set rather than input set, and target set rather than output set. It is usual to include an identifier for the function itself in the signature. Suppose we call this function FIRSTCAP. Then its full signature is:
FIRSTCAP: SeqOfChar → Char.
SeqOfChar comprises all sequences of characters, and so includes some sequences that have no upper-case letters.
The second piece of information required in describing a function is any restriction on the input(s). The informal description of FIRSTCAP states only that the first upper-case letter is returned. It does not specify what happens if there is no upper-case letter in the input. Accordingly, a sensible condition on the set of inputs to FIRSTCAP is that the input sequence must contain at least one upper-case letter. This condition on the input value is called the precondition of the function FIRSTCAP.
The third and final piece of information required is the relationship between output and input values. This relationship is referred to as the semantics of the function. The semantics must ensure that there is a unique output for any given input. We can describe the function FIRSTCAP like this:
FIRSTCAP has signature SeqOfChar → Char; its input sequence must contain at least one upper-case letter, and it returns the first upper-case letter appearing in the input sequence.
function FIRSTCAP(s in SeqOfChar) return in Char
pre s contains at least one upper-case letter.
post The returned value is the first upper-case letter appearing in s.
The signature of the function FIRSTCAP is implicit in the first line of this description. (The signature is FIRSTCAP : SeqOfChar → Char.) This line shows that the function has an input (with identifier s) that comes from SeqOfChar. So its input set is SeqOfChar. The function returns a value in Char. So its output set is Char. We refer to the first line in the full description as the signature line.
The input value s must satisfy the condition given in the line starting pre. This line gives the precondition of the function. The semantics of the function are given in the line starting post. The statement in this line is referred to as the postcondition of the function.
Here, “pre” and “post” are used in the sense of “before” and “after”. Before FIRSTCAP can be applied to a value, that value must satisfy the precondition. After FIRSTCAP has been applied, the returned value will satisfy the postcondition.
Sometimes, we want to refer to the set of input values for which a function is defined. This is called the domain of the function, and is the set of values in the input set that satisfy the precondition of the function.
A function that is defined for all elements in its input set is called a total function. For a total function, no precondition is required on the input value (beyond requiring that it is in the input set). We show this by writing pre true (since the precondition is automatically true).
As another example, consider the process 4.1(d) given earlier. It stated:
given some integer, x, say, return the integer x 2 + x.
function FORMULA(x in Int) return in Int
pre true.
post The returned value is x 2 + x.
Activity 14
- (a) Call the function associated with Example 1(c) on the previous screen, FIRSTCHAR. Give the signature of this function. Write out a full description of it.
- (b) Suggest a full description of a function SUMSEQ, associated with the Example 1(a).
Hide discussion
Discussion
Suitable descriptions are given below.(a) FIRSTCHAR inputs a string (sequence of characters), and returns a character. So its signature is FIRSTCHAR : SeqOfChar → Char. To have a “first character”, the input sequence needs to contain at least one character, so the function needs a corresponding precondition.
function FIRSTCHAR(s in SeqOfChar) return in Char
pre s contains at least one character.
post The returned value is the first character appearing in s.
The choice of identifier for the input is arbitrary. You may well have used some identifier other than s in your answer.
(b) Note that SUMSEQ inputs a sequence of integers, and returns an integer. A suitable description is given below.
function SUMSEQ(s in SeqOfInt) return in Int
pre true.
post The returned value is the total of the numbers appearing in s. If s contains no members, then the returned value is 0.
You might have chosen to say that the input sequence should not be empty, since the idea of “the total of the numbers” might seem unclear if there are no numbers to add up! That would be fine. We have chosen to regard the “total of no numbers” as 0, and have said so explicitly in the semantics. Sometimes, one needs to make more precise an informal idea of a process. Deciding whether to add a precondition, or to explain what happens in special cases, is the sort of clarification that may be needed.
The example process 1(f), given earlier, was:
Given a string and a character, return the position in the string where the character first occurs.
function FIRSTAT(c in Char,t in SeqOfChar) return in Int
pre The character c appears at least once in the sequence t.
post The returned value is the integer n satisfying the condition that the nth character in the sequence t is c, and this is the first occurrence of c in t.
Where a function requires more than one input, the input set is taken to be a Cartesian product of sets, one for each input. For this example, the input set is Char × SeqOfChar. The output set is Int, so the signature of the function is FIRSTAT : Char × SeqOfChar → Int.
We can, for example, apply this function in the form
FIRSTAT(‘s’, “This is a sentence.”). However, we cannot apply it in the form FIRSTAT(“This is a sentence.”, ‘s’). The order of the two inputs given in the signature line in the description of FIRSTAT must be adhered to.
(We could have described a function accepting the inputs in a different order, with the sequence first and the character second. But this would be another function, different from FIRSTAT, just as reversing the order in which two sets are written in a Cartesian product produces a different set.)
Look now at Example 1(e), repeated below.
Given a sequence of items from a set X, and another item from the set X, return the sequence formed by placing the item at the end of the sequence. For example, given the sequence of integers [6,2,5,6] and the integer 1, the value returned is [6,2,5,6,1].
Note that this description is not confined to sequences of numbers. It can be used for sequences with members from any set. This general set is represented here by X. We can describe a function ADDLAST corresponding to this process as below.
function ADDLAST(x in X , s in SeqOfX ) return in SeqOfX
pre true.
post The returned value is formed by placing the item x at the end of the sequence s. For example, ADDLAST(1,[6, 2, 5, 6]) = [6, 2, 5, 6, 1].
Activity 15
- (a) Give the signature of the function ADDLAST.
- (b) What are the values:
- (i) ADDLAST(7,[1, 4, 3, 2]);
- (ii) ADDLAST(‘y’,“qwert”);
- (iii) ADDLAST(“qwert”,‘y’)?
- (i) ADDLAST(7,[1, 4, 3, 2]);
Discussion
- (a) The signature is ADDLAST : X × SeqOfX → SeqOfX . (The order of the sets in the Cartesian product corresponds to the order of the inputs given in the description above.)
- (b) We have:
- (i) ADDLAST(7, [1, 4, 3, 2]) = [1, 4, 3, 2, 7];
- (ii) ADDLAST(‘y’, “qwert”) = “qwerty”;
- (iii) ADDLAST(“qwert”,‘y’) cannot be formed. The inputs are given in the wrong order.
- (i) ADDLAST(7, [1, 4, 3, 2]) = [1, 4, 3, 2, 7];
Activity 16
This activity concerns the three functions on sequences given below. In each case, the sequence members come from an arbitrary set, X. You will meet these functions again later in the unit.
- A function SIZE, which, given a sequence, returns the number of members in it (that is, it returns the length of the sequence). So, for example, SIZE([1, 11, −32, 4, 12, 1]) = 6.
- A function AT, which returns the item that is at a specified position in a sequence. So, for example, AT(4, “author”) = ‘h’.
- A function PUT, which replaces the item that is at a specified position in a sequence with an item supplied as an input. So, for example, PUT(4,“author”,‘q’) = “autqor”.
- (a) Give the values of:
- (i) SIZE(“author”);
- (ii) AT(3,[1, 11, -32, 4]);
- (iii) PUT(3,“paan”,‘i’);
- (iv) PUT(2, [1, 8, 2, 4], 3).
- (i) SIZE(“author”);
- (b) Give the signature of each of the three functions.
- (c) Give full descriptions of each of the three functions.
Discussion
(a) (i) 6 (the number of characters in the string “author”).(ii) −32 (the third item in the sequence [1, 11, −32, 4]).
(iii) We replace the character at the third place in the string “paan” by the input character ‘i’, to get “pain”.
(iv) The first number gives the position of the item to be changed and the final number is the replacement item. So the value is [1, 3, 2, 4].
(b) SIZE has one input, from SeqOfX , and returns a value in Int. The signature is SIZE : SeqOfX → Int.
The function AT inputs an integer and a sequence and returns a value from X, so the signature is AT : Int × SeqOfX → X.
For the function PUT, the input set is a Cartesian product of three sets, one for each of the three inputs.
The signature is PUT : Int × SeqOfX × X → SeqOfX .
(c) Suitable descriptions are given below.
For SIZE, recall that the number of elements in the empty sequence is 0, so this is a total function.
function SIZE(s in SeqOfX ) return in Int
pre true.
post The returned value is the number of items in the sequence s. If s contains no members then the returned value is 0.
For AT, the semantics only make sense if the integer input gives a position actually in the sequence. So we give a precondition that the input integer is at least 1 (when the first item in the sequence will be returned), and that the input integer is not bigger than the number of items in the sequence. If we use another function in a description, as we use SIZE here in describing AT, then we must describe that function too. SIZE was described above.
function AT(i in Int, s in SeqOfX ) return in X
pre 1≤ i and i≤ SIZE(s).
post The returned value is the ith item in the sequence s.
The function PUT has three inputs, an integer (giving the position of the item to be changed), the sequence to be modified, and the replacement item (from the set X). It requires the same precondition as AT.
function PUT(i in Int, s in SeqOfX , x in X ) return in SeqOfX
pre 1 ≤ i and i ≤ SIZE(s).
post The returned value is the sequence formed by replacing the ith item in s by x.
4 Processes: Processes that can be applied to data
Having looked at some forms of data, we now turn our attention to processes that can be applied to data. Each process that we consider in this section will input data of a specified form, and will result in a corresponding value. For example, one process, which we will call ASC, takes a character as input, and has as its resulting value the integer giving the ASCII code of the input character (as listed in Table 2). Another process, which we will call SIZE, takes a sequence as input, and has as its resulting value the length of the sequence (which will be an integer).
It is important to distinguish between a description of the outcome required when a process is applied to a form of data, and a description of the exact steps to be taken to achieve the desired outcome. Here, we are concerned only with the first of these; that is, with providing an overview of a computing process. You might like to think of this as a “black box” view of the process. We do not, at this stage, care how one obtains the output value.
Certain processes change the state of a named variable. For now, though, we shall not think about processes in that way. Each process that we are concerned with here simply produces a value that depends on one (or more) input value(s). Another important feature of the processes that we shall consider is that they result in a value that is entirely predictable. One can envisage a process that takes a string as input, and which results in a value that is a character that appears in the string. With input “This”, the value resulting from such a process might be any of the four characters ‘T’, ‘h’, ‘i’ or ‘s’. We will not consider a process such as that. Our attention will be confined to processes that, if given the same input twice, will produce the same resulting value each time.
Below, we give a number of examples of processes that may be applied to numbers, characters or sequences. Focus first on Example 1(a) below This process is applied to an input, comprising data of a specified form (a sequence of integers). Application of the process results in a value (the sum of the integers in the input sequence). This resulting value will be referred to as the value returned by the process. Similar comments apply to each of these examples. Each process takes data of a specified form as an input, and each process returns a value, based on this input data. The returned value may also be called the output of the process.
Here are some key questions to consider about each process.
It is important to distinguish between a description of the outcome required when a process is applied to a form of data, and a description of the exact steps to be taken to achieve the desired outcome. Here, we are concerned only with the first of these; that is, with providing an overview of a computing process. You might like to think of this as a “black box” view of the process. We do not, at this stage, care how one obtains the output value.
Certain processes change the state of a named variable. For now, though, we shall not think about processes in that way. Each process that we are concerned with here simply produces a value that depends on one (or more) input value(s). Another important feature of the processes that we shall consider is that they result in a value that is entirely predictable. One can envisage a process that takes a string as input, and which results in a value that is a character that appears in the string. With input “This”, the value resulting from such a process might be any of the four characters ‘T’, ‘h’, ‘i’ or ‘s’. We will not consider a process such as that. Our attention will be confined to processes that, if given the same input twice, will produce the same resulting value each time.
Below, we give a number of examples of processes that may be applied to numbers, characters or sequences. Focus first on Example 1(a) below This process is applied to an input, comprising data of a specified form (a sequence of integers). Application of the process results in a value (the sum of the integers in the input sequence). This resulting value will be referred to as the value returned by the process. Similar comments apply to each of these examples. Each process takes data of a specified form as an input, and each process returns a value, based on this input data. The returned value may also be called the output of the process.
Example 1
- (a) Given a sequence of integers, return the sum of all the numbers in the sequence. For example, given [6, 2, 5, 6] the value returned is 19.
- (b) Given a string, return the first upper-case letter that appears in the string. For example, given the string “my name is Bob”, the value returned is ‘B’.
- (c) Given a string, return the first character in the string. For example, given the string “This is a sentence.”, the value returned is ‘T’.
- (d) Given some integer, x, say, return the integer x 2 + x. For example, given the number 4, the value returned is 42 + 4 = 20.
- (e) Given a sequence of items from a set X, and another item from the set X, return the sequence formed by placing the item at the end of the sequence. For example, given the sequence of integers [6, 2, 5, 6] and the integer 1, the value returned is [6, 2, 5, 6, 1].
- (f) Given a string and a character, return the position in the string where the given character first occurs (counting characters from the front of the string). For example, if the string “This is a sentence.” and the character ‘s’ are given, then the value returned is 4, since the first occurrence of ‘s’ in the string is at the fourth place in the sequence [‘T’,‘h’,‘i’,‘s’,‘
’,‘i’,‘s’, . . . ].
- How many inputs are required, and of what type?
- What type of value does the process return?
- What is the relationship between the returned value and the input(s)?
- Are there any restrictions on the input(s)?
- Does the process always produce an output? Given any permitted input, is there an associated returned value?
- Is the output produced predictable? Given the same input, will the process always return the same value?
Exercises on Section 3
Exercise 7
Each of (a)–(c) is a member of one of the sets given in (i)–(iii). Say which item comes from which set.Sets: (i) SetOfSeqOfChar. (ii) SeqOfSetOfChar. (iii) SeqOfSeqOfChar.
- (a) {“error1”, “error2”, “error3”}.
- (b) [“error1”, “error2”, “error3”].
- (c) [{‘e’,‘1’}, {‘T’}, {‘q’,‘w’,‘e’,‘r’,‘t’,‘y’}].
Answer
Solution
- (a) This is a set, as shown by the outer curly brackets. Each member of this set is a string, that is, a sequence of characters. So (a) is a set of sequences of characters. It is a member of SetOfSeqOfChar.
- (b) This is a sequence, as shown by the outer square brackets. It is a sequence of strings. So (b) is a sequence of sequences of characters. It comes from SeqOfSeqOfChar.
- (c) This is again a sequence. Each member of this sequence is a set of characters. So (c) comes from SeqOfSetOfChar.
Exercise 8
Let Mix be the disjoint union Int Char. What is the length of the following sequence from SeqOfMix?[555, ‘5’, ‘5’, ‘5’, 11, 1].
Answer
Solution
There are six items in the sequence [555,‘5’,‘5’,‘5’,11,1] (three integers and three characters), so the length of this sequence is 6.Objectives for Section 3
After studying this section you should be able to do the following.
- Recognise and use the terminology: disjoint union; power set (of a set); representation (of a data abstraction).
- Use and interpret the notation:
- X Y for the disjoint union of the sets X and Y ;
- SeqOfSetOfInt for the set consisting of all sequences whose members are sets of integers (and similar notations).
- X
3.4 Representing data in applications
Suppose that you are designing software for some application. You will be working with a programming language that enables you to communicate instructions to a computer. In this programming language, certain forms of data will already be represented electronically. These will include common forms of data, such as numbers, characters and sequences. In any particular application, you are likely also to be concerned with forms of data that are peculiar to that application. Having identified some form of data that you need to be able to handle, you will then need to represent this in terms of what is available; that is, in terms of forms of data that have already been represented electronically.
As a simple example, imagine that integers, characters and strings are available forms of data, and that you want to represent the days of the week.
One natural form of representation is as strings: “Monday”, “Tuesday”, “Wednesday”, and so on. But other forms of representation are possible. The full names can be inconvenient because they involve a lot of writing, so one might choose to use shortened versions, such as: “Mon”, “Tues”, “Wed”, etc. We could be awkward (from the viewpoint of an English speaker), and use the strings: “Lundi”, “Mardi”, “Mercredi”, and so on. Or we could use integers, and represent Monday as 1, Tuesday as 2, Wednesday as 3, etc. This might be very convenient at times, but one then needs to remember which number represents which day.
There are times when it is important to distinguish between a form of data derived from an application situation and the concrete representation you have chosen for it. We might refer to the idea of the days of the week as an abstraction, in distinction to their representation, perhaps as the strings “Mon”, “Tues”, “Wed”, etc.
One additional point of importance about any form of data in an application concerns the ways in which we need to be able to manipulate it. We turn to processes on data in the next section.
As a simple example, imagine that integers, characters and strings are available forms of data, and that you want to represent the days of the week.
One natural form of representation is as strings: “Monday”, “Tuesday”, “Wednesday”, and so on. But other forms of representation are possible. The full names can be inconvenient because they involve a lot of writing, so one might choose to use shortened versions, such as: “Mon”, “Tues”, “Wed”, etc. We could be awkward (from the viewpoint of an English speaker), and use the strings: “Lundi”, “Mardi”, “Mercredi”, and so on. Or we could use integers, and represent Monday as 1, Tuesday as 2, Wednesday as 3, etc. This might be very convenient at times, but one then needs to remember which number represents which day.
There are times when it is important to distinguish between a form of data derived from an application situation and the concrete representation you have chosen for it. We might refer to the idea of the days of the week as an abstraction, in distinction to their representation, perhaps as the strings “Mon”, “Tues”, “Wed”, etc.
Activity 13
A compact form of representation for days of the week might be to use the first character of the name: ‘M’ for Monday, ‘T’ for Tuesday, and so on. Why would this be a bad idea?
Discussion
Because we could not tell whether ‘T’ meant Tuesday or Thursday (or whether ‘S’ meant Saturday or Sunday). Different entities in the abstract set of application data need to have different representations.3.3 Mixing different forms of data: disjoint union of sets
At the supermarket checkout, some items need to be weighed (organic courgettes for example) and some do not. Let BarcodedItems be the set of items that do not need to be weighed, and WeighedItems be the set of items that must be weighed. When a weighed item is recorded at the till, we must record both the item type and the weight of the item that has been purchased. Earlier, we saw that such a purchase can be seen as an ordered pair, such as (“WALNUTS”, 335), that comes from the set WeighedItems × Int.
Suppose now that we want to form the set of all items that might appear in a transaction at a till. We might call this set TillItems. Specifying this set TillItems poses a complication, since there are two different types of element that might appear in it. An item from the set TillItems will come either from BarcodedItems or from WeighedItems × Int. We express this relationship by saying that TillItems is the disjoint union of BarcodedItems and WeighedItems × Int. We write this as:
You can read X Y as “X or Y.”
TillItems = BarcodedItems (WeighedItems × Int).
In general, the disjoint union of sets X and Y , written X Y , is the set consisting of all items that are either from X or from Y . The term “disjoint” reflects the fact that an item could not come both from BarcodedItems and from WeighedItems × Int. These sets contain different forms of data and have nothing in common. (We will only use disjoint union to combine sets containing different forms of data.)
As in Section 1, suppose that till1 is a variable representing a transaction in progress at till 1. The state of till1 will give the items recorded so far, in the order in which they were entered into the till, either by reading the barcode, or as a weighed item. So we can describe the state of till1 as a sequence of till items. The set of all possible states of till1 is SeqOfTillItems, where TillItems is BarcodedItems (WeighedItems × Int).
As noted earlier, we usually want to avoid mixing data of different forms in a collection such as a sequence. But if we need to do this, we can first use a disjoint union to combine the different forms of data into a single set. So, for example, if we needed to form a sequence whose members might be either characters or integers, then this sequence would come from a set SeqOfMix, where Mix is the disjoint union Int Char.
Search Amazon.com for Data and processes in computing,
Suppose now that we want to form the set of all items that might appear in a transaction at a till. We might call this set TillItems. Specifying this set TillItems poses a complication, since there are two different types of element that might appear in it. An item from the set TillItems will come either from BarcodedItems or from WeighedItems × Int. We express this relationship by saying that TillItems is the disjoint union of BarcodedItems and WeighedItems × Int. We write this as:
You can read X
Y as “X or Y.”TillItems = BarcodedItems
(WeighedItems × Int).In general, the disjoint union of sets X and Y , written X
Y , is the set consisting of all items that are either from X or from Y . The term “disjoint” reflects the fact that an item could not come both from BarcodedItems and from WeighedItems × Int. These sets contain different forms of data and have nothing in common. (We will only use disjoint union to combine sets containing different forms of data.)As in Section 1, suppose that till1 is a variable representing a transaction in progress at till 1. The state of till1 will give the items recorded so far, in the order in which they were entered into the till, either by reading the barcode, or as a weighed item. So we can describe the state of till1 as a sequence of till items. The set of all possible states of till1 is SeqOfTillItems, where TillItems is BarcodedItems
(WeighedItems × Int).As noted earlier, we usually want to avoid mixing data of different forms in a collection such as a sequence. But if we need to do this, we can first use a disjoint union to combine the different forms of data into a single set. So, for example, if we needed to form a sequence whose members might be either characters or integers, then this sequence would come from a set SeqOfMix, where Mix is the disjoint union Int
Char.Search Amazon.com for Data and processes in computing,
Activity 12
Let TillItems = BarcodedItems (WeighedItems × Int), and suppose that BarcodedItems is represented as the set of integers between 10000 and 99999 and WeighedItems as the set of integers between 100 and 999. Which of the sequences given in (a)–(c) below is a member of the set SeqOfTillItems?
(WeighedItems × Int), and suppose that BarcodedItems is represented as the set of integers between 10000 and 99999 and WeighedItems as the set of integers between 100 and 999. Which of the sequences given in (a)–(c) below is a member of the set SeqOfTillItems?- (a) [1, −740, (22, 300)]
- (b) [11, ‘2’, ‘w’, 33000, −22]
- (c) [11023, 11023, (998, 12), 22375, (217, 147)]
Discussion
Only the sequence in (c) is in SeqOfTillItems.- (a) According to the statement, a barcoded item is represented by an integer with five digits. So 1 and −740 are not from the set BarcodedItems.
- (b) This sequence contains some characters, which are neither from the set BarcodedItems nor from WeighedItems × Int.
- (c) Each of the integers 11023 and 22375 lies between 10000 and 99999, and so comes from the set BarcodedItems. The first entry in each of the pairs (998, 12) and (217, 147) is an integer between 100 and 999, so comes from WeighedItems. Thus each of these ordered pairs comes from WeighedItems × Int. So each item in the sequence is either from BarcodedItems or from WeighedItems × Int, and so comes from TillItems.
3.2 Combining data structures
Search Amazon.com Books for Data and processes in computing,
In Section 2, we introduced the notation SeqOfX for the set of all sequences whose members come from the set X. In Section 2, we looked only at sequences whose members were of one of the primitive forms of data (integers, characters or Booleans). We can have sequences whose members are themselves data with a more complicated form. For example, suppose that Jo is working at the till T1 and is replaced by Jessica. We might represent this handover by the 3-tuple (Jo, T1, Jessica). Now suppose that we want to give all the handovers that occur during a particular day, in the order in which they occur. We could give this information in a sequence. This sequence would come from the set SeqOfX , where X is the Cartesian product Staff × Tills × Staff.
As another example, one might think of a sentence as a sequence of words, where each word is seen as a sequence of characters. If we did this, then the sentence would be regarded as coming from the set SeqOfSeqOfChar. We can use notations introduced earlier to show when we want to see a sentence in this way, and when it is to be regarded as a single string (from SeqOfChar).
Search Amazon.com Books for Data and processes in computing,
Consider a computer system which has a finite set of error messages, each of which may be displayed to a cashier at the till. Suppose these messages are: “Barcode error”; “Item code not recognised” and “System error 1234”. This set of error messages can be represented thus:
Errors = {“Barcode error”, “Item code not recognised”, “System error 1234”}.
Each of these messages is given as a string, that is, as a sequence of characters. So Errors is a set of sequences of characters.
In Section 2, we introduced the notation SeqOfX for the set of all sequences whose members come from the set X. In Section 2, we looked only at sequences whose members were of one of the primitive forms of data (integers, characters or Booleans). We can have sequences whose members are themselves data with a more complicated form. For example, suppose that Jo is working at the till T1 and is replaced by Jessica. We might represent this handover by the 3-tuple (Jo, T1, Jessica). Now suppose that we want to give all the handovers that occur during a particular day, in the order in which they occur. We could give this information in a sequence. This sequence would come from the set SeqOfX , where X is the Cartesian product Staff × Tills × Staff.
As another example, one might think of a sentence as a sequence of words, where each word is seen as a sequence of characters. If we did this, then the sentence would be regarded as coming from the set SeqOfSeqOfChar. We can use notations introduced earlier to show when we want to see a sentence in this way, and when it is to be regarded as a single string (from SeqOfChar).
Search Amazon.com Books for Data and processes in computing,
Activity 11
Which of the following is a member of the set SeqOfSeqOfChar?
- (a) [‘W’,‘o’,‘r’,‘d’].
- (b) “This is a sentence.”.
- (c) [“This”,“is”,“a”,“sentence”].
Discussion
Only (c) is a member of SeqOfSeqOfChar.- (a) This is a sequence of characters and so a member of SeqOfChar.
- (b) This is a string, so is again a sequence of characters (written in our more compact notation).
- (c) This is a sequence each of whose members is a string. Thus each item in the sequence in (c) comes from SeqOfChar. The sequence itself comes from SeqOfSeqOfChar.
Errors = {“Barcode error”, “Item code not recognised”, “System error 1234”}.
Each of these messages is given as a string, that is, as a sequence of characters. So Errors is a set of sequences of characters.
3.1 Sets of sets
In Section 2, all the sets and sequences we considered had primitive forms of data as their elements. However, sets and sequences may contain non-primitive forms of data. Let us look first at a situation in which we may find it useful to have a set whose members are themselves sets.
Think again about a shop with just three members of staff, given in the set Staff = {Jo, Jessica, Wesley}. Now let at WorkStaff be the set of staff currently at work. Clearly, at WorkStaff may take a range of values. If just Jo and Wesley are at work, then at WorkStaff is {Jo, Wesley}. If Jessica were to start work and Jo were to leave, then at WorkStaff becomes {Jessica, Wesley}.
Now any combination of staff from the set Staff = {Jo, Jessica, Wesley} might be at work at the same time. Possibilities include all these staff (when at WorkStaff is {Jo, Jessica, Wesley}), and none of them (in which case at WorkStaff is { }). The full list of possibilities (giving the possible values of at WorkStaff ) is given below.
{ }, {Jo}, {Jessica}, {Wesley}, {Jo, Jessica}, {Jo, Wesley}, {Jessica, Wesley}, {Jo, Jessica, Wesley}
Here, we have written out all the sets with members taken from the set Staff = {Jo, Jessica, Wesley}. We can form a set whose members are these sets. We will denote this set by SetOfStaff . So:
SetOfStaff = {{ }, {Jo}, {Jessica}, {Wesley}, {Jo, Jessica}, {Jo, Wesley}, {Jessica, Wesley}, {Jo, Jessica, Wesley}}.
The outer curly brackets here delimit the members of the set SetOfStaff. Each of these members is itself a set, and the inner curly brackets delimit each of these member sets. We will not often need to list the members of a set of sets like this. But it is useful to be aware that we can form a set in this way. We might have a variable atWorkStaff, giving the set of staff currently at work. The set giving all possible states of this variable is then SetOfStaff.
In general, we will use SetOfX to denote the set consisting of all the sets drawn from some given set, X. SetOfX is also known as the power set of X. Various other notations are used for this, including P(X) and 2 X . The latter is sometimes used since, if X has cardinality n, then SetOfX has cardinality 2 n . For example Staff has cardinality 3 and SetOfStaff has cardinality 8, which is 23.
{{}, {T1}, {T2}, {T3 }, {T1, T2}, {T1, T3}, {T2, T3}, {T1, T2, T3}}.
Think again about a shop with just three members of staff, given in the set Staff = {Jo, Jessica, Wesley}. Now let at WorkStaff be the set of staff currently at work. Clearly, at WorkStaff may take a range of values. If just Jo and Wesley are at work, then at WorkStaff is {Jo, Wesley}. If Jessica were to start work and Jo were to leave, then at WorkStaff becomes {Jessica, Wesley}.
Now any combination of staff from the set Staff = {Jo, Jessica, Wesley} might be at work at the same time. Possibilities include all these staff (when at WorkStaff is {Jo, Jessica, Wesley}), and none of them (in which case at WorkStaff is { }). The full list of possibilities (giving the possible values of at WorkStaff ) is given below.
{ }, {Jo}, {Jessica}, {Wesley}, {Jo, Jessica}, {Jo, Wesley}, {Jessica, Wesley}, {Jo, Jessica, Wesley}
Here, we have written out all the sets with members taken from the set Staff = {Jo, Jessica, Wesley}. We can form a set whose members are these sets. We will denote this set by SetOfStaff . So:
SetOfStaff = {{ }, {Jo}, {Jessica}, {Wesley}, {Jo, Jessica}, {Jo, Wesley}, {Jessica, Wesley}, {Jo, Jessica, Wesley}}.
The outer curly brackets here delimit the members of the set SetOfStaff. Each of these members is itself a set, and the inner curly brackets delimit each of these member sets. We will not often need to list the members of a set of sets like this. But it is useful to be aware that we can form a set in this way. We might have a variable atWorkStaff, giving the set of staff currently at work. The set giving all possible states of this variable is then SetOfStaff.
In general, we will use SetOfX to denote the set consisting of all the sets drawn from some given set, X. SetOfX is also known as the power set of X. Various other notations are used for this, including P(X) and 2 X . The latter is sometimes used since, if X has cardinality n, then SetOfX has cardinality 2 n . For example Staff has cardinality 3 and SetOfStaff has cardinality 8, which is 23.
Activity 10
Suppose that the set of tills in a supermarket is Tills = {T1, T2, T3} and active Tills is a variable giving the set of tills that are staffed at any one time. Write out in full the set of possible states for active Tills.
Discussion
The set of possible states is the set SetOfTills. Written in full, this is:{{}, {T1}, {T2}, {T3 }, {T1, T2}, {T1, T3}, {T2, T3}, {T1, T2, T3}}.
Subscribe to:
Posts (Atom)