Introduction

In this chapter, we shall investigate the important class of relations known as mappings or functions. These are relations between two sets such that every possible element of the first set appears in one and only one ordered pair. We can regard the relation as a list, with the first column listing the elements in the domain, and the second listing the values of the function. A mapping is usually specified either by giving a rule for which y appears in each pair (x, y), or, for finite sets, by listing the value of the mapping for each value of x.

Discrete mathematics

Discrete mathematics is the study of those parts of mathematics which do not require any knowledge of limits, convergence, differentiation, and so on. It encompasses most of the foundations of mathematics, such as logic, set theory, relations, and also graph theory, formal language theory and an indeterminate chunk of abstract algebra.

The boundaries are necessarily vague, as they are in any subject, and we can never be sure, as our study progresses, that we will not need some result from another area. Anyone studying the time complexity of sorting algorithms would find it difficult not to use some ideas from the calculus; both logic and formal languages subsume the whole of mathematics; the study of finite error correcting codes leads into some sophisticated uses of matrices and polynomial algebras.

Mathematics provides us with a way of describing the so called ‘real world’ in an accurate, concise and unambiguous way. We extract the properties which we wish to describe, write down a few mathematical relations, and then work algebraically with those relations. As long as the mathematics and the object of our study have those common properties, any deduction we make in the mathematical model can be translated back to the real world.

It does not matter whether the mathematical description is close to the way a task is implemented. A common mistake is to think in terms of concrete realizations rather than properties.

A leisurely introduction to the applications of the material in Chapters 2–5, together with an introduction to the specification language Z, may be found in the following. Z is a cross between mathematics and a programming language, and uses horizontal and vertical lines extensively to try to make the mathematics more palatable.

An Introduction to Discrete Mathematics and Formal System Specification, D. C. Ince, Oxford University Press, 1988.

An account of the theory of how programs, data and computers are modelled, including an excellently readable introduction to program verification, may be found in the next book.

Fundamental Structures of Computer Science, William A. Wulf, Mary Shaw, Paul N. Hilfinger, and Lawrence Flon, Addison-Wesley Publishing Company, 1981.

Database design is covered extensively in the following two books. The second is probably more readable, though sometimes inaccurate.

An Introduction to Database Systems, C. J. Date, Addison-Wesley Publishing Company, 1986.

A Pascal Database Book, Julian R. Ullmann, Oxford University Press, 1985.

The subject matter of Chapter 8 is considerably extended in the following excellently readable book.

Theory of Finite Automata, with an Introduction to Formal Languages, John Carroll and Darrell Long, Prentice-Hall International, Inc., 1989.

The following is only for the mathematically mature. It covers formal languages, automata, the theory of computation, complexity theory, cryptography and Petri nets.

Introduction

The idea of a graph is one of the most elementary and simple in all of mathematics, yet the theory of graphs is remarkably complex, leading to both general theorems and to famous unsolved problems. We have met graphs already, in Chapters 4 and 5, where we used them to illustrate what was happening in a relation or mapping. In fact, we used directed graphs there, which are mathematically identical to binary relations.

There are also undirected graphs, which we shall meet for the first time in this chapter; they are broadly equivalent to symmetric relations. The structure of undirected graphs is simpler than that of directed graphs, leading to a rich and fruitful theory. There are complications inherent in the asymmetry of directed graphs which lead to a different sort of outlook, and a concentration on different kinds of problems.

Undirected graphs

The basic idea in an undirected graph is of a set of points called vertices joined by lines called edges. These points and edges could be thought of as nodes in an electrical network and wires joining them, or as road junctions and stretches of road between junctions. They could also be thought of as symmetric binary relations, where the vertices might be people, and an edge between two vertices might indicate that the people know one another. What is not sanctioned is the merging of two edges, the way two roads or flightpaths between cities might merge.

Introduction

The types of mappings we have met in Chapter 5 have mostly been the sort where the domain has been simple, that is, not a cartesian product of sets. There is a type of mapping which arises frequently in applications, and it is exemplified by the function f : ℝ2 → ℝ given by f(x,y) = x + y. Such mappings are called binary operations, and much effort has been expended during the last two centuries on studying their properties.

A seemingly unrelated problem is that of finding a mathematical specification for strings in programming languages. Strings and binary operations are not all that different when we look at their formalism, and the theory we shall develop will also be able to model stacks, queues, and other related structures.

Finally, we shall look at the way in which programming languages are specified, and shall develop a notation for working with their syntax. We shall investigate the way we can simplify the structure of a language, and how to write a program to recognize valid statements in the language.

The pace of this chapter will be brisker than previous ones. We shall leave more details for the student to fill in. It is hoped that by now the student has acquired enough mathematical confidence to be able to do this.

Introduction

Mathematics is the science of inference. It starts from axioms describing the world, and makes deductions from those axioms according to the accepted rules of reason.

It became apparent in the nineteenth century and early in the twentieth century that these rules of inference themselves could be made the subject of mathematical investigation, and thus there was a possibility that the whole logical process could be mechanized. One could write down the initial assumptions, and then merely turn a handle to obtain the conclusion. These investigations resulted in what is known as symbolic logic. Although the original goal may have eluded us, because of certain profound discoveries concerning the process of proof, what remains is a powerful notation for expressing ideas in a precise form, and an elegant mathematical theory of logic which we shall be studying in this chapter.

