First Order Logic

Logic provides a traditional metalanguage for interpreting expressions from ordinary language. Logicians and mathematicians have formulated artificial languages to help in deduction and inference. Tarski originated one such system late in the nineteenth century in hopes of ridding mathematics of logical inconsistencies. Subsequently, there have been various attempts to extend these formalized systems to natural language, in part to detect logical inconsistencies in natural language, and in part to test the adequacy of the formalized languages.

Formal languages have two components: 1) the language itself (its elements and the means of combining the elements), and 2) a way to interpret the language (i.e., an assignment of truth conditions to propositions). The second component provides a means of relating the logical formuli to objects and situations in the real world. This is what logicians call “giving the semantics for the system.”

The main goal is to provide a metalanguage that provides an explicit representation of the meaning of the ordinary language expressions. Kearns provides an introduction to two elementary types of logic—propositional logic and predicate logic. Propositional logic provides an explicit translation for the connectives used to combine sentences into more complex expressions. It’s goal is to derive the meaning of a combination of sentences from the truth values of the individual sentences and the meaning of the connectives. Predicate logic analyzes the meaning of parts of a sentence to derive the meaning of the sentence. The goal in this chapter is to present some elements of a formal compositional theory of meaning. Linguists should also note the ways in which the interpretation of the formal language differs from the interpretation of ordinary language.

2.2.1 Conjunction

We begin by looking at the logical translation of the word and. In propositional logic the conjunction is only used to conjoin two propositions. Given any two propositions, say p and q, the syntax allows us to produce the complex proposition p&q. Logicians use the term well-formed formuli (wff) as another name for sentences or propositions. A formal way of characterizing a propositional logic with conjunction would be:

      1. Each sentence is a wff.

      2. If p is a wff and q is a wff, then (p&q) is a wff.

Conjunction provides an element of recursion to the language. We can continue to use conjunction as often as we like to produce more complex sentences:

      p

      (p&q)

      (o&(p&q))

      (n&(o&(p&q)))

Logicians use a truth table to provide an interpretation for the sentences constructed by this grammar. Kearns (27) gives the following truth table for conjunction:

In the propositional logic we are dealing with, every sentence has an interpretation of either true (T) or false (F). This table shows how to derive an ‘interpretation’ for every combination of meanings for the individual sentences p and q. We can arbitrarily make the following assignments:

      n—>F

      o—>T

      p—>T

      q—>T

The truth table for conjunction then tells us that our complex expression (n&(o&(p&q))) has the interpretation F. You should check this interpretation for yourself! You should also be able to prove that p&q is logically equivalent to q&p by using the truth table.

So far all we have done is to construct a logic that tells how to interpret complex expressions formed with conjunction. If we want to do something useful with this system we should try translating ordinary English sentences into propositional logic and see if its predictions correspond to our intuitions. Let’s try using one of Kearns’ sentences:

      6a. Moira left and Harry stayed behind.

This sentence is a conjunction of two smaller sentences:

      Moira left.

      Harry stayed behind.

Let’s assume that Moira did in fact leave while Harry did not stay behind. If we let p stand for the sentence Moira left and q stand for the sentence Harry stayed behind then we have the following truth assignments:

      p—>T

      q—>F

The truth table for conjunction predicts that the truth of the complex sentence (6a) will be false. Does your intuition agree with this prediction?

Ordinary English uses and to do more than connect two sentences. It is used to conjoin NPs, VPs and PPs among other constituents:

      NPs     Moira and Harry left.

      VPs     Paul sang and danced.

      PPs      Jane runs on the road and in the rain.

Kearns suggests that our propositional logic can be used to analyze these sentences by adding the process of conjunction reduction. For example, the sentence Paul sang and danced abbreviates the expression Paul sang and Paul danced, which we can translate into our propositional logic.

What happens when we compare the logical translation for this sentence with our intuition? According to the logic we have constructed, the sentence Paul sang and danced is true if Paul sang on Tuesday and danced on Wednesday, but this interpretation doesn’t correspond to my intuition about the meaning of the sentence. Ordinary English insists on a close association between the time of the events in a conjoined phrase. Our logic does not include a way to deal with temporal associations in conjoined sentences.

Other sentences create different problems. Consider the sentence:

      Charlie opened the can and it exploded.

Our intuition suggests a causal connection between opening the can and its explosion. Our world knowledge suggests a sequence of events. Propositional logic predicts that these sentences can be conjoined in either order, but English insists on an iconic relation between the order of events and their conjunction. Clearly, propositional logic only translates part of the meaning of the word and.

