At the heart of modern logic lies a terse, symbolic language capable of expressing all the truths of mathematics. Aristotle too had a terse, symbolic language, but his formalism was not powerful enough to express basic facts. He considered statements like ``All men are mortal.'', ``No man is rational.'', ``Some dogs are rational.'', and ``Not all men are philosophers.'' As far back as the 12th century Abelard knew this symbolism to be inadequate. (See Kline [6].) The problem is that it is impossible to discuss multi-variable relations with this limited. language. Consider the argument, ``Since all men are animals, a man's head is an animal's head.'' Since it depends on the two variable relation, ``x is the head of y'', it cannot be incorporated into Aristotle's logic. Frege's contribution was to develop a logical system which does use multi-variable relations.
Logical formulas are built-up from symbolic names, logical connectives, and grammar symbols such as parenthesis and commas. They are meant to refer to a non-empty set called the universe and make statements about that universe. Some examples of universes are the integers or the real numbers. The symbolic names are supposed to name individuals, relations, or functions of the universe. They can also be used as variables. In mathematics there is no distinction between those names which can name individuals, those names which can name functions, those names which can name relations, and those names which can be used as variables. The type of the name must be determined from implicit or explicit type declarations. We will follow the same procedure here.
A symbolic name is just a finite string of printable characters. Let us say that a symbolic name is a constant symbol when used to name an individual, a function symbol when used to name a function, and a relation symbol when used to name a relation. Otherwise it is a variable. There is one restriction placed on symbolic names. They must give unique readability. That is to say, the names cannot be chosen in such a way that a name turns out to be the same character string as some other logical entity such as a term or a formula. (The definitions of the words term and formula will be given shortly.)
Usually, we have in mind some specific set of names to represent the
elements of some situation. For instance,
in discussing arithmetic, we
might use the constant symbols 0, 1, 2, 3, ..., 1345, ...and the
2-place function symbols, + and 
and the 2-place relation
symbols, = and <. All other symbolic names would be considered variables. Let
us use the term language to mean just such a
specification. That is, a language is a set of symbolic names
together with a specification of how they are to be used. We always assume
that there are infinitely many symbolic names not specified by the language
to be used as variables. In computer science terms, a language is given by
a set of declarations specifying how the names are to be used. The language
just given for arithmetic is widely known as
the language of arithmetic.
Terms and atomic formulas are built-up using the rules:
are terms and f is an n-place function symbol, then
is a term. That is if you have n character strings
representing terms, you can string them together separated by commas, put
parenthesis at each end, and an n-place function symbol at the beginning
and you have another term.
are terms and r is an n-place relation
symbol, then 
is an atomic formula. As a special case,
we allow 0-place relation symbols. If p is such a symbol, then it by
itself is an atomic formula. We call these special formulas,
propositional letters.
Applying this definition to the language of arithmetic, we see that for
that language, x, 1, +(x, 1), and 
are terms while
and 
are formulas.
This is already at odds with ordinary mathematical notation. We always
write x+y, never +(x, y). In our logical system, the former will have
to be considered as an abbreviation of the latter. An
abbreviation is when
we shortcut some of the formal grammar rules in order to produce something
more legible to the humans. The result is not an actual formula; it only
represents a formula in a more user friendly way. Other well known
abbreviations include x = y and x < y. Thus we will use 
as if it were a formula, but it really is just an abbreviation for
the actual formula, . In many computer languages
there is a similar expansion handled by a preprocessor.
The intent of these definitions should be clear. A term without variables
is an expression denoting a member of the universe and an atomic formula
without variables states a basic proposition which may be either true or
false. Examples: 
or 
. (These
atomic formulas use abbreviations which are to be expanded according to
well-known conventions.) The first is true when the universe is taken to be
the integers and the symbolic names are given their usual meanings while
the second is true of the real numbers, again under the default usage for
the symbolic names.
Atomic formulas without variables are called atomic sentences. A sentence expresses a proposition while a formula with variables is a sentence form which only becomes meaningful when names are substituted for the variables.
Consider the important fact about real numbers that if the product of two numbers is zero, then one of the two must also be zero. How can we translate such a statement into a logical formula? If we use variables x and y for the two numbers, we see at once that this proposition states that something is true for every possible value of x and y. Since we are taking the universe to be the real numbers, this means for every pair of real numbers. We also must have a way of stating implications, ``If this, then that.'', and disjunctions, ``Either this or that.''
The way that these compound propositions are translated into logic is
through logical connectives. If x is a variable and A is a formula,
then we stick 
onto the front of A and interpret this as
meaning that A is true no matter what element of the universe is
referred to by x. Similarly the symbol 
is used to
construct if-then statements. 
means ``If A then B.''
While 
means either A or B or both. With these symbols,
our proposition about real numbers becomes,
The other logical connectives that have proved useful are 
which when
put at the front of a formula means that it is not true, 
which
when placed between two formulas means that they are both true, and
which is similar to 
but means that there is at
least one element of the universe making the succeeding formula true.
Thus the logical connectives are the symbols, 
meaning not, or, and, implies, there is,
for all respectively. They are used to build-up formulas from the base of
atomic formulas using the following rules:
.
.
.
.
is a
formula.
is a
formula.
Note that our definition of formula requires many of parenthesis.
We shall
leave many of them out using the convention
that binds tighter
than 
or which in turn are tighter than .
This means that 
is an abbreviation
for 
.
The intuitive meaning of these formulas should be clear. e.g. 
is a sentence which is true if the universe is
the real numbers, but false of the integers.
Atomic formulas with variables cannot have a truth value until the value
of the variable is filled in. For example, it does not make sense to ask
whether or not 
until we know the value of x. On the
other hand variables within the scope of a quantifier cannot take values.
For instance, 
is true of the integers,
and it is not admissible
to substitute values in for x. Variables amenable to substitution are
called free variables and variables within the scope of quantifier
using them are called bound variables. Consider the formula,
. In this formula, x is both free
and bound. Because of this possibility, it makes better sense to talk of
free and bound occurrences
of a variable. We use the word
sentence to mean a formula with no free variables.
Let us say that an interpretation for a language is a non-empty set called the universe together with constants, relations, and functions of that universe corresponding to the names specified in the language. An interpretation may also assign values to a finite set of variables. Once an interpretation has been given, sentences of the language become either True or False. A model for a set of sentences of a language is an interpretation for the language which makes each sentence in the set True. A sentence is a logical consequence of a set of axioms if it is True in every model for the axioms.
Consider the formula . As we pointed out above,
this formula is neither True nor False unless the
variable x has been given a value. That is why we allow
interpretations to assign values to some variables. Filling in
a value for x means extending the interpretation to include
a value for x. The sentence 
however is meant to be True under all usual interpretations
even those which assign value 23 to x. This requires us to
make some rather tricky conventions. The value given a variable
is meant to affect only the free occurrences of the variable.
The use of a quantifier in front of a formula makes the
variable local to that formula. The outside world is barred
from access to it. Then is True because no matter what usual interpretation
we are given, we can choose a variable not used in the interpretation,
call it new_constant, and give it a value so that
the formula 
is True. (In this case of course, new_constant is
given the value 2.) In other words, saying that an existential formula
is True really just indicates a potential to make a
modified version of it
True. The sentence 
is True
because no matter how we fill in a value for new_constant, the
formula 
is
True.
