Dynamic Predicate Logic

See discussions, stats, and author profiles for this publication at: https://www.researchgate.
net/publication/225230664
Dynamic Predicate Logic
Article in Linguistics and Philosophy · February 1991

DOI: 10.1007/BF00628304 · Source: CiteSeer
CITATIONS READS
1,147 1,414
2 authors:
Jeroen Groenendijk Martin Stokhof

University of Amsterdam Tsinghua University
104 PUBLICATIONS 3,799 CITATIONS 127 PUBLICATIONS 4,137 CITATIONS
SEE PROFILE SEE PROFILE
All content following this page was uploaded by Martin Stokhof on 06 May 2020.
The user has requested enhancement of the downloaded file.

JEROEN GROENENDIJK AND MARTIN STOKHOF
DYNAMIC PREDICATE LOGIC
1. INTRODUCTION
This paper is devoted to the formulation and investigation of a dynamic

semantic interpretation of the language of first-order predicate logic. The
resulting system, which will be referred to as 'dynamic predicate logic', is
intended as a first step towards a compositional, non-representational
theory of discourse semantics.
In the last decade, various theories of discourse semantics have emerged
within the paradigm of model-theoretic semantics. A common feature of
these theories is a tendency to do away with the principle of compositional-
ity, a principle which, implicitly or explicitly, has dominated semantics
since the days of Frege. Therefore the question naturally arises whether
non-compositionality is in any way a necessary feature of discourse seman-
tics.
Since we subscribe to the interpretation of compositionality as constitut-
ing primarily a methodological principle, we consider this to be a method-
ological rather than an empirical question. As a consequence, the empha-
sis in the present paper lies on developing an alternative compositional
semantics of discourse, which is empirically equivalent to its non-composi-
tional brethren, but which differs from them in a principled methodolog-
ical way. Hence, no attempts are made to improve on existing theories
empirically.
Nevertheless, as we indicate in Section 5, the development of a composi-
tional alternative may in the end have empirical consequences, too. First
of all, it can be argued that the dynamic view on interpretation developed
in this paper suggests natural and relatively easy to formulate extensions
which enable one to deal with a wider range of phenomena than can be
dealt with in existing theories.
Moreover, the various approaches to the model-theoretic semantics of
discourse that have been developed during the last decade, have consti-
tuted a 'fresh start' in the sense that much of what had been accomplished
before was ignored, at least for a start. Of course, this is a justified strategy
if one feels one is trying to develop a radically different approach to
recalcitrant problems. However, there comes a time when such new ap-
proaches have to be compared with the older one, and when an assessment
of the pros and cons of each has to be made.
Linguistics and Philosophy 14: 39-100, 1991.

© 1991 Kluwer Academic Publishers. Printed in the Netherlands.
40 J. GROENENDIJK AND M. STOKHOF
One of the main problems in semantics today, we feel, is that a semantic

theory such as Montague grammar, and an approach like Kamp's discourse
representation theory, are hard to compare, let alone that it is possible
to unify their insights and results. One of the main obstacles is that the
latter lacks, or has abolished, the principle of compositionality, which is
so central a feature of the former. Hence, the development of a composi-
tional alternative to the semantics of discourse may very well have empiri-
cal import on this score as well: in the end, it may contribute to a uni-
fication of these two approaches which have largely complementary
descriptive domains.
In the extension of modeltheoretic semantics from the sentential to the
discourse level, various theories have emerged: beside discourse represen-
tation theory (Kamp, 1981, 1983), we should mention Heim's file card
semantics (Heim, 1982, 1983), and, in a different framework, the work of
Seuren (Seuren, 1986). None of these theories makes compositionality its
starting point. (However, it seems that Heim (1982, ch. 3), does attach
some value to compositionality.) Since the aim of this paper is restricted
to showing that a compositional alternative can be developed, and since
Kamp's discourse representation theory is both self-consciously non-com-
positional and formally most explicit, we feel justified in restricting com-
parison to just the latter theory.
The paper is organized as follows. In Section 2, we introduce the ele-
ments of dynamic interpretation in a heuristic fashion, discussing a small
number of well-known problematic cases. In Section 3, we recapitulate
our findings and formulate the dynamic semantics of predicate logic sys-
tematically, and study its logical properties. The resulting system is com-
pared with ordinary predicate logic, discourse representation theory, and
quantificational dynamic logic in Section 4. In Section 5, we indicate
prospects for further developments and, in retrospect, we present our
philosophical and methodological motives.
To end this introductory section, we remark that Barwise' proposal for
the interpretation of anaphoric relations within the framework of situation
semantics (Barwise, 1987), which in Rooth (1987) is compared with Heim's
file card semantics and with Montague grammar, are akin in spirit and
content to our approach. So is Schubert and Pelletier (1989). Equally akin
in spirit, but less in content, is Zeevat (1989).
2. ELEMENTS OV DYNAMIC INTERPRETATION

2.1. Cross-sentential and Donkey-anaphora
We begin this section with a brief discussion of two well-known problems:
cross-sentential anaphora and anaphoric relations in donkey-sentences.
DYNAMIC PREDICATE LOGIC 41
We state them anew, because we want to make clear what, we feel, is the
real challenge they offer.
If we use standard first-order predicate logic (henceforth, PL) in trans-
lating a natural language sentence or discourse, anaphoric pronouns will
turn up as bound variables. In many cases, this means that in order to
arrive at formulas which are good translations, i.e., which express the
right meaning, we have to be pretty inventive, and should not pay too
much attention to the way in which the natural language sentence or
discourse is built up. Let us illustrate this with three simple examples,
which nevertheless are representative for the kind of problems we meet:
(1) A man walks in the park. He whistles

(2) If a farmer owns a donkey, he beats it
(3) Every farmer who owns a donkey, beats it
In order for the pronoun he in the second sentence of (1) to be anaphor-

ically linked to a m a n in the first sentence, we have to give an existential
quantifier wide scope over the conjunction of the two sentences involved.
Doing so, we arrive at (la):
(la) 3x[man(x) A walk_in_the_park(x) A whistle(x)]
Now, notice that the translation of the first sentence in (1), which would
be 3x[man(x) A walk_in_the_park(x)], does not occur as a subformula in
(la). Apparently, we do not get from (1) to (la) in a step-by-step, i.e.,
in a compositional way. If we did, we would rather translate (1) as (lb):
(lb) 3x[man(x) A walk_in_the_park(x)] A whistle(x)
But this is not a proper translation of (1), at least not in standard predicate
logic, since in (lb) the last occurrence of the variable x is not bound by
the existential quantifier, and hence the anaphoric link in (1) is not ac-
counted for. However, suppose we could interpret (lb) in such a way that
it is equivalent with (1). Evidently, (lb) would be preferred to (la) as a
translation of (1), since it could be the result of a compositional procedure.
Turning to examples (2) and (3), we observe that a proper translation
in PL for both of them is (2a):
(2a) V x V y [ [ f a r m e r ( x ) A donkey(y) A own(x, y)]

beat(x, y)]
These cases are more dramatic than the previous one. Although (2) and
(3) contain indefinite terms, which normally translate as existentially qu-
antified phrases, we need universal quantification to account for their
meaning in these kinds of examples. And notice, moreover, that the
corresponding universal quantifiers Vx and Vy have to be given wide scope
over the entire formula, whereas the indefinite terms in (2) and (3) to
which they correspond, appear inside the antecedent of an implication in
the case of (2), and way inside the relative clause attached to the subject
term e v e r y f a r m e r in the case of (3). If we use PL as our means to
represent meaning, these kinds of examples prevent us from uniformly
translating indefinite terms as existentially quantified phrases. Again, this
constitutes a breach of the principle of compositionality, a principle which
is not only intuitively appealing, but also theoretically parsimonious and
computationally plausible.
From a compositional point of view, translations like (2b) for sentence
(2), and (3b) for sentence (3), are to be preferred:
(2b) 3x[farmer(x) A 3y[donkey(y) A own(x, y)]]

--+ beat(x, y)
(3b) Vx[[farmer(x) A 3y[donkey(y) A own(x, y)]]
--+ beat(x, y)]
But then again, (2b) and (3b) do not have the proper meaning in PL. For
one thing the occurrences of the variable y in case of (3b), and of the
variables x and y in case of (2b), in the respective consequents, are not
bound by the existential quantifiers in the antecedents. Hence, (2b) and
(3b) are not equivalent with (2a), at least not in PL.
Examples like (1)-(3) have been treated successfully in discourse repre-
sentation theory (henceforth DRT), but at a cost: the problem of providing
a compositional translation is not really solved, and DRT uses a rather
non-orthodox logical language. In DRT, (1) would be represented as (lc),
(2) and (3) as (2c):
(lc) [x] [man (x), walk_in_the_park (x), whistle (x)]

(2c) [ ][[x, y][farmer(x), donkey(y), own(x, y)]
[ ][beat(x, y)]]
We will not go into the semantics of these discourse representation struc-

tures here (cf. Section 4.2), for the moment it suffices to note that (lc)
and (2c) have essentially the same truth conditions as (la) and (2a) respec-
tively. The important thing, however, is that these representations differ
in structure from the corresponding sentences in much the same way as
the PL-translations. In fact, the structure of (lc) is essentially that of (la),
and not that of (lb). And in (2c) no representation of the relative clause
w h o o w n s a d o n k e y or of the intransitive verbphrase o w n a d o n k e y -
which form a constituent in (2) and (3) respectively - can be isolated as
a substructure of (2c). So, from a compositional point of view, they are

hardly a change for the better. For the moment we leave it at this obser-
vation, but we return to the issue in some detail in Section 4.2.
In this paper we give an alternative account of the phenomena exempl-
ified by (1)-(3); we do so by replacing the standard semantics of the
language of first-order predicate logic by a dynamic semantics, which is
inspired by systems of dynamic logic as they are used in the denotational
semantics of programming languages. (See Harel (1984) for an overview.)
The resulting system of dynamic predicate logic (henceforth, DPL) consti-
tutes an improvement over D R T in the following sense: to the extent that
this is possible in a first-order language at all, it gives a compositional
semantic treatment of the relevant phenomena, while the syntax of the
language used, being that of standard predicate logic, is an orthodox one.
More specifically, using D P L it becomes possible to represent the mean-
ings of the sentences (1), (2) and (3) by means of the formulas (lb), (2b)
and (3b). AS we remarked above, such representations are to be preferred
from a compositional and a computational point of view. The dynamic
semantics of D P L makes sure that (lb) comes out with the same truth
conditions as (la) is assigned in PL, and that (2b) and (3b) come out with
the same truth conditions as (la) and (2a) have in PL.
2.2. The Dynamic View on Meaning
The general starting point of the kind of semantics that D P L is an instance

of, is that the meaning of a sentence does not lie in its truth conditions,
but rather in the way it changes (the representation of) the information
of the interpreter. The utterance of a sentence brings us from a certain
state of information to another one. The meaning of a sentence lies in the
way it brings about such a transition. Although this 'procedural' dynamic
view on meaning as such is not particular to semantic theories of discourse
(it can also be found in theories about sentence meaning, e.g., in the work
of Stalnaker), it is a view which is endorsed by all approaches to discourse
semantics which we referred to above.
It should be noted, though, that in most cases one really studies only
one particular aspect of the information change potential that makes up
the meaning of a sentence, at a time. For example, in the standard version
of D R T , information change is narrowed down to the (im)possibilities
of subsequent anaphoric reference that sentences determine. All other
information that a sentence conveys, is treated in a static, rather than in
a dynamic fashion. D P L is like D R T in this respect. It, too, restricts the
dynamics of interpretation to that aspect of the meaning of sentences that
44 J, GROENENDIJK AND M. STOKHOF
concerns their potential to 'pass on' possible antecedents for subsequent

anaphors, within and across sentence boundaries. (See Groenendijk and
Stokhof (1988) for some more discussion of this point.)
As has been observed by several authors, there is a strong correspon-
dence between the dynamic view on meaning, and a basic idea underlying
the denotational approach to the semantics of programming languages,
viz., that the meaning of a program can be captured in terms of a relation
between machine states. Given the restriction to antecedent-anaphor re-
lations, the observed correspondence comes down to the following. A
machine state may be identified with an assignment of objects to variables.
The interpretation of a program can then be regarded as a set of ordered
pairs of assignments, as the set of all its possible 'input-output' pairs. A
pair (g, h) is in the interpretation of a program ~r, if when 7r is executed
in state g, a possible resulting state is h.
For example, the execution of an atomic program consisting of a simple
assignment statement 'x := a' transforms a state (assignment) g into a state
(assignment) h which differs from g at most with respect to the value it
assigns to x, and in which the object denoted by the constant a is assigned
to x.
Another simple illustration is provided by sequences of programs. The
interpretation of a sequence of programs '~-~; 7r2' is as follows. It can take
us from state g to h, if there is some state k such that the program 7r~ can
take us from g to k, and 7r2 from k to h. Or to put it differently, the
second program is executed in a state which is (partly) created by the
first.
As we intend to show in this paper, the basic idea that (certain aspects
of) meaning can be described in terms of relations between states, can
be applied fruitfully in natural language semantics as well. It should be
remarked, though, that the aims and perspectives of systems of dynamic
logic as they are used in the semantics of programming languages, are
rather different from the purpose for which we want to use the system to
be developed below. And consequently, there are differences between
these systems as such. Some discussion of these matters can be found in
Section 4.3.
2.3. Dynamic Conjunction and Existential Quantification
In the present and the next two sections, we introduce a dynamic interpret-
ation for the language of extensional first-order predicate logic in a step-
by-step fashion, deferring an explicit statement and a formal investigation
of D P L to Section 3. In the present section we introduce dynamic conjunc-
tion and existential quantification, which will enable us to deal with the
first of the three examples discussed above, which concerned cross-senten-
tial anaphora. In Section 2.4, we discuss implication and existential quanti-
fication. Their dynamic treatment will give us the means to treat simple
donkey-sentences, such as exemplified by the second example. And finally
in Section 2.5, we turn to universal quantification and negation in order
to be able to deal with the more complicated donkey-sentences as exempl-
ified by the last example.
The vocabulary of D P L consists of n-place predicates, individual con-
stants and variables. They are interpreted in the usual fashion. The models
that we use, are ordinary extensional first-order models, consisting of a
domain D of individuals and an interpretation function F, assigning indi-
viduals to the individual constants, and sets of n-tuples of individuals to
the n-place predicates. Further, we use assignments as usual, i.e., as total
functions from the set of variables to the domain. They are denoted by
'g', 'h', and so on. By "h[x]g' we mean that assignment h differs from g
at most with respect to the value it assigns to x. When in what follows we
speak of the interpretation of an expression, we mean its semantic value
in a suitable model. The function assigning semantic values is denoted by
,~ ~,.
In the standard semantics of predicate logic, the interpretation of a
formula is a set of assignments, viz., those assignments which verify the
formula. In the dynamic semantics of D P L the semantic object expressed
by a formula is a set of ordered pairs of assignments. Trading on the
analogy with programming languages, such pairs can be regarded as pos-
sible 'input-output' pairs: a pair (g, h) is in the interpretation of a formula
~b iff when ~b is evaluated with respect to g, h is a possible outcome of the
evaluation procedure. Since g and h are assignments of objects to vari-
ables, the difference between an input assignment g and an output assign-
ment h can only be that a different object is assigned to one or more
variables. This is precisely what happens when an existentially quantified
formula is interpreted dynamically. Consider the formula 3xPx. In the
standard semantics, an assignment g is in the interpretation of 3xPx iff
there is some assignment h which differs from g at most with respect to
the value it assigns to x, and which is in the interpretation of Px, i.e.,
which assigns an object h(x) to x such that h(x) E F(P). When 3xPx is
treated dynamically, all assignments h such that h[x]g & h(x) ~ F(P), are
taken to be possible outputs with respect to input g. In other words:
~3xPx~ = {(g, h)[h[x]g & h(x) E F(P)}

This will not yet do for the general case of 3xqS. We have to reckon with
46 J. GROENENDIJK AND M. STOKItOF
the possibility that the interpretation of q% too, has dynamic effects. (For
example, ¢b itself might be an existentially quantified formula.) Taking
this into account, the dynamic interpretation of 3x~b will consist of those
pairs of assignments (g, h) such that there is some assignment k which
differs from g at most in x and which together with h forms a possible
input-output pair for oh. The interpretation clause for existentially quant-
ified formulas then reads as follows:
[[3x~b~ = {(g, h)13k: k[x]g & (k, h) E ~4)]1}

In order to show that this interpretation of 3xq5 squares with the one
given above for 3 x P x , we first have to state the interpretation of atomic
formulas.
Unlike existentially quantified formulas, atomic formulas do not have
dynamic effects of their own. Rather, they function as a kind of 'test' on
incoming assignments. An atomic formula tests whether an input assign-
ment satisfies the condition it embodies. If so, the assignment is passed
on as output, if not it is rejected. So, the dynamics of an atomic formula
consists in letting pass the assignments which satisfy it, and blocking those
that don't. This is captured in the following definition:
~Rt~ . . . t,,]l = {(g, h)lh = g & (~t~]],. . . . . . ~t,,~,,) e F(R)}
Here, as usual, ~t~h = F(t) if t is an individual constant, and [[tlh = h(t) if

t is a variable.
We first work out our simple example of an existentially quantified
formula 3xPx:
~3xPx~ = {(S, h) l 3k: k[x]g & (k, h) • ~Px~} =

{<g,h>13k: k[x]g & k = h a h(x) • F(P)}} =
{(g, h)lh[x]g & h(x) • F(P)}
This example illustrates the interpretation of the existential quantifier and

that of atomic formulas. The meaning of 3 x P x determines that for a given
input assignment g, we get as possible outputs those assignments h which
differ from g at most in x and which satisfy the condition that the individual
h(x) has the property F(P).
The dynamic interpretation of existential quantification presented here
is only one ingredient of a treatment of cross-sentential anaphoric binding
as it was illustrated by the first example discussed in Section 2.1. The
example consists of a sequence of two sentences, the first of which contains
an indefinite term which functions as the antecedent of an anaphoric
pronoun occurring in the second sentence. Although this obviously is not
all there is to it, within the framework at hand, simple sentence sequencing
is best represented as conjunction. Going about compositionally, what we

get in this case is a conjunction consisting of an existentially quantified
formula and a formula containing a free occurrence of the variable corre-
sponding to the quantifier. The simplest example of a formula that is of
this form is 3xPx A Qx.
To get the required interpretation for this kind of formula, a dynamic
interpretation of existential quantification alone does not suffice, we need
a dynamic treatment of conjunction as well. For example, in order to get
the required anaphoric reading we have to interpret 3xPx A Qx in such
a way that the second occurrence of x, which is outside the scope of the
quantifier, is bound by that quantifier with the same force as the first
occurrence of x, which is inside its scope.
So the first thing we require of the dynamic interpretation of conjunction
is that it passes on values of variables from the first conjunct to the second.
Moreover, we note that values assigned to variables in a conjunction
should remain available for further conjuncts that are added. If we con-
tinue the discourse 'A man walks in the park. He meets a woman' with
'He kisses her ~, we must view this as adding another conjunct. And this
newly added conjunct may contain 'free' occurrences of variables (pro-
nouns) which nevertheless are bound by existential quantifiers (indefinite
terms) which have occurred earlier on.
In fact, this is exactly what the interpretation of a sequence of programs
as described above amounts to. Hence, our definition of dynamic conjunc-
tion is the following:
According to this definition, the interpretation of & A O with input g may

result in output h iff there is some k such that interpreting q5 in g may
lead to k, and interpreting O in k enables us to reach h.
We are now fully equipped to deal with the first of the three examples
discussed above, which concerned cross-sentential anaphora. Calculating
the interpretation of 3xPx A Qx shows that indeed the binding effects of
an existential quantifier may reach further than its scope, more in parti-
cular they reach over further conjuncts:
~3xPx A Qx~ = {{g, h}jBk: {g, k) E [[3xPx]] & (k, h) ~ ~Qx] } =
{(g,h}13k: k[x]g & k(x) E F(P) & h = k & h(x) ~ F(Q)} =
{{g, h)lh[x]g & h(x) ~ F(P) & h(x) ~ F(Q)}
Here, we see that the occurrence of x in the second conjunct Qx, although
it is not in the scope of the quantifier 3x in the ordinary sense, is neverthe-
less bound by it with the same force as the occurrence of x in Px in the