Kearns notes that conjunction reduction does not apply to group predicates:

      Paul and Mary had a baby.

The reduction fails because English uses and to express the members of a group as well as to conjoin clauses.

Relevance also governs the conjunction of sentences in ordinary English:

      Birds fly and Dillons sells skim milk.

Following the Principle of Relevance, we attempt to construct some explanation why a speaker would conjoin two unrelated events. Propositional logic is unconcerned about issues of relevance.

Kearns discusses this problem under the heading of truth functionality. She compares the conjunction and with the conjunction because and claims that because is not truth functional because the truth of the conjoined sentence depends on the content (i.e. intension) of its parts rather than just the truth values of its constituent sentences.

2.2.2 Negation

Negation (‘~’) is another logical operator. The syntactic rule for negation is:

      If p is a wff, then ~p is a wff.

The interpretation for negation in propositional logic is supplied by the following table:

Propositional negation is commonly translated into ordinary English by the circumlocution it is not the case that. Given the proposition Martha sang, its negation would be It is not the case that Martha sang.

Negation works in mysterious ways in ordinary language. The following sentences are equivalent even though only one of them is overtly marked for negation:

      Sally stayed at the party.

      Sally would not leave the party.

The Principle of Informativeness should rule out the use of negation and force us to accentuate the positive in our conversations. A negative statement is usually much less informative than a positive statement.

A little thought shows that propositional negation does not provide an adequate translation for all the forms of negation we find in English. Compare the following sentences:

      Bob is not happy.

      Bob is unhappy.

Happy and sad are equipollent antonyms; they code distinct properties. If Bob is not happy he is not necessarily sad. On the other hand unhappy is synonymous with sad. If Bob is unhappy, he must be sad. On the other hand, a number that is not rational is irrational. There is also a contrast between being amoral and immoral, or between being inhuman, unhuman and nonhuman. We must be careful to distinguish between propositional and affixal negation.

Propositional negation in English licenses the use of either, positive tags and the not even continuation (Frawley 1992:393):

Either/too

      Marsha didn’t eat the cake and I didn’t either/??too.

      Marsha ate the cake and I did too/??either.

Tag questions

      Marsha didn’t eat the cake, did she/??didn’t she?     Positive Tag

      Marsha ate the cake, didn’t she/??did she?                Negative Tag

Not even

      Marsha didn’t eat the cake, not even a crumb.

      ??Marsha ate the cake, not even a crumb.

We can use these constructions to test whether other English structures represent instances of propositional negation. Negative adverbs, like never, produce similar results:

      Henry never saw the falcon, and I never saw one either/??too.

      Henry never saw the falcon, did he/??didn’t he?

      Henry never saw the falcon, not even the one on the post.

Negative indefinites trigger the same results:

      Nobody saw the falcon, and nobody saw the egret either/??too.

      Nobody saw the falcon, did they/??didn’t they?

      Nobody saw the falcon, not even the one on the post.

Examples with lexical negation do not trigger the full range of propositional negation diagnostics. For example, deny means roughly ‘to assert that a state of affairs is not true.’ Its meaning appears to contain a form of negation, and yet it does not pass our tests:

      Ginny denied all responsibility, and I did, too/??either.

      Ginny denied all responsibility, didn’t she/??did she?

      ??Ginny denied all responsibility, not even a little bit.

The adverb seldom has the meaning ‘not often’, but produces mixed results:

      Rich seldom watched tv, and I seldom did, too/??either.

      Rich seldom watched tv, did he/didn’t he?

      Rich seldom watched tv, not even in the summer.

The quantifier few has the meaning ‘not many’, and also produces mixed results:

      Few girls came to the party, and few boys had a good time, too/either.

      Few girls came to the party, did they/didn’t they.

      ??Few girls came to the party, not even after ten.

These diagnostics indicate that not all negative forms in English have equal force. Some, like not, work along the lines of logical negation, while others negate by degree. McCawley (1988:588) stated that

We should also mention the use of negation in discourse, for example:

      Mother: Eat your peas!

      Child: No, I want a cookie.

In discourse, no is used to reject a previous assertion or command rather than negate a proposition. The child is not claiming that they do not want a cookie, they are saying they do not want to eat the peas. What happens when you apply the negation diagnostics to this example of discourse negation?

2.2.3 Disjunction

The logical connective is best translated by the English expression and/or even though most logicians commonly translate it as simply or. Kearns uses the lowercase letter v as a symbol for disjunction. The syntactic rule for disjunction is:

      If p is a wff and q is a wff, then (pvq) is a wff.

The interpretation for logical disjunction is supplied by the following table.

The table above provides truth values for what is more properly known as inclusive disjunction. Inclusive disjunction is true if either or both of the propositions are true. The ordinary English connective or seems to vary in meaning between inclusive and exclusive disjunction. In exclusive disjunction, the expression is true if either, but not both of the combined propositions are true. It is easy to supply a truth table for exclusive disjunction:

Kearns suggests an alternative to representing exclusive disjunction by adding the qualifying statement but not both to the expression for inclusive disjunction:

      (pvq)&~(p&q)

You should check to see if this complex expression is logically equivalent to exclusive disjunction defined by the table above.

We need to be careful when translating ordinary English sentences with or into propositional logic. Would you use inclusive or exclusive disjunction to translate the following sentences?

      Give me liberty or give me death.

      This eraser works with pens or pencils.

      Neither rain or snow will stay these workers from making their rounds.

      Trick or treat!

      You can have limon or lime.

We invite all passengers who need some extra time, or who are traveling with small children, to board the aircraft.

      Nick or Nina will pick you up.

All of these sentences use some form of disjunction reduction from their equivalents in propositional logic. They also illustrate the ambiguity found in ordinary English that makes logicians see red. The exercise of translating English sentences into logic forces us to examine the meaning and use of English words more critically.

In some cases, or is best translated into logic as a conjunction rather than a disjunction:

      A doctor or dentist can write prescriptions.

This statement corresponds to the expanded sentence:

      A doctor can write prescriptions and a dentist can write prescriptions.

There are no cases when a doctor can write prescriptions and a dentist cannot which would be predicted by the use of disjunction.

2.2.4 Material Implication

The logicians favorite connective is the material implication. It translates roughly as if or if ... then. Kearns uses an arrow ‘—>’ as the symbol for material implication. The syntactic rule for material implication is:

      If p is a wff and q is a wff, then (p—>q) is a wff.

The p in this expression is traditionally known as the antecedent, while the q is known as the consequent. The antecedent is usually marked by if. The antecedent states a condition, and such sentences are called conditional sentences. The antecedent can come either before or after the consequent in ordinary English:

      If Martha calls, I will go.

      I will go if Martha calls.

The interpretation for material implication is supplied by the following table.

The table shows that the material implication is only false when the antecedent is true and the consequent is false. The material implication, like conjunction, is strictly truth functional. The terms antecedent and consequent imply causation, but causation does not have a role in logic. You can verify which of the following sentences are true by material implication:

      If snow is white, then hamsters are mammals.

      If the moon orbits the earth, then everyone has a birthday.

      If you are in a semantics class, then k is a vowel.

      If Picasso was an artist, then trains run on time.

      If Tolkien wrote Ulysses, then hamsters walk on stilts.

      If the sun orbits the earth, then 4 is the product of 2 and 3.

Once again you should compare this logic table with your own intuitions.

      If Martha calls, I will go.

      Suppose Martha calls and I go.                We get T for the material implication.

      Suppose Martha calls and I do not go.     We get F for the material implication.

This much seems obvious. The cases where the antecedent is false are less clear.

      Suppose Martha doesn’t call and I go.                 We get T for the material implication.

      Suppose Martha doesn’t call and I do not go.      We get T for the material implication.

The material implication implies that a false antecedent has no effect on the consequent. I can go or not go without Martha’s personal invitation. We usually understand the sentence to mean something stronger—If Martha calls I will go, but not otherwise. We are in the habit of adding a causal interpretation to conditional sentences in English. Material implication asserts a much weaker association rather than a causal connection. This weaker association is more apparent if we try translating a causal statement with the material implication:

      If you water these plants once a week, they will grow quickly.

We interpret this sentence as asserting that watering the plants once a week will cause them to grow quickly. The material implication is false if the plants do not respond quickly to weekly watering. The third line of the truth table suggests that the plants may grow quickly even if you do not water them weekly. We could avoid this difficulty if it were possible to leave the last two lines of the truth table undefined. Unfortunately, logic insists on evaluating expressions as true or false. Other options lead to logical contradictions. In the absence of this option, the best compromise is to interpret a conditional as verified as long as it is not falsified. The only time the conditional is falsified is when its antecedent is true and its consequent is false. In the case of my plants, it is always possible that something else will enable them to grow despite an absence of weekly watering.

McCawley (1981:49) discusses paraphrasing ‘If A, then B’ as ‘A only if B’. Quine (1962:41) suggested that ‘But whereas “if” is thus ordinarily a sign of the antecedent, the attachment of “only” reverses it; “only if” is a sign of the consequent’. This claim implies the following sentences are equivalent:

      If all men are mortal, then Aristotle is mortal.

      All men are mortal only if Aristotle is mortal.

McCawley finds many sentences that do not display this equivalence:

      If you’re boiled in oil, you’ll die.

      You’ll be boiled in oil only if you die.

      If Mike straightens his tie once more, I’ll kill him.

      Mike will straighten his tie once more only if I kill him.

      If there are weapons of mass destruction, then we invade Iraq.

      There are weapons of mass destruction only if we invade Iraq.

The only if sentences seem to reverse the causal or temporal relations expressed in the if sentences. For example, the conditional sentence about boiling in oil asserts that death takes place after boiling, while the only if version suggests that boiling will follow your death. The following sentences reverse this effect. It is the simple sentences that have the bizarre readings.

      My pulse goes above 100 only if I do have exercise.

      If my pulse goes above 100, I do heavy exercise.

      You’re in danger only if the police start tapping your phone.

      If you’re in danger, the police (will) start tapping your phone.

While ‘If A, then B’ is a poor substitute for ‘A only if B’, ‘If not B, then not A’ is a much better paraphrase:

      If I don’t do heavy exercise, my pulse doesn’t go above 100.

      If the police don’t start tapping your phone, you’re not in danger.

This result is surprising since the logical translation for conditionals (p—>q) is logically equivalent to that for ‘If not B, then not A’ (~q—>~p). Either the logical system should be revised so these propositions are not equivalent or ordinary if should not be identified with material implication.

McCawley favors Geis’ (1973) suggestion that material implication be translated into English by the phrase in (all) cases in which:

      If Bill comes tomorrow, I’ll give him the books.

 =   In all cases in which Bill comes tomorrow, I’ll give him the books.

      I’ll give Bill the books only if he comes tomorrow.

 =   I’ll give Bill the books only in cases in which he comes tomorrow.

 =   I won’t give Bill the books in cases other than those in which he comes tomorrow.

This phrasing highlights the implication that the consequent is only true in those cases or states of affairs that are relevant in the appropriate way. This makes the notion of ‘case’ heavily context-dependent. Material implication can then be analyzed as involving a degenerate notion of ‘case’—one in which the only ‘case’ considered is the actual state of affairs.

McCawley also discusses some experimental work on the processing of material implication by Braine and Wason & Johnson-Laird. Wason and Johnson-Laird (1972) found large differences in subjects’ abilities to process modus ponens arguments and modus tollens arguments.

Modus Ponens Argument

      If John loves Mary, Mary is happy.

      John loves Mary

      Mary is happy

Modus Tollens Argument

      If John loves Mary, Mary is happy.

      Mary is not happy.

      John does not love Mary.

Wason and Johnson-Laird found that subjects make few errors and give rapid responses when asked to judge the validity of modus ponens arguments but make many errors and give slower responses when judging modus tollens arguments. Braine (1978) replicated Wason & Johnson-Laird’s study, but also included stimuli in which the first premise had the form ‘A only if B’. Braine found that this stimuli eliminated the difference between the modus ponens and modus tollens arguments. McCawley claims that Braine was wrong in assuming ‘A only if B’ was an instance of modus ponens. McCawley claims it is really a modus tollens argument given his analysis of only if conditionals.

Kearns shows the fourth line of the truth table for material implication corresponds to a common conversational gambit. We often express doubt about a statement with sentence like:

      If that’s a Picasso, I’ll eat my hat.

If we assume that the consequent is false (I don’t really want to eat my hat), then for the conditional sentence to be true, the antecedent must be false. Note how this interpretation agrees with the fourth line of the truth table.

2.2.5 Equivalence and the Biconditional

The biconditional connective asserts the logical equivalence between two expressions. Kearns uses the symbols ‘<—>’ and ‘≡’ to represent the biconditional. Two propositions are logically equivalent if they have the same truth value under all conditions.

The biconditional is commonly translated into the ordinary English expressions if and only if, abbreviated as iff. These expressions are extremely rare in conversational English. Speakers often use conditionals to assert biconditional statements:

      If Martha calls, I’ll go.

I really mean that if Martha doesn’t call I will not go.

McCawley (53) notes that given his analysis of the conditional, the biconditional should be treated as the conjunction of A if B and A only if B. Compare the biconditional in the first line with the following propositions:

      A if and only if B.

      If A, then B, and if B, then A.

      If not B, then not A, and if B, then A.

      If B, then A, and if not B, then not A.