Let us first look at a few places where mathematical logic is used.

Introduction

Suppose that we are using the notations of mathematical logic, as described in Chapter 2. We have some universe of discourse E, and let us suppose that a predicate R(x) is given. We could look at the objects in E in turn, and check for each object whether or not R(x) is true. If we then selected the collection of objects which made R(x) true, we would have what is known as a set.

Although the predicate calculus allows us to do anything we desire, it has been found over the last century or so that set notation is far more convenient and natural. A predicate in one variable is thought of as expressing a property of objects in the universe of discourse; a set is the collection of all those objects with that property. Conversely, given a collection of objects in the universe of discourse, we can form a predicate which expresses the property of being in that collection. Sets and one place predicates are completely interchangeable.

Perspective differences at the Postal Giro

When we enter a large organization like the Postal Giro, we will be exposed to a large inhomogeneous mass of written and spoken language: we listen to the speech of workers engaged in work, interview them and talk to them, read manuals and look at the screen images they work with, and talk to management in offices removed from the shop floor. Although many of these verbal exchanges clearly refer to the same physical phenomena, the linguistic forms can be quite different. It soon appears that each linguistic form is adapted to the particular function the speaker fulfills in the total structure of work processes and power relations in the organization. Each sub-language expresses a particular perspective (on perspective, see Section 1.2.2.2) and reveals a partial truth about the organization.

In the development of the PGP system there was one major issue that in a nut-shell illustrates the intricate interplay between language, perspectives and position in the division of labor. In semiotic terms, the issue was simply the relation between signifier and signified, in this specific case taking the form of a disagreement between union and management about electronic scanning of paper forms.

Management wanted to get rid of all paper by optical scanning of the paying-in-forms and wanted all subsequent work involving the cards to be done by means of electronic card images on a video screen. The union demanded that the basis of data recording should still be the paper forms, so that a direct feeling of the amount of work remained intact. The union succeeded in preventing electronic scanning of paper forms.

In the previous part, I described the basic properties of computer-based signs. They have three main kinds of features (permanent, transient and handling features) and are organized in two main chains (concurrent and sequential). In this part, I shall treat composite computer-based signs. How are smaller computer-based signs combined to form larger signs?

It is very clear that complex signs corresponding to linguistic concepts like phrases, sentences, and periods exist. The player of video games will experience long nerve-racking combat episodes involving the hero and one or more enemies, and the user of a word processor will engage in major tasks like proof-reading a manuscript or reorganizing the composition of a text, involving extensive handling of tools and text. Since these larger activities are manifested in system processes, they must be considered signs also, and since they contain smaller recurrent elements with meaning (the hero and enemy, the tools and texts), they are composite signs.

Although the three main features of computer-based signs have been treated in detail, I have not yet said much of the analytical consequences of the fact that computer-based signs participate in two different chains.

I shall continue using the textbook on folk-dance from Section II. 1.2, since a dance instructor or a writer of textbooks on dance faces problems similar to those facing a designer of computer systems. Like the designer prescribing the sequence of computer-based actions and the stage of the screen, the dance instructor must teach the dancers how to move in time on the floor, how to coordinate their movements with their partner, how to hold each other, and how to establish collective patterns.

A psychological definition of language games

In the preceding section, I showed how to use semantic fields of lexical material for various purposes: when the system developer enters the organization she can use them to get an impression of conceptual differences of the organization, when she starts doing particular applications she can use them to design the general data structure, and when she has made a prototype, semantic fields are useful for evaluating its reception and for redesigning it. Finally, researchers studying the general effects of computerization on organizations can use semantic fields to record language changes in the organization, and use these data as a basis for setting up hypotheses about changes of culture and cognition.

However, language is more than a vehicle for interpretation and description. Besides the ideational functions, language also has an action aspect that is subsumed under Halliday's interpersonal functions.

Although it is not a bad idea to start with the ideational aspect, since professional languages are registers and tend to differ in vocabulary, the action aspect is equally important in systems development. Language in work situations is not only used to interpret and describe, but also to act verbally, and in a similar way, computer systems are used as media for distributing work, giving orders, and reporting. Designers not only need to know which kind of information is needed and how it should be structured semantically, they also need to know when it is needed and for which purposes.

In the preceding section, I showed how to use work and conversation patterns as a basis for design. In this last section I discuss principles for building these patterns into the system. What does it mean to “put work patterns into the system”? To what degree should it be done? How should it be done?

As my example I shall use the data entry parts of the data entry (registrering) process classified as control style in Section II.2.2.2. Here I noted that the PGP-system is in control in this part of the work process and guides the worker through a fixed standardized sequence of operations:

In addition, it automatically provides the next card of the same batch, and the first card of the next batch when the last of the previous batch is finished and the batch tallies. If it does not tally, it enters the completing subview. The system supervises the user's work, and directs the worker's attention to and from the screen by means of error messages like

a type of control which was consciously introduced by the developers: they wanted to “stop a phase where you work with the card, and initiate a phase where you work with the screen”.

I have already classified this standardization of work as a “frozen” variant structure.