This is another great basics topic, and it’s also one of my pet peeves. In general, I’m a big

science fiction fan, and I grew up in a house where every saturday at 6pm, we all gathered in front

of the TV to watch Star Trek. But one thing which Star Trek contributed to our vocabulary, for which

I will never forgive Gene Rodenberry, is “Logic”. As in, Mr. Spock saying “But that would not be

logical.”.

The reason that this bugs me so much is because it’s taught a huge number of people that

“logical” means the same thing as “reasonable”. Almost *every* time I hear anyone say

that something is logical, they *don’t* mean that it’s logical – in fact, they mean something

almost exactly opposite – that it seems correct based on intuition and common sense.

If you’re being strict about the definition, then saying that something is logical by itself is an almost meaningless statement. Because what it means for some statement to be “logical” is really

that that statement is inferable from a set of axioms in some formal reasoning system. If you don’t know *what* formal system, and you don’t know *what* axioms, then the statement that something is logical is absolutely meaningless. And even if you *do* know what system and

what axioms you’re talking about, the things that people often call “logical” are *not* things that are actually inferable from the axioms.

Logic, in the sense that we generally talk about it, isn’t really *one thing*. Logic is a

name for the general family of formal proof systems with inference rules. There are *many*

logics, and a statement that is a valid inference (is logical) in one system may not be valid in

another. To give you a very simple example, most people are familiar with the fact that in logic, if

you have a statement “A”, then either the statement “A or not A” must be true. In the most common

simple logic, called *propositional* logic, that’s a tautology – that is, a statement which is

always true *by definition*. But in another common and useful logic – intuitionistic logic – “A or not A” is *not* necessarily true. You cannot infer *anything* about whether it’s true or false without proving whether A is true or false.

To give another example: the most common logic that we use in arguments is called first order predicate logic (FOPL). FOPL is a very useful logic for things like geometric proofs. But it’s

absolutely awful at talking about *time*. In FOPL, there’s no good way to say something

like “I won’t be hungry until 6pm tonight.” that really captures the temporal meaning of that statement. But there *are* several kinds of logic that are very good at that kind of statement – but they’re not particularly useful for the kinds of things that FOPL is good at.

So what is a logic? A typical formulation would be that a logic is a formal symbolic

system which consists of:

- A way of writing a set of statements (the
*syntax*of the logic); and - A system of rules for performing mechanical
*inferences*over those statements.

The easiest way to get a sense of this is to look at one familiar logic: the first order predicate logic (FOPL). The first order predicate logic is the most common logic that we really use; it’s the one that we’re generally using implicitly when we write things like proofs in geometry.

Logicians tend to use a very strange method of describing the syntax of logical statements. I’m going to ignore that, and just walk through the syntax informally. FOPL has five kinds of basic things that are put together to form statements. As I go through the syntax, I’ll give some examples based on reasoning about my family.

- A
*constant*is a particular object, number, or value which can be reasoned

about using the logic. In reasoning about my family, the constants will be the names

of members of my family, the places we live, and so on. I’ll write constants as either

numbers, or quoted words. - A
*variable*is a symbol which represents a value. Variables can be used in

the logic to reason about things like universal properties – if every object has

a property (like, for example, every person has a father), there’s a way of using

a variable to say that in the logic. - A
*predicate*is something which allows you to make statements about

objects and variables. A predicate is written as an uppercase identifier,

with the objects it’s talking about following inside parens. For example, I

can say that my father is Irving using a predicate named “Father”:`Father("Irving", "Mark")`

. - Quantifiers are things that introduce new variables. For a statement to be valid

every variable in that statement must have been introduced by a quantifier. There

are two quantifiers in FOPL: ∀ (for all, the*universal quantifier*, which is

used to make statements about all possible constants); and ∃ (there exists, the*existential quantifier*, which is used to make statements that there is some constant

for which a statement is true). - An operator is something that modifies or connects sentence(s). There are five

