ÐÓ°ÉÔ­´´

A CENTURY and a quarter ago, a man died who, according to Bertrand Russell,
discovered pure mathematics. Better known perhaps for the algebras named
after him, or as the creator of modern logic, George Boole was one of the
most influential thinkers of the 19th century. His celebrated treatise,
The Laws of Thought, published in 1854, opened up new possibilities, not
just for logic or mathematics, but also for the yet-to-be-born science of
electronic computing. What has been the contribution of Boole’s legacy –
his ideas, methods and discoveries – to contemporary science and technology?
Let us begin with a quick tour of his masterpiece, whose full title is An
Investigation of the Laws of Thought on which are founded the Mathematical
Theories of Logic and Probabilities.

From the opening paragraph, Boole states the ambitious design of his
work: ‘. . . to investigate the fundamental laws of those operations of
the mind by which reasoning is performed; to give expression to them in
the symbolical language of a Calculus, and upon this foundation to establish
the science of Logic and construct its method . . .’. In the course of these
inquiries, he also intends to collect ‘some probable intimations concerning
the nature and constitution of the human mind’.

For a subject that is essentially mathematical, Boole employs remarkably
little technical jargon. He seems to write for the cultivated intellect,
not just the experts, quoting poets and philosophers, often in the original
Greek or Latin, and occasionally shifting from logic to psychology, sociology
or metaphysics.

According to Boole, the operations of the mind engaged in reasoning
are ruled by certain ‘algebraic’ laws, analogous to the laws of the familiar
operations on numerical quantities – addition, multiplication and so on.
From these fundamental laws, which he expresses using mathematical symbols,
he constructs a method for solving problems in logic. First, the hypotheses,
or initial assumptions, are put in the form of equations. Then, algebraic
manipulations of the symbols replace the usual process of logical deduction.
Thus, reasoning is performed by ‘calculating’ or, to put it bluntly, logic
is reduced to algebra.

To be sure, what Boole understood by ‘logic’ is only what we would call
today the algebra of classes and propositional logic. But he must be credited
with a radically new approach, from which modern mathematical logic emerged.
In his algebra of classes, collections of things are represented by single
letters. For example, a may represent the class of all persons ‘ill with
AIDS’; h the class of ‘healthy’ people; v the class of those carrying the
AIDS virus (or HIV-positive); and b those persons who came in contact with
blood. The universal class, or class of all things under discussion, is
denoted 1 (in our case, 1 = ‘people’). The symbol 0 stands for the empty
class or class with no members. Classes obtained out of other classes by
certain operations are represented by algebraic expressions. Thus, ab is
the class of all things that are members of both classes a and b (those
ill with AIDS who have been in contact with blood) and 1 – v is the class
of things under discussion that are not members of v (the HIV-negative class).
In case two classes have no members in common, you can form their ‘sum’
h + a, which stands for the class of all persons who are either healthy
or ill with AIDS. Relations among classes are then written as equations.

A logical view of AIDS

To illustrate this, assume that the AIDS virus (HIV) may be transmitted
only through sexual intercourse or by coming in contact with blood. Also,
let us say that someone is ‘ill with AIDS’ if, in addition to carrying the
HIV, the person presents what might be called the ‘AIDS symptoms’. These
relations are translated into the two equations:

v(1 – (x + (1 – x)b)) = 0

a = vs

where x and s are the classes of those who had sexual intercourse and
those who have the AIDS symptoms, respectively. From the assumed relations
among the classes, other relations follow ‘logically’, in other words, are
implied by them. Boole’s method provides a series of rules for ‘solving’
the system of equations and interpreting the solution so as to yield the
implied relations. For example, solving the above system for the class (1
– s) + sx, would result in the final equation:

(1 – s) + sx = a(1 – b) + (1 – a)v + (0/0) ab + (0/0) (1 – v)

whose interpretation is: the class of all those individuals who either
do not have the AIDS symptoms or did not refrain from sex (or both) consists
of all those ill with AIDS who did not come in contact with blood; all HIV-positives
who do not have AIDS; an indefinite part – some, none or all – of those
ill with AIDS who have been in contact with blood and an indefinite part
of the HIV-negative class. This constitutes the complete relation among
the given classes that is implicit in the assumptions.

To those who, after seeing examples such as the above, might still be
unimpressed with the power of his method, Boole offers the following advice:
‘that they examine the problem by the rules of ordinary logic, remembering
at the same time, that whatever complexity it possesses might be multiplied
indefinitely, with no other effect than to render its solution by the method
of this work more operose, but not less certainly attainable’. He also defends
his method on aesthetic grounds, claiming that the perfection of a method
should not only be judged on the basis of its power and efficiency, but
also by the harmony and beauty it manifests – a position somewhat out of
phase with today’s standards.