first conjunct, which obviously is in the scope of 3x. This means that in
D P L there is no difference in meaning between the formula 3xPx/x Qx
and the formula 3x[Px A Qx]. From the latter fact it is also clear that if
we continue a conjunction ~ A ~ with a further conjunct %, the binding
force of quantifiers in either one of the conjuncts ~ and ~Owill remain
active.
Because of its power to pass on variable bindings from its left conjunct
to the right one, we call conjunction an internally dynamic connective.
And because of its capacity to keep passing on bindings to conjuncts yet
to come, we call it an externally dynamic connective as well. For similar
reasons, the existential quantifier is called both internally and externally
dynamic: it can bind variables to the right, both inside and outside its
scope.
It is precisely this feature of DPL, that it allows for existential quantifiers
to bind variables yet to come which are outside their scope, that lends it
the power to solve the problem of getting a compositional treatment of
antecedent-anaphor relations which go across sentence boundaries. It al-
lows us to translate the sentence containing the antecedent indefinite term,
without having to look ahead at what is still to come, treating it as an
ordinary existentially quantified phrase. Then we can translate a sentence
which follows and which contains an anaphor, without having to re-analyze
the translation so-far, regarding the anaphoric pronoun as an ordinary
variable. The dynamic semantics takes care of the rest. It makes sure
that the pronoun is treated as a variable bound by the quantifier which
corresponds to the indefinite term.
2.4. Dynamic Existential Quantification and Implication
The second kind of example which we introduced in Section 2.1, concerns

simple donkey-sentences. The main problem of donkey-sentences is the
occurrence of an indefinite term in the antecedent of an implication which
is anaphorically linked to a pronoun in the consequent. As we indicated
above, if we are to represent the meaning of such sentences in ordinary
predicate logic, which allows quantifiers to bind only those variables which
occur in their syntactic scope, then we are forced to regard the indefinite
term as a universal quantifier and to give it wide scope over the implication
as a whole. This goes against compositionality in two ways: first of all, we
cannot use the ordinary, lexically determined meaning of indefinite terms,
and secondly, we must deviate from the syntactic structure by 'raising'
these terms from their position in the antecedent to a position outside the
implication. In order to show that this kind of example can be treated in

D P L in a more compositional, and hence more satisfactory way, we have
to say what the dynamic interpretation of implication is.
The simplest example of a formula corresponding to a donkey-sentence
is 3xPx --+ Qx. In order for this formula to get the required interpretation,
the dynamic interpretation of implication has to allow for an existential
quantifier in its antecedent to bind a variable in its consequent. This means
that implication is like conjunction in the following respect: it passes on
values assigned to variables in its antecedent to its consequent. In other
words, implication is an internally dynamic connective.
But that is not all. We also observe that the existential quantifier in the
antecedent has universal force. This can be accounted for as follows. With
respect to an input assignment, the antecedent of an implication results
in a set of possible output assignments. For the implication as a whole, it
seems reasonable to require that every assignment that is a possible output
of the antecedent, be a possible input for the consequent. By this we
mean that an output assignment h of the antecedent, when taken as input
to the consequent, should result in at least one output assignment k. In
other words, the interpretation of an implication 05--+ ~ should be such
that for every pair (g,h) in the interpretation of 05 there is some assignment
k such that (h,k) is in the interpretation of ~. This feature of the interpret-
ation of implication results in universal force of an existential quantifier
occurring in the antecedent. Consider 3xPx-+ Qx. With respect to an
input assignment g, the antecedent 3xPx results in the set of assignments
h such that h[x]g and h(x) E F(P). If we require, as we do, that every
such h should be a proper input of the consequent Qx, the result is that
every h such that h(x) E F(P), also satisfies h(x) E F(Q).
This does not yet determine which pairs of assignments constitute the
interpretation of 05 ~ ~0, it only tells us with respect to which assignments
05 ~ ~0 can be 'successfully executed'. To get at the full interpretation of
05-+ & we need yet another observation, which is that normally an impli-
cation as a whole does not pass on values assigned to variables by quantifi-
ers in the implication itself, to sentences yet to come. Consider the follow-
ing example:
(4) If a farmer owns a donkey, he beats it.* He hates it
In this example, the pronouns he and it in the second sentence cannot be

anaphorically linked to the indefinite terms in the preceding implication.
And quite generally it is concluded on the basis of examples such as these
that a quantifier which occurs inside an implication, be it in the antecedent
or in the consequent, cannot bind variables outside the implication. (A
lot more needs to be said about this, and for some of it we refer to Section
5.1.) In this respect implication is unlike conjunction: it is not externally
dynamic; like an atomic formula, an implication as a whole has the charac-
ter of a test.
What we thus end up with as the dynamic interpretation of implication,
is the following:
~[4~~ 01 = {(g, h)lh = g & Vk: (h, k) ~ ~qS~~ 3j: (k, j) E ~t)~}
The interpretation of cb--+ ~ accepts an assignment g iff every possible

output of 4) with respect to g leads to a successful interpretation of 4', and
it rejects g otherwise. Armed with this definition, we can now proceed to
show that D P L assigns the required interpretation to formulas which
correspond to the kind of donkey-sentences exemplified by our second
example. By way of illustration, we work out the interpretation of the
formula 3xPx ~ Qx:
3x Px --~ Qx~ --
{(g, h) lh = g & Vk: (h, k) ~ [3xPx~ ~ 3j: (k, j} ~ ~Qx~} :
{(g, g)lVk: (g, k) e ~3xPx~ ~ 3j: {k, j) e ~Qx~} =-
{{g, g)]Vk: k[x]g & k(x) E F(P) ~ k(x) ~ F(Q)}
This example shows that the binding effects of an existential quantifier

occurring in the antecedent of an implication extend to occurrences of
the corresponding variable in the consequent, and that such a quantifier
occurrence has universal force. It also shows that dynamic effects are
restricted to the implication as such, and are not passed on to any formulas
which might follow it. In effect, as we shall see below, 3xPx ~ Qx is
equivalent in D P L to Vx[Px --* Qx].
2.5. Universal Quantification, Negation and Disjuriction
For a treatment of the second, more complicated kind of donkey-

sentences, exemplified by our third example, we need to state the interpre-
tation of the universal quantifier. One aspect of this interpretation is
illustrated by the following two examples:
(5) Every man walks in the park.* He whistles

(6) Every farmer who owns a donkey beats it.* He hates it
The pronoun he occurring in the second sentence of (5), cannot be in-

terpreted as being anaphorically linked to the universal term in the sen-
tence preceding it. Nor can the pronouns he and it in the second sentence
of (6) be anaphorically linked to the terms every farmer and a donkey in
the first sentence of (6). Generally, from examples such as these it is

