# Atoms and Connectives Introduction

### Atoms

An English sentence like 'Socrates is a biped' is made up
of a noun phrase, in this case the proper name 'Socrates',
and a verb phrase 'is a biped'. This is the simplest kind
of sentence construction, having no embedded clauses or
other deep constructs. Our notation for such "atomic"
sentences in the language of formal logic takes them to be
formed by applying a predicate (standing for the verb
phrase) to a name (the simplest type of noun phrase). For
the purpose of writing proofs and such in these notes, we
use lower case letters as names and upper case letters as
basic predicate symbols. Conventionally, we write the
predicate symbol before the name. We might use the letter
'*s*' to stand for the name 'Socrates' and
'*B*' for '*is a biped'*, in which case the
formula

*B*(*s*)

would represent the claim that Socrates is a biped. More
accurately, it represents the *form* of that
sentence, but the mnemonic choice of letters may be
helpful in context.

An atomic formula always starts with exactly one predicate
symbol, but it may contain more than one name. An atom
doing duty for the sentence 'Socrates taught Plato', for
instance, might usefully relate the two names using
a *binary* predicate symbol '*T*' to
represent the teaching relation:

*T*(*s,p*)

'Plato taught Aristotle' might then
be *T*(*p,a*) in the same notation. Any
number of names are allowed in an atomic formula, though
each individual predicate symbol applies to a fixed number
of them (one in the case of '*B*' above, and two in
the case of '*T*').

The web-based tool
Logic for Fun
makes heavy use of predicate symbols and the more general
class of function symbols (of which
more later) to represent
problems in logical notation. It allows arbitrary strings
of letters (and some other characters) to be used in place
of single letters as names and predicates, and requires
the names in an atomic formula to be written in a
comma-separated list in parentheses, as above. For
purposes of constructing proofs, however, we generally use
single letters (again as above) so we can omit the
parentheses and commas, writing '*Bs*' and
'*Tsp*' etc in order to simplify the notation.

### Connectives

For the next few sections of these notes, we are going to
concentrate on that branch of logic known as the
*sentential* or *propositional*
calculus. This involves only whole sentences and the
logical relationships between forms of combination of
whole sentences. Thus most of the inner complexity of the
statements in arguments will be ignored since we are
abstracting from it. We shall cease (for a while) to worry
about such locutions as 'all' and 'some' and about such
things as names and predicates. For that reason, we shall
(for now) abbreviate atomic formulae to single "sentence
letters" *p, q, r*, etc. and disregard their
internal structure. Instead we shall consider such
expressions as

It is false that . . .

Either . . . or . . .

If . . . then . . .

where the gaps are to be filled with statements. These are
called *connectives*. A connective is an expression
which applies to one or more sentences to form a longer
sentence in which the originals function as parts. Natural
languages like English abound with connectives, like

The Ancient Greeks knew that . . .

. . . because . . .

. . . although . . .

Probably . . .

Maybe . . .

I find it incredible/disgusting/exciting/etc that . . .

To gain some feel for how connectives work, try filling in the blanks with various typical English sentences like

The square root of 2 is irrational.

Llamas are bigger than frogs.

Some people get pleasure from Logic courses.

Pigs can fly.

giving typical English sentences like "Pigs can fly because the square root of 2 is irrational", etc.

Most connectives are of very little interest to logic, however fascinating they may be to the linguist. We shall concentrate on just five whose logical properties are particularly clear. These, with the notation we shall use for them, are:

Both . . . and . . . | AND |

Either . . . or . . . | OR |

If . . . then . . . | IMP |

It is not the case that . . . | NOT |

. . . if and only if . . . | IFF |

With this notation, starting from sentence letters
*p*, *q*, etc., we can build up sentence
forms of any complexity:

NOT*p* IMP *q*

(*p*
AND *q*) OR (*p* AND *r*)

*p* IMP (*q* IMP (*r*
IMP *s*))

etc.

Notice that we use parentheses in the familiar way to
disambiguate compounds. Just as in arithmetic
(3 × 4) - 1
is different from
3 × (4 - 1)
so in logic we must distinguish between
(*p* AND *q*)
IMP *r* and
*p* AND (*q*
IMP *r*). The
symbol 'NOT' is always read as
applying to the smallest following sentence, so that for
instance
NOT*p* AND *q*
is read as
(NOT*p*) AND *q*
rather than
NOT(*p* AND q*)*.
If we want to express the latter we have to
parenthesise. Sentence forms built up in this way with the
given formal connectives shall be called *formulae*. A
precise definition of 'formula' will be given
later.

Nesting of connectives makes sense in natural languages as well. It makes linguistic sense to form sentences like "√2 is irrational although I find it incredible that the ancient Greeks believed that some people enjoy Logic courses because pigs can fly", even if this particular sentence is unlikely to have been uttered by anyone. Note, though, that sentences like this easily become ambiguous, making you wish that spoken English had some device analogous to the parantheses in logical formulae.

Before developing the formal calculus of logic we should
note a few more important concepts. Firstly, every
occurrence of a connective in a formula has
a *scope*. Its scope is defined to be the shortest
formula or subformula in which that occurrence lies. So
the scope is the connective itself together with the
formulae it connects. For example, consider the formula
NOT(*p* AND *q*) IMP
((*p* OR *r*) IMP NOT*s*).
The scope of the first 'NOT' is
NOT(*p* AND *q*) while
that of the second 'NOT'
is NOT*s*. The scope of the
'AND'
is *p* AND *q* and that
of the second
'IMP' is
(*p* OR *r*) IMP NOT*s*.
In the obvious way we can say that one connective
occurrence is inside the scope of another. To continue the
example, the 'AND' occurs inside
the scope of the first occurrence
of 'IMP' but outside the scope of
the second.

Secondly, the *main connective* of any formula
(other than just a sentence letter of course) is the one
which is not inside the scope of any other. Thus the main
connective of our sample formula is the first
'IMP'. The scope of the main
connective is the whole formula. To take another example,
the main connective of
(*p* AND *q*) AND *r*
is the second 'AND' while the
main connective of
*p* AND (*q* AND *r*)
is the first 'AND'. All the rules
of our formal calculus will operate on main connectives
only, so the concept, though simple, is very
important. For that purpose we need to see the sample
formula
NOT(*p* AND *q*) IMP
((*p* OR *r*) IMP
NOT*s*)
just as something of the form
*A* IMP *B*
abstracting from the internal structure of the *A*
and the *B*, like this:

Finally, one more bit of terminology can conveniently be
introduced at this point. One formula is said to be a
substitution instance of another if and only if every
sentence of the first form is also of the second. Another
way to say the same thing is this: formula *A* is a
substitution instance of formula *B* if and only
if *A* results from *B* by substitution of
formulas for sentence letters. Analogously and
importantly, sequents can be substitution instances of
other sequents. As a special case (logicians are fond of
limiting cases) note that every formula is a substitution
instance of itself. To illustrate,
(*p* AND *q*) OR NOT*r*
is a substitution instance of
*q* OR *p*,
resulting from it by substitution of the formula
*p* AND *q*
for *q* and
NOT*r* for *p*. The
same formula is not a substitution instance of
*q* OR *q* because
substitution must be uniform , the same formula replacing
the same sentence letter throughout. This definition of
'substitution instance' is specific to propositional
logic. When we later come to more intricate parts of the
subject it will have to be made more elaborate.