operators in FOPL. Four of them connect pairs of statements: (A ∧ B (and), A ∨ B (or), A ⇒ B (implies), A ⇔ B (if and only of). The fifth one negates a statement: ¬ A.

The meanings of the statements are:

- Predicate Statement
- A predicate with its parameters filled in with either constants or variables.
- And statement
- Two sentences joined by ∧.
`A ∧ B`

is true if/f both A and B are true. - Or statement
- Two sentences joined by ∨.
`A ∨ B`

is true if/f either A or B is true. - Implication statement
- Two sentences joined by ⇒.
`A ⇒ B`

is true if/f when A is true, B is also true, and when B is false, A is also false. - If/f statement
- Two sentences joined by ⇔.
`A ⇔ B`

is true if/f`(A ⇒ B) ∧ B ⇒ A)`

is true. - Universal Statement
- A sentence preceeded by the universal quantifier and a variable:
`∀x:A(x)`

. A

universal statement is true if*any*constant substituted for the variable will result

in a true statement. - Existential Statement
- A sentence preceeded by the existential quantifier and a variable:
`∃x:A(x)`

. An

existential statement is true if there is at least one constant that can be substituted for the variable that will result in a true statement - Parenthesized Statement
- Any statement surrounded by parens. The only meaning of parens is grouping.

The *meanings* of the different statements can be briefly described as follows:

- Each
*constant*represents some specific entity or object which

the logic is going to be reasoned about. So, for example, if I wanted

to do reasoning about my family, the atoms would be me, my wife, my

children, etc. - A
*predicate*statement expresses a property of the atoms

that are its parameters. Continuing with the example of my family, I

could write statements like`Father("Mark","Aaron")`

,`Father("Mark","Rebecca")`

,`Spouse("Mark","Jennifer")`

. - ∧ statements combine two statements; they’re true when both of the

member statements are true.`Spouse("Mark","Jennifer") ∧ Father("Mark","Aaron") ∧ Mother("Jennifer","Aaron")`

. - The ∨ connector works in basically the same way as ∧, except that it’s

true when*either*of its component statements are true.`Father("Mark","Aaron") ∨ Father("Jennifer","Aaron")`

- ¬ is logical negation: ¬X is true when X is false.
`¬Father("Jennifer","Aaron")`

. - ⇒ is an implication statement:
`A ⇒ B`

means that if A is true, then B must be true; if B is false, then A must also be false. (Note the reversal there – if A is false, it says nothing about whether or not B is true, and if B is true, it says nothing about whether or not A is true.) For example,`Spouse("Mark","Jennifer") ⇒ Spouse("Jennifer","Mark")`

(If Mark is Jennifer’s spouse, then Jennifer is Mark’s spouse.) - ∀ and ∃ statements are where it gets interesting. ∀ is read “For all”, and ∃ is read “there exists”. For example,
`∀c : (∃p : Father(p,c))`

(For every person, there is a person who

is their father.);`∃f: Father("Mark",f)`

(There is someone whose father is Mark.)

What I’ve gone through so far is not yet a logic. It’s just a language for writing

statements. What makes it into a logic is the addition of *inference rules*, which

give you a way of *using* statements that are known to be true, and using them to

infer other true statements. I’m not going to go through the entire set of inference

rules allowed in FOPL in detail, but I’ll give you a couple of examples, followed by the full list of rules.

- If we know that
`P(x) ∧ Q(x)`

is true, then we can infer that`P(x)`

must be

true. - If we know that
`P(x) ⇒ Q(x)`

is true, and we also know`P(x)`

is true, then we can infer that`Q(x)`

is also true. - If we know that
`∀x: P(x)`

is true, and`"a"`

is a constant, then we can infer that`P("a")`

is true. - If
`x`

is a constant, and we know that`P("a")`

is true, then

we can infer that`&exists;x:P(x)`

is true.

The rules are divided into two groups. One is a set of equivalences – if you know something on one side of the ≡ sign, then you can infer whatever is on the other side. The second set of rules is implications: if know you know the left side, then you can infer the right.

The

equivalence rules are:

- ¬∀x:P(x) ≡ ∃x:¬P(x)
- ¬∃x:P(x) ≡ ∀x:¬P(x)
- ∀x:(∀y: P(x,y)) ≡ ∀y:(∀x:P(x,y))
- ∃x:(∃y: P(x,y)) ≡ ∃y:(∃x:P(x,y))
- ∀x:P(x) ∧ ∀x:Q(x) ≡ ∀x:P(x)∧Q(x)
- ∃x:P(x) ∨ ∃x:Q(x) ≡ ∃x:P(x)∨Q(x)

And the implication rules are:

- ∃x : ∀y: P(x,y) → ∀y : ∃x: P(x,y)
- ∀x: P(x) ∨ ∀x: Q(x) → ∀x: P(x) ∨ Q(x)
- ∃x:(P(x) ∧ Q(x)) → ∃x:P(x) ∧ ∃x:Q(x)
- ∃x:P(x) ∧ ∀x:Q(x) → ∃x:(P(x) ∧ Q(x))
- ∀x:P(x) → P(c)
*(where c is a constant)* - P(c) → ∃x:P(x)
*(where c is a constant, and x is not an unquantified*

variable in P(c))

To reason with a logic, you start with a set of *axioms* – that is, a set of statements that you *know* are true even though you don’t have a proof. Given those axioms, we say that a statement can be *proven* if there is

some way of applying the inference rules to generate the statement.

So, once again with an example from my family. Here’s a set of axioms about

my family.

1: Father("Mark","Rebecca") 2: Mother("Jennifer","Rebecca") 3: Father("Irving","Mark") 4: Mother("Gail","Mark") 5: Father("Robert", "Irving") 6: Mother("Anna", "Irving") 7: ∀a, ∀b:(Father(a,b) ∨ Mother(a,b)) ⇒ Parent(a,b) 8: ∀g,∀c : (∃p : Parent(g,p) ∧ Parent(p,c)) ⇒ Grandparent(g, c)

Now, suppose we want to prove that Irving is Rebecca’s grandparent.

- Since we know by statement 1 that
`Father("Mark","Rebecca")`

, we can infer`Parent("Mark","Rebecca")`

. We’ll call this inference I1. - Since we know by statement 3 that
`Father("Irving","Mark")`

, we can infer

`Parent("Irving","Mark")`

. We’ll call this inference I2. - Since we know by I1 and I2 that
`Parent(Irving,Mark)`

and`Parent(Mark,Rebecca)`

, we can infer`Parent(Irving,Mark)∧Parent(Mark,Rebecca)`

. We’ll call this inference I3. - Since by I3, we know
`Parent(Irving,Mark)∧Parent(Mark,Rebecca)`

, using

statement 8, we can infer`Grandparent(Irving,Rebecca)`

That chain of inferences is a proof in the first order predicate logic. A very important thing to notice is that the proof is *entirely* symbolic: we don’t need to know what the atoms represent, or what the predicates mean! The inference process

in logic is purely symbolic, and can be done with absolutely *no clue at all* about what the statements that you’re proving mean. It’s all a mechanical process

of working from the premises using the inference rules. Given the right set of premises,

you can prove almost *any* statement; given a choice of both logics and premises, you can prove *absolutely* any statement.

So when someone says, a la Mr. Spock, that something is logical, the correct thing to do is to whack them in the head with a logic textbook for saying something nonsensical.