Semantic Parsing and Meaning Representations › Logical Forms

Logical forms are the classical answer to the question, "What is the meaning of a sentence?" A logical form is a formula in a formal language with a model-theoretic semantics. The formula denotes a truth value in a model, or a set of satisfying assignments. Three historical contributions provide useful reference points for the discussion here. Frege distinguished the sense of an expression from its reference, Tarski gave a rigorous definition of truth in a model, and Montague showed that a fragment of English could be given a compositional model-theoretic semantics. Here we compare representation, interpretation, and composition through these contributions.

In first-order logic, we have constants, variables, predicates, quantifiers, and connectives. Constants name individuals, variables range over individuals, and predicates denote relations. The quantifiers introduced here express whether a formula holds for every domain individual or for at least one; connectives combine formulas. A simple sentence becomes a predicate application:

$$\text{like}(\text{alice}, \text{bob})$$

A quantified sentence becomes a formula with a quantifier:

$$\forall x \, (\text{student}(x) \to \exists y \, (\text{book}(y) \land \text{read}(x,y)))$$

This formula says: for every entity $x$, if $x$ is a student, then there exists an entity $y$ such that $y$ is a book and $x$ reads $y$.

The displayed formulas are already closed sentences: none of their variables occurs free. Their truth values are determined only after choosing a model. The predicate like could denote different binary relations in different models, and the constants alice and bob could denote different entities. Syntax specifies the formula; interpretation supplies its denotation.

The implication in the universal formula is not an accident. "Every student reads a book" does not say that everything is a student. It says that for anything, if it is a student, then it reads a book. Using conjunction instead would say that everything is both a student and a reader, which is far too strong. The existential formula uses conjunction for the opposite reason: it asserts that something exists that is both a book and read. Using implication there would be trivially satisfied by any non-book.

The meaning of a formula is defined relative to a model $\mathcal{M}=(D,I)$ and, for formulas with free variables, an assignment $g$. The domain $D$ contains the entities; $I$ interprets constants as entities and predicates as relations. The assignment maps each free variable to an entity in $D$. Write $\mathcal{M},g\models\phi$ for satisfaction, and let $g[x\mapsto d]$ change only the value assigned to $x$, keeping every other variable fixed. The recursive rules are:

• $\mathcal{M},g\models P(c)$ if $I(c)\in I(P)$. For a variable argument, use its value under $g$.
• $\mathcal{M},g\models\neg\phi$ if $\mathcal{M},g\not\models\phi$.
• $\mathcal{M},g\models\phi\land\psi$ if both conjuncts are satisfied under the same assignment $g$.
• $\mathcal{M},g\models\forall x\,\phi$ if $\mathcal{M},g[x\mapsto d]\models\phi$ for every $d\in D$.
• $\mathcal{M},g\models\exists x\,\phi$ if $\mathcal{M},g[x\mapsto d]\models\phi$ for at least one $d\in D$.

For a closed sentence, satisfaction does not depend on $g$, so we can write $\mathcal{M}\models\phi$ without it. The recursive definition states how the truth of a complex formula depends on its parts. In a finite model with explicitly available relations, you can evaluate quantifiers by enumerating the domain, as our code will do. The definition alone does not provide a terminating algorithm for arbitrary infinite models or a general decision procedure for first-order validity.

This semantics is precise, but it is also demanding. To parse natural language into first-order logic, a system must decide which predicates to use, how to handle quantifier scope, how to represent events, and how to ground names and pronouns. Those decisions are not dictated by English. They are modeling choices.

A parser that uses read(x, y) and a parser that uses reading_event(e) ∧ agent(e, x) ∧ patient(e, y) can both be correct, but they are not interchangeable. The first is simpler; the second supports adverbial modification and temporal annotation. The choice depends on what the downstream system needs to do.

First-order logic gives us a target language, but it does not tell us how to build the formula from a sentence. Lambda calculus gives us a compositional glue. The principle of compositionality says that the meaning of a complex expression is determined by the meanings of its parts and by the way those parts are combined. Lambda calculus is the standard formal tool for making this principle precise. It provides a uniform operation, function application, that mirrors the way syntactic constituents combine.

The simply typed lambda calculus has base types $e$ for entities and $t$ for truth values. Function types are written $\langle \sigma, \tau \rangle$ or $\sigma \to \tau$. Types matter because they rule out nonsensical combinations. You cannot apply an entity to an entity, or a truth value to a predicate, without a type error. A typed grammar therefore constrains the space of possible parses and gives the parser a way to reject ill-formed combinations early.

A verb like "likes" can be treated as a function from objects to functions from subjects to truth values:

$$\text{likes} := \lambda y. \lambda x. \text{like}(x,y)$$

The type is $\langle e, \langle e, t \rangle \rangle$. The object "Bob" has type $e$. Applying "likes" to "Bob" gives a predicate:

$$(\lambda y. \lambda x. \text{like}(x,y))(\text{bob}) \;\to_{\beta}\; \lambda x. \text{like}(x,\text{bob})$$

Applying that predicate to "Alice" gives a truth value:

