Informally, different statements in different languages can mean
"the same thing." Formally, that "thing," called
a *proposition*, represents abstract, language-independent,
semantic content. As an abstraction, a proposition has no physical
embodiment that can be written or spoken. Only its statements
in particular languages can be expressed as strings of symbols.

According to Peirce (1905), "The meaning of a proposition is itself
a proposition. Indeed, it is no other than the very proposition
of which it is the meaning: it is a translation of it."
Mathematically, Peirce's informal statement may be formalized
by defining a proposition as an *equivalence class* of sentences
that can be translated from one to another while preserving meaning.
Some further criteria are necessary to specify what kinds
of translations are considered to "preserve meaning."
Formally, a *meaning-preserving translation* *f* from
a language *L*_{1} to a language *L*_{2} may be defined
as a function that satisfies the following constraints:

*Invertible*. The translation function*f*must have an inverse function*g*that maps sentences from*L*_{2}back to*L*_{1}. For any sentence*s*in*L*_{1},*f*(*s*) is a sentence in*L*_{2}, and*g*(*f*(*s*)) is a sentence in*L*_{1}. All three sentences,*s*,*f*(*s*), and*g*(*f*(*s*)) are said to*express*the proposition*p*.*Proof preserving*. When a sentence*s*in*L*_{1}is translated to*f*(*s*) in*L*_{2}and back again to*g*(*f*(*s*)) in*L*_{1}, the result might not be identical to*s*. But according to the rules of inference of language*L*_{1}, each one must be provable from the other:*s*|-*g*(*f*(*s*)), and*g*(*f*(*s*))|-*s*. Similarly,*f*(*s*) and*f*(*g*(*f*(*s*))) must be provable from each other by the rules of inference of language*L*_{2}.*Vocabulary preserving*. When*s*is translated from*L*_{1}to*L*_{2}and back to*g*(*f*(*s*)), the logical symbols like " and the syntactic markers like commas and parentheses might be replaced by some equivalent. However, the same*content words*or symbols that represent categories, relations, and individuals in the ontology must appear in both sentences*s*and*g*(*f*(*s*)). This criterion could be relaxed to allow terms to be replaced by synonyms or definitions, but arbitrary content words or predicates must not be added or deleted by the translations.*Structure preserving*. When*s*and*g*(*f*(*s*)) are mapped to*Peirce Normal Form*(with negation ~, conjunction Ù, and the existential quantifier $ as the only logical operators), they must contain exactly the same number of negations and existential quantifiers, nested in semantically equivalent patterns.

Attempts to apply formal definitions to natural languages are fraught
with pitfalls, exceptions, and controversies. To avoid such problems,
the definition of meaning-preserving translation may be restricted
to formal languages, like CGs and KIF. The sample sentence
in Figure 5.12 could be defined as part of a formal language
called *stylized English*, which happens to contain many
sentences that look like English. Yet even for formal languages,
the four criteria require further explanation and justification:

*Invertible*. The functions*f*and*g*are not exact inverses, since*g*(*f*(*s*)) might not be identical to*s*. To ensure that*f*is defined for all sentences in*L*_{1}, the language*L*_{2}must be at least as expressive as*L*_{1}. If*L*_{2}is more expressive than*L*_{1}, then the inverse*g*might be undefined for some sentences in*L*_{2}. In that case, the language*L*_{2}would express a superset of the propositions of*L*_{1}.*Proof preserving*. Preserving provability is necessary for meaning preservation, but it is not sufficient. It is a weak condition that allows all tautologies to be considered equivalent, even though the proof of equivalence might take an exponential amount of time. Informally, the test to determine whether two sentences "mean the same" should be "obvious." Formally, it should be computable by an efficient algorithm ¾ one whose time is linearly or polynomially proportional to the length of the sentence.*Vocabulary preserving*. Two sentences that mean the same should talk about the same things. The sentence*Every cat is a cat*is provably equivalent to*Every dog is a dog*, even though one is about cats and the other is about dogs. Even worse, both of them are provably equivalent to a sentence about nonexistent things, such as*Every unicorn is a unicorn*. An admissible translation could make some changes to the syntactic or logical symbols, as in the sentence*If something is a cat, then it is a cat*. It might replace the word*cat*with*domestic feline*, but it should not replace the word*cat*with*dog*or*unicorn*.*Structure preserving*. Of all the logical operators, conjunction Ù is the simplest and least controversial, while negation ~ introduces serious logical and philosophical problems. Intuitionists, for example, deny that ~~*p*is identical to*p*. For*relevance logic*, Anderson and Belnap (1975) disallowed the*disjunctive syllogism*, which is based on Ú and ~, because it can introduce extraneous information into a proof. Computationally, ~~*p*and*p*have different effects on the binding of values to variables in Prolog, SQL, and many expert systems. The constraints on quantifiers and negations help ensure that formulas in the same equivalence class have the same properties of decidability and computational complexity.

**Examples of Meaning-preserving Translations. **
To illustrate the issues, consider meaning-preserving translations
between two different notations for first-order logic.
Let *L*_{1} be predicate calculus with Peano's symbols
Ù, Ú, ~, É, $, and ",
and let *L*_{2} be predicate calculus with Peirce's
symbols +, ×, -, -<, S, and P.
Then for any formulas or subformulas *p* and *q* in *L*_{1},
let *f* produce the following translations in *L*_{2}:

