Symbolic Logic

Michael Genesereth
Computer Science Department
Stanford University

Although it is possible to teach Logic using only English language, this is problematic. Natural language sentences can be complex; they can be ambiguous; and failing to understand the meaning of a sentence can lead to errors in reasoning.

Even very simple sentences can be troublesome. Here we see two grammatically legal sentences. They are the same in all but the last word, but their structure is entirely different. In the first, the main verb is blossoms, while in the second blossoms is a noun and the main verb is sank.

The cherry blossoms in the Spring.
The cherry blossoms in the Spring sank.

As another example of grammatical complexity, consider the following excerpt taken from the University of Michigan lease agreement. The sentence in this case is sufficiently long and the grammatical structure sufficiently complex that people must often read it several times to understand precisely what it says.

The University may terminate this lease when the Lessee, having made application and executed this lease in advance of enrollment, is not eligible to enroll or fails to enroll in the University or leaves the University at any time prior to the expiration of this lease, or for violation of any provisions of this lease, or for violation of any University regulation relative to resident Halls, or for health reasons, by providing the student with written notice of this termination 30 days prior to the effective data of termination, unless life, limb, or property would be jeopardized, the Lessee engages in the sales of purchase of controlled substances in violation of federal, state or local law, or the Lessee is no longer enrolled as a student, or the Lessee engages in the use or possession of firearms, explosives, inflammable liquids, fireworks, or other dangerous weapons within the building, or turns in a false alarm, in which cases a maximum of 24 hours notice would be sufficient.

As an example of ambiguity, suppose I were to write the sentence There's a girl in the room with a telescope. See Figure 6 for two possible meanings of this sentence. Am I saying that there is a girl in a room containing a telescope? Or am I saying that there is a girl in the room and she is holding a telescope?



Figure 6 - There's a girl in the room with a telescope.

Such complexities and ambiguities can sometimes be humorous if they lead to interpretations the author did not intend. See the examples below for some infamous newspaper headlines with multiple interpretations. Using a formal language eliminates such unintentional ambiguities (and, for better or worse, avoids any unintentional humor as well).

Crowds Rushing to See Pope Trample 6 to Death
Journal Star, Peoria, 1980
Scientists Grow Frog Eyes and Ears British Left Waffles On Falkland Islands
The Daily Camera, Boulder, 2000
Food Stamp Recipients Turn to Plastic Indian Ocean Talks
The Miami Herald, 1991 The Plain Dealer, 1977
Fried Chicken Cooked in Microwave Wins Trip
The Oregonian, Portland, 1981

As an illustration of errors that arise in reasoning with sentences in natural language, consider the following examples. In the first, we use the transitivity of the better relation to derive a conclusion about the relative quality of champagne and soda from the relative quality of champagne and beer and the relative quality or beer and soda. So far so good.

Champagne is better than beer.
Beer is better than soda.
Therefore, champagne is better than soda.

Now, consider what happens when we apply the same transitivity rule in the case illustrated below. The form of the argument is the same as before, but the conclusion is somewhat less believable. The problem in this case is that the use of nothing here is syntactically similar to the use of beer in the preceding example, but in English it means something entirely different.

Bad sex is better than nothing.
Nothing is better than good sex.
Therefore, bad sex is better than good sex.

Symbolic Logic eliminates these difficulties through the use of a formal language for encoding information. Given the syntax and semantics of this formal language, we can give a precise definition for the notion of logical conclusion. Moreover, we can establish precise reasoning rules that produce all and only logical conclusions.

In this regard, there is a strong analogy between the methods of Formal Logic and those of high school algebra. To illustrate this analogy, consider the following algebra problem.

Xavier is three times as old as Yolanda. Xavier's age and Yolanda's age add up to twelve. How old are Xavier and Yolanda?

Typically, the first step in solving such a problem is to express the information in the form of equations. If we let x represent the age of Xavier and y represent the age of Yolanda, we can capture the essential information of the problem as shown below.

x - 3y = 0
x + y = 12

Using the methods of algebra, we can then manipulate these expressions to solve the problem. First we subtract the second equation from the first.

x - 3y = 0
x + y = 12
-4y = -12

Next, we divide each side of the resulting equation by -4 to get a value for y. Then substituting back into one of the preceding equations, we get a value for x.

x = 9
y = 3

Now, consider the following logic problem.

If Mary loves Pat, then Mary loves Quincy. If it is Monday and raining, then Mary loves Pat or Quincy. If it is Monday and raining, does Mary love Quincy?

As with the algebra problem, the first step is formalization. Let p represent the possibility that Mary loves Pat; let q represent the possibility that Mary loves Quincy; let m represent the possibility that it is Monday; and let r represent the possibility that it is raining.

With these abbreviations, we can represent the essential information of this problem with the following logical sentences. The first says that p implies q, i.e. if Mary loves Pat, then Mary loves Quincy. The second says that m and r implies p or q, i.e. if it is Monday and raining, then Mary loves Pat or Mary loves Quincy.

pq
mrpq

As with Algebra, Formal Logic defines certain operations that we can use to manipulate expressions. The operation shown below is a variant of what is called Propositional Resolution. The expressions above the line are the premises of the rule, and the expression below is the conclusion.

p1 ∧ ... ∧ pk q1 ∨ ... ∨ ql
r1 ∧ ... ∧ rm s1 ∨ ... ∨ sn
p1 ∧ ... ∧ pkr1 ∧ ... ∧ rm q1 ∨ ... ∨ qls1 ∨ ... ∨ sn

There are two elaborations of this operation. (1) If a proposition on the left hand side of one sentence is the same as a proposition on the right hand side of the other sentence, it is okay to drop the two symbols, with the proviso that only one such pair may be dropped. (2) If a constant is repeated on the same side of a single sentence, all but one of the occurrences can be deleted.

We can use this operation to solve the problem of Mary's love life. Looking at the two premises above, we notice that p occurs on the left-hand side of one sentence and the right-hand side of the other. Consequently, we can cancel the p and thereby derive the conclusion that, if is Monday and raining, then Mary loves Quincy or Mary loves Quincy.

pq
mrpq
mrqq

Dropping the repeated symbol on the right hand side, we arrive at the conclusion that, if it is Monday and raining, then Mary loves Quincy.

mrqq
mrq

This example is interesting in that it showcases our formal language for encoding logical information. As with algebra, we use symbols to represent relevant aspects of the world in question, and we use operators to connect these symbols in order to express information about the things those symbols represent.

The example also introduces one of the most important operations in Formal Logic, viz. Resolution (in this case a restricted form of Resolution). Resolution has the property of being complete for an important class of logic problems, i.e. it is the only operation necessary to solve any problem in the class.