How to Represent Opaque Sentences in First Order Logic

1 Introduction

In BegrijjHchrijt, a formula language for pure thought modeled upon that of arithmetic, Gottlob Frege (1879) takes identity to be a relation between names or signs of objects:

mean that the .Jign A and the .Jign B have the same conceptual content, 80 that we can every­ where put B for A and conver.Jely.

This is the basic idea behind the axioms of equality which are assumed by various systems of logic. Following is an explicit list of the axioms of equality: reflexivity x = x, synunetry x = y --> y = x, transitivity x = y II y = z --> X = z, substitution in predicates

substitution in functions

A number of theorem provers 1 that are based on such logics implement the axioms of equality either directly or by various methods and rules of inference. It is because of the axioms of equality that certain conclusions can follow from premises. For example if it is true that eight is greater than five

and that the atomic numb"er of oxygen is eight

it can then be concluded, on the bases of 1, 2 and the axioms of equality, that:

which truthfully expresses the proposition that the atomic number of oxygen is greater than five . In the paper titled On Sen.Je and Denotation, Frege (1892) ex­ presses dissatisfaction with his earlier choice of the iden­ tity relation. He explnines in detail why a name cannot always be replaced by another of the same truth-value or content, in the view of the in variance of the truth of the whole sentence. It is of course assumed that declarative sentences denote a truth value (either true or false) and express a proposition (the objective content which is ca­ pable of being the common property of many), just as names have a denotation (the particular object named) and a sense (the manner and context of presentation). Ajdukiewicz (1967) illustrates the same point with the following example:

If it is true that Newton knew that eight IS greater than five

then it can be concluded, on the basis of 2, 4 and the axioms of equality that:

which is certainly not true since it expresses the proposi­ tion that Newton knew that the atomic number of oxy­ gen is greater than five (a fact which was beyond his ken).

1 For example, see the work of Wos and Robinson (1969) and more recently Digricoli and Harrison (1986).

How is it, then, that a sound system oflogic admits false conclusions based on true premises and standard rules of inference?

According to the terminology of Church (1983), this problem is called the paradoz? of the name relation. A number of radically different solutions have been pro­ posed to solve the paradox of the name relation. Follow­ ing are various contrasting views whence the source of the problem lies and how it should be solved.

2 Philosophical Views

2.1 Sense and Denotation

Frege's (1892) solution to this paradox revolves around the idea that names, sentences, or signs have associated with them a sense (the proposition expressed) which is no less relevant than the denotation. He also identifies three different contexts, ordinary, dir~ct, and indirect, in which names can be used. In an ordinary context, names have their customary denotation and sense. The direct context is what is now known as the use-mention distinction: words name (denote) other words 3 . In an indirect context, names denote their custon1ary sense, not their customary denotation, and have an indirect sense which is different than their customary sense.

The paradox is resolved since formula 4 is about the customary sense of the number eight, not its customary denotation, and formula 2 is about the customary de­ notation of the number eight, not its customary sense. Therefore, formula 2 does not warrant the substitution of f(o) for 8 in formula 4. Frege did not present a for­ mulation, similar to that provided in Begri!Juchrijt, for the logic of sense and denotation.

