Computer design and programming
In the most general terms a computer is a
device that calculates a result ("output")
from one or more initial items of information
("input"). Inputs and outputs are usually
represented in binary terms--i.e., in strings of
0s and 1s--and the values of 0 and 1 are realized in the
machine by the presence or absence of a current (of
electricity, water, light, and so on). When the output
is a completely determined function of the input, the
connection between a computer and the two-valued
logic of propositions is immediate, for a valid argument
can be construed as a partial function of the truth
values of the premises such that when the premises each
have the value true, so does the conclusion.
One of the simplest computers has one input, either 0
or 1 (i.e., a current either off or on), and one
output, namely, the reverse of the input. That is, when
0 is input, 1 is output, and, conversely, when 1 is
input, 0 is output. This is also the behaviour of the
truth function negation ( p)
when applied to the truth values true and false. Thus a
circuit elements that behaves in such a way is called a
NOT gate:
When no current is input from the left, a current
flows out on the right, and, conversely, when a current
flows in from the left, none is output to the right.
Similarly, devices with two inputs and one output
correspond in behaviour to the truth functions
conjunction (p q) and disjunction (p 
q). Specifically, in an AND gate,
current flows out to the right only when current is
present in both inputs; otherwise there is no output. In
an OR gate, current is output when a current is present
in either or both of the inputs on the left.
Other truth functional connectives are easily
constructed using combinations of these gates. For
example, the conditional, (p 
q), is represented by:
There is no output if there is input from p
("p" is true) and none from q
("q" is false).
It is also possible to connect these gates to memory
devices that store intermediate results in order to
construct circuits that perform elementary binary
arithmetic: addition, subtraction, multiplication, and
division. These simple circuits, and others like them,
can be connected together in order to perform various
computations such as determining the implications of a
set of premises or determining the numerical value of a
mathematical function for specific argument values.
The details of computer design and
architecture depend less on logical theory and more on
the mathematical theory of lattices and are outside the
scope of this article. In computer programming,
however, logic has a significant role.
Some modern computers, such as the ones in
automobiles or washing machines, are dedicated; that is,
they are constructed to perform only certain sorts of
computations. Others are general-purpose computers,
which require a set of instructions about what to do and
when to do it. A set of such instructions is called a
program. A general-purpose computer operating
under a program begins in an initial state with a given
input, passes through intermediate states, and should
eventually stop in a final state with a definite output.
For a given program, the various momentary states of the
machine are characterized by the momentary values of all
the variables in the program.
In 1974 the British computer scientist Rod M.
Burstall first remarked on the connection between
machine states and the possible worlds used in the
semantics of modal logic. The use of concepts and
results from modal logic to investigate the properties
and behaviour of computer programs (e.g.,
does this program stop after a finite number of steps?)
was soon taken up by others, notably Vaughan R. Pratt
(dynamic logic), Amir Pnueli (temporal logic), and David
Harel (process logic).
The connection between the possible worlds of the
logician and the internal states of a computer is
easily described. In possible world semantics, p
is possible in some world w if and only if p
is true in some world w' accessible to w.
Depending on the properties of the accessibility
relation (reflexive, symmetric, and so on), there will
be different theorems about possibility and necessity
("p is necessary" = "Mp").
The accessibility relation of modal logic semantics can
thus be understood as the relation between states of a computer
under the control of a program such that, beginning in
one state, the machine will (in a finite time) be in one
of the accessible states. In some programs, for
instance, one cannot return from one state to an earlier
state; hence state accessibility here is not
symmetric.
|