concluded that the universal quantifier shares with implication the charac-
teristic of being externally static. Neither a universal quantifier itself, nor
any existential quantifier inside its scope can bind variables outside the
scope of that universal quantifier. (Again, we refer to Section 5.1 for some
discussion of this point.) But, of course, inside the scope of a universal
quantifier dynamic effects may very well occur, as the donkey-sentence
(3) shows. This leads to the following definition of the interpretation of
universal quantification:
~Vx6]] = {(g, h)lh = g & Vk: k[xlh @ 3m: (k, m) ¢ ~6~}

So, a universally quantified formula 'v'x~b, too, functions as a test. An
input assignment g is passed on iff every assignment that differs at most
from g in x is a proper input for qS, otherwise it is blocked. An output
assignment is always identical to the corresponding input.
That the dynamic interpretation of the universal quantifier, together
with that of the existential quantifier and implication, allows us to deal
with the donkey-sentence (3) in the manner discussed at the beginning of
this section, is shown by working out the interpretation of a formula that
exhibits the relevant structure:
~Vx[[Px /x 3y[O s/x Rxy]] ~ Sxy]~ =

{(g, h)lh = g & Vk: k[x]h ~ 3rn: (k, m) E
~[Px /x 3y[Qy /x Rxy]] ~ Sxy~} =
{(g, g)lVk: k[x]g ~ (Vj: (k, j)
[[Px /~ =ly[Qy /x Rxy]]] ~ 3z: (j, z} e [[Sxy]])} =
{(g, g)lVk: l~[x]g & l¢(x) E F(P)
(W: j[y]k & j(y) ~ F(Q) & (j(x),j(y))
F(R) ~ (j(x), j(y)) E F(S))} =
{(g, g)lVh: h[x, ylg & h(x) ~ F(P) &
h(y) E F(Q) & (h(x), h(y)) ~ F(R) ~ (h(x), h(y)) E F(S)}
This example illustrates that the dynamic semantics of DPL enables us to
treat the more complicated type of donkey-sentences, too, in a straightfor-
ward, intuitive and compositional manner. D P L allows us to translate an
indefinite term uniformly as an existentially quantified phrase in situ, i.e.,
when and where we encounter it in a structure, without any need of re-
analysis. We can treat a pronoun which is anaphorically linked to such a
term simply as a variable corresponding to the quantifier. The dynamic
interpretation of the existential quantifier and of the implication, ensures
that the proper bindings result, and that the indefinite term has the re-
quired universal force.
52 J, GROENENDIJK AND M. STOKHOF
Within the limits set by a first-order language, the account we have

given above of cross-sentential anaphora and donkey-sentences, is as com-
positional as can be. Using D P L as our semantic representation language,
we can proceed to obtain representations of the meanings of simple natural
language discourses in an on-line, more or less left-to-right manner, guided
by the ordinary syntactic structures and the usual lexical meanings of the
phrases we encounter.
We conclude this section by stating the interpretation of negation and
disjunction. Negation is like implication and universal quantification in
that it, too, normally blocks anaphoric links between a term that occurs
in its scope, and a pronoun outside of it, i.e., negation is static. (More
on this in Section 5.1.) The following two examples illustrate this:
(7) It is not the case that a man walks in the park. *He whistles.
(8) No man walks in the park. *He whistles.
Hence, the interpretation of a negation ~ 4~ will be of the type of a test:

it returns an input assignment g iff q5 can not be successfully processed.
If q5 can be successfully processed with respect to g as input, g is blocked
by ~ 4~:
[[-n~bl]= {(g, h) lh = g & -7 3k: (h, k) E ~eh~}
The following example, which has the structure of such sequences of

sentences as (7) and (8), illustrates how negation works:
~ 3xPx A Qx~ =
{(g, h) 13k: (g, k) E ~ 3xPx~ & (k, h) • ~Qx~} =
{(g, h) 13k: (g, k) • ~-n 3xPx~ & h = k & h(x) • F(Q)} =
{(g, h) l(g, h) • ~ 3xPx~ & h(x) • F(Q)} =
{<g, h)Lh = g 8: ~ 3k: (h, k) • {(g, h)Jh[xlg
& h(x) • F(P)} & h(x) • F(Q)} =
{(g,h}lh = g & ~ 3 k : k[x]h & k(x) •
F(P) & h (x) • F(Q)} =
{(g, g) l ~ 3k: k[x]g & k(x) • F(P) & g(x) • F(Q)}
As we can see, the first conjunct, being a negation, does not change the
assignment with respect to which the second conjunct is interpreted. The
test-like character of a negation leaves the occurrence of x in the second
conjunct unbound by the existential quantifier which occurs within its
scope in the first conjunct. This means that, whereas 3xPx A Qx and
Qx /x 3xPx differ in meaning, ~ 3xPx A Qx is equivalent to Qx A -7 3xPx.
As for disjunction, it shares the feature of being externally static with
implication, negation and the universal quantifier. It, too, tests an input
assignment g, and the condition it embodies is that at least one of its

disjuncts be interpretable successfully with g as input. Only if this condition
is met, g is returned as output:
[[05 v ~O]]= {(g, h) lh = g & 3k: (h, k) ~ [[05~v <h, k) ~ ~ }

According to this interpretation of disjunction, no antecedent-anaphor
relations are possible between the disjuncts, i.e., disjunction is not only
externally, but also internally static. We will come back to this in Sections
4.3 and 5.1.
This concludes our introduction of the ingredients of DPL. In the next
section, we will present D P L more systematically, and investigate some
of the logical facts touched upon above in somewhat more detail.
3. D P L , A SYSTEM OF DYNAMIC PREDICATE LOGIC
This section is devoted to a formal study of the DPL-system. In Section

3.1, we present its syntax and semantics systematically. Section 3.2 con-
tains definitions of some basic semantic notions, such as truth and equiva-
lence. In Section 3.3, we turn to the subject of scope and binding, and in
Section 3.4, we state some logical facts. Section 3.5 is concerned with the
notion of entailment.
3.1. Syntax and Semantics
The non-logical vocabulary of D P L consists of: n-place predicates, individ-

ual constants, and variables. Logical constants are negation 7 , conjunction
A, disjunction v , implication -+, the existential and universal quantifiers
3 and V, and identity =.
D E F I N I T I O N 1 (Syntax).
1. If t, . . . . . t,, are individual constants or variables, R is an n-place

predicate, then R t , . . . t,, is a formula.
2. If tl and t2 are individual constants or variables, then t~ = t2 is a
formula.
3. If 05 is a formula, then ~ 05 is a formula.
4. If 05 and 0 are formulas, then [05 A 4'] is a formula.
5. If 05 and ~ are formulas, then [05 v q,] is a formula.
6. If 05 and 0 are formulas, then [05 --+ ~] is a formula.
7. If 05 is a formula, and x is a variable, then 3x05 is a formula.
8. If q~ is a formula, and x is a variable, then Vx(h is a formula.

9. Nothing is a formula except on the basis of 1-8.
So, the syntax of D P L is that of ordinary predicate logic.

A model M is a pair (D, F), where D is a non-empty set of individuals,
F an interpretation function, having as its domain the individual constants
and predicates. If a is an individual constant, then F(a) ~ D; if oz is an
n-place predicate, then F ( a ) C
C_ D". An assignment g is a function assigning
an individual to each variable: g(x) E D. G is the set of all assignment
functions. Next, we define [[t]]g = g(t) if t is a variable, and ~t~g = F(t) if t
is an individual constant. Finally, we define the interpretation function
{[ ]IDPL C G × G as follows. (As usual, we suppress subscripts and super-
scripts whenever this does not give rise to confusion.)
D E F I N I T I O N 2 (Semantics).
1. ~Rtl . . . tn~ = {(g, h)[h = g & ([[ttl], . . . . [[tn~h) ~ F(R)}.

2. [[h = t2~ = {(g, h)jh = g & ~ t ~ h = ~tz~h}.
3. [[-7 ~b]]= {(g, h}lh = g & ~ 3 k : (h, k) ~ [[qS]]}.
4. [[q5 A 0]] = {(g, h)13k: (g, k) E ~b~ & <k, h) ~ {[0]]}.
5. [[4~ v ~]] = {(g, h) lh = g & 3k: (h, k) ~ [[~h~ v (h, k) ~ [[0~}.
6. [[6 ~ t)]l = {(g, h) lh = g & Vk: (h, k) e {[qS~~ 3j: (k, j) e [[+l]}.
7. [[3xO~ = {(g, h)13k: k[x]g & (k, h) ~ [[4,11}.
8. [[Vx~b~ = {(g, h)lh = g & Vk: k[x]h ~ 3j: ( k , j ) E ~ch~}.
Besides the clauses that were discussed in the previous section, Definition
2 also contains a clause which gives the interpretation of identity state-
ments. It will come as no surprise that such statements are interpreted as
tests.
3.2. Meaning, Truth and Equivalence
The notion of the interpretation of a formula that the semantics of D P L

specifies, differs from the one we are familiar with from PL. The latter
can be given in the form of a recursive specification of a set of assignments,
those which satisfy a formula, whereas the semantics stated above defines
a recursive notion of a set of pairs of assignments, those which are proper
input-output pairs.
The notion of interpretation of PL brings along a notion of truth with
respect to an assignment which is defined as follows: q5 is true with respect
to g iff g is an element of the set denoted by 4~. In the present, essentially
richer scheme a similar notion can be defined. We call a formula true with
respect to an assignment g in a model M iff with g as input, it has an
output:
D E F I N I T I O N 3 (Truth). q5 is true with respect to g in M iff

3h: (g, h) E ~qS~a,,.
In terms of this notion, we define when a formula is valid and when it is

a contradiction:
D E F I N I T I O N 4 (Validity). q5 is valid iff VMVg: 0 is true with respect to

g i n M.
D E F I N I T I O N 5 (Contradictoriness). ~b is a contradiction iff VMVg: ch is

false with respect to g in M.
Notice that the interpretation of any contradiction is always the empty

set. For valid formulas things are different: no unique semantic object
serves as their interpretation. They either denote the identity relation on
G, or a certain extension of this. For example, Px v ~ Px always denotes
the set of all pairs (g, g), but 3 x [ P x v ~ Px] denotes the set of all pairs
(g, h) such that h differs at most with respect to x from g. Both formulas
are valid according to Definition 4, since both are true with respect to any
g in any M. So, whereas semantically there is only one contradiction,
there are many different tautologies. What distinguishes these can be
expressed in terms of the variables they bind.
The set of all assignments with respect to which a formula is true in M,
we call its satisfaction set in M, and we denote it by ' \ \ M':
D E F I N I T I O N 6 (Satisfaction set). \~h\M = {gl 3h: (g, h) ¢ ~b~M}.
So, truth with respect to g in M can also be defined as g E \~b\M, validity

as \&\M = G for every M, and contradictoriness as \qS\M = 0 for every M.
The notion of a satisfaction set is of the same type as the notion of
interpretation in PL. But truth conditions do not exhaust dynamic mean-
ing. The satisfaction set of a compound formula can not always be defined
in terms of the satisfaction sets of its compounds, it is determined by its
compositional interpretation in terms of the notion ~ l]. The latter gives
the building blocks of meaning. And meaning in its turn determines,
globally but not locally, what the truth conditions of compound ex-
pressions are.
These considerations make clear that the notion of equivalence of stan-

dard logic, that of two formulas having the same truth conditions, although
definable in D P L in terms of the notion of a satisfaction set, has only a
marginal role to play. We call it s-equivalence, and denote it by ~-,.':
D E F I N I T I O N 7 (s-equivalence). 4~-~, 0 @ VM: \q~\ M = \ 0 \ M.
Full equivalence of two formulas requires that their interpretations be the

same in every model. We call it equivalence simpliciter, and denote it by
D E F I N I T I O N 8 (Equivalence). 4)= 04::)VM: [[qS~M= [[O~g"
Of course, if two formulas are equivalent they will also have the same
satisfaction set, i.e. they will be s-equivalent:
F A C T 1 . ~b-~O~&-~sO.
The reverse does not hold. For example, 3xPx and 3yPy have the same
satisfaction sets, G or ft, but they differ in meaning, since they produce
different output assignments, viz., {hlh(x) E F(P)} and {hlh(y) E F(P)}
respectively. The first formula has the potential to bind free occurrences
of x in formulas to come, and the second has the potential to bind occur-
rences of y. We can formulate this in terms of the notion of the production
set of a formula, the set consisting of those assignments which are its
possible outputs, which we write as '/ /M':
D E F I N I T I O N 9 (Production set). 1~)1~, 1 7--. {hl3g: (g, h) ~ ~d)~M}.
Whereas the satisfaction sets of 3xPx and 3yPy are the same, their produc-
tion sets are different. If two formulas always have the same production
set, we call them p-equivalent, denoted by '-~p':
D E F I N I T I O N 10 (p-equivalence). ~b ~--p I/]~ ::} VM:/eh/M =/~1/M.
Of course, analogous to the previous fact, we have:
F A C T 2. ch -~ 0 ~ 4~ = p ~"
So, if two formulas have the same meaning, they always have the same
satisfaction set and the same production set. However, the reverse does
not hold:
F A C T 3. ~b = , to & & - p to ~ q5 = tO.
If two formulas always have the same satisfaction set and always the same
production set, this does not imply that they have the same meaning. So,
meaning can not be defined in terms of satisfaction and production sets.
Consider the following simple example. The two tautologies Px v ~ Px
and 3x[Px v - ~ P x ] both have the total set of assignments G as their
satisfaction set and as their production set. But, as we have seen above,
their meanings are different. The interpretation of the former is {(g, h)]g =
h}, and that of the latter is {(g, h)]h[x]g}.
We end this section with the definitions of two other notions that will
prove useful for what is to come.
As we have seen in the previous section, various kinds of DPL-formulas
have the characteristic that they do not pass on bindings created by ex-
pressions which occur in them. They function as a kind of 'test' in this
sense that they examine whether an input assignment meets a certain
condition, return it as output if it does, and reject it otherwise. Seman-
tically, they can be characterized as follows:
D E F I N I T I O N 11 (Test). 4) is a test iff VMVgVh: (g, h) ~ ~49~M~ g = h.
Notice that for a test q~ the definition of truth with respect to g given above
boils down to (g, g) E [[~b]]. Also, we observe that for tests equivalence, s-
equivalence and p-equivalence coincide.
F A C T 4. If ~b and to are tests, then: & -~, to <::>q5 -~ to<=>& %, to.
The notion of a test is a semantic one. A partial syntactic characterization

can be given as follows. In view of their semantic interpretation, atomic
formulas, negations, implications, disjunctions, and universally quantified
formulas are tests. Further, it holds that a conjunction of tests is a test.
We will refer to this syntactically delineated class of formulas as conditions:
D E F I N I T I O N 12 (Conditions).
1. If q5 is an atomic formula, a negation, a disjunction, or an implication,

then q5 is a condition;
2. If 05 and 0 are conditions, then [05 A ~] is a condition;

3. Nothing is a condition except on the basis of 1 or 2.
A n d we note the following fact:
F A C T 5. If 05 is a condition, then 05 is a test.
With the exception of contradictions, which have the e m p t y set as their

interpretation, and hence are tests, the syntactic notion of a condition
characterizes the semantic notion of a test:
F A C T 6. 05 is a test iff 05 is a condition or a contradiction.
3.3. Scope and Binding
A distinctive feature of D P L is that it allows for existential quantifiers to

bind variables which are outside their syntactic scope. In this section we
give a syntactic characterization of w h e n an occurrence of a variable is
b o u n d by an occurrence of a quantifier. This characterization will consist
of a simultaneous recursive definition of three notions:
• bp(05), the set of binding pairs in 05;

• aq(05), the set of active quantifier occurrences in 05;
• fv(05), the set of free occurrences of variables in 05.
A binding pair consist of a quantifier occurrence and a variable occurrence

such that the first binds the second. A n active quantifier occurrence is one
which has the potential to bind occurrences of the corresponding variable
further on. A free occurrence of a variable is one which is not in any
binding pair. T h e definition, which is a bit sloppy since we have refrained
from explicitly introducing a notation for occurrences, is as follows:
DEFINITION 13 (Scope and binding).
1. b p ( R h . . . . . t,,) =
a q ( R h . . . . . t,,) =
f v ( R h . . . . . t,,) = {ti[ti a variable}.
2. b p ( ~ 05) = bp(05)
aq(-q 05) =
f v ( ~ 05) = fv(05).
3. bp(05 A 0) = bp(05) U bp(O) U {(3x, x)13x e aq(05) a x E fv(O)}
aq(05 A g,) = aq(O) U {3x ~ aq(05) I3x (£ aq(4,)}
fv(05 A g,) = fv(05) U {x C fv(0) 13x ~ aq(05)}.
4. bp(4) v t)) = bp(4)) U bp(4,)

aq(4) v g,) = 0
fv(4) v +) = fv(4)) u fv(~).
5. bp(4)--+ ~) = bp(4)) U bp(4,) U {(3x, x)13x E aq(4)) & x E fv(0)}
aq(4) --+ 4,) = 0
fv(4) -+ 4J) = fv(4)) U {x ¢ fv(~)l 3x ¢ aq(4))}.
6. bp(3x4)) = bp(4)) U {{3x, x)lx ~ fv(4))}
aq(3x4)) = aq(4)) U {3x}, if 3x ¢ aq(4)), = aq(4)) otherwise
fv(3x4)) = fv(4)) minus the occurences of x in 4).
7. bp(Vx4)) = bp(4)) U {{Vx, x)lx ~ fv(~b)}
aq(Vx4)) =
fv(Vx4)) = fv(4)) minus the occurrences of x in 4).
The 'test'-like character of atomic formulas, negations, disjunctions, impli-

cations and universally quantified formulas, is reflected in the above defi-
nition by the fact that for such formulas 4), aq(4)) = 0, i.e., no quantifier
occurring in such a formula is able to bind occurrences of the correspond-
ing variable further on. Notice that if we conjoin two formulas which
each have an empty set of active quantifier occurrences, the resulting
conjunction has no active occurrences either. This reminds us of the notion
of a condition defined above. In fact, the requirement that aq(4))= 0
characterizes those 4) which are conditions, and hence it also characterizes
those 4) which are tests, with the exception of contradictions.
The extra(-ordinary) binding power of the existential quantifier, the fact
that it is externally dynamic, is reflected in Clause 6. The occurrence of
3x in 3x4) is added to the active occurrences of ~b, unless, of course, there
is already an active occurrence of that same quantifier in 4), in which case
the latter remains the active occurrence. It is precisely in this respect that
the binding properties of existential and universal quantification differ.
Only existential quantifiers can have active occurrences, and for any for-
mula, only one occurrence of a quantifier in that formula can be active.
That disjunction is internally static is reflected in the first line of Clause
4. The set of binding pairs of a disjunction is simply the union of the
binding pairs of its disjuncts. So, no binding relations are possible across
the disjuncts of a disjunction. In contrast to this, the binding pairs of a
conjunction or an implication are not simply obtained by putting together
the binding pairs of the constituent formulas; what is further added are
pairs consisting of active occurrences of quantifiers in the first conjunct or
in the antecedent, together with free occurrences of the corresponding
variables in the second conjunct or in the consequent.
In addition to the three notions just introduced, we define a fourth one,
which will turn out to be convenient when we c o m p a r e D P L and P L in

Section 4.1. It is the set of scope pairs, sp(4,), of a f o r m u l a 4':
DEFINITION 14 (Scope pairs).
1. s p ( R h . . . . . t,,) = ft.
2. s p ( = 4') = sp(4,).
3. sp(4, A q,) = sp(4,) U sp(~O).
4. sp(4~ v g,) = sp(O) U sp(4').
5. sp(4, -+ ~0) = sp(4,) tO sp(6).
6. sp(3x4,) = sp(4,) tO {(3x, x>lx ~ fv(~)}.
7. sp(VxqS) = sp(4') U {(Vx,x)lx ~ fv(4,)}.
W e note two things about this definition. First, if we replace the notion
fv(q~), the notion of a free variable in D P L as defined above, by the notion
fvpL(4,), the notion of a free variable in PL, we end up with the notion
of binding in PL. Secondly, concerning D P L itself again, the following
fact can be p r o v e d by simple induction:
F A C T 7. sp(4,) C_ bp(4,).
So, it is sufficient but not necessary for a variable to be b o u n d by a

quantifier that it occurs in its scope. O f course, in some cases, all variables
b o u n d by a quantifier are also inside its scope. This holds for e x a m p l e for
3x[Px /x Qx]: bp(3x[Px /x Qx]) = sp(3x[Px A Qx]). In Section 3.6, we
will show that for any formula q5 there is a formula 4,' which is equivalent
in D P L to qS, such that bp(4,') = sp(4,').
F o r some p u r p o s e s it is convenient to talk a b o u t the free variables of a
formula, rather than a b o u t their occurrences. W e will write the set of free
variables in 4, as 'FV(4,)':
DEFINITION 15. x E FV(4,) iff there is an occurrence of x in fv(qS).
F o r similar reasons, we introduce the notion of the set of variables x such

that there is an active occurrence of 3x in 4', and denote it as ' A Q V ( 4 ' ) ' :
DEFINITION 16. x E A Q V ( 4 ' ) iff 3x ¢ aq(4').
It is useful to point out the following two facts, which both can be p r o v e n
by simple induction on the complexity of 4' (by g = vv(e,) h we m e a n that
for all x E FV(4'): g(x) = h(x)):
F A C T 8. If g =vv(~) h, then VM: g E \q$\M <=~h E \¢h\M.
F A C T 9. If 3M: (g, h} E [[q$~M& g(x) 4: h(x), then x e AQV(~b).
Fact 8 says that if two assignments differ in that the one is in the satisfac-
tion set of a formula of, whereas the other is not, they should also differ
in the value they assign to at least one of the free variables of 4~. And
Fact 9 says that if two assignments which assign a different value to a
certain variable x form an input-output pair in the interpretation of a
formula ~b, then there is an active occurrence of the quantifier 3x in ~b.
3.4. Some Logical Facts
Let us now turn to an exposition of some basic logical facts, which will
illustrate various properties of DPL.
We start with the interdefinablity of the logical constants. A simple
calculation with the relevant clauses of Definition 2 shows that negation,
conjunction and existential quantification can be used as our basic logical
constants, the others being definable in terms of them in the usual way:
4, -.-, e- = -~ [,:/, A ~ ,/,]

d , v ,/,--~ ~ [ ~ 4, A ~,/,]
Vxd, = -n = l x ~ 4>
It should be noted, though, that contrary to what is the case in ordinary

predicate logic, a different choice of basic constants is not possible. The
following facts show that we cannot do with the universal quantifier and
disjunction, nor with the universal quantifier and implication:
3xd~ 4~ ~Vx-~ 4,
The reason for this is, of course, that the expressions on the right are
tests, which lack the dynamic binding properties of the expressions on the
left. In the first and in the last case, the satisfaction sets, i.e., the truth
conditions, of the expressions on the right and of those on the left indeed
are the same: they are s-equivalent. This does not hold in the second case,
because of the fact that disjunction is not only externally, but also intern-
ally static.
::[X¢~ = s - q V X q ¢~
Furthermore, we may note that, whereas disjunction can be defined in

terms of implication, the reverse does not hold:
4 ) ~ # , ~ ~4) v 0
Disjunctions and implications are both tests, they are externally static.
However, an implication is internally dynamic, i.e., an existential quan-
tifier in the antecedent can bind variables in the consequent. But no such
binding relations are possible between the disjuncts of a disjunction, the
latter being also internally static. This is also the reason why in the last
case not even the truth conditions of the expressions on the right and on
the left are the same: no s-equivalence obtains in this case:
4)~ ~4~,74) v 0
In some special cases, some of these non-equivalences do hold. For exam-

ple, if (and only if) 4)/x O is a test, it is equivalent with 7 [4) --~ -10].
And if 4) is a test, or more generally if no binding relations exist between
4) and qJ, i.e., if AQV(4)) 71FV(0) : 0, then 4)--+ 0 is equivalent with
7 4) v 0. Similarly, 3x4) is equivalent with ~ Vx -7 4) iff 3x4) is a test, which
it is only if 4) is a contradiction.
A relationship between the existential and the universal quantifier that
does hold unconditionally is:
7 :Ix4) -~ Vx -7 4)
Of course, this follows from the fact that negation turns anything into a
test.
From the latter observation, we may conclude that the law of double
negation will not hold unconditionally. Consider a formula 4) that is not
a test. Negating 4) results in the test ~ 4), and a second negation, which
gives -7-7 4), does not reverse this effect. And this seems correct, since a
doubly negated sentence in general does not allow subsequent pronouns
to refer back to elements in the scope of the negations. (But see Section
5.1 for some further discussion.) Precisely in this respect, 4) and -7~4)
may differ in meaning. However, as far as their truth conditions are
concerned, the two coincide, so 4) and -7 ~ 4) are s-equivalent. We can
formulate the following restricted versions of the law of double negation:
- 1 7 4) = 4) iff 4) is a test
Hence, double negation is not in general eliminable. The effect of applying
double negation is that the meaning of a formula is restricted, so to speak,
to its truth conditions. It is useful to introduce an operator, O, which