Boole extends his calculus to propositional logic, which deals with
propositions about propositions (instead of about classes of things), for
example, ‘If the proposition Y is true, then the proposition X is true’,
and the like. When he applies it to the analysis of some classical demonstrations
in metaphysics and ethics, he finds that the chief difficulty is to determine
exactly what the actual premises or assumptions of the argument are. For
as soon as this is done, and the premises expressed in the form of symbolic
equations, his calculus leads him inexorably and automatically to the logical
conclusions. In this aspect of his method he senses the notion of ‘effective
computability’ (which would only be made precise almost a century later
by Alan Turing, the designer of the Turing machine – the most fundamental
computing device) when he observes that it proceeds ‘with a precision which
might almost be termed mechanical’.

Boole also discusses the time-honoured logical system of Aristotle,
which occupied an important place in academic education, with the intention
of ‘removing one or two prevailing misapprehensions respecting its extent
and validity’. He challenges its claim that all logical inferences may be
reduced to a syllogism (a typical syllogism is the deduction of ‘All Xs
are Zs’ from the propositions ‘All Xs are Ys’ and ‘All Ys are Zs’). The
truths of scholastic logic, he concludes, are too incomplete and not sufficiently
fundamental to constitute a science.

Over the years, Boole’s creation has been modified, improved and generalised
in many directions, and his original formulation replaced by simpler systems.
Nonetheless, for all its imperfections, the validity of his method remained
intact and, above all, it illustrated in a dramatic way how logic could
be associated with mathematics.

Boole and probability theory

In contrast to his work in logic, Boole’s contributions to the theory
of probabilities have left no historical mark. The last to consider Boole’s
ideas on the subject seems to have been John Maynard Keynes – almost 70
years ago. In his treatise on probability, the famous economist compares
favourably his own, simpler methods with those of Boole’s, mentioning nevertheless
that Boole’s writings are full of originality and genius. Historians have
perhaps failed to give Boole due credit for his contributions to probability
theory. Some of his ideas are now commonplace and have found practical applications
in areas ranging from insurance claims to medical diagnosis.

To appreciate the significance and originality of Boole’s ideas, one
has to consider the state of British mathematics in his day – not to mention
Boole’s own social condition and background. The son of shoemaker, he became
a teacher as soon as he finished his common schooling to help support his
parents. By the age of 18, and without any mathematical training beyond
the rudiments, he was ploughing through advanced treatises in mechanics
and analysis, learning his mathematics in the same way as he had learnt
his Greek and most of his Latin – by self-instruction. A few years later
he was publishing in mathematics journals, earning a reputation for his
achievements in analysis and differential equations. His paper On a General
Method in Analysis obtained the gold medal of the Royal Society for the
most significant communication in mathematics between 1841 and 1844.

The increasing recognition of Boole’s mathematical talents culminated
in 1849 with his appointment to a professorship in one of the newly founded
Queen’s Colleges, at Cork. At about that time, the British school was making
great contributions to the understanding and the renovation of algebra,
chiefly through the works of four British mathematicians: George Peacock,
Augustus de Morgan, Charles Babbage and Duncan Gregory. But it took the
vision of Boole to begin the transformation of algebra into a field concerned
not just with numbers, but also with abstract ‘objects’ and ‘operations’,
whose nature matters less than the laws of combination that they obey.

Boole must be credited with yet another achievement: the discovery of
invariants, which Arthur Cayley at Cambridge University and James Sylvester
at Johns Hopkins University in the US, and also at Oxford, were to develop
fully. This early algebraic work grew into the mathematical theory of invariance,
which not only has important applications within mathematics but also played
a crucial role in Einstein’s theory of relativity.

Technical applications of Boole’s algebra of logic first appeared in
the 1940s, when the American mathematician Claude Shannon used Boolean algebras
to analyse switching circuits. These are networks of relay contacts that
occur in practically every electrical system designed to perform complex
operations automatically, such as telephone exchanges or a railway signalling
circuit. Initially, computer circuitry was also made up of relays and switches,
but they were replaced by faster and smaller components. How do Boolean
algebras come into the picture? The intuitive notion of a switch is ‘something
that is either on or off’. A more precise definition is ‘something that
is at all times in one of two mutually exclusive states’. You can realise
these states physically in many ways, by the presence or absence of a current
or voltage, for example. They are usually represented by the two symbols
0 and 1.

