brainwash

Archive for the ‘logic’ Category

good logic vs bad logistics

In lisapicks, logic on 02/01/2007 at 10:09 pm

Deconstructing Mr. Spock: “It’s illogical to call Mr.Spock logical.”

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.

thanks mark 🙂

Advertisements