1    Logical Form: Propositions

Translate the following English sentences into propositional logic and verify that they parse with LogicParser. Provide a key which shows how the propositional variables in your translation correspond to expressions of English.

Here's an example to get you started.

(1.1) If Kim sings, it is not the case that Lee sings.

Key: k = 'Kim sings', l = 'Lee sings'

>>> lp.parse('(k -> -l)')
<ImpExpression (k -> -l)>

This output provides some information about the kind of expression that the parser has recognized, namely an ImpExpression. In order to suppress this, use print:

>>> print lp.parse('(k -> -l)')
(k -> -l)

An alternative English rendering of the meaning in (1.1) might be:

(1.2) Lee doesn't sing if Kim does.

This could receive the same translation, namely '(k -> -l)'. There is another possible interpretation however: '-(k -> l)'. In other words, the scope of the negation could either be restricted to Lee's singing, or else be the whole implication. So in the case of ambiguity, you can give one or more of several possible answers.

Now try the following:

(1.3) Fido runs and barks.

(1.4) It will snow if it doesn't rain.

(1.5) It's not the case that Suzie will be happy if Peter or Rob comes.

(1.6) Kim didn't cough or sneeze.

(1.7) If you don't come if I call, I won't come if you call.

2   Logical Form: Relations

In the next example, we have decomposed the clauses into predicates and arguments:

(2.1) Lee likes Fido and Kim hates Rover.

>>> print lp.parse('(like(lee,fido) & hate(kim,rover))')
(like(lee,fido) & hate(kim,rover))

Here are some more examples for you to translate in a similar fashion. Don't try to be too faithful to the English; getting a 'correct' analysis in terms of compositional semantics can be quite subtle.

(2.2) Lee is taller than Kim.

(2.3) Fluffy washes herself.

(2.4) Dana saw Seth, but Kim didn't.

(2.5) Fido is a fourlegged friend.

(2.6) Lee and Claude are near each other.

3   Logical Form: Quantifiers

Here's the standard example of a quantified sentence with two readings:

(3.1) Everybody loves somebody.

>>> print lp.parse('all x. exists y. love(x,y)')
all x.exists y.love(x,y)
>>> print lp.parse('exists y. all x. love(x,y)')
exists y.all x.love(x,y)

Give translations of the following English examples. For some of them, you may want to use the connective '<->', which stands for the biconditional.

(3.2) Kim loves someone and someone loves Kim.

(3.3) Kim loves someone who loves Kim.

(3.4) Nobody loves Kim.

(3.5) Somebody coughs and sneezes.

(3.6) Nobody coughed or sneezed.

(3.7) Kim loves somebody other than Kim.

(3.8) Nobody other than Kim loves Lee.

(3.9) Kim loves everyone except for Lee.

(3.10) Exactly one person walks.

4   Logical Form: Lambda Abstracts

Lambda abstraction gives us a method of constructing a function from any open formula. For example, if we replace 'fluffy' by 'x' in 'wash(fluffy,fluffy)' we get three different open formulas:

(4.1)

1. wash(fluffy,x) --> 'be an x such that Fluffy washes x'
2. wash(x,fluffy) --> 'be an x such that x washes Fluffy'
3. wash(x,x) --> 'be an x such that x washes x'

These cannot be given a truth value unless we first specify a semantic value for 'x'. However, the variable can be bound by lambda, and the result is a function expression whose type is IND → BOOL.

(4.2)

1. \x. wash(fluffy,x) --> 'be an x such that Fluffy washes x'
2. \x. wash(x,fluffy) --> 'be an x such that x washes Fluffy'
3. \x. wash(x,x) --> 'be an x such that x washes x'

Can you think of more idiomatic translations of these?

We also parse expressions like these:

>>> print lp.parse('\\x. wash(x,x)')
\x.wash(x,x)

Because '\' is interpreted as a special character in Python, we either have to escape it with another '\' as just shown, or else use so-called raw strings of the form r'...', as here:

>>> print lp.parse(r'\x. wash(x,x)')
\x.wash(x,x)

Give translations for the following using lambda abstraction.

(4.3) feed Fido and give Rover water

(4.4) be given 'War and Peace' by Kim

(4.5) be loved by everyone

(4.6) be loved or hated by everyone

(4.7) be loved by everyone and hated by no-one

5   Logical Form: Lambdas and Function Application

Since lambda abstracts are functors, they can be applied to arguments, yielding an ApplicationExpression:

>>> lp.parse('\\x. love(kim,x)(fido)')
<ApplicationExpression (\x.love(kim,x))(fido)>

To carry out beta-conversion, we call the simplify() method on the expression, as shown here.

>>> print lp.parse('\\x. love(kim,x)(fido)').simplify()
love(kim,fido)

When working with lambda abstracts, it is often convenient to build up the expressions in stepwise fashion. Here's a couple of methods for doing this. First, we can build the parse expressions one by one, and then use the ApplicationExpression constructor to do the application:

>>> e1 = lp.parse('\\x. all y. love(y,x)')
>>> e2 = lp.parse('kim')
>>> e3 = ApplicationExpression(e1, e2)
>>> print e3.simplify()
all y.love(y,kim)

A second technique works on the string level, and uses string interpolation. Recall that we can use '%s' as a placeholder in a string, and then apply the % operator to this string and a tuple of fillers to get a complete string.