*Conjunction*.*p*Ù*q*Þ*p*×*q*.*Disjunction*.*p*Ú*q*Þ -(-*p*×-*q*).*Negation*. ~*p*Þ -*p*.*Implication*.*p*É*q*Þ -(*p*×-*q*).*Existential quantifier*. ($*x*)*p*Þ S_{x}*p*.*Universal quantifier*. ("*x*)*p*Þ -S_{x}-*p*.

*Conjunction*.*p*×*q*Þ*p*Ù*q*.*Disjunction*.*p*+*q*Þ*p*Ú*q*.*Negation*. -*p*Þ ~*p*.*Implication*.*p*-<*q*Þ*p*É*q*.*Existential quantifier*. S_{x}*p*Þ ($*x*)*p*.*Universal quantifier*. P_{x}*p*Þ ("*x*)*p*.

The functions *f* and *g* in the previous example show that
it is possible to find functions that meet the four criteria.
They don't map any sentences to the same equivalence class unless
they can be said to "preserve meaning" in a very strict sense,
but they leave many closely related sentences in different classes:
permutations such as *p*Ù*q* and *q*Ù*p*; duplications such as
*p*, *p*Ù*p*, and *p*Ù*p*Ù*p*; and formulas with renamed
variables such as ($*x*)P(*x*) and ($*y*)P(*y*).
To include more such sentences in the same equivalence classes,
a series of functions *f*_{1}, *f*_{2}, ..., can be defined,
all of which have the same inverse *g*:

*Sorting*. The function*f*_{1}makes the same symbol replacements as*f*, but it also sorts conjunctions in alphabetical order. As a result,*p*Ù*q*and*q*Ù*p*in*L*_{1}would both be mapped to*p*×*q*in*L*_{2}, which would be mapped by*g*back to*p*Ù*q*. Therefore,*f*_{1}groups permutations in the same equivalence class. Since a list of N terms can be sorted in time proportional to N*log*N, the function*f*_{1}takes just slightly longer than linear time.*Renaming variables*. The function*f*_{2}is like*f*_{1}, but it also renames the variables to a standard sequence, such as*x*_{1},*x*_{2}, ... . For very long sentences with dozens of variables of the same type, the complexity of*f*_{2}could increase exponentially. A typed logic can help reduce the number of options, since the new variable names could be assigned in the same alphabetical order as their type labels. For the kinds of sentences used in human communications, most variables have different types, and the computation time for*f*_{2}would be nearly linear.*Deleting duplicates*. After*f*_{1}and*f*_{2}sort conjunctions and rename variables, the function*f*_{3}would eliminate duplicates by deleting any conjunct that is identical to the previous one. The deletions could be performed in linear time.

This series of functions shows how large numbers of closely related
sentences can be reduced to a single *canonical form*.
If two sentences express the same proposition, their canonical forms,
which can usually be calculated efficiently, would be the same.
The function *f*_{2} has the effect of reducing sentences to
*Peirce Normal Form* (PNF) ¾ the result of translating a
sentence from predicate calculus to an existential graph and back again.
As an example, consider the following sentence, which Leibniz
called the *Praeclarum Theorema* (splendid theorem):

This formula may be read(( pÉr) Ù (qÉs)) É ((pÙq) É (rÙs)).

This form is not as readable as the original, but it serves as the canonical representative of an equivalence class that contains 864 different, but highly similar sentences. The function~((~( pÙ ~r) Ù ~(qÙ ~s)) Ù ~(~(pÙq) Ù ~(rÙs)) ).

To account for synonyms and definitions, another function *f*_{4}
could be used to replace terms by their defining lambda expressions.
If recursions are allowed, the replacements and expansions would be
equivalent in computing power to a Turing machine; they could take
exponential amounts of time or even be undecidable.
Therefore, *f*_{4} should only expand definitions
without recursions, direct or indirect.
Since the definitions may introduce permutations, duplications,
and renamed variables, *f*_{4} should expand the definitions
before performing the reductions computed by *f*_{3}.
Without recursion, the expansions would take at most polynomial time.

**Meaning in Natural Languages. **
When functions like the
*f*_{i}
series are extended
to natural languages, they become deeply involved
with the problems of syntax, semantics, and pragmatics.
In his early work on *transformational grammar*,
Noam Chomsky (1957) hoped to define transformations as
meaning-preserving functions. But the transformations that moved
phrases and subphrases had the effect of changing the scope
of quantifiers and the binding of pronouns to their antecedents:

*Every cat chased some mouse.*

Þ*Some mouse was chased by every cat.**We do your laundry by hand; we don't tear it by machine.*

Þ*We don't tear your laundry by machine; we do it by hand.*

AI-based computational linguistics has also involved a search for
meaning-preserving translations, but with more emphasis on semantics
and pragmatics than on syntax. Roger Schank (1975), for example,
developed his *conceptual dependency theory* as a canonical
representation of meaning with an ontology of eleven primitive action
types. Although Schank was strongly opposed to formalization
of any kind, his method of reducing a sentence to canonical form
could be viewed as a version of function *f*_{4}.
In his later work (Schank & Abelson 1977; Schank 1982), he went beyond
the sentence to higher-level structures called *scripts*,
*memory organization packets* (MOPs), and *thematic
organization packets* (TOPs). These structures, which have been
implemented in framelike and graphlike versions of EC logic,
address meaning at the level of paragraphs and stories.
Stuart Shapiro and his colleagues have implemented versions of
*propositional semantic networks*, which support similar
structures in a form that maps more directly to logic (Shapiro 1979;
Shapiro & Maida 1982; Shapiro & Rappaport 1992). Shapiro's propositional
nodes serve the same purpose as Peirce's ovals and McCarthy's contexts.

Besides the structural forms of syntax and logic, the meaning-preserving translations for natural languages must account for the subtle interactions of many thousands of words. The next two sentences, for example, were adapted from a news report on finance:

*The latest economic indicators eased concerns that inflation is increasing.**The latest economic indicators heightened concerns that inflation is increasing.*

Last Modified: