HOMEWORK 4

CS 224U / LING 188/288, Spring 2014, Stanford

Our language L

Throughout this assignment, we will work with the following first-order lambda calculus. The notation is slightly different from that of Manning 2005 because we are going to use it to query a live database using the wonderful Python NLTK semantic module (documentation).

  1. Type Ind expressions: bart, lisa, maggie, marge, homer, burns
  2. Type Ind variables: x, y, z
  3. Type <Ind → Bool> expressions: simpson, child, parent, boss, female, male, bald, musical, student, skateboarder
  4. Type <Ind → <Ind → Bool>> expressions: teases, admires, telephoned
  5. Functional application: If φ is an expression of type <Indn → Bool>, where Indn is an n-ary sequence of Ind-types, and ψ1...ψn is a sequence of Ind-type expressions, then (φ(ψ1,...,ψn)) is an expression of type Bool.
  6. Lambda abstraction: If φ is an expression of type b and χ is an variable of type Ind, then (\χ .φ) is an expression of type <Ind → b>.
  7. Equality: If φ and ψ are expressions of type a, then (φ = ψ) is an expression of type Bool.
  8. Boolean negation: If φ is an expression of type Bool, then is an expression of type Bool.
  9. Boolean combinations: If φ and ψ are expressions of type Bool, then (φ & ψ), (φ | ψ), (φ -> ψ), and (φ <-> ψ) are expressions of type Bool.
  10. Quantification: If φ is an expression of type Bool and χ is an variable of type Ind, then (exists χ.φ) and (all χ.φ) are expressions of type Bool.

Thus, with the above definition, we have formulae like these:

child(bart)
parent(lisa)
teases(lisa, y)
(\x .parent(x))
(\x .-parent(homer))
(\y .(\x .admires(x, y)))
(exists x.(parent(bart) -> -child(x)))

The syntax is pretty picky. We recommend paying close attention to bracketing and other details. Some outer brackets can be safely left off, but not all the standard association conventions are implemented.

Our model

We have specified a model for the above language, but we are not going to show it to you in full. Rather, we're asking you to use the above language to query it.

We have also specified an assignment function g that provides values for the variables x, y, z. We aren't going to show you that either, but here is a hint: it assigns a different entity to each variable.

Query interface

Enter a well-formed formula of L to see how its is interpreted in our model:

Interpretation:

Questions

The following are all worth 0.5 points each.

  1. Provide a formula that will answer the question of whether Maggie is musical in our model, and provide the return value as well.
  2. Provide a formula that will answer the question of whether everyone is a Simpson in our model, and provide the return value as well.
  3. Figure out who g(x) is. (That is, figure out who our variable assignment g maps the variable x to.) Provide the shortest possible formula (in terms of string length) that answers this question.
  4. Use the lambda operator to specify the property of being a parent or a child. Provide your lambda expression and its interpretation in the model (you can copy out the return value).
  5. Provide a formula that will answer the question of who admires Lisa in our model. (Hint: the return value should be a function from individuals to truth values.)
  6. Provide a formula that will answer the question of who Lisa admires in our model.
  7. Provide a formula that corresponds to the sentence No one is a parent and a child, and provide the return value as well.
  8. Provide a formula that corresponds to the sentence No one is a parent and no one is a child, and provide the return value as well.

The following are all worth 1 point each.

  1. Our negation operator - is boolean in the sense that it applies only to expressions of type Bool (and yields expressions of the same type). This is unfortunate from the perspective of natural language, since sentential negations are rare and marked cross-linguistically. We can remedy this with lambdas, though. Provide an <Ind → Bool>-typed lambda expression that corresponds to the property of being not bald.
  2. Verbs like telephone are transitive in the sense that they typically have direct objects (Bart telephoned Lisa), but they can also be used intransitively (Bart telephoned), where they have roughly the sense of ‘telephoned someone’. Use lambdas and the existential quantifier to create an intransitive version of telephoned. What set of entities does this function pick out (i.e., which set of entities does it map to True?)
  3. There are two readings of Everyone admires someone, one where the subject takes wide scope and one where the direct object takes wide scope. Provide formulae corresponding to each of these two readings and give their interpretations in our model.
  4. Repeat the previous problem for Everyone telephoned someone.
  5. In compositional semantic interpretation, daughter nodes are combined via functional application (clause (e) above) to create the meaning for the mother node. Complete the compositional interpretation of the following structure by providing the logical expressions for nodes A and B, along with the semantic value of the root node B in our model (by entering it into the above query interface).
                      B
                      |                
         -------------------------- 
         |                        A
        bart                      |          
                        --------------------
                        |                  |
          (\y .(\x .admires(x, y)))      lisa 
    
  6. In the following structure, for the sentence Maggie is Homer, you are given the overall meaning, and the task is to fill in meanings for the two missing nodes. Again, assume that the only way to combine daughter nodes is via functional application. (No need to supply the meaning of maggie = homer in our model — it's False).
               maggie = homer
                      |                
         -------------------------- 
         |                        A
      maggie                      |          
                        --------------------
                        |                  |
                        B                homer