>>> b = 'beans'
>>> t = 'toast'
>>> 'I love %s on %s' % (b, t)
'I love beans on toast'

Here's how we do the same thing with lambda abstracts:

>>> s1 = '\\x. all y. love(y,x)'
>>> s2 = 'kim'
>>> s3 = '%s(%s)' % (s1, s2)
>>> s3
'\\x. all y. love(y,x)(kim)'
>>> print lp.parse(s3).simplify()
all y.love(y,kim)

You can use whichever approach you like, but in the following exercises, we'll stick to the first method. What you have to do is find a value for e1 such that a given reduction holds. Here's an example:

(5.1)

>>> e2 = lp.parse('kim')
>>> e3 = ApplicationExpression(e1, e2)
>>> print e3.simplify()
exists y.love(kim,y)

So one possible answer in this case is

>>> e1 = lp.parse('\\x. exists y. love(x,y)')

Now try the following. As well as finding e1, provide an English version of the final output.

(5.2)

>>> e2 = lp.parse('kim')
>>> e3 = ApplicationExpression(e1, e2)
>>> print e3.simplify()
exists y.(love(kim,y) | love(y,kim))

(5.3)

>>> e2 = lp.parse('kim')
>>> e3 = ApplicationExpression(e1, e2)
>>> print e3.simplify()
(exists y.love(kim,y) | all z.love(z,kim))

(5.3)

>>> e2 = lp.parse('kim')
>>> e3 = ApplicationExpression(e1, e2)
>>> print e3.simplify()
(-exists y.love(kim,y) | love(kim,kim))

(5.4)

>>> e2 = lp.parse('kim')
>>> e3 = ApplicationExpression(e1, e2)
>>> print e3.simplify()
walk(fido)

6   Logical Form: Higher-order Abstraction

So far, we have only looked at individual variables being bound by lambda. However, much of the power of the lambda calculus depends on being able to bind variables over function expressions. We follow standard practice in using upper-case letters for variables over functors. In particular, 'P', 'Q', 'R' are variables over expressions of type IND → (IND → ... (IND → BOOL)...)). Here's a simple example:

>>> print lp.parse('\\P. P(fido,kim)(love)').simplify()
love(fido,kim)

We can loosely paraphrase '\P. P(fido,kim)' as 'be a property P such that P holds between Fido and Kim'. Here's a slightly more complex example:

>>> print lp.parse('\\P. all x. P(kim,x)(love)').simplify()
all x.love(kim,x)

In the cases we looked at so far, the result of function application has been an expression of type BOOL. However, it doesn't have to be this way. Consider the following example:

>>> e1 = lp.parse('\\P. \\x. P(x,kim)')
>>> e2 = lp.parse('chase')
>>> e3 = ApplicationExpression(e1, e2)
>>> print e3.simplify()
\x.chase(x,kim)

Here, the result after beta-reduction is itself a lambda abstract, corresponding to the VP chases Kim.

Incidentally, there is a more succinct notation for multiple lambda abstraction, as shown here:

>>> e1 = lp.parse('\\P x. P(x,kim)')

Using lambda abstracts with variables over functions takes us outside first-order logic. However, we are going to assume that such lambda abstracts never enter into interpreted sentences of the semantic representation. Instead, they are always removed by beta-reduction, and serve as a kind of 'glue language' for assembling semantic representations in a compositional manner.

Now, find an e1 that gives the following results:

(6.1)

>>> e2 = lp.parse('chase')
>>> e3 = ApplicationExpression(e1, e2)
>>> print e3.simplify()
\x.all y.(dog(y) -> chase(x,kim))

(6.2)

>>> e2 = lp.parse('chase')
>>> e3 = ApplicationExpression(e1, e2)
>>> print e3.simplify()
\x.exists y.(dog(y) & chase(kim,x))

(6.3)

>>> e2 = lp.parse('give')
>>> e3 = ApplicationExpression(e1, e2)
>>> print e3.simplify()
\x0.\x1.exists y.(present(y) & give(x1,y,x0))

Let's suppose that we translate the verb barks as the non-logical constant 'bark', or equivalently as '\x. bark(x)'. How are we going to translate every dog in such a way that the correct translation for every dog barks results from a function application involving the translations of every dog and walks? In the tradition of Montague grammar, we do it like this:

>>> e1 = lp.parse('\\P. all x. (dog(x) -> P(x))')
>>> e2 = lp.parse('bark')
>>> e3 = ApplicationExpression(e1, e2)
>>> print e3.simplify()
all x.(dog(x) -> bark(x))

Now, find e1 such that the following hold:

(6.4)

>>> e2 = lp.parse('bark')
>>> e3 = ApplicationExpression(e1, e2)
>>> print e3.simplify()
exists y.(dog(x) & bark(x))

(6.5)

>>> e2 = lp.parse('bark')
>>> e3 = ApplicationExpression(e1, e2)
>>> print e3.simplify()
bark(fido)

In the preceding examples, we have treated the subject as the functor and the verb as the argument. Devise a translation for barks that makes it the functor and the subject the argument. In other words, find an appropriate value of e1 for the following result to be obtained:

(6.6)

>>> e2 = lp.parse('\\P. all x. (dog(x) -> P(x))')
>>> e3 = ApplicationExpression(e1, e2)
>>> print e3.simplify()
all x.(dog(x) -> bark(x))