McCawley’s analysis predicts the biconditional would correspond to the last two lines rather than the second line. Consider these sentences:

      My pulse goes above 100 if and only if I do heavy exercise.

      If my pulse goes above 100, I do heavy exercise, and if I do heavy exercise, my pulse goes

            above 100.

      If I do heavy exercise, my pulse goes above 100, and if I don’t do heavy exercise, my pulse

            doesn’t go above 100.

      Butter melts if and only if it is heated.

      If butter melts, it is heated, and if butter is heated, it melts.

      If butter is heated, it melts, and if butter is not heated, it doesn’t melt.

The last sentence in each group is an excellent paraphrase of the first sentence. The second sentence is not a good paraphrase.

McCawley concludes that the English expression if and only if is not symmetric. The proposition A if and only if B is not interchangeable with B if and only if A. Try testing this claim with McCawley’s examples. The English expression is not a good translation for logical equivalence (‘≡’) which is symmetric both syntactically and semantically, i.e., A≡B is equivalent to B≡A. The proposition A—>B&B—>A is another translation for logical equivalence and is also symmetric.

Discussion Questions (de Swart 1998)

1. Sentence (i) is ambiguous. Represent the two readings of (i) in propositional logic. Be sure to provide a key to the propositional variables you use. Compute the truth value of sentence (i) under both readings in the situations a-c:

      i. It is not the case that Jack is singing or Jill is dancing.

            a. Jack is singing; Jill is dancing.

            b. Jack is not singing; Jill is not dancing.

            c. Jack is singing; Jill is not dancing.

2. Translate the following sentences into propositional logic giving the key to the variables you use.

      i. Although it was extremely cold, Sally did not stay indoors.

      ii. Jim has been elected president, or Sally has been elected, and a new era has begun.

      iii. If Sally brought an umbrella, but Jim did not, they will stay dry.

      iv. Sally only goes to the party if Jim does not go.

      v. Mary goes to the party if Bill does, and the other way around.

      vi. You don’t mean it, and if you do, I don’t believe you.

      vii. We are going unless it is raining.

3. Translate the following section of the US tax code into a sentence in propositional logic:

      You must file a return if any of the following apply:

            Your unearned income was over $750.

            Your earned income was over $4,750.

            Your gross income was more than the larger of:

                  $750 or

                  Your earned income (up to $4,500) plus $250.

4. Let v stand for the standard inclusive or and + the exclusive one. If or in ordinary English is ambiguous, a sentence like (ia) or (ib) would be ambiguous and have the interpretations shown in (ii).

 i.a. Bill smokes, or Bill drinks, or Bill smokes and drinks.

   b. Bill smokes or drinks or both.

ii. p = Bill smokes, q = Bill drinks

      a. [[pvq] & [p&q]]      c. [[p+q] + [p&q]]

      b. [[p+q] v [p&q]]      d. [[pvq] + [p&q]]

Now consider (iiia) and (iiib):

iii.a. [pvq] b. [p+q]

Prove that (iia-c) are all equivalent to (iiia), and that (iid) is equivalent to (iiib). Does this result show anything about the hypothesis that or is ambiguous between an inclusive and exclusive reading?

5. Explain why the following syllogism is not a valid reasoning pattern:

      If it rains, the streets are wet some time afterwards.

      The streets are wet.

      It rained some time before.

This pattern is called abduction, which is an inference to the best explanation. Explain why abduction is often used in daily conversation even though the argument is invalid. How is abduction related to the following inference:

      The streets are wet.

      It must have rained.

Find another example of abduction.

References

Braine, Martin D. S. 1978. On the relation between the natural logic of reasoning and standard logic. Psychological Review 85:1-30.

Geis, Michael. 1973. If and unless. In B. J. Kachru, et al. eds., Issues in linguistics: papers in honor of Henry and Renee Kahane, pp. 231-253. Urbana and Chicago: University of Illinois Press.

Horn, Laurence R. 2001. A Natural History of Negation. Stanford: CSLI Publications.

McCawley, James D. 1981. Everything that linguists have always wanted to know about logic but were ashamed to ask. Chicago: University of Chicago Press.

de Swart, Henriëtte. 1998. Introduction to natural language semantics. Stanford, CA: CSLI Publications.

Frawley, William. 1992. Linguistic Semantics. Hillsdale, NJ: Lawrence Erlbaum.

Wason, P. C. and Johnson-Laird, P. N. 1972. Psychology of reasoning: structure and content. London: Batsford.