performs this function:
D E F I N I T I O N 17 (Closure). [[Q~b]]= {(g, h)lg = h & =lk: (h, k) E [[q)~}.
One can look upon ~ as a kind of assertion or closure operator. It can

be used to close off a piece of discourse, blocking any further anaphoric
reference, stating: this is how things stand.
We notice that the following hold:
~b -~ 7 -7 q5 ~- 4, i f f ~b is a test
In terms of the operator ~ we can also state the restricted versions of the
interdefinability of the logical constants discussed above:
O3xq~ -~ - T V x 7 4~
Let us now turn to some properties of conjunction. First of all, it can

be noticed that conjunction is associative:
[ 6 / , ~] A x-~ q~/, [~0 A x]

Notice that associativity holds despite the increased binding power of the
existential quantifier. This is so because if two conjuncts each contain an
active occurrence of the same quantifier, it is the rightmost one which is
active in the conjunction as a whole, the left one being 'de-activated'.
Compare [3xPx A 4'] A BxQx with BxPx A [~b A 3xQx]. The last occur-
rence of 3x is the active one. Hence, it is this occurrence that binds the
x in Hx, both in [ [ B x P x A O ] A 3 x Q x ] A H X , and in [BxPxA
[~b A BxQx]] A Hx. The structure of the respective conjunctions is irrelev-
ant in this respect.
Conjunction is not unconditionally commutative, however, as the simple
example of =IxPx A Qx and Qx A ::IxPx shows. In fact, the latter of these
two formulas is a counterexample against idempotency of conjunction as
well.
4~A 04~ 0 A 4,
,b4~ 6 A 4,
Of course, if both 4 and 4' are tests, commutativity holds, and if 4 is a

test idempotency holds:
o 4 A 04' = 04' A O 4
O 6 --~ O4) A O4'
That 4 is a test is not a necessary condition for idempotency of conjunction
to hold. It is sufficient that active occurrences of a quantifier in 4 are
unable to bind flee variables in 4:
AQV(&)aFV(4):00&-~4A4
This condition isn't a necessary one either, e.g. Px/x 3xPx~-
[Px A 3xPx] A [Px A 3xPx].
Similarly, 4 and 4' need not necessarily be both tests for commutativity
of conjunction to hold. An example of a conjunction which does not
consist of tests, but which nevertheless is commutative is BxPx A Qy,
which has the same meaning as Qy A 3xPx. Commuting this conjunction
does not interfere with its binding pattern. In general, if commuting the
conjuncts does not change the binding pairs, nor the active occurrences
of quantifiers in the conjunction, commutativity holds:
AQV(4) 71FV(4') = 0 ]
AQV(4')r~FV(4)=0 I~&A 4'--~4'/X4
AQV(4) 71AQV(4') = 0
In this case, too, the conditions are sufficient but not necessary. A case
in point is the contradiction [Px/x --nPx]/x 3xQx.
As is to be expected, disjunction, being both internally and externally
static, is unconditionally idempotent, commutative and associative:
4--4v4
4v 4'=4'v4
4 v [4' v x]--- [4 v 4'] v x
Idempotency and commutativity of disjunction reflect that there cannot
be any anaphoric relations across disjuncts. (But see Sections 4.3 and 5.1
for some discussion.)
As for the classical de Morgan laws, DPL validates the following:
o [ 4 A [4' v xll -~ [6 A 4'1 v [6 A x]

4 v [O4'A X]--~ [4 v 4'1A D V X ]
The latter is a special instance of:
AQ(4')I"IFV(x ) = 0 ~ 4 V [ 4 ' A X ] = [ 4 V ~] A [6VX]
Turning to implication, we may observe that the following form of

contraposition goes through unconditionally:
[-~ 4, ~ Ol = [-~ ~ 4,1

But for the general case we need, again, the condition that no binding
pairs are distorted:
[04, ~ o] - [-~ ~ ~ ~ 4,]
AQV(4,) 71 FV(0) = 0 ~ [4, ~ 4'] = [-7 0 --+ ~ 4,]
The reason that we need a condition here, is that quantifiers in the
antecedent of an implication may bind variables in the consequent. Impli-
cations, as we noted repeatedly, are internally dynamic. But no outside
binding effects are permitted, they are externally static, and this is re-
flected in the following two equivalences:
[4'-+ 0] -- 0 [ 4 , - - , 01
[4,--, 0] = [4, ~ ~ o ]
The first equivalence is another way of saying that an implication is a test,
the second expresses that an implication turns its consequent into a test.
A last fact concerning implication that we want to note, is the following:
4,-,,[4,~x1 - [4, A ~ , ] ~ x
Finally, we notice some facts concerning the interplay of quantifiers and
connectives:
3x4, A 0-~ 3x[4, A ~]

x ~ (FV(4,) U AQV(4,)) ~ 4, A 3xO-~ 3x[4, A ~]
The first fact illustrates the dynamics of the existential quantifier: its
binding power extends indefinitely to the right. This is what makes D P L
a suitable instrument for the representation of antecendent-anaphor re-
lations across sentence boundaries. The second fact states under which
condition the scope of an existential quantifier may be extended to the
left in a conjunction: under the usual condition that the left conjunct has
no free occurrences of x, and further that the active occurrence of 3x is
not 'de-activated' by an occurrence of that same quantifier in the first
conjunct.
The following equivalence is important for the analysis of 'donkey'-like
cases of anaphora:
3x4,--> O = Vx[ 4, ~ 4,]

Existential quantifiers in the antecedent of an implication may bind occur-
rences of variables in the consequent, and they have 'universal' force.
One final observation:
3xq5 4~ 3y[y/x]ch
Here, [y/x]ch denotes, as usual, the result of replacing all free occurrences
o f x in q5by y. This non-equivalence illustrates the fact that bound variables
in D P L are 'more meaningful' expressions than in PL. Notice that 3x4~
and 3y[y/x]O are s-equivalent if no occurrence of y that is free in 3xq5 is
bound in 3y[y/x] c~:
y ¢ FV(40 ~ 3x~b -~s 3y[y/x]d)

The above observations mark some of the ways in which the dynamic
semantics of D P L differs from the ordinary, static interpretation of PL.
A more detailed comparison can be found in Section 4.1.
3.5. Entailment
In standard logic, 4~ entails 0 iff whenever 4~ is true, 0 is true as well.
Since we have defined a notion of truth in DPL, we can also define an
analogue of this notion of entailment for DPL. We will refer to it as
s-entailment, and write it as '~s':
D E F I N I T I O N 18 (s-entailment). 4~ ~s ~ iff VMVg: if ~b is true with respect

to g in M, then 0 is true with respect to g in M.
In other words, 4~ s-entails 6 iff VM: \qS\M C_\O\~. Obviously, s-equiva-

lence as it was defined above, is mutual s-entailment.
Unlike the notion of entailment in PL, in D P L the notion of s-entailment
does not coincide with that of meaning inclusion, which is denoted by ' 4 ' :
D E F I N I T I O N 19 (Meaning inclusion). ~b ~< 0 iff VM: [[~b~MC_ ~0]M.
In DPL, meaning is a richer notion than in PL, where interpretation and

satisfaction coincide. Meaning inclusion implies s-entailment, but not the
other way around:
F A C T 10. qS~ 0 ~ q S ~ , 0 .
The notion of equivalence -~ defined in Section 3.2 is nothing but mutual

meaning inclusion.
In an important sense, the notion of s-entailment is not a truly dynamic
notion of entailment. One way to illustrate this, is to point out the fact
that the notion of s-entailment does not correspond in the usual way to
implication. For example, although it holds that G 3 x P x - + Px, we have
3xPx ~s Px. Whereas in an implication an existential quantifier in the
antecedent can bind variables in the consequent, the notion of s-entailment
does not account for similar binding relations between premiss and con-
clusion. However, in natural language, such relations do occur. From A
man came in wearing a hat, we may conclude So, he wore a hat, where
the pronoun in the conclusion is anaphorically linked to the indefinite
term in the premiss. As we have just seen, if we want to account for this,
the notion of s-entailment is not the one we are after. For similar reasons,
meaning inclusion is not what we are looking for either. It is too strict:
3 x P x 4~ Px. And it is also not strict enough. For <~ is reflexive, but, as is
argued below, dynamic entailment is not: Px A 3 x Q x does not entail
Px A 3xQx.
Hence, we have to find another, an inherently dynamic notion of entail-
ment. Taking up our processing metaphor once more, which means look-
ing at sentences as a kind of programs, a reasonably intuitive notion is
the following. We say that 05 entails 0 if every successful execution of 05
guarantees a succesful execution of ~. Or, to put it slightly differently, 05
entails 0 iff every assignment that is a possible output of 05 is a possible
input for 0. This is captured in the following definition of dynamic entail-
ment:
D E F I N I T I O N 20 (Entailment).
05 ~ t) iff VMVgVh: (g, h) ~ [[05]]M~ 3k: (h, k) ~ I[~M.

Using the notions of satisfaction set and production set, we can write this
more economically as:
05 ~ 0 iff VM:/05/M C_\ 0\ M

As requested, the notion of dynamic entailment corresponds in the
usual way to the interpretation of implication:
F A C T 11 (Deduction theorem). 05 ~ 0 iff ~ 05 -+ 0.
Entailment is related to s-entailment in the following way:
F A C T 12. 05 G t) iff ~ 05 ~ t).
More generally, entailment and s-entailment coincide if no binding

relations exist between premiss and conclusion:
68 J. GROENENDIJK AND M, STOKHOF
F A C T 13. If AQV(05) n FV(0) = 0, then: 05 ~s 0¢::~ 05 ~ 0-
We note further that mutual entailment of 05 and ~ does not mean that
05 and ~ are equivalent. For example, 3xPx and Px do entail each other,
but they are not equivalent. The same pair of formulas illustrates that
entailment does not imply meaning inclusion. And the reverse does not
hold in general either. For example, the meaning of Qx/x 3xPx includes
the meaning of Qx/~ 3xPx, but the latter does not entail the former.
Meaning inclusion does imply entailment if there are no binding relations
between premiss and conclusion:
F A C T 14. If AQV(05) n FV(0) = 0, then: 05 ~ 0 ~ 05 ~ ¢).
In the proof of this fact, the two Facts 8 and 9 stated in Section 3.3 play
a central role. Suppose AQV(05) n FV(0) = ~ and 05 ~< 0. Let h ~/05/m,
that is 3g: (g, h) E ~05~M. Since, if (g, h) E [[05~M, then h[AQV(05)]g (Fact
9), and AQV(05) n FV(0) = 0, it holds for all x E FV(~) that g(x) = h(x).
Since 05~< 0, it also holds that (g, h ) E ~O~M, and hence that g ~ \~\M.
From g(x) = h(x) for all x ~ FV(¢)), and g E \0\M, we may conclude on
the basis of Fact 8 that h E \¢)\ M as well.
Precisely because the notion of entailment is truly dynamic in the sense
that it allows active quantiflers in a premiss to bind variables in the
conclusion, it lacks some properties which more orthodox notions, such as
s-entailment, do have, notably the properties of reflexivity and transitivity.
We already encountered a typical counterexample to reflexivity of dy-
namic entailment in the formula Px/x 3xQx, which does not entail itself.
The reason is that in the occurrence of this formula as a conclusion, the
variable x in the first conjunct gets bound by the quantifier in the occur-
rence of the formula as a premiss, whereas in the occurrence of the
formula as a premiss it is free. The following restricted fact about reflexiv-
ity, however, does hold as an immediate consequence of Fact 14 and the
reflexivity of 4 :
F A C T 15 (Reflexivity). If AQV(05) n FV(~b) = 0, then 05 ~ 05.
The condition on reflexivity given here is a sufficient, but not a necessary

one. For example, the formulas Px/x 3xPx, and Px A 3xPx/x Qx, both
do entail themselves. Conditions similar to the one on reflexivity can be
laid upon other facts about entailment known from ordinary predicate
logic, in order to accommodate them to DPL. An example is the following:
If AQV(t)) n FV(~0) = ~, then 05/x ~0~ ¢)

We mention in passing that if one would use D P L for practical purposes,

one would certainly choose active quantifiers and free variables in such a
way that these troublesome cases are avoided.
Not only reflexivity, but transitivity, too, may fail when free occurrences
of variables in a conclusion, are bound by a premiss. If we arrive at a
conclusion X in several steps 01 • • • ~. from an initial premiss 4~, we cannot
simply omit these intermediary steps, and conclude immediately from ~b
to X. Roughly speaking, we first have to m a k e sure that there are no
antecedent-anaphor relations between one of the intermediate steps and
the conclusion which are not due to a similar relation between premiss
and conclusion. For example, although -1 ~ 3xPx ~ 3xPx, and 3xPx ~ Px,
we notice that -7 -n 3xPx ~ Px.
The cases which present problems for transitivity can be characterized
as follows. Suppose q5 ~ ~ and ~O~ X. If we want to conclude from this that
q5 ~ X, then problems may arise if x E F V ( x ) and x E AQV(O). Consider
again -7 ~ 3xPx, 3xPx, and Px. Clearly, the first entails the second, and
the second entails the third, without the first entailing the third. On the
other hand, consider 3xPx, 3xPx, and Px, or 3xPx A Qx, 3xPx, and Px.
These are two cases where nothing goes wrong. So, not all cases where X
contains a free occurrence of x, and ~ contains an active ocurrence of 3x
are to be excluded. Evidently, what also matters is what 4~ 'says' about x,
in the dynamic sense of what constraint it puts on whatever free occur-
rences of x that are still to come. Roughly speaking, what q5 says about
variables which occur freely in X and which are bound by ~, should be at
least as strong as what ~ says about them. So, what is needed is a stronger
version of the notion of entailment that covers the condition that the
premiss puts at least as strong a condition on certain variables as the
conclusion does. This notion can be defined as follows, where by
'h =x~ . . . . . g' we m e a n 'h(x~) = g(xl) & . . . & h(xn) = g(x~)':
D E F I N I T I O N 21 (xi •. • xn-Entailment).
q5 ~xl . . . . . ~ iff VMVg: g E/ch/M ~ 3h: (g, h) ~ ~O~M

& h =xl . . . . . g
Notice that (~Xl . . . . ~t implies that 4 ~ 0, and that if n = 0 , then

(~ ~Xl ...... I/1 collapses into q5 ~ 0.
Now we are ready to state the following fact:
F A C T 16 (Transitivity). ~b )AQV(O)NFV(x) ~J • ~t ) X ~ (} ~ X.
The p r o o f of this fact runs as follows. Suppose g E/~)/M. Then

70 j. GROENENDIJK AND M. STOKHOF
3h: {g, h) ~ [[O~M, and for all x E A Q V ( x ) rq FV(~), it holds that g(x) =
h(x). Since 0 k X, it holds that h ~ \X\M. For any variable x E FV(x), if
x ~ AQV(40 then g(x) = h(x) by assumption; but if x ~ AQV(O), then
also g(x) = h(x), since (g, h} E I[0I]M (use Fact 9). Hence, we have g(x) =
h(x) for all variables x E FV(x), and hence g ~ \X\M (Fact 8).
The above shows that there are some complications inherent in the
notion of dynamic entailment. These do pay off, however. We can trans-
late 'natural language' reasonings in which pronouns are introduced in
intermediary steps, directly into DPL. Consider the following, admittedly
stylized, example and its translation into DPL:
1. It is not the case that nobody walks and talks ( ~ 3x[Px a Qx]).
2. So, somebody walks and talks (3x[Px A Qx]).
3. So, he walks (Px).
4. So, somebody walks (3xPx).
5. So, it is not the case that nobody walks ( 7 -q 3xPx).
The interesting bit is the step from 2 to 3. The pronoun he occurring in

3 is bound by somebody in 2. So, although 1 implies 2, and 2 implies 3,
1 does not imply 3, precisely because 1 cannot, and should not, bind the
pronoun in 3. But in the transition from 2 via 3 to 4, 3 can be omitted.
And the same holds for all other intermediate steps. So, in the end, 5 is
a consequence of 1.
Up to now, we have only discussed entailment with respect to a single
premiss. It makes sense to generalize the definition of entailment given
above in the following way:
D E F I N I T I O N 22 (Entailment, general form).
05t,..., 05,,P Oiff V M V h V g , . . . g , , : <g,,g2} ~ ~051~m& . . .

& (g,,, h} e ~05,,~M~ 3k: <h, k} e ~O~M
Notice that it is not a set, but a sequence of formulas, a discourse, that
can be said to entail a formula. In view of the above, this is not surprising.
What holds, of course, is:
05,. . . . . 05n P Oiff 05t A . . . a 05,, ~ Oiff ~ [05, A . . . A 05,,1--> ~

Since the order of the conjuncts matters for the interpretation of a conjunc-
tion, so will the order of the premisses matter for entailment. For example,
although 3xPx, 3xQx ~ Qx, we have 9xQx, 3xPx ~ Qx. Further, we note
that in a certain sense dynamic entailment is not monotonic. Whereas it
holds unconditionally that if 05 ~ ~p, then X, 05 ~ ~, we may not always
conclude from 05 ~ ~0 that 05, X ~ ~. The reason for this being, again, that
X may interfere with bindings between ~b and ~, for example, it does hold
that 3xPx ~ Px, but we have 3xPx, 3xQx ¢:Px.
Again, for practical purposes these complications can be evaded by a
suitable choice of active quantifiers and free variables. For example, in
adding a premiss which contains an active quantifier, we better choose
one which does not already occur actively in one of the other premisses.
Such practical considerations are particularly important in designing a
proof system. In cooperation with Roel de Vrijer, a sound and complete
system of natural deduction for D P L is being developed, which we hope
to present in a separate paper.
4. COMPARISONS
In Section 4.1, we compare D P L with ordinary predicate logic. In Section

4.2, the relation between D P L and D R T is discussed. And in Section 4.3,
we turn to a comparison of D P L with quantificational dynamic logic.
4.1. DPL and PL
In discussing some basic logical facts concerning DPL, we have noticed a

number of differences between D P L and PL, all arising from the essen-
tially richer notion of binding of the former. In this section we show that
this is indeed exactly the point at which the two systems differ. First we
show that for any formula q5 there is a formula ~b' which is DPL-equivalent
to ~b, in which all variables bound by a quantifier are brought under its
scope, i.e., for which it holds that bp(~b') = sp0b' ). Then we show that
for any formula 4~ such that bp(qS) = sp(qS), the truth conditions of ~b in
D P L and in PL coincide. If we put these two facts together, it follows
that for any formula q5 there is a formula ~b' which is equivalent to it, and
for which it holds that its truth conditions in D P L and PL are the same.
We already noticed above that the satisfaction set of a DPL-formula,
the set of assigments with respect to which it is true, is the same type of
semantic object as the PL-interpretation of a formula. Because PL and
D P L have the same syntax, we may speak of the PL- and the DPL-
interpretation of one and the same formula.
We first define the semantics of PL in the same kind of format we used
for the semantics of DPL. PL-models are the same as DPL-models, as
are assignments and the interpretation of terms. The definition of the
interpretation function [[ ]]~tL C G is as follows. (We drop subscripts when-
ever this does not lead to confusion, and we continue to use '[[ ]]' without
a superscript to denote interpretation in DPL.)
D E F I N I T I O N 23 (PL-semantics).
1. [[Rh . . . tn~PL = {gl (~tl]]g . . . [tn]~g) E F(R)}.

2. [[tt = t2]]eL = {gl l[h]]g = [[t2l]g}.
3. [[-7 4,11PL = {gl g ~ [¢~PL}.
4. ~¢ v +~PL = {gig ~ [¢~PL v g E [[O]]PL}.
5. [[4~~ ~#]]PL= {gl g E [[~b]]PL ~ g E ~#]]PL}.
6. ~b A +~PL = { g i g ~ [¢~PL & g E [[o~PL}.
7. [[qx¢]]PL = {glqk: k[x]g a k e ~b~eL}.
8. ~ V X ( ~ PL = {gl Vk: k[xlg ~ k C ~q~PL}.
The set of assignments which is the interpretation of a formula, consists

of those assignments which satisfy the formula: we call ¢ true with respect
to g in M iff g E ~¢~PL.
The satisfaction set \~b\ of a formula in D P L , and its interpretation
{[0~PL in PL are both sets of assignments. But the satisfaction set of a
formula need not be the same as its PL-interpretation. For example, the
satisfaction set of 3 x P x / x Q x is not identical to its PL-interpretation.
However, for the formula 9 x [ P x / x Qx], which is equivalent to 3 x P x / ~ Q x
in DPL, it does hold that its satisfaction set and its PL-interpretation are
the same. The difference between the two is that in the latter all occur-
rences of x which are bound by the existential quantifier are also brought
in its scope. Similarly, the satisfaction set and the PL-interpretation of
3 x P x ~ Q x are different, whereas the satisfaction set and the PL-interpre-
tation of V x [ P x ~ Qx], which is equivalent in D P L to 9 x P x - + Qx, are
the same. Again, the difference between the two is that in the latter case
all bound variables are brought under the scope of a quantifier.
In fact, for every formula ¢ there is a formula ¢' which is equivalent
to ~b in D P L such that in rh' all variables which are bound by a quantifier,
occur in its scope. We define a recipe b which provides us with such a
variant for every formula. We will call b~b the normal binding f o r m of ¢:
D E F I N I T I O N 24 (DPL normal binding form).
1. b R h . . . tn = Rtt . . . t,.
2. b ( h = t.) = (tl = tn).
3. b - 7 ~ ' = T b O.
4. b[01 v 02] = [bO, v b~2].
5. b 3 x ~ = 3 x b ~ .
6. b V x O = V x b ~ .
7. b [ + t A ~2] =
(a) b[xt A [X2 A $2]] if qJl = [X~ A X2].
(b) [ 3 x b [ x A ~2]] if O~ = 3xx.

(C) [ b ~ l A bff.t2] otherwise.
8. b [t~l - + ~2] =
(a) b[x, + [)(2 -+ ~/2]] if 0l ~-- [,)(i A X2].
(b) [Vxb[x--+ ~.t2]] if e, = 3xx.
(c) [bg'l --+ b~92] otherwise.
The interesting bit in this definition are Clauses 7 and 8. Clause 7(a)
rebrackets complex conjunctions in such a way that all closing brackets
are moved to the right end side. For example, [[Px A Ox] A Rx] is turned
into [Px A [Ox A Rx]], and [[[Px A Ox] A Rx] A Sx] is first turned into
[[Px A Qx] A [Rx A Sx]], and then into [Px A [Qx A [Rx A Sx]]]. Clause
7(b) moves existential quantifiers which are inside the first conjunct of a
conjunction, outside that conjunction. For example,
b[[3xPx A 3yQy] A Rxy] = b[3xPx A [3yQy A Rxy]] =
3xb[Px A [3yQy A Rxy]] = 3x[bPx A b[ 3yQy A Rxy]] =
3x[Px A 3y[Qy A Rxy]].
The workings of 7(a) and 7(b) make sure that after repeated application,
one will always end up with a conjunction of which the first conjunct is
neither a conjunction, nor an existentially quantified formula, i.e., it will
be a condition. That is when Clause 7(c) applies. Clause 8 defines an
analogous procedure for implications. Notice that all clauses leave the
length of the formula unchanged. A proof that the recipe will always
terminate can easily be given.
Now, we prove the following fact:
F A C T 17. For all formulas th: O = bch.

The proof is by induction on the length of 4~. For the cases which concern
the Clauses 1-6, 7(c) and 8(c), the proof is trivial. For the Clauses 7(a)
and (b), and 8(a) and (b), it suffices to point out the following four DPL-
equivalences:
[,~,, ~] A x = 4, A [ ~ A x ]
3xcb/, ~, = 3x[ch/, 0]
[O A ~] --'x-~ ~--" [ ~ - - ' x ]
3 x ~ --, ~ Vx[4, --, ~]
=
Next, we show that when a formula is brought in normal binding form,

all variables bound by a quantifier are in its scope:
F A C T 18. bp(bqS) = sp(bch).
The proof is by induction on the length of qS.

Clauses 1-6 are simple. For 7(a) we only need to remark that
bp([x1/x X2]/x ~2) = bp(x1/x [X2 A ~2]), as can be seen from Definition
13. Similar observations can be made for 7(b), 8(a) and 8(b).
The crucial clauses are 7(c) and 8(c). Consider Case 7(c); i.e.
q~ = I/t1 A ~t2 and b~b = b O l A b 0 2 . We have bp(bOl A b 0 2 ) =
b p ( b O 0 U bp(b~2) U {(3x, x)] 3x ¢ aq(bOx) & x ¢ fv(bO2)}. Since in this
case b0~ can not be a conjunction or an existentially quantified formula,
it holds that aq(b~0,) = 0. This means that in this case bp(b01 A bO2) =
bp(bO 0 U bp(b~02). By induction, b p ( b O 0 = sp(bg, l) and bp(bO2) =
sp(bO2). Hence, bp(bO~/x bO2) = sp(bOl) U sp(bO2). And according to
the definition of sp, the latter is the same as sp(b~0t A btP2). For 8(c) a
similar reasoning can be given.
Now we show that for any formula in which all variables which are
bound by a quantifier are inside its scope, it holds that its satisfaction set
and its PL-interpretation coincide:
F A C T 19. If bp(4~) = sp(qS), then VM: \qS\M = ~qS~t'.
The proof proceeds by induction on the length of ~b.

Obviously, it holds for atomic formulas. And for all but the internally
dynamic connectives -~ and A, the result follows by a straightforward
induction. For example: let q5 = 3x4,, and suppose b p ( 3 x O ) = sp(3xO).
This is the case iff bp(O) = sp(O). Now,
\ 3 x 0 \ = {g[ 3k: k[x]g & 3h: (k, h) ~ ~0]~} =
{gl 3k: k[xlg & k~ \ ~\ }
By induction the latter is the same as:

{gl 3k: k[xlg & k E [[~PL}
which in turn equals:
~3x01] PL
The case of ~ is slightly more complex. Let q5 = ~0-*X. Suppose

bp(~--+X) = sp(~-+X). In other words, bp(~) = sp(~), bp(A~) = sp(x),
and if 3x E aq(qJ), then x ¢ fv(x). We also know that:
\0~x\ = {g] Vh: (g, h) ~ ~4,~ ~ h E \X\}

It follows by Facts 8 and 9 from Section 3.3 that this is equal to:
{g] Vh: (g, h) e ][0~ ---~g e \X\}
For, by Fact 9, g and h differ only in variables which have a correspond-

ing active occurrence in 0. By our assumption that bp(O--+ X) = sp(O ~ X),
these variables do not occur freely in ~v, whence it follows by Fact 8 that
if h C \X\, then g E \X\.
The above, in its turn, is equal to:
{gl g E \4,\ ---,g E \ x \ }

Applying induction, we see that this is the same as:
{gl g E ~0~eL ~ g E ~,¥~PL}
which equals:
~4, - , x~ PL
We end the proof by noting that for the remaining case of 4) = O/~ X, the
proof proceeds in a similar fashion.
From Facts 18 and 19 it now follows that:
F A C T 20. VM: \b4)\ = ~b4)~1"I-.
And putting the latter fact together with Fact 17 we get:
F A C T 21. For any formula 4) there is a formula 4)' such that VM: ~4)~4 =
~4)']]M, and \4)'\M = [[4),]]PL.
Moreover, we also have that:
F A C T 22. For any formula 4) there is a formula 4)' such that

VM: ]4)~} = ~4)'~}, and ~4),~L = \4)'\M.
It is easy to see that this holds. In PL any formula 05 is equivalent to a

formula # 4) in which all occurrrences of A, --+ and 3x are eliminated in
favour of v , 7 and V. Clearly, b p ( # 4 ) ) = sp(#4)). Hence, by Fact 19,
\ =~4)\~I = [=~:4)~PML, for all M.
Finally, we note the following:
F A C T 23. If bp(4)) = sp(4)), then PPL 4) iff kDPL 4).
This follows directly from Fact 19.

Summing up:
F A C T 24. For any formula 4):
1. There is a formula 4)' such that )DPL 4) iff ~DPL 4)' iff ~PL 4)"
2. There is a formula 4)" such that ~PL 4) iff ~PL 4)" iff ~DPL 4)"-
4.2. D P L a n d D R T
In this section we compare the language of D P L with what corresponds to

it in Kamp's D R T , viz., the language in which the discourse representation
structures (DRS's) are formulated. D P L is intended to be 'empiricallly
equivalent' to DRT: it was designed to deal with roughly the same range
of natural language facts. The difference between the two approaches is
primarily of a methodological nature and compositionality is the watershed
between the two. Therefore, besides giving a formal comparison of the
logical languages of the two systems in the present section, we shall also
discuss the matter of compositionality in somewhat more detail in Section
5.2.
The DRS-language and the language of D P L differ in several respects.
First of all, in the DRS-language, a syntactic distinction is made between
c o n d i t i o n s and DRS's. It is by means of the latter, that natural language
sentences and discourses are represented; conditions are elements out
of which DRS's are constructed. In other words, conditions occur as
subexpressions of DRS's. Corresponding to this syntactic distinction, there
is a semantic one. Conditions are interpreted in terms of their truth
conditions, DRS's are interpreted in terms of their v e r i f y i n g e m b e d d i n g s .
A second difference between the DRS-language and the language of
D P L is that the former contains negation, implication and disjunction, but
not conjunction and no quantifiers. The basis of the DRS-language is
formed by a set of atomic conditions. Further, there is a single, non-
iterative rule which has DRS's as output: DRS's are formed by prefixing
a number of variables to a number of conditions. This rule is to compen-
sate D R T ' s lack of conjunction and quantifiers. The prefixed variables
function as D R T ' s quantification mechanism, and the conditions to which
they are prefixed can be viewed as the conjunction of those conditions.
These conditions can be either atomic or complex. Complex conditions
are in turn built from DRS's by means of the connectives. Negation turns
a DRS into a condition, implication and disjunction take two DRS's and
deliver a condition.
Choosing a format that resembles as closely as possible that of DPL,
the syntax and semantics of D R T can be defined as follows. The non-
logical vocabulary consists of: n-place predicates, individual constants,
and variables. Logical constants are negation 7 , disjunction v , implication
---~, and identity =. The syntactic rules are as follows:
D E F I N I T I O N 25 (DRT-syntax).
1. If h . . . tn are individual constants or variables, R is an n-place

predicate, then R h • • • tn is a condition.
2. If tl and t2 are individual constants or variables, then tl = t2 is a

condition.
3. If 05 is a DRS, then -n 05 is a condition.
4. If 05 and 0 are DRS's, then [05 v 0] is a condition.
5. If 05 and 0 are DRS's, then [05 ~ 0] is a condition.
6. If 051... 05~ (n ~>0) are conditions, and X l . . . X k are variables
(k/> 0), then [ x 1 . . . x k ] [ 0 5 ~ . . . 05,,] is a DRS.
7. Nothing is a condition or a DRS except on the basis of 1-6.
Models for the DRS-language are the same as those for DPL, as are
assignments and the interpretation of terms. Parallel to the syntactic dis-
tinction between conditions and DRS's, the semantics defines two notions
of interpretation. First of all, we define an interpretation function
[[ ~ t Rs C_ G x G, for DRS's. Here, '(g, h) ~ [[05]]DRS, corresponds to the
DRT-notion 'h is a verifying embedding of 05 with respect to g'. Since
DRS's are built up from conditions, we also need to define a notion of
interpretation of conditions: ~ ]]Cone
~ C_ G, where ,g E ~05~Cond, corresponds
to the DRT-notion '05 is true with respect to g'. So, DRS's receive the
same type of interpretation as DPL-formulas. In one respect our definition
of these notions differs from the one given in DRT: we prefer assignments
to be total functions rather than partial ones. This is no matter of principle.
Just as is usually done in D R T , we could rephrase the semantics of D P L
in terms of partial assignments.
The simultaneous recursive definition of the notions [[ ~C/ond and
] ] ~ s runs as follows (where we drop subscripts again, whenever this
does not lead to confusion):
D E F I N I T I O N 26 (DRT-semantics).
l. [ R h . . . tn~C°nd = {gl @ l ~ g . . . ~tn~g) ~ F(R)}.
2. ~t~ = t2]]c°"° = {gl ~tt~g = [t2~g}.
3. [[--'1(]~Cond = {gi 7 3h: <g, h) ~ ~o~DRS}.
4. ~05 v t/t~C°nd = {gl 3h: <g, h) e [[6] DRS v (g, h) e [[[]/~DRS}.
5. ~05--+ O]]c°nd = {gl Vh: (g, h) ¢ ~05~DRS~ 3k: (h, k) ~ ~o~DRS}.
6. [[[Xl. . . X k ] [ 0 5 1 . . . 05n]~ DRS =
{ ( g , h)[ h [ x l . . . x k ] g • h ~ ~051~C°nd ~ . . . ~ h ~ ~05n~C°nd}.
In order to make clear in what sense the set of variables introduced in

Clause 6 functions as D R T ' s quantification mechanism, we first define the
notion of a DRS being true with respect to an assignment in a model:
D E F I N I T I O N 27 (Truth in D R T ) . A DRS 05 is true w i t h r e s p e c t to g in

M iff 3h: (g, h) E [[&]]DRS.
So, the notion of truth for DRS's is the same as the notion of truth in
DPL. And from Definition 27 we see that the variable set in a DRS
behaves like existential quantification over these variables. A simple DRS
like [x][Px, Qx] has the same truth conditions as the formula 3x[Px A Qx]
in PL and DPL. Moreover, the interpretations of this DRS and of the
DPL-formula are also the same. To give another example, the DRS
[x,y][Px, Qy, Rxy] has the same meaning as the DPL-formula
3x3y[Px A Qy A Rxy].
Notice that DRS's can also be built from conditions by means of empty
DRS-quantification. For example, [ ][Px] is a DRS, and its interpretation
according to Definition 26, is {(g, h)l h[ ]g & h(x)~ F(P)}. Now, h[ ]g
means the same as h = g, so the 'atomic DRS' [ ][Px] and the atomic
DPL-formula Px have the same interpretation. In fact, this procedure can
be applied to turn any DRT-condition into a DRS, giving it structurally
the same interpretation as the corresponding DPL-condition.
The interpretation of a DRS, being the same kind of object as the
interpretation of formulas in DPL, is of a dynamic nature. The dynamics
of DRS's is put to use in the interpretation of implications (and nowhere
else, by the way). For example, the DRT-condition [x] [Px] ~ [ ][Qx] has
the same truth conditions as the DPL-formula 3xPx--~ Qx. This, of
course, is the key to D R T ' s successful treatment of donkey-sentences.
Having made these observations, we now turn to the definition of a
translation from the DRS-language into that of DPL. We translate both
DRS's and DRT-conditions into DPL-formulas. Blurring the syntactic and
semantic distinction between DRS's and conditions in this way is justified,
since DRT-conditions will translate into DPL-conditions, and the latter
are tests, i.e., their meaning and truth conditions in D P L are one-to-one
related. The translation t05 of a DRS or a condition 05 is defined as follows:
D E F I N I T I O N 28 ( D R T - t o - D P L translation).
1. t R h . . . t , = R h . . . t , .
2. t(tl = t.) = (h = t.).
3. t ~ @ = ~ t O .
4. t[Ot v ~21 = [t@~ v t02].
5. t[@l --> @21 -- [t@~ ~ ]'@21.
6. t [ x l . . , x~][@, . . . 0~] ----3 X l . . . 3xk[t@, A . . . A t@.].
We prove that our translation is meaning-preserving in the following

sense:
F A C T 25
1. If 05 is a condition, then V M : ~05]]CM°nd ~---\t05\M.

2. If 05 is a D R S , then VM: ~05]]~RS = ~t05~M.
This fact is p r o v e n by induction on the complexity of 05. F o r the Clauses

1-5 of Definition 25, which build D R T - c o n d i t i o n s , the p r o o f is trivial. So,
what remains to be shown is that:
~ [ x ~ . . . xk][0~ • • • 0,,]]]Das = [ [ 3 x l . . . 3xk[t01 A . . . At0,,]]]
By definition it holds that:
~[Xl " " "Xk] [0I • " ' On]]] DRS =

{<g, h>] h[xl... Xk]g & h e ~01~c°nd & . . . & h ~ ~0n~c°nd}
By induction: [[0s]]c ° n a = \ t 0 ~ \ , for 1 ~< i ~< n. So, we m a y continue our
e q u a t i o n as follows:
= {(g, h) 1h[x~...xk]g&h E\t0~\&.. • & h E \¢0,,\}
Next, we note two auxiliary facts:
F A C T 26. If 05 and 0 are D R T - c o n d i t i o n s , then t05 A tO is a condition in

D P L as well.
F r o m Definition 28 it is easy to see that if 05 and 0 are D R T - c o n d i t i o n s ,

then t05 and t 0 are conditions in D P L as well. By Definition 12 it then
follows that t05 A t O is also a D P L - c o n d i t i o n .
F A C T 27. If q5 and 0 are D P L - c o n d i t i o n s , then \& A 0 \ = \05\ ['7 \ I / A .
This can be p r o v e n by a simple calculation.

N o w we return to o u r p r o o f o f Fact 25. O n the basis of our auxiliary
facts, we arrive at the following continuation of our equation:
= {(g, h)l h[xl...xk]g & h ~ \tO~ A . . . A t~0,,\}
Since t~ A ... A t~ is a DPL-condition, it holds that

h ¢ \t0~ A . . . A ? 0 n \ iff (h, h) ~ lit01 A . . . A tO,,]]. This implies that we
can continue as follows:
= {(g, h>l 3k k[x~... Xk]g & (k, h) e [It01 A . . . A t0,,]}

= [[3x~... 3x~[t~ A . . . A t0~]]l
By which the p r o o f of Fact 25 is completed.
B e f o r e turning to the less urgent, but m o r e difficult p r o b l e m of translat-
80 J. GROENENDIJK AND M, STOKHOF
ind DPL-formulas into DRS's, we return, by way of a short intermezzo,

to two of the examples discussed in Section 2.1, and compare, once again,
the corresponding DPL-formulas and DRS's. By t D R T we mean the
translation of the DRT-representation in DPL.
(1) A man walks in the park. He whistles.

(la) 3x[man(x) A walk_in_the_park(x) A whistle(x)] P L / t D R T
(lb) 3x[man(x) A walk_in_the_park(x)] A whistle(x) DPL
(lc) [x][man(x),walk_in_the_park(x), whistle(x)] DRT
(3) Every farmer who owns a donkey beats it
(3a) VxVy[[farmer(x) A donkey(y) A own(x, y)] --~ beat(x, y)] PL
(3b) Vx[[farmer(x) A 3y[donkey(y) A own(x,y)]] ~ b e a t ( x , y ) ] DPL
(3c) [ ][[x, y] [farmer(x), donkey(y), own(x, y)] --+ [ ][beat (x, y)]] DRT
(3d) 3x3y[farmer(x) A donkey(y) A own(x, y)] --+ beat(x, y) ? D R T
Consider the first example. If our diagnosis of the problem that such a
sequence poses, viz., that the real problem is to provide a compositional
translation of such sequences of sentences into a logical representation
language, is correct, then the DRT-representation has as little to offer as
the PL-translation. The two component sentences cannot be retrieved
from (lc), neither can they be isolated from (la) as subformulas. The
DPL-representation differs precisely at this point.
As for the second example, it is not possible to retrieve the component
parts of the sentence from either the PL- or the DRT-representation, nor
from the ?DRT-translation. But in the DPL-formula, we do find an open
formula which corresponds to the complex noun farmer who owns a
donkey, viz., farmer(x) A 3y[donkey(y) A own(x, y)]. But no such sub-
expression is to be found in the DRT-representation or in the correspond-
ing tDRT-formula.
In fact, each of the two examples can be used to make a point in favour
of DPL. The preferable DPL-translation of the first example is available
precisely because DPL has dynamic conjunction, whereas such a concept
is lacking in DRT. As for the second example, here DPL fares better
because, unlike DRT-quantification, DPL-quantification is iterative. It is
precisely these two concepts of DPL which enable us to give a composi-
tional treatment of the cases at hand. In fact, if both conjunction of DRS's
and iterative quantification were added to DRT, it would simply collapse
into DPL.
This is a rather surprising result, since one of the trademarks of theories
such as those of Kamp and Heim is the non-quantificational analysis of
indefinite terms, whereas it is characteristic of DPL that it does allow us
to treat such terms as existentially quantified expressions.
A host of arguments have been presented against a quantificational

analysis of indefinites, see in particular in Heim (1982). However, these
arguments now appear to be directed, not against a quantificational analy-
sis as such, but only against the traditional quantificational analysis, which
is static. The dynamic DPL-approach is not affected by these.
We do not discuss the various arguments here, with one exception.
This argument concerns what Heim calls the 'chameleontic' nature of the
quantificational force of indefinites. What follows is in essence, but not in
all details, taken from Helm (1982).
Consider the following variants of our example (2):
(9) If a farmer owns a donkey, he always/usually/sometimes/never

beats it
These variants of the donkey-example (2) have readings which can be

paraphrased as in (10):
(10) In all/most/some/no cases in which a farmer owns a donkey,

he beats it
Examples such as those in (9) are taken to support the view that what
appears to be the quantificational force of an indefinite term, is in fact
either due to a different expression, a so-called 'adverb of quantification',
as in (9), or is implicit in the construction, as for example in the original
donkey-sentence (2). Following Lewis (1975), it is assumed that the sen-
tences in (9) are to be analyzed along the following lines. The main
operator is the adverb of quantification, which takes two arguments, the
antecedent and the consequent. The indefinite terms are treated as free
variables, which are unselectively bound by the main operator, which
determines the quantificational force. The antecedent serves as a restric-
tion on the unselective quantification. For the original donkey-sentence,
which lacks an overt adverb of quantification, i t is assumed that the
construction itself acts as a universal adverb of quantification.
At first sight, this argument seems not to be restricted to the traditional,
static quantificational analysis, but seems to apply to any quantificational
approach which associates a specific quantificational force with indefinite
terms. However, in view of our observations concerning the relationship
between D P L and D R T , this can not really be correct. In fact, it is not
difficult to incorporate the 'adverbs-of-quantification' analysis of sentences
such as (9) in DPL, thus showing its compatibility with a quantificational
treatment of indefinites.
Recall that in the interpretation clause of implication, there is universal
quantification over the output assignments of the antecedent:
~d9~ t~ = { (g, h) l h = g & for all k: (h, k) ~ ~05~,3j: (k, j) ~ ~ }
What we can do is simply generalize this to other quantificational forces,

and index the implication accordingly:
[{05---~o ~0~ = {(g, h) l h = g & for Qk: (h, k) ~ ~05~,3j: (k, j) C ~t~}
This has the required effects. Consider the following example:
(11) If a farmer owns a donkey, he never beats it
If we translate this using ~ n o , the result is:
3x[farmer(x) A 3y[donkey(y) A own(x, y)]] ~no beat(x, y)
This denotes the following set of pairs of assignments:
{(g, g)l ~ 3h: h[x, y]g & h(x) E F(farmer)

& h(y) E F(donkey) & (h(x), h(y))
F(own) & (h(x), h(y)) E F(beat)}
Notice that this analysis works precisely because indefinite terms are ana-
lyzed as dynamically existentially quantified expressions. For this has the
effect that the quantification in the general scheme is restricted to the
variables which correspond to indefinite terms.
We do not intend this as a final analysis of adverbs of quantification,
since, for one thing, such an analysis has to be higher-order and inten-
sional, and D P L is only first-order and extensional. But we do take the
above to show that an 'adverbs-of-quantification' analysis is perfectly com-
patible with a quantificational analysis of indefinite terms, provided this
is a dynamic one.
After this intermezzo, we return to the formal comparison of D P L and
DRT. As we already remarked above, the formulation of a translation
from the DPL-language to the DRS-language, is more difficult than the
other way around. In fact, no strict interpretation-preserving translation
is possible, though one which preserves truth conditions is. We point out
the main features of such a translation, written as '§', without, however,
going into details.
Notice that the fact that D R T distinguishes between conditions and
DRS's, presents no problem. Defining a translation from DPL-formulas
into DRS's is sufficient, for as we saw above, any DRT-condition can
easily be turned into a DRS by means of empty DRT-quantification.
Now, there are three complications. The first concerns universal quanti-
fication, which is lacking in D R T . We can either use the definition of Vx05
in terms of ~ 3 x ~ 05, or turn §Vx05 directly into the condition [x][ ] --+ §05.
The remaining two complications, not surprisingly, stem from the two
essential differences between D R T and D P L which we noticed above.
Because D R T lacks a notion of DRS-conjunction, we cannot composi-
tionally translate a DPL-conjunction. Something like §[~bA 0] =
[ ][§qS, §to] would work only if both conjuncts are DPL-conditions, which,
of course, they need not be.
Similarly, no compositional translation of existentially quantified for-
mulas is possible either. Again, §3xq5 = [x]§q5 works only if q5 is a DPL-
condition. Suppose that ~b in its turn is 3yRxy. Then the resulting transl-
ation would be [x][y]Rxy. But this is not a well-formed DRS, since [y]Rxy
is not a DRT-condition.
To get things to work, we first need to define a special format for DPL-
formulas which enables us to translate them in a non-compositional, global
manner into DRS's. In order to arrive at the required format, any DPL-
formula q5 should be turned into a formula q~', such that any subformula
of ~b' is of the form 3xl . . . 3x,,to (n ~> 0), where tO is a DPL-condition.
It is possible to give an algorithm that has the required effect, but it is
not strictly meaning-preserving. The following two examples may serve to
illustrate this. Consider the formula Px A 3xQx. In order to give it the
right format, the existential quantifier in the second conjunct has to be
moved outside of the conjunction. But this can't be done, since there is
a free occurrence of x in the first conjunct. So, we have to resort to an
alphabetic variant: 3y[PxA Qy]. As a second example, consider
3xPx/x 3xQx. In this case, too, both quantifiers have to be moved outside
the conjunction, and then again, we need an alphabetic variant:
3x3y[Px A Qy]. The use of alphabetic variants implies that the algorithm
is not meaning preserving, for in D P L such variants have different mean-
ings: 3xq5 4~ 3y[y/x]ch.
These features of DPL-to-DRT-translation illustrate once more, we
think, what exactly makes D P L a more suitable instrument for semantic
analysis. Its dynamic notion of conjunction, and its dynamic and iterative
concept of existential quantification allow us to deal with various phenom-
ena in a simple, intuitive and compositional manner.
4.3. DPL and Quantificational Dynamic Logic
Although there are important resemblances between D P L and certain

systems of dynamic logic as they are discussed in Harel (1984), there are
also major differences. To begin with, there is an important difference in
perspective and over-all aims. Dynamic logic is meant to be used in the
formalization of reasoning about computer programs, about the effects of
their execution, their soundness and correctness, and so on. Typically,

the formulas of a system of dynamic logic are interpreted as assertions
about programs. And the semantic interpretation of these formulas is an
ordinary static interpretation. However, in order to be able to talk about
programs in a logical language, one also needs expressions that refer to
these programs. And that is where dynamic interpretation comes in. The
expressions which are the logical stand-in's for programs, do receive a
dynamic interpretation. However, they only appear as sub-expressions in
the formulas that make up the logical system, they are not themselves
formulas of the logic.
We note in passing, that in this respect we find precisely the opposite
situation in D R T . There as well, we have a distinction between statically
interpreted expressions, D R T ' s conditions, and dynamically interpreted
ones, the DRS's. But in D R T it is the dynamic expressions that play first
fiddle, and the static conditions only occur as subexpressions in these.
In DPL, it is the formulas themselves that receive a dynamic interpret-
ation, the kind of interpretation that programs receive in ordinary dynamic
logic. D P L is a system in which certain kinds of 'programs' can be ex-
pressed, but we cannot formulate assertions about these programs in D P L
itself. Since it is a logical language which is designed to represent meanings
of natural language sentences, one could say that it embodies the view
that the meaning of a sentence is a program, an instruction to the interpre-
ter. So, one could view D P L as a kind of 'programming language', rather
than as a language to reason about such programs. Of course, one can
reason about it in a metalanguage. And, in fact, one could use ordinary
dynamic logic as a means to formalize reasoning about DPL.
Of course, this difference in what the systems are meant to be able to
do, is reflected in various aspects of their organization. We illustrate
this by presenting the syntax and semantics of a particular system of
quantificational dynamic logic, referred to as ' Q D L ' , which proves to be
intimately related to DPL.
Dynamic logic is related to modal logic. The models contain a set S of
possible (execution) states. The formulas are interpreted as sets of states,
the set of states in which a formula is true. Programs are conceived of as
transformations of possible states, i.e., as relations between possible
states. In this respect, the interpretation of a program is like an accessi-
bility relation in modal logic. Each program or corresponds to an accessi-
bility relation [[0r~MC_ S × S. A pair (s, s') is an element of ~'~M if when
executed in s, 0r may lead to s'. (If the program is deterministic, [~-~M
would be a (partial) function.)
In view of their association with accessibility relations, we can build
m o d a l o p e r a t o r s (~-) and [Tr] a r o u n d a p r o g r a m 7r. Like their c o u n t e r p a r t s

in m o d a l logic, these o p e r a t o r s can be prefixed to a f o r m u l a 05 to f o r m
a n o t h e r f o r m u l a , (~-)05 or [~-]05. A f o r m u l a (~-)05 is true in a state s iff
execution of ~r in s m a y lead to a state s' such that 05 is true in s'. In o t h e r
words, (7r)05 expresses that it is possible that 05 is true after 7r has b e e n
executed. Similarly, [Tr] 05 is true in s iff all executions of 7r in s will lead
to a state s' in which 05 is true. So, [Tr] 05 m e a n s that 05 must be true after 7r
has b e e n executed. [trio5 is equivalent to -7 (~r)~ 05, where ~ is interpreted
as ordinary static negation.
In systems of quantificational d y n a m i c logic, the set of possible states
is not just a set of primitive objects, but is identified with the set of
assignment functions G. T h e i n t e r p r e t a t i o n of a f o r m u l a 05 is [[05]]MC_ G.
A n d the i n t e r p r e t a t i o n of a p r o g r a m rr is [[rr~a4 C_ G x G.
W e n o w present a particular version of Q D L that has precisely the
features we need to c o m p a r e it with D P L . W e start out f r o m the language
of P L and add the following features. Basic p r o g r a m s are r a n d o m assign-
m e n t s to variables, written as 'x := r a n d o m ' . (This is a feature not present
in standard Q D L , w h e r e o r d i n a r y deterministic assignments 'x := a' figure
in the language.) F u r t h e r , we add an o p e r a t o r '?', which turns a f o r m u l a
05 into a p r o g r a m ?05. Such a p r o g r a m is called a 'test', and its interpret-
ation is indeed like that of a test in D P L , it is the set of identity pairs
(g, g) such that 05 is true with respect to g. Next, we add the o p e r a t o r ';'
to f o r m sequences of p r o g r a m s . ( O r d i n a r y deterministic assignments can
be defined in terms of these notions as: x := r a n d o m ; ?x = a.) Finally, we
add the ' m o d a l o p e r a t o r s ' discussed above. So, Q D L has the following
syntax:
DEFINITION 29 (Syntax of Q D L ) .
1. T is a formula.
2. If t l . . . t, are individual constants or variables, R is an n-place
predicate, then R t l . . . tn is a formula.
3. If h and t2 are individual constants or variables, then t~ = t2 is a
formula.
4. If 05 is a f o r m u l a , then -7 05 is a formula.
5. If & and 0 are formulas, then [ & - + ~], [&/x 0] and [& v 0] are
formulas.
6. If 05 is a f o r m u l a , then 3x05 is a formula.
7. If 05 is a f o r m u l a , then Vx05 is a formula.
8. If 05 is a f o r m u l a , then ?05 is a p r o g r a m .
9. If x is a variable, then x := r a n d o m is a p r o g r a m .
10. If 7h and 'rr2 are programs, then [rq; ~r2] is a program.

11. If 7r is a program and q5 is a formula, then 0r)05 is a formula.
12. If ~r is a program and 05 is a formula, then [rr]05 is a formula.
13. Nothing is a formula or a program except on the basis of 1-12
Models for Q D L are like those for (D)PL. Like in D R T , we simulta-

neously define two interpretation functions, one for formulas:
[[ ]~DL C_ G; and one for programs: ~ ~ o g C G x G as follows (as usual,
we suppress subscripts whenever this does not give rise to confusion):
D E F I N I T I O N 30 (Semantics of QDL).
1. [[TI° D E = G.
2. ~ R t l . . , tn~QDL = {gl ( ~ f l ~ g . ' ' ~tn~g) • F ( R ) } .
3. [[tl = t2~QDL = {gl ~tl~g = ~t2~g}.
4. [[~ 05~ODL= {gig q~ [[05~ODL}.
5. ~05~ @~QDL= {g]g • I[05~QDL~ g • [[0~ODL}, and similarly for A, v.
6. [[3xO~°De = {g[ 3k: k[x]g & k • I[&~ODL}.
7. [[VX05~°DL = {gl Vk: k [ x ] g ~ k e [&~ODL}.
8. [[?05~Prog= {(g, h) I h = g a h • ~&~ODL}.
9. IX := random~ er°g = {(g, h)l h[x]g}.
10. b n ; ~-2~Pr°g -- {(g, h)l ?k: (g, k) • ~,B-I~Pr°g ~ (k, h) • ~3T2~Pr°g}.
11. I(~-)05~ODE = {gl 3h: (g, h> • [[Tr]]Pr°g & h • ~05~QDL},
12. [[[7r]05~QDL = {g] Vh: (g, h) • ~T~ er°g ~ h • I05~QDL},
First, we note that the language defined above can be economized rather
drastically. Of course, the interdefinability of the connectives and quanti-
tiers in PL carries over to QDL. But, moreover, as appears from the
following two equivalences, we can conclude that all that is characteristic
of PL can be eliminated altogether:
0 5 ~ 0 = [70510
3x05 -~ (x := random)05
So, in terms of negation, the test-operator, random assignments and one
of the two modal operators, all other logical constants can be defined.
As we noted above, DPL-formulas can be conceived of as a kind of
programs. The following definition presents a translation '~>' of DPL-
formulas into QDL-programs:
DEFINITION 31 (DPL-to-QDL translation).

1. E>Rta . . . tn = ?Rtl . . . tn.
2. {>~05= ?-~(~>05)T.
3. > [ 4 A 4,] = [ > 4 ; >~].

4. > [ 4 v ~] = ? [ ( > 4 ) T v (E>@T].
5. > [ 4 - - * ~] = ? [ D 4 I ( > @ T .
6. D 3 x 4 = I x : = random; > 4 ] .
7. > V x 6 = ?[x := random](I>@T.
The last but one of these clauses illustrates that in D P L we need not
introduce the existential quantifier syncategorematically: we could take
3x itself to be a formula of DPL, with the same interpretation as a random
assignment statement, and we could write 3x/x 6 instead of 3x6.
The following fact can be proven by induction on the complexity of 05:
F A C T 28. VM: [[4]]M = IlP"'&llPr°g

h t v %']1M •
Unlike in the case of D R T , we can equally easily define a translation in

the opposite direction. Like in our translation from D R T to DPL, we
don't pay attention to the distinction between formulas and programs in
QDL. No problems can arise from this, since QDL-formulas will be
translated into DPL-conditions. We make only one small addition to DPL:
we add T as a basic formula, and interpret it as the identity relation on
G. We denote the translation function by ~<5':
D E F I N I T I O N 32 ( Q D L - t o - D P L translation).
1. <~T = T.
2. <~Rt, . . . & = Rtz . . . tn.
3. q~4=~<4.
4. q [ 4 - + ~] = [ q 4 - - + <~4,], and similarly for v and A.
5. q 3 X 4 = O3X<14.
6. < V x 4 = V x q 4.
7. q?4 = q4.
8. <~x := random = 3xT.
9. <[~ri; ~'2] = [<~vr~ A qvr~ I.
10. < < ~ ) 4 = o [ < , ~ A <4,1.
11. <~[rr]4= [ q r r - + < l ~ ] .
By simultaneous induction on the complexity of the programs rr and

formulas 4 of Q D L it can be shown that the translation is meaning-
preserving in the following sense:
F A C T 29.
1. VM: [[4~ Q D L = \<~4\M ,
2. VM: ~ 4 ~ ; °g = ~<4~M.
88 J. GROIENENDIJK AND M. STOKHOF
The redundancy of Q D L is reflected illuminatingly in the translation. Most

DPL-operators can be found twice on the right hand side. In some cases,
they occur once in a dynamic and once in a static variant, the latter being
obtained by prefixing the closure operator. Notice that since PL forms a
fragment of QDL, the translation presented above is also a translation of
PL into DPL.
We end this section by discussing two standard features of quantifi-
cational dynamic logics that we have left out solar. The one is program
disjunction, the other program repetition. We also discuss briefly their
possible use in natural language semantics.
The syntax and semantics of program-disjunction are defined as follows:
DEFINITION 33 (Program disjunction).
1. If Irl and ~r2 are programs, then [Iri U 7r2] is a program.

2. I[TT1 U IT2]]pr°g = ~['B'I]]Pr°g U I[7T2]]Pr°g,
Of course, the same definition could be used to introduce a second notion

of disjunction U besides v in DPL. Unlike the latter, U is a dynamic
notion, but it differs in an interesting way from dynamic implication
and conjunction. Whereas implication is only internally dynamic, and
conjunction is both internally and externally dynamic, U is only externally
dynamic. An existential quantifier 3x in the first disjunct cannot bind free
occurrences of x in the second disjunct (nor vice versa), but an existential
quantifier in either disjunct can bind variables in a further conjunct. In
the formula [3xPx U 3xQx] A Hx both occurrences of 3x in the first
conjunct bind the occurrence of x in the second conjunct. In fact, the
formula in question is equivalent to [3xPx A Hx] U [3xQx A Hx]. More
generally the following holds:
[ uo] A x =
[ d , u e] = A
Adding this kind of disjunction to our dynamic repertoire would enable us

to treat the anaphoric links in examples like (12) and (13) in a completely
straightforward way:
(12) A professor or an assistant professor will attend the meeting
of the university board. He will report to the faculty
(13) If a professor or an assistant professor attends the meeting of
the university board, then he reports to the faculty
However, as we shall see in the next section, adding this new kind of
dynamic disjunction still leaves certain dynamic features of natural lan-

guage disjunction unexplained.
We now turn to program repetition. This concept is important in the
semantic analysis of program constructions like ' w h i l e . . . d o . . . ' and 're-
p e a t . . , u n t i l . . . ' . The syntax and semantics of program repetition is de-
fined as follows:
D E F I N I T I O N 34 (Program repetition).
1. If ~- is a program, then 7r* is a program.

2. ~w*~er°g = {{g, h)[ 3 n 3 g o , gL . . . . . gn: go = g & gn = h &
Vi: 1 <~ i <~ n: {gi-1, gi) E tt[]-7/"]]Pr°gl
IIM I.
According to this definition, a pair <g, h) is in the interpretation of ~-* iff

h can be reached from g by a repeating ~- a finite but non-deterministically
determined number of times.
At first sight, this kind of concept seems of no use in natural language
semantics. However, consider the following example (due to Schubert and
Pelletier (1989)):
(14) If I've got a quarter in my pocket, I'll put it in the parking

meter
Notice first of all, that unlike a DRT/DPL-analysis would have it, one
who utters (14), probably does not intend to spend all the quarters in his
pocket on the parking meter. Now, notice that a procedural meaning of
(14) could informally be paraphrased as " R e p e a t getting coins out of your
pocket until it is a quarter; then put it in the parking meter". So maybe
after all, adding repetition to D P L could add to its use as a tool in natural
language semantics.
As one of the referees pointed out, the Schubert and Pelletier analysis
can be dealt with in D P L in a more straightforward way, too. It would
suffice to define another notion of implication as follows:
~l---"> ~ : d e f ~ l (D V I l i A ~]]
See also Chierchia (1988, 1990), where this conservative notion of impli-
cation is argued for.
5. PROSPECT AND RETROSPECT
5.1. P r o b l e m s and Prospects
As we have pointed out in the introduction of this paper, we are interested

in developing a compositional, non-representational semantics of dis-
course, one which will enable us to marry the compositional framework of

Montague grammar to a dynamic outlook on meaning such as can be
found in D R T and its kin. The development of D P L is only a first step
in achieving this over-all aim. At the empirical level, D P L matches D R T ,
and from a methodological point of view, it is in line with MG. At least
at the following two points, D P L needs to be extended. First of all, like
D R T , D P L is restricted to the resources of an extensional first-order
system, whereas M G essentially makes use of intensional higher order
logic. And secondly, D P L shares several empirical characteristics with
D R T which have been disputed in the literature.
As for the first point, D P L offers as compositional a treatment of
natural language expressions as a first-order system permits; nothing more,
nothing less. However, to match MG, and more in particular to be able
to cope with compositionality below the sentential level in the way familiar
from MG, we do need more. In fact, we need a higher-order, intensional
language with A-abstraction, or something else that is able to do what that
does. In Groenendijk and Stokhof (1990) one way to go about is pre-
sented, which uses a version of dynamic intensional logic (DIL) as it was
developed in Janssen (1986) with the aim of providing a Montague-style
semantics for programming languages. The resulting system of 'dynamic
Montague grammar' (DMG) is able to cope with the phenomena D P L
deals with in a completely compositional fashion - below, on, and beyond
the sentential level.
The second issue we want to touch upon here concerns certain empirical
predictions that D P L shares with DRT.
As we remarked several times in the above, only conjunction and the
existential quantifier are treated in a fully dynamic fashion. They are
both internally and externally dynamic. All other logical constants are
externally static. In this respect, D P L is like DRT. In our informal intro-
duction to D P L in Section 2, we motivated the interpretation clauses for
the various logical constants by pointing out that they behave differently
with regard to possible anaphoric relations. (Cf. examples (4)-(8).) Thus
it was argued, for example, that conjunction and implication should be
internally dynamic, because both allow an antecedent in their first argu-
ment to bind an anaphor in their second argument. However, it was
concluded that only conjunction is also externally dynamic, since it also
passes on bindings to sentences to come, whereas implication, in view of
the fact that it lacks this feature, should be treated as externally static.
The interpretation of the universal quantifier, negation, and disjunction
was motivated in a similar fashion.
Several authors have provided examples which seem to indicate that
the predictions that D R T and DPL make here, are not borne out by the
facts. (See e.g. Roberts (1987, 1989), Kadmon (1987).) Consider the
following examples (which are (variants of) examples that can be found
in the literature):
(15) If a client turns up, you treat him politely. You offer him a
cup of coffee and ask him to wait
(16) Every player chooses a pawn. He puts it on square one.
(17) It is not true that John doesn't own a car. It is red, and it is
parked in front of his house
(18) Either there is no bathroom here, or it is in a funny place. In
any case, it is not on the first floor
Different conclusions may be drawn from these observations, some of

which are compatible with the way in which the logical constants are
interpreted in D R T and DPL. However, one might also take these ex-
amples to show that, at least in certain contexts, the universal quantifier,
implication, disjunction, and negation are both internally and externally
dynamic. Without wanting to commit ourselves to the latter position, we
want to explore its consequences a little here.
As for the first of the examples, it can then be observed that the second
sentence is interpreted as an additional conjunct of the consequent of the
implication in the first sentence, as the following paraphrase of (15) shows:
(19) If a client turns up, you treat him politely, you offer him a cup
of coffee, and ask him to wait
So, what we need is an interpretation of implication which will make (20)

equivalent to (21):
(20) [3x[client(x) A turn_up(x)] --+ treat_politely(y, x)] A offer_

coffee(y, x) A ask_to_wait(y, x)
(21) 3x[client(x) A turn_up(x)] ~ [treat_politely(y, x) A offer_
coffee(y, x) A a s k t o _ w a i t ( y , x)]
More generally, an externally dynamic interpretation of implication will
make [cb --~ ~] A X equivalent with q5--~ [4~ A X].
AS for the second example, similar observations can be made. It can
be paraphrased as (22), which indicates that an externally dynamic treat-
ment of universal quantification will make (23) equivalent with (24):
(22) Every player chooses a pawn, and (he) puts it on square one
(23) Vx [player (x) --~ 3y[pawn(y) A choose(x, y)]] A put_on_
square one(x, y)
(24) Vx [player (x) ~ 3y[pawn(y) A choose(x, y) A p u t _ o n _ s q u a r e

one(x, y)]]
So, on this approach, Vxq5 A 4, turns out to be equivalent with Vx[~b A 4,].
And if this is combined with a dynamic interpretation of implication,
Vx[~b -~ 4,] A X will be equivalent with Vx[q5 --+ [4, A/"]].
In a similar fashion, the third example may be taken to indicate that a
dynamic version of negation is needed for which the law of double ne-
gation holds.
The last example indicates that disjunction, too, can sometimes be
interpreted dynamically. This interpretation should make [q5 v 4,] A X
equivalent with ~b v [4' A 1"]. Notice that the dynamic interpretation of
disjunction that is at stake here, differs from the one discussed in Section
4.3. The latter, as we have seen, is essentially internally static, and only
externally dynamic, whereas the present notion is both internally and
externally dynamic. Also, their external dynamic behaviour is different:
[q5 U 4,] A X is equivalent with [4) A X] U [4, A 1'].
These observations characterize one way of dealing with such examples
as (15)-(18). We end our discussion of them with three remarks. First of
all, saying what the desired effect of the dynamic interpretations of the
logical constants involved are, is, of course, not the same as actually giving
the interpretations themselves. And secondly, the availability of suitable
dynamic interpretations would leave unanswered the question why it is
that the logical constants involved act dynamically in certain contexts, but
not in others. Finally, in view of the latter fact, one would not want to
postulate two independent interpretations. Rather, the static interpret-
ation should be available from the dynamic one by a general operation of
closure.
The first and the last issue are discussed at length in Groenendijk and
Stokhof (1990). There it is shown that using the richer framework of
DMG, the required dynamic interpretations can indeed be obtained, and
in such a fashion that the static interpretations are the closures of the
dynamic ones. As for the second point, this seems to be more an empirical
than a formal question, to which D M G as such does not provide an
answer.
From this, we conclude that the kind of dynamic approach to natural
language meaning that is advocated in this paper, is not restricted to the
particular form it has taken here, i.e., that of the DPL-system, but is
sufficiently rich to allow for alternative analyses and extensions (see, e.g.,
Chierchia (1988, 1990), Dekker (1990), van den Berg (1990)).
5.2. Meaning and Compositionality
The primary motivation for the DPL-undertaking was that we were inter-
ested in the development of a compositional and non-representational
theory of meaning for discourses. Compositionality is the corner-stone of
all semantic theories in the logical tradition. As a consequence, it has
also been of prime importance in those approaches to natural language
semantics which use tools developed in the logical paradigm. However,
compositionality has been challenged as a property of natural language
semantics. Especially when dealing with the meaning of discourses people
have felt, and sometimes argued, that a compositional approach fails.
In the context of natural language semantics, we interpret composi-
tionality as primarily a methodological principle, which gets empirical,
computational, or philosophical import only when additional, and inde-
pendently motivated constraints are put on the syntactic or the semantic
part of the grammar that one uses. In other words, it being a methodolog-
ical starting point it is always possible to satisfy compositionality by simply
adjusting the syntactic and/or semantic tools one uses, unless that is, the
latter are constrained on independent grounds. In view of this interpret-
ation of compositionality, our interest in the possibility of a compositional
semantics of discourse is also primarily of a methodological nature. Faced
with non-compositional theories that give an account of interesting phe-
nomena in the semantics of natural language discourses, we wanted to
investigate the properties of a theory that is compositional and accounts
for the same facts. We knew in advance that such a theory should exist,
what we wanted to know is what it would look like: it might have been
that being compositional was the only thing that speaks in favour of such
a theory, in which case there would have been good reasons to abandon
it.
As we already remarked in the introduction, beside these methodolog-
ical considerations, there may also be practical reasons to be interested
in trying to keep to compositionality. One such reason can be found in
computational requirements on the semantics of discourses, or texts. For
example, in a translation program one would like to be able to interpret
a text in an on-line manner, i.e., incrementally, processing and interpret-
ing each basic unit as it comes along, in the context created by the
interpretation of the text solar. Although certainly not the only way to
meet this requirement, compositionality is a most intuitive way to do so.
As such, on-line interpretation does not preclude that in the interpretation
of a unit of text, other things than the interpretation of the text sofar play
a role. But it does require that at any point in the processing of a text we
are able to say what the interpretation thus far is. In other words, it does
rule out approaches (such as DRT) in which the interpretation of a text
is a two-stage process, in which we first build a representation, which only
afterwards, i.e., at the end of the text, or a certain segment of it, mediates
interpretation of the text as such. So, from the viewpoint of a compu-
tational semantics, there is ample reason to try and keep to compositional-
ity.
Yet another reason is provided by certain philosophical considerations.
These concern the fact that non-compositional semantic theories usually
postulate a level of semantic representation, or 'logical form', in between
syntactic form and meaning proper, which is supposed to be a necessary
ingredient of a descriptively and explanatorily adequate theory. Consider
the following two sequences of sentences (the examples are due to Partee,
they are cited from Heim (1982)):
(25) I dropped ten marbles and found all of them, except for one.
It is probably under the sofa.
(26) I dropped ten marbles and found only nine of them. It is
probably under the sofa.
There is a marked contrast between these two sequences of sentences.
The first one is all right, and the pronoun it refers to the missing marble.
The second sequence, however, is out. Even though it may be perfectly
clear to us that the speaker is trying to refer to the missing marble with
the pronoun it, evidently, this is not the way to do this. Like most authors,
we start from the assumption that co-reference and anaphora are, by and
large semantic phenomena. ('By and large' in view of the fact that some-
times certain syntactic features are involved in pronoun resolution as well.
A case in point is syntactic gender in languages like German and Dutch.)
Therefore, we may take the following for granted: the contrast between
(23) and (24) marks a difference between the respective opening sen-
tences, and this difference is one of meaning, in the broad, intuitive sense
of the word. But what does this difference consist in? For notice that the
first sentences of (23) and (24) do characterize the same situation. There
is no difference in their truth conditions, therefore it seems that they
are semantically equivalent. Indeed, they are equivalent in any standard
semantic system that explicates meaning solely in terms of truth (or more
generally, denotation) conditions. And we speculate that it is for this
reason that many semanticists have taken the view that the difference in
question is one of (logical) form, of (semantic) representation, rather than
one of content.
For various reasons, we think that one should not adopt this point of
view too hastily. For, it means that one has to postulate an intermediate
level of representation in between natural language and its interpretation.
True, most semantic frameworks interpret natural language via translation
into a logical language, but the general methodological strategy here has
always been to make sure that the translation procedure is compositional,
and hence, in view of the compositional nature of the interpretation of the
logical language, in principle dispensable. The logical translation serves
practical purposes only, in principle it can be discarded. But notice that
the level of representation that is assumed if one views the difference
between (23) and (24) as one of form, is not of this (optional) nature.
The two sentences involved will be mapped onto different logical forms,
or semantic representations, which in their turn will receive an equivalent
interpretation. Accounting for the difference between (23) and (24) in this
way, makes the existence of this level of representation imperative, rather
than useful. It would be a necessary go-between natural language and its
meaning. So it seems that, perhaps without being aware of it, many have
put a constraint on the semantics: meaning is truth (denotation) con-
ditions. Then, indeed, compositionality becomes a contentfull, rather than
a methodological principle, and one which is falsified: the facts force the
existence of a level of semantic representation on us.
There are several reasons why we think that the move to a semantic
theory which assumes such an independent level of semantic representa-
tion, distinct both from syntactic structure and from meaning proper,
should be looked upon with reserve. First of all, there is the familiar,
almost commonplace reason of theoretical parsimony. Levels of represen-
tation, too, should not be multiplied beyond necessity, and although this
is perhaps not too exciting a comment to make, we feel that from a
methodological point of view it is still a sound one. Of course, its relevance
in the present context does presuppose that we are not really forced to
introduce such a level of semantic representation, that we can do without
it. Such a claim can not be substantiated in general, but it can be shown
to be correct in particular cases. And the development of the DPL-system
shows that, in the case at hand, the principle of compositionality has not
only negative implications, but also points positively towards a satisfactory
treatment of the issues involved. For the phenomena in question, no level
of representation is needed, for compositionality clearly guides towards a
notion of meaning which allows us to do without.
Be that as it may, our appeal to this methodological principle will be
waved by those who claim that there is empirical evidence for the existence
of a level of semantic representation. In fact, quite often when such a
level of representation is postulated, this is accompanied by the claim that

it is somehow psychologically 'real'. We must be careful in our evaluation
here, for one might be making a weaker and a stronger claim. The weaker
one is that in producing and understanding language, people somehow
represent meanings, extract them from linguistic structures, manipulate
them, 'put them into words', and so on. This claim is in fact subsidiary
to the view of the mind as a calculating machine. Notice, however, that
this weaker claim is not necessarily at odds with our parsimonious starting
point. For, as such there may very well be a separate level of semantic
representation, without it being a necessary ingredient of a descriptively
and explanatorily adequate semantic theory. The stronger claim adds
exactly this to the weaker one: it claims, not just the cognitive reality of
representation of meaning, but the existence of a level of representation
which carries information that goes beyond that what is represented there,
viz., meaning. In effect, this view splits the intuitive notion of meaning in
two: those aspects which are covered by the technical notion of meaning
(or interpretation) that the theory provides (or borrows from other frame-
works), and those which are accounted for by properties of the particular
kind of representation of the former.
Thus, a mentalist we call someone who claims that a level of representa-
tion is necessary, not someone who merely claims that it exists. Should
we include among the mentalists the latter kind of person too, we would
be forced to consider the Wittgenstein of the Tractatus as a mentalist, for
he claimed that there exists a level of thoughts and thought-elements
which is isomorphic to language, and hence to the world. However, he
did consider this level completely irrelevant for an account of the nature
of meaning and the way in which it is established. Thus Wittgenstein
apparently accepted the existence of a level of 'semantic representation',
but considered its existence of no interest for semantics proper. In connec-
tion with this, it may be worthwhile to point out the close correspondence
between the isomorphic 'picturing' relation between language and the
world of the Tractatus, and the modern-day, algebraic explication of com-
positionality, as it can be found, for example, in Janssen (1986). Of course,
the later Wittgenstein would have discarded even any talk of a 'cognitive'
sub-stratum of our linguistic behaviour, which may help to remind us that
even the weaker claim is not as philosophically neutral as some apparently
think it is.
To return to the main point, we think that the stronger claim is unwar-
ranted, and that it certainly cannot be justified simply by an appeal to the
linguistic facts of the matter. As for the weaker claim, the view on the
mind and its operations that it stems from, when taken literally is, of
course, not philosophically neutral. Those who really subscribe to it face
the burden of showing that there are such things as 'mental' representa-
tions and the like, a task which is not without philosophical pitfalls.
Notoriously, these issues are as interesting as they are undecidable. Our
own opinion, for whatever it is worth, is that the calculating mind is a
m e t a p h o r rather than a model. It is a powerful metaphor, no doubt, on
which m a n y branches of 'cognitive' science are based, and sometimes it
can be helpful, even insightful. But it remains a way of speaking, rather
than a true description of the way we are. However, whatever stand one
would like to take here, it does not affect the point we want to make,
which is that it is better to try to keep ones semantic theory, like every
theory, as ontologically parsimonious and as philosophically neutral as
possible. The stronger claim goes against this, and hence has to be re-
jected, unless, somehow, proven.
As for the weaker claim, subscribing to it or not makes no real differ-
ence, but one has to be careful not to let it interfere with the way one
sets up ones semantic framework. The best way to go about, then, is to
carry on semantics as really a discipline of its own, not to consider it a
priori a branch of cognitive science, and to enter into the discussion of
the reality of mental representations in a 'modular' flame of mind.
It may be the case, though, that for some the acceptance of a level of
logical representation springs forth from a positive philosophical convic-
tion, viz., a belief in the deficiencies of natural language as a means to
convey meaning. Now such there may be (or not) when we consider
very specialized kinds of theoretical discourse, such as mathematics, or
philosophy, or particle physics. A n d again, natural language may be de-
ficient (or not) when we consider a special task that we want to be
performed in a certain way, such as running a theorem prover based on
natural deduction on natural language sentences, or such a thing. In such
cases, clearly there is r o o m for extension and revision, for regimentation
and confinement. But that is not what is at stake here. H e r e , it turns
on the question whether natural language structures themselves, as we
encounter them in spoken and written language, then and there are in
need of further clarification in order to convey what they are meant to
convey. In this matter, semantics, we feel, should start from the premiss
that natural language is all right. If anything is a perfect means to express
natural language meaning, natural language is. It can very well take care
of itself and is in no need of (psycho)logical reconstruction and improve-
ment in this respect. To be sure, that means taking a philosophical stand,
too, but one that is neutral with respect to the question whether there is
such a thing as an indispensable level of logical representation in seman-
tics. As we said above, if such there is, this has to be shown, not taken
for granted.
Our ideological point of view concerning the status of mental represen-
tations is in line with the methodological interpretation of the principle of
compositionality. As was already remarked above, this interpretation not
only forces us to reject certain approaches to the problems we started out
with, it also positively suggests us a proper solution. Compositionality
dictates that the meanings of (23) and (24) should be functions of the
meanings of their parts. We take it to be an obvious fact that the immedi-
ate components of the sequences of sentences (23) and (24) are the two
sentences of which they consist. Because of the difference in acceptability
we cannot but conclude that the first sentence of (23) and the first sentence
of (24) differ in meaning. Accepting the fact that their truth conditions
are the same, this leads to the inevitable conclusion that truth conditions
do not exhaust meaning. ('Do not exhaust m e a n i n g . . ,', because we do
want to stick to the idea that truth conditions are an essential ingredient
of meaning.) What compositionality strongly suggests, then, is that we
look for an essentially richer notion of meaning of which the truth con-
ditional one is a special case. Our claim is that the kind of dynamic
semantics that D P L is an instance of, naturally suggests itself as a first
step on the right track.
ACKNOWLEDGEMENTS
The first version of this paper was presented in June, 1987 at the
ASL/LSA-meeting in Stanford, and on several other occasions. A pre-final
version was prepared for the First European Summerschool on Natural
Language Processing, Logic and Knowledge Representation, held in
Groningen in July 1989.
At these and other meetings, and in correspondence, many friends and
colleagues have prompted even more questions and comments, which
have helped and stimulated us. We thank them, and the two anonynous
referees of Linguistics and Philosophy.
Since the summer of 1988, our ITLI-colleague Roel de Vrijer has joined
in with our work on DPL. More in particular, he has dedicated himself
to the development of a complete and sound proof theory for DPL. We
hope to report on the results in a separate, joined paper. Some of the
results of this c o o p e r a t i v e work have already p e n e t r a t e d the p r e s e n t paper.

M o r e in particular, this holds for the sections o n scope a n d b i n d i n g , a n d
o n e n t a i l m e n t . A n d at m a n y o t h e r points as well, we have greatly b e n -
efitted from R o e l ' s acute c o m m e n t s a n d criticisms.
T h e p a p e r partly originates from a research project carried o u t by the
first a u t h o r from S e p t e m b e r 1986 to S e p t e m b e r 1988, c o m m i s s i o n e d by
Philips R e s e a r c h L a b o r a t o r i e s , E i n d h o v e n , T h e N e t h e r l a n d s . A t the final
stage of this research, b o t h a u t h o r s were e n g a g e d o n the Dyana-project
( E B R A - 3 7 1 5 ) c o m m i s s i o n e d by the E u r o p e a n C o m m u n i t y .
REFERENCES
Barwise, J.: 1987, 'Noun Phrases, Generalized Quantifiers and Anaphora', in P. Gfirdenfors
(ed.), Generalized Quantifiers, Reidel, Dordrecht, pp. 1-29.
Berg, M. van den: 1990, 'A Dynamic Predicate Logic for Plurals', in M. Stokhof and L.
Torenvliet (eds.), Proceedings of the Seventh Amsterdam Colloquium, ITLI, Amsterdam.
Cbierchia, G. : 1988, "DynamicGeneralized Quantifiers and Donkey Anaphora', in M. Krifka
(ed.), GenerieiO' in Natural Language, SNS, Tt~bingen.
Chierchia, G.: 1990, "Anaphora and Dynamic Logic'. in J. Groenendijk, M. Stokhof, G.
Chierchia and P. Dekker, Quantification and Anaphora II, Dyama-deliverable R2.2.a.
Centre for Cognitive Science, Edinburgh.
Dekker, P.: 1990, 'Dynamic Interpretation, Flexibility, and Monotonicity', in M. Stokhof
and L. Torenvliet (eds.), Proceedings of the Seventh Amsterdam Colloquium, ITLI, Am-
sterdam.
Groenendijk, J. and M. Stokhof: 1988, 'Context and Information in Dynamic Semantics',
in B. Elsendoorn and H. Bouma (eds.), Working Models of Human Perception, Academic
Press, New York, pp. 457-488.
Groenendijk, J. and M. Stokhof: 1990, "Dynamic Montague Grammar', in g. Kfilmfinet al.
(eds.), Proceedings of the Second Symposium on Logic and Language, Budapest.
Harel, D.: 1984, 'Dynamic Logic', in: D. Gabbay and F. Guenthner (eds.), Handbook of
Philosophical Logic, vol. H, Reidel, Dordrecht.
Heim, I.: 1982, The Semantics of Definite and Indefinite Noun Phrases, dissertation, Univer-
sity of Massachusetts, Amherst.
Heim, I.: 1983, 'File Change Semantics and the Familiarity Theory of Definiteness', in R.
Bar,erie, Ch. Schwarze, and A. von Stechow (eds.), Meaning, Use and Interpretation of
Language, De Gruyter, Berlin.
Janssen, T.: 1986, Foundations and Applications of Montague Grammar, CWI, Amsterdam.
Kadmon, N. 1987, On Unique and Non-Unique Reference and Asymmetric Quantification,
dissertation, University of Massachusetts, Amherst.
Kamp, H.: 1981, ~A Theory of Truth and Semantic Representation', in J. Groenendijk, T.
Janssen, and M. Stokhof (eds.), Formal Methods in the Study of Language, Mathematical
Centre, Amsterdam, pp. 277-322 [reprinted in J. Groenendijk, T. Janssen, & M. Stokhof
(eds.), 1984, Truth, Interpretation and Information, Foris, Dordrecht, pp. 1-41].
Kamp, H.: 1983, 'Situations in Discourse Without Time or Questions', manuscript.
Lewis, D.: 1975, 'Adverbs of Quantification', in E. Keenan (ed.), Formal Semantics of
Natural Language, Cambridge University Press, Cambridge, pp. 3-15.
Roberts, C.: 1987, Modal Subordination, Anaphora, and Distributivity, dissertation, Univer-
sity of Massachusetts, Amherst.
]00 J. GROF~NENDIJK AND M. STOKHOF
Roberts, C.: 1989, 'Modal Subordination and Pronominal Anaphora in Discourse', Linguis-
tics and Philosophy, 12, 683-723.
Rooth, M.: 1987, 'Noun Phrase Interpretation in Montague Grammar, File Change Seman-
tics, and Situation Semantics', in P. G~irdenfors (ed.), Generalized Quantifiers, ReideI,
Dordrecht, pp. 237-269.
Schubert, L. and F. J. Pelletier: 1989, 'Generally Speaking, or, Using Discourse Representa-
tion Theory to Interpret Generics', in G. Chierchia, B. H. Partee, and R. Turner (eds.),
Properties, Types and Meaning, Vol. II, Kluwer, Dordrecht, pp. 193-268.
Seuren, P.: 1986, Discourse Semantics, Blackwelt, Oxford.
Zeevat, H.: 1989, "A Compositional Approach to Discourse Representation Theory',
Lblguistics and Philosophy, 12, 95-131.
University of Amsterdam
Department of Philosophy
Nieuwe Doelenstraat 15
NL-IOI2 CP Amsterdam
View publication stats

Dynamic Predicate Logic

Uploaded by

Copyright:

Available Formats

Dynamic Predicate Logic

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Dynamic Predicate Logic

Uploaded by

Copyright:

Available Formats

See discussions, stats, and author profiles for this publication at: https://www.researchgate.

Dynamic Predicate Logic

Article in Linguistics and Philosophy · February 1991

Jeroen Groenendijk Martin Stokhof

SEE PROFILE SEE PROFILE

The user has requested enhancement of the downloaded file.

DYNAMIC PREDICATE LOGIC

This paper is devoted to the formulation and investigation of a dynamic

Linguistics and Philosophy 14: 39-100, 1991.

One of the main problems in semantics today, we feel, is that a semantic

2. ELEMENTS OV DYNAMIC INTERPRETATION

(1) A man walks in the park. He whistles

In order for the pronoun he in the second sentence of (1) to be anaphor-

(la) 3x[man(x) A walk_in_the_park(x) A whistle(x)]

(lb) 3x[man(x) A walk_in_the_park(x)] A whistle(x)

(2a) V x V y [ [ f a r m e r ( x ) A donkey(y) A own(x, y)]

(2b) 3x[farmer(x) A 3y[donkey(y) A own(x, y)]]

(lc) [x] [man (x), walk_in_the_park (x), whistle (x)]

We will not go into the semantics of these discourse representation struc-

a substructure of (2c). So, from a compositional point of view, they are

2.2. The Dynamic View on Meaning

The general starting point of the kind of semantics that D P L is an instance

concerns their potential to 'pass on' possible antecedents for subsequent

2.3. Dynamic Conjunction and Existential Quantification

~3xPx~ = {(g, h)[h[x]g & h(x) E F(P)}

[[3x~b~ = {(g, h)13k: k[x]g & (k, h) E ~4)]1}

~Rt~ . . . t,,]l = {(g, h)lh = g & (~t~]],. . . . . . ~t,,~,,) e F(R)}

Here, as usual, ~t~h = F(t) if t is an individual constant, and [[tlh = h(t) if

~3xPx~ = {(S, h) l 3k: k[x]g & (k, h) • ~Px~} =

This example illustrates the interpretation of the existential quantifier and

is best represented as conjunction. Going about compositionally, what we

According to this definition, the interpretation of & A O with input g may

less bound by it with the same force as the occurrence of x in Px in the

2.4. Dynamic Existential Quantification and Implication

The second kind of example which we introduced in Section 2.1, concerns

implication. In order to show that this kind of example can be treated in

(4) If a farmer owns a donkey, he beats it.* He hates it

In this example, the pronouns he and it in the second sentence cannot be

The interpretation of cb--+ ~ accepts an assignment g iff every possible

This example shows that the binding effects of an existential quantifier

2.5. Universal Quantification, Negation and Disjuriction

For a treatment of the second, more complicated kind of donkey-

(5) Every man walks in the park.* He whistles

The pronoun he occurring in the second sentence of (5), cannot be in-

the first sentence of (6). Generally, from examples such as these it is

~Vx6]] = {(g, h)lh = g & Vk: k[xlh @ 3m: (k, m) ¢ ~6~}

~Vx[[Px /x 3y[O s/x Rxy]] ~ Sxy]~ =

Within the limits set by a first-order language, the account we have

Hence, the interpretation of a negation ~ 4~ will be of the type of a test:

The following example, which has the structure of such sequences of

assignment g, and the condition it embodies is that at least one of its

[[05 v ~O]]= {(g, h) lh = g & 3k: (h, k) ~ [[05~v <h, k) ~ ~ }

3. D P L , A SYSTEM OF DYNAMIC PREDICATE LOGIC

This section is devoted to a formal study of the DPL-system. In Section

3.1. Syntax and Semantics

The non-logical vocabulary of D P L consists of: n-place predicates, individ-

1. If t, . . . . . t,, are individual constants or variables, R is an n-place

8. If q~ is a formula, and x is a variable, then Vx(h is a formula.

So, the syntax of D P L is that of ordinary predicate logic.

1. ~Rtl . . . tn~ = {(g, h)[h = g & ([[ttl], . . . . [[tn~h) ~ F(R)}.