On Logical Formulation of the Computation Process in Semantical Systems

Jun-Tin WangCOLING 1973

TL;DR

This paper proposes a unified framework for formalizing semantical systems using first-order predicate logic. It demonstrates how syntactic rules and semantic evaluation can be elegantly represented as logical axioms and recursive definitions, offering a more rigorous and systematic approach to understanding meaning in both natural and computer languages.

What Problem Does This Paper Address?

The paper addresses the challenge of rigorously defining semantics for both natural and computer languages. While various approaches to semantics exist (e.g., Scott and Strachey's for computer languages, Suppes's for context-free fragments of natural language, Lewis's for categorial grammar), there's a need for a unified and systematic way to represent and relate these diverse systems. The authors aim to provide such a framework by leveraging the expressive power of predicate logic, specifically first-order logic, to formalize the computational processes involved in semantic interpretation. This approach seeks to improve upon existing methods by offering a more logical and less ad-hoc representation of syntactic rules and their semantic consequences.

Methods

The core methodology presented is the formalization of syntactic rules and semantic evaluation within the framework of first-order predicate logic.

  • Syntactic Formalization: Context-free grammar rules, typically expressed as rewrite rules, are translated into logical formulas. For a rule like $A \to A_1 \dots A_n$, this is represented as a logical formula involving predicate symbols for non-terminals and individual constants for terminals, connected by conjunction and implication. These formulas form the "nonlogical axioms" of a first-order theory corresponding to the grammar.
  • Semantic Formalization: Semantic evaluation functions are defined recursively using logical formulas. This is achieved by defining semantic rules "by cases," where each case corresponds to a syntactic rule. The structural description of a syntactic rule is translated into a logical implication, where the premise represents the syntactic condition and the conclusion defines the semantic outcome.
  • Grammatical Transformations: Grammatical transformations (like the passive transformation) are represented as implication formulas in first-order logic, where the premise describes the input phrase-marker and the conclusion describes the output.

The paper illustrates these methods with examples from numeral languages, context-free fragments of natural languages, and categorial grammar.

Datasets

Not discussed in the paper. The paper focuses on formalizing theoretical frameworks rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Unified Logical Framework: The paper argues that first-order predicate logic can serve as a unifying language for diverse semantical systems, providing a rigorous and systematic way to represent syntactic rules and semantic interpretation.
  • Syntax as Logical Axioms: Context-free grammar rules can be directly translated into nonlogical axioms in a first-order theory, establishing a clear logical foundation for syntax.
  • Semantics as Recursive Logical Definitions: Semantic evaluation functions can be defined recursively using logical formulas, akin to definitions by cases in mathematics. This avoids the need for explicit phrase-markers in some semantic formalisms.
  • Grammatical Transformations as Implications: Transformations in grammar can be elegantly represented as logical implications, capturing the input-output relationship of the transformation.
  • Elimination of Phrase-Markers: For certain semantic systems (like the one for numerals), the logical formulation of rules can directly compute denotations without relying on the explicit construction of phrase-markers, simplifying the process.

Key Results

The paper presents a methodology for reformulating and improving existing semantical systems (Scott and Strachey, Suppes, Lewis) within a unified logical framework. It demonstrates how:

  • A context-free grammar can be represented as a first-order theory.
  • Syntactic rules can be characterized by logical formulas representing structural descriptions.
  • Semantic evaluation functions can be defined recursively by cases using logical rules.
  • Specific examples of numeral languages, context-free fragments of natural languages, and categorial grammar are reformulated using this logical approach.

The primary result is the conceptual framework itself, offering a more principled and unified way to approach the formalization of semantics.

Limitations and Future Work

  • No General Principle for Semantic Functions: The paper acknowledges that there isn't a universal principle for choosing the appropriate set-theoretic semantic function for each syntactic rule, especially in Suppes's system. This suggests that while the logical framework is powerful, the mapping from syntax to semantics might still require domain-specific insights.
  • Extensional vs. Intensional Semantics: The paper notes that Suppes's approach, while formalized, represents only the extensional part of semantics. The discussion of Lewis's intensional semantics hints at the complexity of capturing richer semantic phenomena.
  • Future Work: The paper implicitly suggests that this logical framework can be extended to handle more complex semantical systems, including those for computer languages and more intricate aspects of natural language semantics. The authors aim to apply this general principle to various concrete semantical systems, as demonstrated by their treatment of the examples.

Summary updated

BibTeX
@inproceedings{wang1973logical,
  author = {Jun-Tin Wang},
  title = {{On Logical Formulation of the Computation Process in Semantical Systems}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1973},
}
Figure