A Brief History of Logi

Moshe Y. Vardi

January 15, 2003

1 Trivia
The word trivial has an interesting entymology. It is omposed of \tri" (meaning
\3") and \via" (meaning \ways"). It originally referred to the trivium, the three
fundamental urri ulae: grammar, rhetori s, and logi . Mastery of these sub-
je ts was onsidered essential before study ould ontinue with the quadrivium,
whi h onsisted of arithmeti , geometry, musi , and astronomy.
Why was logi onsidered to be fundamental to one's edu ation? To answer
this question, it is ne essary to explain what we mean by the term \logi ".
Lewis Carroll, Through the Looking Glass:

\Contrariwise," ontinued Tweedledee, \if it was so, it might be;<

and if it were so, it would be; but as it isn't, it ain't. That's logi ."
Some attempts by the lass to dene logi were:
1. The ability to determine orre t answers through a standardized pro ess.
2. The study of formal inferen e.
3. A sequen e of veried statements.
4. Reasoning, as opposed to intuition.
5. The dedu tion of statements from a set of statements.
In a sense, all of these denitions are orre t.
Logi was originally studied by the Sophists, who engaged in formal debates.
Eventually, they sought to devise an obje tive system of rules to determine be-
yond any doubt who had won an argument. Logi was devised for this purpose.
As Fran is Ba on put it, in 1605,
\Logi diereth from rhetori ..in this, that logi handleth reason
exa t and in truth, and rhetori handleth it as it is planted in popular
opinions and manners."

1
So logi deals with a set of rules for reasoning and arguing. Thus, it deals with
a fundamental problem in intelle tual pursuits: how to distinguish what is true
from what is false, what is right from what is wrong.

2 The First Age of Logi : Symboli Logi (500

B.C. - 19th Century)
Originally, logi dealt with arguments in the natural languages used by humans.
For example, it would be used to demonstrate the orre tness of arguments like
the following:
All men are mortal.
So rates is a man.
Therefore, So rates is mortal.
If we hange \all" to \some", the argument doesn't hold. But how ould we
demonstrate this? We ould attempt to dene words su h as \all" and \some"
in terms of what inferen es we ould draw from them. Then the demonstration
would follow from these denitions. The problem is that natural language turns
out to be very ambiguous. For example, onsider the word \any". In the
senten e
\Eri does not believe that Mary an pass any test."
it ould be taken to mean either \all" or \one". (Note: in this lass, or in any
te hni al ontext, don't use the term \any").
Also, onsider the senten e
\I only borrowed your ar.".
Dierent in e tions imply dierent meanings.
Another problem with natural language was that it led to many paradoxes.
The most famous is The Liar's Paradox. Consider the senten e
\This senten e is a lie."
If it were true, then it must be a lie, as it says, but this is impossible. Similarly,
if it were a lie, then what it says is true!
Other examples are:
The Sophist's Paradox. A Sophist is sued for his tuition by the s hool that
edu ated him. He argues that he must win, sin e, if he loses, the s hool
didn't edu ate him well enough, and doesn't deserve the money. The
s hool argues that he must lose, sin e, if he wins, he was edu ated well
enough and therefore should pay for it.

2
 The Surprise paradox. A logi professor announ es to his lass that there will
be a test next week, but he won't tell whi h day. He promises, \When
you get it, you'll be surprised.". The students dedu e that the test an't
be given on Friday: if it were, then, ome Friday morning, they would
know it had to be given on that day, and, therefore, they wouldn't be
surprised. But sin e they now know it an't be on Friday, they reason that
it an't be on Thursday either, sin e they would no longer be surprised on
Thursday morning. Similarly, it ouldn't be held on Wednesday, Tuesday,
or Monday, But on Tuesday, the professor does give the test, and the
students are very surprised.
These paradoxes, along with the ambiguities of natural language, eventually
led to the eort to formulate logi in a symboli language.

3 The 2nd Age of Logi : Algebrai Logi (Mid

to late 19th Century)
In 1847, George Boole, in \The Mathemati al Analysis of Logi " attempted to
formulate logi in terms of a mathemati al language. Rules of inferen e were
modeled after various laws for manipulating algebrai expressions:
\The design of the following treatise is to investigate the funda-
mental laws of the operations of the mind by whi h reasoning is
performed; to give expressions to them in the symboli language of
a al ulus, and upon this foundation to establish the s ien e of logi
and onstru t its methods."
The basis for his work was the similarity between the relationship of set union
and interse tion and that of numeri al addition and multipli ation, e.g.,
a(b + ) = (ab) + (a ) is similar to x \ (y [ z ) = (x \ y ) [ (x \ z ).

Unfortunately, Boole would sometimes take the analogy too far. For example,
he tried to nd a set operation analogous to division, even though no su h
operation exists in logi .
Soon to follow Boole's work was that of Charles Ludwig Dodgeson, known
as Lewis Carol, who published several texts on the subje t, and developed Venn
Diagrams as a means of reasoning about sets.
It was also during this period that Ernst S hroeder anti ipated the impor-
tan e of developing fast algorithms to de ide various logi al and mathemati al
problems. In \The Algebra of Logi " he writes:
\Getting a handle on the onsequen es of any premisses, or at least
the fastest method for obtaining these onsequen es, seems to me to
be one of the noblest, if not the ultimate goal of mathemati s and
logi ."
On e symboli logi matured, it be ame tremendously useful in resolving many
serious problems developing in mathemati s.

3
4 The 3rd Age of Logi : Mathemati al Logi
(late 19th to mid 20th Century)
As mathemati al proofs be ame more sophisti ated, paradoxes began to show
up in them just as they did in natural language.
For example, in 1820: Cau hy \proved" that for all innite sequen es
( ) ( ) ( )
f1 x ; f2 x ; f2 x ;

of ontinous fun tions, the sum

( )=
f x
X1 i f (x)
i=1
was also ontinuous. But in 1826 Abel found a ounterexample!
To deal with issues su h as these, in 1879, Frege proposed logi as a lan-
guage for mathemati s. This development was anti ipated enturies earlier by
Leibnitz, but it wasn't until the late 19th Century that the logi al tools existed
to allow for it. The rigor of mathemati al proofs in reased dramati ally. In
the eld of analysis, the now standard epsilon-delta denition of limits resolved
ambiguities su h as the one above.
With the rigor of this new foundation, Cantor was able to analyze the notion
of innity in ways that were previously impossible. He on luded that, instead of
there being just one innity, there was a whole hierar hy of them. His argument
was follows:
Consider the set 2N of all subsets natural numbers. Suppose, for a ontra-
di tion, that there is only one innity. Then this set, whi h is innitely large,
must be of the same size as the natural numbers, whi h is also innitely large.
Therefore, we ould assign ea h subset of N a distin t n 2 N , forming an in-
nite sequen e P0 ; P1 ; P2 ; : : : of subsets of N . Now onsider the set Q of natural
numbers n su h that n 62 Pn . Sin e Q 2 2N , it must have been assigned some
number j . But then onsider the question of whether j 2 Q:
j 2 Q , j 2 P j , j 62 Q
A ontradi tion.
Therefore, our original supposition is in orre t, and 2N is stri tly larger than
N . (Note that this leaves open the question of the existen e of other sets with

sizes falling in between these onstru ted sizes. See below.) We ould further
N
devise an analogous argument that 22 is stri tly larger than 2N , and so on,
forming an innite hierar hy of innities.
So how do we determine the size of innite sets? Cantor dened the relative
size of two sets as follows:
Denition: jAj  jBj i there exists a one-to-one fun tion from A to
B.

4
This leads to a range of all possible sizes known as the ardinal numbers. It
starts with a size for ea h of the natural numbers, and then ontinues with sizes
for innitely large sets. These new sizes are denoted with the symbol  (read
as \aleph"). The rst su h size (0 ) is the size of the natural numbers.
0; 1; :::0 ; 1 ; : : :
Then, at the turn of the 20th Century, David Hilbert, the most prominent
mathemati ian of his time, proposed a grand program to devise a single formal
pro edure that would derive all mathemati al truth:
\On e a logi al formalism is established one an expe t that a sys-
temati , so-to-say omputational, treatment of logi formulas is pos-
sible, whi h would somewhat orrespond to the theory of equations
in algebra."
The rst major stumbling blo k ame when Bertrand Russell dis overed that
naive set theory, again like the natural language logi s, led to paradoxes. Russell
wondered whether the olle tion of all sets is a set. He on luded that this leads
to the so- alled Russell's Paradox: Consider the set
T = fS jS 62 S g
Then T 2 T , T 62 T (a ontradi tion).
Russell worked around this problem by reformulating mathemati s in terms
of a hierar hy of sets. Sets of a given hierar hy ould only ontain sets from
lower hierar hies. His work ulminated in the Prin ipia Mathemati a, a joint
work with Alfred North Whitehead. This work formally proved (i.e., with sheer
symboli manipulation) the bulk of the mathemati al knowledge of its time.
In addition, mathemati ians soon took advantage of the fa t that symboli
logi , being a formal system, ould itself be the obje t of mathemati al investi-
gation. To the limited extent that logi formed a foundation for mathemati s,
the results of this investigation yielded results on the nature of mathemati s
itself.
For example, a natural question that arose from Cantor's proof of higher
innities was: what is the relationship between 20 and 1 ? It was onje tured
that 20 = 1 . This was known as the Continuum Hypothesis (CH). Despite
many attempts to prove and disprove it, nobody su eeded. Later, in the 1930's,
Kurt Godel proved that, within the framework of logi and formal set theory
as the foundation of mathemati s, supposing CH to be true will never lead to a
ontradi tion. Then, in the 1960's, Cohen proved that supposing the negation of
CH wouldn't lead to a ontradi tion either. This established the independen e
of CH from mathemati s as based on set theory.
Although the analysis of logi as a mathemati al obje t proved to be a very
powerful te hnique, it was soon to yield two results that proved devastating to
Hilbert's Program:
1. Godel's First In ompleteness Theorem. Kurt Godel proved that, in a
formal system powerful enough to form statements about what it an

5
 prove, there will always be true statements that the system an express but
an't prove. These statements ould be proven with even more powerful
systems, but these new systems ould then express new statements that
they ouldn't prove, and so on.
2. Godel's Se ond In ompleteness Theorem. Kurt Godel proved that a for-
mal system powerful enough to form statements about arithmeti s annot
prove its own onsisten y.
3. Alonzo Chur h and Alan Turing showed that there are some problems that
no algorithm ould ever solve. If su h problems exist, then there ould be
no hope of nding a single algorithm to produ e all mathemati al truth.
Despite these results, logi ontinued to ourish, not as the universally a epted
ultimate foundation of all mathemati s, but simply as another bran h of it. Also,
various independent formal systems ould still serve as the foundations for the
individual, well-dened, bran hes of mathemati s.

5 The 4th Age of Logi : Logi in Computer S i-

en e
Logi gave us hara terization of omputability or solvability. Before 1920's
people did omputing in their heads, whi h be ame in redibly ompli ated with
time. Today, with the advent of the ele troni omputer, a new home has been
found for logi : omputer s ien e. In omputer s ien e, we design and study
systems through the use of formal languages that an themselves be interpreted
by a formal system. In short, \Des ription is our business". So it is quite
natural that the formal des riptive languages of modern logi ould serve as a
working tool for omputer s ien e. Some of the most basi appli ations of this
tool are:
1. Boolean ir uits: The design of hardware built out of gates that implement
Boolean logi primitives. This forms the foundation of modern digital
design. ENIAC - an early digital omputer implemented in de imal digits.
But it was found that working in boolean logi is mu h easier. Billions
of dollars are spent yearly in this industry. Boole intended to dis overed
the \laws of the mind", but his biggest impa t has been on the omputer
industry. In Ele tri al Engineering boolean logi is hardware onsisting of
gates.
2. Some problems seem to be so hard that omputers annot solve them no
matter how fast they are. The reason for the diÆ ulty is a ombinatorial
explosion that seem to be inherent in this problems. Logi played a ru ial
role in the development of the theory of NP- ompleteness, whi h formalize
the on ept of ombinatorial explosion.

6
 3. A omputer has to be told what to do, in very pre ise and formal way. An
appli ation of this exa t des ription is SQL (Standard Query Language):
a language used for interfa ing with databases. Although the syntax is
dierent, it is essentially equivalent to standard rst-order logi .
4. Semanti s: To make sure that dierent implementation of a programming
language yield the same results, programming languages need to have a
formal semanti s. Logi provides the tool to develop su h a semanti s.
5. Design Validation and veri ation: to verify the orre tness of a design
with a ertainty beyond that of onventional testing. It uses temporal loi .
The famous Intel bug of 1995, involving faulty oating point divisions ost
500 million dollars.
6. AI: me hanized reasoning and expert systems. There are many domains
in whi h expertise, a quired by humans over de ades, an be des ribed
with a formal system. The resulting system an often yield results on
par with the human expert, and sometimes better. It tries to apture
" ommon-sense reasoning" in a formal way.
7. Se urity: With in reasing use of network, se urity has be ome a big issue.
Hen e, the on ept of proof- arrying ode. If an applet ame with it's own
proof of safety and orre tness, then it would be really ni e.
As our understanding of omputer s ien e, and logi , improve, in reasingly
deeper onne tions are made. As a result, logi is sometimes des ribed as the
\ al ulus of omputer s ien e". We will learn propositional and First-Order
Logi , with appli ations in Complexity, Database, and Veri ation.