Now, you can completely determine what the operations of a switching
circuit are, in the final analysis, by specifying how the states of a certain
number of output switches Y₁, Y₂, …,Y_m depend on the states of input switches
X₁, X₂, …,X_n. As an example, consider the simple series-parallel circuit
in Figure 1a. Capital letters X₁, X₂ and so on, represent switches or contacts
that may be either open (in state 0) or closed (in state 1). Switches labelled
with the same letter are simultaneously open or closed.

The symbols ³Ý¯₁, ³Ý¯₂, … indicate switches whose states are at any time
the opposite of those of X₁, X₂,.. . The points t₁ and t₂ are the terminals
of the circuit. They form another ‘switch’ Y, whose state is 1 if current
flows through the terminals, 0 if it does not. The state of this output
switch Y is, therefore, completely determined by the states of the four
input switches X₁, X₂, X₃ and X₄. A table (see Figure 1b) may be used to
specify the output state for each one of the 16 (=2⁴) possible combinations
of input states. For example, the first line in the table results from the
fact that if all four input switches are in state 0 (open) then Y is in
state 1, for current flows through the lowest branch of the circuit. Such
a table defines the output state as a function of the input states, thus
the analysis of switching circuits leads to the study of two-valued, or
binary, functions of n binary variables. Any such function may be built
from the three operations (join, meet and complement) on the two-element
Boolean algebra (see Figure 2). This allows us to represent the function
(and hence, also the circuit) by an equation in the symbols of Boolean algebra.
For example, the function associated with the circuit in Figure 1 may be
described by the Boolean equation, when ‘V’ is the symbol for ‘join’:

Y = X₁(X₂VX₃VX₄)VX₃
X₄V(X₃VX₄)X₂³Õ³Ý¯₁³Ý¯₂
³Ý¯₃³Ý¯₄

for if we replace the letters X1, X2, X3 and X4 with the input states
and perform the Boolean operations, the corresponding output state results.
The process may be reversed, and the complete circuit built from the equation.

To design a particular circuit or network, you first specify what you
require as a system of Boolean equations, then simplify them by algebraic
manipulation or other procedures. Finally, the equations can be implemented
using the appropriate hardware, such as relays or transistors.

An electronic computer is a typical example of a digital system. This
transmits signals or information in the form of a sequence of digits. If
we use only two digits, we have a binary digital system. Machines that handle
discrete data are almost always binary for reasons of accuracy and reliability.
The term ‘logic circuit’ is usually applied to circuits that perform operations
on binary signals. This brings us back to binary functions of n binary variables
and, therefore, to their synthesis using the three basic Boolean operations.
Logic circuits are built from elements called logic gates, which perform
like the basic Boolean operations or combinations of them (see Figure 3).
Unlike the contacts in the circuit of Figure 1, gates do not operate in
both directions, and signals pass only from input towards output. The ‘logic’
in ‘logic circuit’ comes from the relationship between the Boolean operations
and propositional logic. A proposition is any statement that may be classified
as being ‘true’ or ‘false’. For example: ‘George Boole was born in Moscow’
(false); ‘George Boole died in 1864’ (true). ‘True’ and ‘False’ are the
two possible ‘truth-values’ of propositions. If X and Y are two propositions,
then so are ‘XorY’ (their disjunction) and ‘X&Y’ (their ‘conjunction’).
Also, for each proposition X there is another, ‘not-X’, its ‘negation’.
By convention, the truth-value of these compound propositions is determined
as:

X&Y is true if both X and Y are true, otherwise it is false; XorY
is true if either X or Y or both are true, and it is false otherwise; not-X
is true if X is false, and false if X is true. For example, ‘George Boole
was born in Moscow & died in 1864’ is false; ‘George Boole was born
in Moscow or he died in 1864’ is true, whereas ‘George Boole did not die
in 1864’ is false. If ‘True’ is represented by 1 and ‘False’ by 0, then
the two-element Boolean algebra (see Figure 2) becomes an algebra of truth-values.
In the tables of Figure 2, if x,y are the truth-values of propositions X,Y
then xy, xVy and x are the truth-values of X&Y, XorY and not-X, respectively.