$$(\lambda x. \text{like}(x,\text{bob}))(\text{alice}) \;\to_{\beta}\; \text{like}(\text{alice},\text{bob})$$

The reduction rule is beta reduction:

$$(\lambda x. M) N \;\to_{\beta}\; M[x := N]$$

where $M[x := N]$ means capture-avoiding substitution of $N$ for free occurrences of $x$ in $M$. Rename a bound variable first when it would otherwise capture a free variable in $N$. Function application combines compatible typed meanings in the examples below.

In a full Montague-style grammar, every syntactic rule is paired with a semantic rule. The grammar says how words and phrases combine; the semantic rule says how their meanings combine. The pairing is what makes the composition systematic rather than ad hoc.

A generalized quantifier is a function from predicates to truth values. Its type is $\langle \langle e,t \rangle, t \rangle$. Noun phrases like "every student" and "a book" have this type. The determiners "every" and "a" are one level up: they take a predicate and return a generalized quantifier, so their type is $\langle \langle e,t \rangle, \langle \langle e,t \rangle, t \rangle \rangle$.

Treating a determiner as a relation between two predicates makes its restriction and scope explicit. The universal does not carry existential import: "every student reads" entails "some student reads" only if the class of students is nonempty. The existential determiner supplies its own witness.

$$\text{every} := \lambda P. \lambda Q. \forall x \, (P(x) \to Q(x))$$ $$\text{a} := \lambda P. \lambda Q. \exists x \, (P(x) \land Q(x))$$

For each potential subject $x$, apply "a book" to the predicate $\lambda y.\,\text{read}(x,y)$. Abstracting over $x$ gives the verb-phrase predicate consumed by "every student":

$$\text{every}(\text{student})(\lambda x. \text{a}(\text{book})(\lambda y. \text{read}(x,y)))$$

which beta-reduces to:

$$\forall x \, (\text{student}(x) \to \exists y \, (\text{book}(y) \land \text{read}(x,y)))$$

This is the surface-scope reading. It says each student may read a different book. The universal quantifier is outermost, so its scope includes the existential. This describes logical scope rather than an evaluation-order rule. The alternative reading, in which the existential takes wide scope, is discussed next.

The string "Every student reads a book" is compatible with another reading:

$$\exists y \, (\text{book}(y) \land \forall x \, (\text{student}(x) \to \text{read}(x,y)))$$

This is the inverse-scope reading. It says there is one particular book that every student reads. English does not disambiguate the two readings with word order alone. Context and world knowledge can favor one reading. Prosody can also influence scope interpretation, although its effects depend on the construction and discourse; stress does not reliably select a reading in every double-quantifier sentence.

Scope choices can matter in sentences such as "A student talked to every professor": one student may have talked to everyone, or each professor may have talked to a different student. Distinct scope orders do not always yield distinct meanings; for example, two universal quantifiers commute in ordinary first-order logic. Adding quantifiers can increase the number of potential scope orders, while linguistic constraints may rule out orders. Underspecification can postpone the choice.

The truth of a scoped formula depends on the world, not only on the string. A small model makes the divergence between readings concrete.

Classical semantic parsers sometimes output one reading. That is a modeling decision, not a fact about the sentence. More sophisticated systems represent underspecification. Hole semantics, for example, uses metavariables for missing scope information and constraints on how those holes can be filled. The parser can leave scope unresolved until later.

Underspecification is attractive because it avoids committing to a reading before the context is known. This can complicate evaluation because the output retains unresolved alternatives rather than selecting one fully resolved reading.

This matters for evaluation. Under exact-match evaluation, if a test set contains one gold logical form per sentence, a parser that chooses the other reading is marked wrong even if its reading is linguistically valid. Exact-match evaluation of logical forms can therefore punish legitimate ambiguity. We will return to this issue in the evaluation discussion. A partial remedy is to annotate a set of acceptable readings and accept predictions that match one of them, using explicit annotation guidelines.

Many sentences describe events. In an event-based analysis, "Alice buttered the toast" asserts that a buttering event occurred, with Alice as the agent and the toast as the patient.

Davidson's insight was that making the event explicit solves several problems at once. It explains why "Alice buttered the toast with a knife" entails "Alice buttered the toast": the first formula conjoins more predicates to the same event variable. It also gives a natural place to attach temporal and locative modifiers.

Event semantics introduces an event variable. In Davidson's original form, the verb remains a relation over the event variable and its arguments:

$$\exists e \, (\text{butter}(e, \text{alice}, \text{toast}))$$

Neo-Davidsonian formulations separate the event predicate from its semantic roles. The following formula uses a unary buttering predicate and separate role relations, then adds an instrument and a time as further conjuncts:

$$\exists e \, (\text{butter}(e) \land \text{agent}(e,\text{alice}) \land \text{patient}(e,\text{toast}) \land \text{with}(e,\text{knife}) \land \text{time}(e,\text{noon}))$$

This style connects directly to the semantic roles and argument structure discussed earlier in this part. It also connects to AMR, which uses PropBank-style frames and role labels such as :ARG0 and :ARG1. The correspondence is not exact, but the intuition is the same: meaning is organized around events and their participants, not around a flat relation between two names.