Click here to learn more about author Adam Pease.

In Part 1 I discussed the difference between procedural and declarative languages, and mentioned the confusion that can come from thinking that Turing equivalence applies to declarative languages. Now I’ll discuss some different logical languages. This is just an informal introduction. For the formal logician who is interested in a rigorous treatment, one could start with Herbert Enterton’s “A Mathematical Introduction to Logic.” There are also many different logical languages with many different properties. Logicians invent new logics almost every day. I’ll just look at some popular choices and how they compare.

Most logic textbooks start with “propositional logic.” The fundamental unit of such as a logic is a statement or proposition. For example:

The moon is made of green cheese. Paris is the capital of France.

We can join propositions together with simple logical operators, as in:

If Paris is the capital of France then the moon is made of green cheese. Paris is the capital of France and it is not true that the moon is made of green cheese.

Propositions are indivisible units. In mathematical notation for propositional logic we can simply abbreviate any proposition with a unique name. So we can have:

“The moon is made of green cheese.” = A
“Paris is the capital of France.” = B

B implies A
B and not(A)

In this language we can’t have variables. This is very limiting and prevents us from saying many simple things about the world. But it does make computation in the language very fast and very simple. We should emphasize that a predicate logic by definition doesn’t have variables. There is no way around this restriction in the language. If you add variables to the language you no longer have a propositional logic but rather a different sort of logic – such as a predicate logic. The different language has different formal properties and a different procedure, in this case one that handles variables and quantification, is needed to answer questions about statements in the logic.

Most logic textbooks start with a classic example of predicate logic:

Socrates is a man. All men are mortal.

and then the deduction that is possible in response to the query “Who is mortal.” is to answer “Socrates.” These simple deductions are possible using natural language but it took logicians around the 1900’s to create a consistent mathematical notation and inference rules that allowed more rigorous progress to be made. That work also enabled the creation of automated theorem provers, which can mechanically apply rules to perform deductions that are valid, and answer queries against bodies of formalized knowledge.

We can express the statements above in now standard mathematical notion

man (socrates )

∀X : man(X) ⇒ mortal (X)

A simple query solver would try to find solutions by searching all the statements until it finds a match or a true statement that entails a match. So if we query mortal(X) our prover would search, trying to unify variables as it goes along. Let’s do a very informal proof –

1. mortal(X) ⇒ Query

2. man (socrates) ⇒ A fact we know

3. ∀X : man(X)
mortal(X) ⇒ Another fact we know, and this rule right hand side matches our query, now look for a match for the left hand side of the rule

4. man(socrates) ⇒ Use lines 2 and 3 – found a match for the left hand side with X = socrates

5. man(socrates) 
    mortal(socrates) ⇒ After we substitute variables using lines 3 and 4

6. mortal(socrates) ⇒ Combine lines 2 and 5. Since we know the premise of the rule we can conclude the consequent to reach the conclusion

So we’ve now seen how different logics allow us to express different things.

Without variables, there’s simply no way in propositional logic to say very common things, such as what we can express in predicate logic. This is also true for other logics – each logic has different properties that governs what it can express, and therefore how its proof procedure operates. If we add different properties to a logic, it becomes a different logical language.

Knowing what you need to express and what you need to compute automatically in a logical language is essential for choosing a particular logical language.