Underlying all these applications of Boolean algebra – to circuits,
digital systems, propositional logic and so on – there is a simple mathematical
theory: the symbolic calculus of binary functions of n binary variables.
But while modern mathematicians and engineers found this tool was readily
available, Boole had to create it. For all his fascination with symbolical
methods – which proved so successful in logic – Boole remained faithful
to one of his principles: that the use of symbols should be a means towards
an end, that end being the knowledge of some intelligible fact or truth.
Did he realise that symbols could one day be also ‘intelligible’ to machines,
and that they could be used to convey mere information – never mind truth?
Boole spent his last years working and publishing as actively as ever, while
honours were pouring on him in the form of prizes, honorary degrees and
memberships in learned societies. Death came suddenly on 8 December 1864,
when he was only 49 and still in his mathematical prime. The first two lines
of an acrostic presented to Boole in 1846, proved prophetic: ‘Great man,
thy fame will live when thou art gone, Ennobling thee far more than sculptur’d
²õ³Ù´Ç²Ô±ð.’

Arturo Sangalli is in the Department of Mathematics at Champlain Regional
College, Lennoxville, Quebec.

* * *

1: Sets and the beauty of Boolean algebras

IMAGINE a collection of objects x,y,z, ..any pair of which may be combined
to produce other objects x V y and xy, called their ‘join’ and ‘meet’, respectively.
Also, associated with each x there is an object x, the ‘complement’ of x.
Finally, there are two particular objects, denoted 0 and 1 (not necessarily
the familiar ones from arithmetic). Your collection is said to form a ‘Boolean
algebra’ if the following ‘laws’ are satisfied:

xy = yx, xVy = yVx

(commutative laws)

x1 = x, xV0 = x

(identity laws)

x(yVz) = xyVxz, xVyz = (xVy)(xVz)

(distributive laws)

xx¯ = 0, xVx¯ = 1

(laws of complement)

If you are familiar with the language of set theory, an example of a
Boolean algebra is the collection of all subsets of a given set X. The operations
of join and meet are the union and the intersection of subsets, respectively,
and x is the complement of x relative to X. The special object 0 is the
empty set, and 1 is the set X. Another example, relevant to logic, is the
collection of formal propositions, constructed from the ‘propositional variables’
p,q,r, ..and the connectives ‘or’, ‘&’ and ‘not’ – for example, ‘(p&not-q)
or (not-p&r)’. The object 0 is ‘False’ (or a proposition which is always
false, like ‘p&not-p’) and 1 is ‘True’ (or the proposition ‘pornot-p’).

Boolean algebras come only in sizes that are powers of 2, that is, they
can have only 2ⁿ elements (for some n = 1,2,3, and so on), or else they
have infinitely many. The smallest one consists solely of the elements 0
and 1 (see Figure 2) and, despite its simple structure, plays a central
role in the theory. For example, if some equation, such as
(x¯V¯y¯)z = x¯;(y¯z),
is always true when x,y and z are replaced by 0 or 1 in all possible ways,
then it will be true for the elements of any Boolean algebra. This has practical
consequences for the applications of the theory, because it reduces the
solution of many problems to the ‘mechanical’ process of testing 0s and
1s. The elements of any Boolean algebra may be disposed in a lattice-like
pattern thanks to an order relation implicit in the laws (see Figure below).
In this ordering, the element x precedes y in case x = xy.

Over the past 50 years, the theory of Boolean algebras and related structures
has grown into an extensive branch of pure mathematics, with applications
within as well as outside mathematics.

* * *

2: Logic circuits and binary computation

IN A DIGITAL computer, numbers are represented as strings of 0s and
1s. Let us assume that they are written in base 2, so that the number 13
is coded ‘1101’ (13 = 1 X2**3+1X2**2+0X2**1+1X2). Computations are then
performed in base 2, or binary, arithmetic. To illustrate the use of logic
circuits in computation, we show how to design a binary adder. We start
with a half-adder, which adds two binary digits x and y and gives as output
the last digit s of their sum, together with the ‘carry’ digit c. For example,
if x = 1 and y = 1, then 1 + 1 = 10 (in base 2), so that s = 0 and c = 1.
The Boolean equations for the half-adder are:

s = (xVy) x¯y¯

c = xy

and the corresponding circuit is below:

A full adder adds two binary numbers in a step-by-step fashion. It has
three inputs x, y and cin, the carry from the previous step. It gives as
outputs the sum digit s and cout, the carry for the next step. The computation
proceeds like the usual addition of numbers using paper and pencil. For
example, after adding 1101 to 101, our working sheet would look like this:

The Boolean equations, which give s and cout for each possible combination
of inputs, are:

s = (x y) c_in

c_out = xy V (x y) c_in

where x y is the ‘exclusive-or’ operation, defined in terms of the basic
Boolean operations by the equation:

(x y) = (x V y) x¯y¯

A circuit for the full adder may be built using two half-adders.

In the actual implementation, a delay device is needed to store the
carry from each step and feed it back in one time-unit later.