Church presents three different alternatives under which. a formulation of the logic of sense and denotation can be carried out . The three alternatives-Alt(~J, Alt{l}, Alt(O )- correspond to different sets of assumptions un­ der which two sentences can be considered to have the same sense or express the same proposition. That two sentences S and S1 have the same sense if and only if S = S1 is logically valid is called Alt( ~ ). A stronger criterion of identity between senses, A lt( 1 }, is that S is convertible to S1 according to the rules oflambda calcu­ lus. The strongest criterion of identity between senses, Alt(O}, is that S and S1 differ at most by one or more alphabetic changes of bound variable, or one or more interchanges of synonymous notations. Two names are synonymous if they have the same denotation as well as the same sense.

A sound system of axioms characterizing two of these altematives, Alt(~) and Alt{l}, has been specified by Church (1973, 1987). McCarthy (1979) also presented a first order theory of individual concepts and proposi­ tions based on Frege's solution ·. Formulation of the logic of sense and denotation remains open under Alt{O ), the strongest alternative under which two sentences can be considered to express the same proposition. The solu­ tion presented in this paper is under Alt{O }, however, it differs from the logic of sense and denotation.

2 Carnap (1956) used the word antinomy, but the word paradoz is preferable since no apparent contradiction occurs in the absence of any further assumptions.

,In writing, quotation marks or italic1 are used for direct contexts.

· It differs, however, from Frege's solution in that the latter calls for an infinite hiearchy of senses where as the former

2.2 Contextual Descriptions

Russell's (1905 ) 5 solution to the paradox eliminates names altogether from the language, and introduces con­ textual descriptions. The relevant distinction is that con­ textual descriptions have no meaning of their own; how­ ever, every sentence in which they occur has a meaning. It was commonly believed that the theory of contextual description can be used to resolve the paradox of the name relation as well as other paradoxes. By providing counter examples Church (1983) demonstrates that, if intensionality is to be avoided, then the theory of con­ textual descriptions cannot be adopted as a solution to the paradox of the name relation. Contextual descrip­ tions, however, remain useful for solving a variety of other problems.

2.3 Nonclassical Logics

The notion of possible worlds has recently received a lot of attention from philosophers because it can be used to provide an analysis of necessity and possibility. More re­ cently it has also been applied to propositional attitudes such as believing and knowing. A number of different modal logics based on the possible world models have been proposed.

There are disagreements, however, an10ng philoso­ phers regarding the nature of these possible worlds. Some say that possible worlds combine the actual world with other worlds that contain only things similar to those in the actual world. Others say that a possible world is described by a set of propositions, such that each proposition or its negation is a member of the set . Some of the modal logics based on possible world seman­ tics mmecessarily commit the agents to be what Hin­ tikkn (1975) called logically omniuienf. The strongest objection to nonclassical logics is the lack of efficient in­ ferencing mechanisms. Construction of efficient infer­ ence engines for modal logics must also address the com­ putational complexities of logics that are based on the possible world models.

2.4 Proposition Surrogates

This paper presents a modification, Arbab (1988), of the solution first proposed by Ajdukiewicz (1960) and later formalized by Church (1983) . The solution follows the philosophy that there is nothing inherently wrong with the underlying logic (either the rules of inference or the axioms of equality); therefore, it is unnecessary to con­ struct new logics, e.g., modal logics, or to abandon (or weaken) the axioms of equality. The source of the prob­ lem lies in how natural language sentences are to be for­ mulated in the formal language. In short, if well-formed formulas corresponding to English sentences are written correctly, then paradoxical conclusions will not arise. For example, 4 is not the correct representation of the fact that Newton knew that eight is greater than five, since it leads to paradoxical conclusions. What are, then, the well-formed formulas corresponding to natural language sentences?

allows only a single level. An infinite array of senses is called for since various levels ofindirection (Pat knows that Newton knew that ... ) can easily be formed.

5 In 1903, Russell had outlined a different solution to the paradox of the name relation. Russell (1905), however, flatly states that the Russell (1903) solution is very similar to Frege (1892), and both are shown to be unsatisfactory. The particular line of reasoning presented by Russell (1905) re­ mains unclear to this author!

8 An exception to this is Church's (1951) formulation of the logic of and sense and denotation under Alt(!) which is also based on the possible world models.

The answer is based on the idea that sentences denote truth-values and express propositions. The proposition expressed by a sentence is, of course, independent 7 of the particular natural language in which it happens to be written and can be expressed by sentences in differ­ ent languages. For example, the two sentences eight i.J greater than five, in English, and Acht i.Jt grafter al.J fiinf, in German, both express the proposition that eight is greater than five. One method of encoding propositions within a formal language is presented in this paper. The encodings are called propo.Jition .Jurrogate.J, since in the formal language they play the role of the proposition ex­ pressed by a sentence. The algorithm for constructing proposition surrogates can then be added to any formal language. h1 this paper an inference engine based on the proposition surrogate solution is presented and applied to some examples.

3 Solution

Ajdukiewicz (1960, 1967) argues that if sentences are in an indirect context, then they are ambiguous. It is primarily this ambiguity that leads to paradoxical con­ clusions. There are at least two different meanings that can be attributed to such sentences. Let us call these 'li and fl. The paradox arises because we understand the sentence on the basis of 'li, but formulate it on the basis of fl. The solution, then, is to formulate the sentence according to the understood meaning. For example, the first meaning, 'li, of the sentence

Newton knew that

the atomic number of oxygen i.J greater than five (6) can informally be stated as follows :

Newton knew about the atomic number of elements, about oxygen, about the relation greater than, about the number five, that the atomic number of oxygen is greater than five.

Sentence 6 can be formulated on the basis of~ as follows:

7 The existence of propositions are not effected by the fact that they can or can not be expressed in a particular natural or formal language.

where f, o, gt, and 5 correspond, respectively, to the atomic number of elements, the constant oxygen, there­ lation greater than, and the constant five. The ordered n­ tuple occurring in the second position of the knew pred­ icate is a proposition surrogate. Its first member corre­ sponds to the form of the formula, and the rest contain the primitive constants, function, and predicate symbols that occur in the formula. For every about clause in 'li, there is an appropriate constant, function, or predicate name in the proposition surrogate.

The formula which corresponds to a proposition sur­ rogate can be obtained by applying the first member of the proposition surrogate which is always a lambda ex­ pression containing the particular form ofthe formula to the rest of the members which are always the par­ ticular con.Jtant.f occurring in the fonuula. The formula which corresponds to the above proposition surrogate is gt(f ( o ), 5), which expresses the proposition that the atomic number of oxygen is greater than five.

The second meaning, n, of 6 can informally be stated as follows :

Newton knew

about the atomic number of oxygen, about the relation greater than, about the number five, that the atomic number of oxygen is greater than five.

Sentence 6 can be formulated on the basis of n as follows :

The distinction between the two meanings can now be made clear by examining the different number of about clauses. According to 'li, Newton knew about the atomic number of elements [f], oxygen [o], and that the value of the atomic number of oxygen [f(o)) is greater than five . IT sentence 6 is understood according to 'li, then its truth value is falsehood, since knowledge of the atomic number of elements [f) can not be attributed to New­ ton. Sentence 6 understood according to n, however, is true. The second meaning, n, of 6 does not attribute explicit knowledge of the atomic number of elements [f) or oxygen [o) to Newton: they do not individually ap­ pear among the primitive constants of the proposition surrogate.

The difficulty with this solution to the paradox of the name relation lies in the way primitive constants of the formalized language are handled: an equality relation between primitive constants of the formalized language can be used to reintroduce the paradox. Consider, for exatuple, the two sentences:

John believed that Dr Jekyll was a gentleman (9)

Sentence 9 is formalized under Alt(O) as:

where john, gent, and dj are primitive constants of the language corresponding to John, gentleman, and the Dr Jekyll respectively. Sentence 10, IS formalized m the usual way as:

lu formula 11, it is possible to substitute mh for dj on the basis of the axiom of equality and formula 12, thus arriving at the conclusion:

which corresponds to the paradoxical conclusion:

An extensional solution to the problem of primitive constants is outlined below. The idea of pointers to con­ stants (address of a particular cell within the memory of a computer) and the associated operators (obtaining the address and de-referencing) is well-known in the field of computer science. The analogy 8 between pointers and what Frege (1892) called the sense of a name Cl\ll be used to construct a solution to the problem of primitive constants of proposition surrogates.

Church's 1983 algorithm for obtaining the proposition surrogate under Alt(O) is modified so that every occur­ rence of a primitive constant, say c, in the proposition surrogate is replaced by @c (the particular pointer to c); and every occurrence of a bound variable in the body of the lambda term corresponding to the primitive constant c, is replaced by application of the * (de-referencing) operator to that variable. For example, 9 will now be fornmlized under Alt(O) as:

and although dj = mh, it does not follow that @dj = @mh. Thus, the paradoxical conclusion:

is avoided. Additionally, the proposition surrogate .in 15 may be reduced to < *(@gent), *(@dj) > which in turn cm1 be reduced to gent(*( @dj)) and finally to gent( dj).

4 Example

Let us assume, then, the availability of a two place pred­ icate ps(S, P) such that P is the proposition surrogate corresponding to S under Alt(O), for the exact details and the Prolog code see Arbab (1988) . This example .is called the The Wise Man Puzzle and has been used to test the representational ability of formalisms for knowl­ edge representation.

A certain King wishes to determine which of his three wise men is the wisest. He arranges them in a circle so that they can see and hear each other and tells them that he will put a white or black spot on each of their foreheads, but that at least one spot will be white. In fact, all three spots are white. He then offers his favor to the one who will first tell him the color of his spot.

8 This is not to suggest that Frege's (1892) sense of a name is simply a pointer to that name, only that pointers can play the logical role of the sense of a name.

After a while, the wisest announces that his spot is white. How does he know'f'J

The solution to this puzzle requires a wise man to reason about what other wise men know and do not know, from observations and the king's announcements. The puzzle solved here is actually a simplified version of the original puzzle. The simplifying assumptions are that there are only two wise men, and that after some time the first wise man l\llnounces that he cmmot tell the color of his spot, whereupon the second wise man says his own spot is white. The following is a partial list of a formulation of the puzzle in first-order logic, and Prolog modified with proposition surrogates (the complete list can be found in Arbab (1988)).

• That each wise man knows that there is at least one white spot is expressed by

Note that m is short hand for the proposition surrogate of P under Alt(O) obtained according to the algorithm presented in the last section. The corresponding Prolog clause .is:

Note that ptJ( S, P) is true iff P .is the proposition surrogate of S . Also, .if P is unbound then the Fro­ log interpreter will compute the proposition surro­ gate of S Rlld bind it to P.

• That each wise man knows that the other wise man knows that there .is at least one white spot, is ex­ pressed by

The corresponding Prolog clause is:

Notice the doubly-indirect context- thus the two calls to the ps predicate.

• That A does not know that he has a white spot, since he made an announcement to this effect, is expressed by

The corresponding Prolog clause is:

non(know(a, w(a))).

• That B knows that A does not know that he has a white spot, since B heard A's Rllnouncement, IS expressed by

know(B,[-=know(A,~_0]) I) (20) The corresponding Prolog clause is:

9 This puzzle has been attributed, by Konolige (1986), to an unpublished note by McCarthy.

kno'R'(b, P) :- ps('R'(a), P1), ps(non(kno'R'(a, P1)), P).

Once these are consulted by a Prolog interpreter, the following questions can be answered according to the standard rules of inference:

• Does B know that he has a. white spot? The Prolog formulation is:

?- ps('R'(b), P),kno'R'(b, P).

Note that, in order to answer the above question, the system must reason not only about what B knows, but also about what B knows that A knows, and so on. The reported answer is: yes.

• Does B know that A has a white spot? The Prolog formulation is:

?- ps('R'(a), P),kno'R'(b, P).

The reported answer is: yes.

• Who knows that he has a white spot? The Prolog formulation is:

?- ps('R'(X), P),kno'R'(X, P),'R'rite(X).

The distinction between this question and the first one is in the use of a Prolog variable. The reported answer is: b yes.

• List everyone who knows that he has a white spot . The Prolog formulation is:

?- ps('R'(X), P),kno'R'(X, P),'R'rite(X),fail.

The distinction between tlus question and the for­ mer is that the final fail clause will force the inter­ preter to look for all possible answers, to show that no incorrect solution is found by the interpreter. The reported answer is: b no.

5 Conclusion

It was shown that the common interpretation of the iden­ tity relation, i.e., a relation involving only denotation of names, leads to the paradox of the name relation. This is the source of inconsistencies when a classical set of axioms and rules of inference are assumed by the formal language. The philosophical point of view defended here is that the elinunation of the paradox of the name rela­ tion requires neither a modification of the classical set of axioms, nor of the rules of inference.

An inference engine based on the logic of proposition surrogates can play an important role in the field of ma­ chine intelligence, for if a machine is ever to interact in­ telligently with other agents, machines or humans, then it must be able to represent and reason with facts about the agents' state of mind. An agent's state of mind, of course, includes, but is not linuted to, facts about its knowledge, beliefs, awareness, and expectations.

The logic of proposition surrogates can be used to rep­ resent and reason with such facts . An inference engine based on the logic of proposition surrogates enables a machine not only to represent, but also to discover, log­ ical consequences of such facts.

6 Acknowledgement

This work was carried out at UCLA under the supervi­ sion of Professor Stott Parker of the Computer Science Department, and Professor Alonzo Church of the Phi­ losophy and Mathematics Departments. The author is grateful for their contributions of ideas ·and corrections made over the years. Needless to say, all remaining er­ rors are attributable solely to the author.