On Logical Formulation of the Computation Process in Semantical Systems

In the recent years there is an intensive search for a rigorous and explicit semantics in the theory of natural languages (and in the field of computer languages). In this paper we want to present a general framework in which all these ideas and results can be stated and related in a unified and systematic way, and at the same time, by the using of the language of predicate logic, eventually of higher order, to reformulate and improve the different semantical systems: the system discussed by Scott and Strachey in their development of the theory of mathematical semantics for computer languages, the set-theoretic semantics for context-free fragments of natural languages proposed by Suppes and, finally, Lewis's iutensional semantics for a categorial grammar. In § 1, mainly by the example of context-free grammar, we show that the language of predicate logic of first-order can be used to describe the syntax of an object language. We obtain then in § 2 a logical characterization of structural descriptions associated with each reformulated syntactic rule. This leads to the development of the recursive mechanism in the form of definition of semantic functions by cases. This general principle will be then applied in § 3--5 to treat the concrete semantical systems mentioned above.

In the recent years there is an intensive search for a rigorous and explicit semantics in the theory of natural languages (and in the field of computer languages). In this paper we want to present a general framework in which all these ideas and results can be stated and related in a unified and systematic way, and at the same time, by the using of the language of predicate logic, eventually of higher order, to reformulate and improve the different semantical systems: the system discussed by Scott and Strachey in their development of the theory of mathematical semantics for computer languages, the set-theoretic semantics for context-free fragments of natural languages proposed by Suppes and, finally, Lewis's iutensional semantics for a categorial grammar. In ~ 1, mainly by the example of context-free grammar, we show that the language of predicate logic of first-order can be used to describe the syntax of an object language. We obtain then in ~ 2 a logical characterization of structural descriptions associated with each reformulated syntactic rule. This leads to the development of the recursive mechanism in the form of definition of semantic functions by cases. This general principle will be then applied in ~ 3-5 to treat the concrete semantical systems mentioned above.

GRAMMAR (SYNTAX) AND FIRST-ORDER THEORY
Let us begin with the study of the representation of a grammar as a first-order theory, namely as a theory formalized in the language of predicate logic of first-order. We consider especially the contextfree grammar, since it builds up on the one hand the basis for the development of the transformation grammar, on the other hand all the This work is supported by Deutsche Forschungsgemeinschaft. semantical systems to be discussed below are referred essentially to context-free languages.
In general, a context-free grammar consists of a set of rewriting rules each of which is of the form where A, Ai,, .... At,, stand for nonterminal symbols (category symbols) and a¢,, ..., ain for terminal symbols and some of A i and at may be null. We can describe this form of context-free rule by the following logical formula (here and in the sequel we omit the universal quantifications) : (1:2) At, (xl)^ A,, (x=)^ ... ^ A,,, (x,,) = A (x'i'aFx~'aF...-x~'at,,), where we take A, Ai,, ..., Ain as unary predicate symbols and at1, ..., at, as individual constants; the symbols "^" and "~ " are the conjunction and implication sign and the function symbol ..... stands for concatenation. The set of logical formulae thus obtained are called the nonlogical axioms of the first-order theory corresponding to the given context-free grammar.
• As an example, we consider the following context-free grammar given•by P. SUVVES (1971) Corresponding to this set of context-free rules we can state the following nonlogical axioms: It is obvious that a context-free grammar and its corresponding firstorder theory enumerate the same set of terminal strings. More precisely, for each K-derivation of a terminal string w in a given contextfree grammar in the sense of Chomsky, where K stands for any nonterminal symbol in this grammar, the formal sentence

K(w)
is in the corresponding first-order theory logically derivable (J. T. WANe, 1973).
With this result we can state even the principle to formulate each grammatical transformation, which according to Chomsky is a mapping of phrase-markers into phrase-markers, as a nonlogical axiom in the following way: we describe both the applied phrase-markers and the resulting phrase-markers, or parts of them, with formulae in the language of predicate logic of first-order which occur then respectively as premises and conclusion of an implication formula. This very implication formula can be. then taken as the representation of the grammatical transformation in question. As an example, for the passive transformation, which has been specified by Chomsky as follows: structural description: NP, Aux, V~, NP structural change: x~-xa-xa-x4 ~ x4-x~-be-x3-en-by-xl we might state then the following nonlogical axiom:

S(xlx2x3x4) A NP(xl)^ Aux(x2)A Vt(xa)^ NP(x,) , D S(x~'x~'be-x~'en-by'~x~)^ Ve(x~'be-x~en-br-Xx ).
It seems evident, that the same principle stated above can be applied to the logical formulation of other grammatical transformations as well.

SYNTACTIC RULE AND STRUCTURAL DESCRIPTION
The results obtained abo~ce indicate that, in general, syntactic rules can be described in the language of predicate logic of first-order in the form p~/X where P stands for a conjunction of formulae as premises and A for a conjunction of formulae as conclusion of the rule (nonlogical axiom) corresponding to the given syntactic rule. This suggests, however, that we may take the formula P^A as a characterization of the structural description of the strings generated by the reformulated syntactic rule in question. For example, we can take the formula The set of formulae of structural descriptions thus obtained, one for each reformulated syntactic rule, specify therefore exhaustly and disjoin@ the syntactic conditions, with respect to which the semantic evaluation function, which assigns a denotation or meaning to each generated terminal string, can be defined recursively. This is the kind of the definition of the (semantic) functions by cases in the usual mathematical sense. With this general characterization of our approach we are going now to treat the concrete semantical systems.

SEMANTICAL SYSTEM FOR THE LANGUAGE OF NUMERALS
Our general idea of using the language of predicate logic, eventually. of higher order, to give a recursive definition of the semantical functions can be well illustrated by reformulating the simple semantical system for the language of numerals, whicl'/has been given by D. SCOTT and C. STI~AClIEY (1971) as an example in their development for a theory of mathematical semantics for computer languages. In the following, we give just our reformulation and do not repeat their specification of syntax and semantics for this simple language.
The numerals are expressions in a certain familiar language; while the numbers are mathematical objects (abstract objects) which provide the intended interpretations of the expressions. Based on the explicit syntax given by Scott and Strachey in the form of context-free grammar, we can describe this syntax for binary numerals by the following logical formulae: Thus, for each x ~ Nml, the function value f(x) is the number denoted by the numeral x.
Based on the idea of the semantical equations given by Scott and Strachey and using our general principles described in ~ 2, we can use the language of predicate logic to state the following semantic rules which define precisely this evaluation function:

Numeral (x),, Numeral (xA1) = f(xA1) = 2f(x) + 1.
This set of logical formulae forms a recursive definition of the semantic evaluation function f with the help of the auxiliary numbertheoretic functions of addition and multiplication. It is a definition of function by cases in the usual mathematical sense. Furthermore, this formulation corresponds to the intuitive idea in the linguistic theory, that on the basis of the grammatical properties and the meaning of the basic expressions of the languages the semantic rules enable one to determine the meaning of any well-formed expression in terms of its syntactic structure. In the terminology ofJ. J. KaTz, J. A. FODOR (1963), (3.1) and (3.2) can be considered as the dictionary component, and (3.3) and (3.4) as the projection rules. However, it is essential to note, that is this kind of logical formulation of syntactic and semantic rules there is no need of any existence of phrase-marker for the semantical system where the symbol Numeral is a predicate symbol and the symbols " 0" and " 1" are individual constants. Thus, a numeral is either one of the digits " 0 " or " 1 " or is the result of suffixing one of these digits to a previously obtained numeral. Let the set of all numerals be called Nml. Semantically speaking each of the numerals is meant to denote a unique number. Let N be the set of numbers. The obvious principle of interpretation provides a function f, the evaluation mapping, which has the functional character: to compute the denotation or meaning of the expressions. The structural description of a string generated by a syntactic rule is used just as the premises of the semantic rule corresponding to this very syntactic rule.
In this way, we can treat the other complicated semantical systems for computer languages discussed by Scott and Strachey. However, with this simple illustration of our general approach to semantics, we like to continue our study of the semantics for natural languages.

EXTENSIONAL SEMANTICS OF CONTEXT-FREE FRAGMENTS OF NATURAL
LANGUAGES Within our general framework described in ~ 1-2 and illustrated in 3 we want now to treat the semantical system proposed by P. SUVVES (1973). We indicate informally at first his approach and give then our reformulation and improvement of his system.
In his study of the semantics of context-free fragments of natural languages, Suppes intends to give a set-theoretical account of the meaning of a sentence. To do this, a set-theoretical object will be assigned to each basic expression (word). In the case of a noun like men the class of men will be assigned; in the case of a proper noun like John the class consisting of a certain single member will be assigned; in the case of a transitive verb like hit the class consisting of pairs of individuals x and y such that x hit y will be assigned. In this kihd of approach, we assume thus, that over the individual words an assignment function v be defined, which assigns a denotation to each word. (We leave aside the discussion about syncategorematic expressions). To give an account of meanings (or denotations) of the various parts of a sentence and their relationships, Suppes introduces set-theoretical functions, just like we have used number-theoretic functions in the semantical system for the language of numerals. With each syntactic rule of the grammar there is associated a semantic set-theoretical function, For example Using the assignment function v which assigns denotations to basic expressions only and using these semantic set-theoretical functions associated with each syntactic rule, the denotation of each labeled node of phrase-marker of the sentence will be then calculated. In Suppes's explicit formulation, the nodes of the phrase-marker will be numbered, so that the denotation function f is actually defined for pairs (n, s), where n is the number assigned to a node of the phrase-marker and s is a terminal or nonternfinal symbol. For example, a numbered phrase-marker looks like this otherwise.
The calculation of the denotations of expressions will be thus indirectly achieved by the way of the calculation of the denotations of the nodes of the numbered phrase-marker. This unnecessary complication with the whole matter of numbered phrase-marker, which can be traced back to the specification of context-free grammar in form of rewriting rules, would not arise at all, if the context-free grammar had been formulated in the language of predicate logic since the very beginning of the development of theory of grammar by Chomsky. In fact, the process to compute the denotation of an expression can be specified by the following set of logical formulae directly and precisely: (4.1) (4.2) (4.3) (4.4) (4.5) (4.6) (4.7)

~. g,(A, B) = F.
By the set of the semantic rules which use these set-theoretic operations, the denotation of any well-formed expressions in this defined language can be then directly calculated. Thus, the denotation of the composed expression hit Mary is the set of individuals who hit Mary; the sentence John hit Mary is true if and only if the set consisting of the single individual John is properly contained in the set of individuals who hit Mary. This set of logical formulae forms with respect to the given assignment function v a recursive definition of the denotation functionf which assigns to each well-formed expression of the language a set-theoretical object. This function has namely the functional character:

f: Expressions-+ Set-theoretical Objects.
It is just what Suppes intends to have.
Again, (4.1)-(4.3) can be considered as the dictionary component, and (4.4)-(4.7) as projection rules. The whole set of formulae constitutes a definition of function by cases. The premise of each rule states the syntactic condition, with respect to which the function value is then specified. At the same time, we do not need even the notion of phrase-marker which has played the central role in the concept formation in the theory of generative grammars.
Note there is no general principle to guide us in choosing for each syntactic rule the corresponding semantic set-theoretical function. It may be even possible that no set-theoretical operation can be found for a given syntactic rule at all. It seems likely that in our usual understanding of natural languages we do not use any set-theoretical operation. Anyway, from the standpoint of theory of meaning, the semantics treated by Suppes is only the extensional part of the semantics of a language (A. CHURCH, 1951). With these remarks in mind, let us now consider the intensional semantics discussed by Lewis in his theory of categorial grammar.

5.
INTENSIONAL SEMANTICS FOR CATEGORIAL GRAMMAR D. LEWIS (1970) treats a categorial grammar in the sense of Ajdukiewicz as a context-flee grammar of the following sort.
First, we have a finite number of basic categories like the categories of name (N), common noun (C) or sentence (S). Second, we have infinitely many derived categories like the categories of intransitive verb (S/N), adjective (G/C) or article ((S/(S/N))/C). In general, whenever c, q, ..., c,, for n ~ 1, are any categories, either basic or derived, we have a derived category c/q ... c,. Third, we have context-free rule of the form (5.1) c~c/cx ... c.+q +... +c.
corresponding to each derived category, where "-t-" stands for the concatenation.
One of the main ideas behind the theory of categorial grammar is that the phrases of a derived category are phrases which combine phrases of basic or derived categories to form other phrases of certain category, which may be basic like the category of sentence or derived. Such phrases are called functors by H. B. CURRY (1961). Every functor combines one or more phrases, called its arguments, to form a new phrase called its value. This syntactic property shall be reflected in stating the semantic projection rule. We note here that the contextfree rule of the form (5.1) can be described, as before, by the following logical formula as a direct translation: where we take c/q ... q, cl ..... cn and c again as unary predicate symbols. The word order as specified in the context-free rule (5.1) is sometimes too odd; the phrase of a derived category takes always the left-most position in its combined phrase. To take into account the natural word order, we should actually describe it.by the following logical formula: With these remarks about the syntactic rules in a categorial grammar, we are prepared to treat Lewis's intensional semantics within our general framework.
Let us denote the sets of phrases of name, common noun, adjeCtive, intransitive verb, article etc. by Names, Common-Nouns, Adjectives, Intransitive Verbs and Articles respectively. Let Things denote the set of things and Sets the set of sets of things. And let T denote the set of truth values, and let I denote the set of indices, each of which is, roughly speaking, a package of the various factors like possible world, time, place and speaker on which the extension of an expression may depend. As used before, given any two domains D1 and Da, we write [D~ ~ D~] for the set of all functions from D1 into D2. We write h: D1 ~ D2 to indicate that h is just such a function.
According to Lewis's theory, an appropriate intension for a name is any function from indices to things; an appropriate intension for a common noun is any function from indices to sets of things; an appropriate intension for an adjective is any function from commonnoun intensions to common-noun intensions, etc. In adapting this point of view, we shall consider in the sequel assignment functions, each of which assigns an appropriate meaning to a word of certain category, with the following functional charact.ers: is the assigned meaning of the word man, where this meaning itsel is a kind of function from indices to sets of things (individuals). In what follows, we assume that such assignment functions specifying an appropriate meaning for each word of certain category are already given or known to us, for example by learning or ostensive definition, In other words, we assume we know the meaning of each individual word. The problem is just how we can know the meaning of any well-formed expression in this language. We ask namely for a semantic evaluation function, which can compute the meaning of any wellformed expression on the basis of its syntactic structure and the meaning of its constituting words. This evaluation function f shall have namely the following functional character: To define this function, .we begin with the specification of its value for the individual words or basic expressions, based on the given assignment functions. As before, we state thus the following semantic rules, here formulated in the language of predicate logic of higherorder due to the functional characters of the assignment functions: based on the assumption, that the meaning of an expression depends on the meanings of its parts; it is a function of the meanings of its parts. This function g, which uses the meanings of these parts as arguments to compute the meaning of the composed phrase as its value, must be, first of all, specified. In general, as we have seen in the case of Suppes's system, there is no uniform principle to do it. In his semantic theory for categorial grammar, Lewis holds, however, the view that the result of concatenating a phrase of the category c/q ... c~ with intension i0, a phrase of the category c1 with intension/1, ..., and a phrase of the category q with intension i, is a phrase of the category e with intension ;0(il ..... i.).

s/N ( 1 ep4,, n (John) =.f (John-steees)=f (sleees) 0 r (john)).
In combination with the logical formulae (5.4)-(5.8), such rules enable one to derive logically the meaning of the sentence like John steeps, which can be represented as v, (sleefs) (vx (John)). And this representation would correspond to the usual so-called logical form: SLEEP (j). The set of projection rules thus obtained specifies in connection with those semantic rules like (5.4)-(5.8), which constitute the dictionary component, the evaluation function f recursively. This kind of formulation of semantic rules stands very near to our intuition, that on the basis of the syntactic structure and on the knowledge of the meanings of the constituting words we can understand the meaning of an expression. The semantic projection rule stated above has a nice homogeneous feature in specifying semantic evaluation function. This holds actually for all grammars using the notion of functor which combines one or more phrases as its arguments to form a new phrase. The meaning of the composed phrase can be then always considered as the result of the operation of the meaning of the functor with the meanings of its arguments. According to H. B. CURRY (1961), what Harris and Chomsky call transformations are also functors. From this point of view, we can then state the semantic projection rule for a given transformation rule in the same way as described above.