THE LOGIC NOTES

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 enjoy Logic courses.
Pigs can fly.

giving standard English compound 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:

NOTp 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 NOTp AND q is read as (NOTp) 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 NOTs). The scope of the first 'NOT' is NOT(p AND q) while that of the second 'NOT' is NOTs. The scope of the 'AND' is p AND q and that of the second 'IMP' is (p OR r) IMP NOTs. 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 NOTs)  just as something of the form A IMP B abstracting from the internal structure of the A and the B, like this:

NOT(p AND q) IMP (p OR r) IMP NOTs) A IMP B

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 NOTr is a substitution instance of q OR p, resulting from it by substitution of the formula p AND q for q and NOTr 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.