A Logical Model of Knowledge
Proceedings of the Eighth International Joint Conference on Artificial Intelligence. Knowledge Representation. Pages 374-375.
© 1983 International Joint Conferences on Artificial Intelligence
Abstract
There are several approaches to formalizing knowledge. The concept of knowledge is often introduced by a special operator whose properties are de fined by a number of axioms. A situation is then mod e ll ed by using this operator in problem-specific axioms. This article presents a different approach - a ftrst-order logical model which does not use any new operators. The properties of knowledge should fo llow from the problem-specific axioms only . The advantages are that the model is simpler and requires fewer axioms. The formalization of a problem can almost directly be used as a computer program which produces the solutions.
- 6J (
- 8J (9J Hintikka, J .: Knowledge and Belief: Aa /atrotlactioa to tile Logic of tile Two Notion•. Cornell University Press, Ithaca, New York , 1962.
- Konolige, K.: A Firlt-Order Forrnali.:ratioa of Knowledge utl Actio a for a Malti-Agent Planning S111tem. Technical Note 232, SRI International, Menlo Park, California, 1980.
- Levesque, H. J .: Tile lrlleractioa witll Incomplete Knowledge Bau1: A Formal Treatment. In Proc. IJCAI-81. Vancouver, B.C., Canada, August, 1981 , Vol. 1, pp. 24~245.
- Mc Carthy, J.: Firlt Order Tlleorie• of lntlindaal Concept• and Propolition1. In J .E. Hayes Ill D. Michie Ill L.l. Mikulich: Machine Intelligence 9. Ellis Horwood Ltd, 1979, pp. 120-147. "Challenge• attributed to John McCarthy. AISB Quarterly, Issue 35, October, 1979, p.
- McCarthy, J . & P .J. Hayes: Some Pllilo•opllical Problem~ from the Standpoint of Artificial Intelligence. In B. Meltzer Ill D. Michie: Machine Intelligence 4. Edinburgh University Press, Ed inburgh , 1969, pp. 463-502.
- Moore, R.: RetJioning &boat Knowledge &lltl Action. Technical Note 191 , SRI International, Menlo Park, California, 1980.
- Nilsson, M.: A Logical Model of K11.owledge tll&t Ha11.dlu Fal1e Knowledge. Technical Report (in preparation). UPMAIL, Com- puting Science Department, Uppsala University, Sweden, 1983.
- Pereira, L. M. Ill F. Pereira Ill D. Warren: U1er'1 Gaide to DEC1111tem-10 Prolog. Laboratorio Nacional de Engenharia Civil, Lisbon, Portugal, 1979.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. Introdudlon
The classical work in the field of formalizing knowledge is by Hiotikka III. McCarthy and Hayes 161 point to the importance or epi& temology for Artificial Intelligence. Several different epistemological theories with connections to computer science have followed, e.g. by McCarthy 141, Moore 171, Konolige 121, and Levesque 131.
All of the authors 11,2,3,4,71 model knowledge by introducing a truth-valued operator K . This operator is described by a number of axioms. The knowledge that a formula holds is formalized by saying that K holds for an argument that is a term which represents that formula. A drawback of this method is that a large number of axioms are required to describe K , and to define the mapping between terms and formulas. Another hard problem is the problem of substituting equals for equals in the arguments of a referentially opaque operator like K . Following an example by Aristotle: The man approaching you is Coriscus. You know that Coriscus is musical, but that does not imply that you know that the approaching man is musical, even though the men are identical. You have to know that they are iden tical. There are plenty of other problems with models of knowledge, and they are carefully studied in the impressively thorough work 171.
We argue that too many axioms will make the computational treatment of knowledge more complicated than necessary. They force the user to have a general theorem prover, they increase the indeter minacy of the computation, etc. The main dill'erence between the above models and our model is that it does not have the intermediate step of a knowledge operator. The formalization of a problem is self contained (except for the logical axioms of first-order logic). It bas a form which greatly simplifies use of the formalization as a computer program.
type or logic, or properties or such a logic, which are often associated with possible worlds.
For every problem we have a domain W0 , which is the set or possible worlds or descriptions of states. One or these is the actual world, or a description or the current state. The set of all possible solutions W1 is the set or all members .z or W0 such that some problem specific constraint p(.z) holds. Sometimes we might need to generalize this idea a bit: The set or solutions is instead the set or function values I : W1 , where W1 is the set or all states in W0 satisfying p(.z). The function I extracts the interesting information from the state description.
Traditional philosophy classifies questions as "whether" questions and "what" questions. The former kind asks Cor a truth value, "Does p hold?" The latter kind asks for a value, "For which .z does p(.z) hold!" If predicates are regarded as truth valued functions, we can cover both or these cases by a more general question: "What is the value or l(.z) when p(.z)!" In the first case, the function I is equivalent top, and in the second, it is the identity function. Let .z be the actual world, i.e. a description or the current state. Then the actual answer to the question above will be l(.z). It is important to note here that the actual answer is supposed to be unique. The question "What is a square root or l!" should therefore be reformulated as "What are the square roots or 1!" The domain could then be the set or sets or numbers, and the solution is the set {-1,1}. We cannot choose the set or numbers as the domain, since that does not give us a sufficient state representation.
6. A Model of Knowledge
We shall now model knowledge in terms or the number of possible solutions to a question.
If we describe knowledge by "having the answer to a question," we can formalize it by saying that the set or possible solutions contains exactly one element, namely the actual world. If the set or possible solutions contains more than one element, we can't know which one corresponds to the actual world, and therefore we don't know the solution. Thus our basic models of knowledge are
where W is the set or possible worlds.
Conditions such as "A knows that B knows 1." where A and B are two different agents, can now easily be formulated: Let W(A) be A's set of possible worlds, and let W(B, .z) be B's set of possible worlds seen from A's viewpoint. This set depends on the actual world .z. Since A does not necessarily know what the actual world is, he has to try out all his possible worlds for .z.
The first formula here says that p holds for all elements of W(A), i.e. A knows that p. The second defines p(.z) to hold iff A computes I : W(B, .z) to contain exactly one element, i.e. it A can deduce that B must know I, assuming that the actual world is .z. For comparison, using logic notation, equivalent formulas are:
The different sets or possible worlds usually depend on two arguments - the agent and the actual world (or what is assumed to be the actual world tor the moment)- and the corresponding predicates depend on the same two and also the possible world to be tested. The predicate w here is in tact very similar to the accessibility relation K ot I7J. Here, bowever, no apec:ial axiom ilauppoeed to bold i'or w.
"I know" is represented with a singleton, and "I don't know" with a set of more than one element. It is natural to ask if the empty set equation I : W = {} has any meaning. I : W is empty iff W is empty. Erroneous information or an incorrect assumption has made the agent rule out the actual world from his set or possible worlds. ([71 prohibits this exclusion by a reflexivity axiom which in our formalism would be VaV.zw(a, .z, .z).) This corresponds to false questions in the theory or questions. A classical example is "Have you stopped beating your wife yet!" This question contains false premises (hopefully), and bas no answer. Here, neither or "I know that you have stopped" nor "I don't know if you have stopped" is adequate. A third case, which can be interpreted as a detection or a false premise, must be included. This view seems to be adequate particularly for problems about false knowledge ISJ.
0. Examples of Properties of Knowledge
The deductions in this section are somewhat informal for the sake or space. An intuitive property or knowledge is that "I know /" implies that "I know that I know I." In our model the first statement is
Ir we define p(.z) .... 1: w = {-} (where w is independent or .z) we can express the statement by V.z p(.z). But since W is non-empty, we must have
which simply says that "I know that I know 1-"
Another example is Aristotle's Coriscus-problem. One possible world representation here is a tuple or boolean values, <m .. iclllitr oi-Cori·c .. , m .. iclllitr-ol-rruu&>. If we define
the tact that it is known that Coriscus is musical becomes
The knowledge that the mao is musical becomes
p 1 restricts W to{< True,True >, < True,Fal1e >}. Now, (B) holds only it W is further restricted by a constraint that implies that the two components are equal, or, in other words, that it is known that they are equal.
Suppose that it is known that p holds, and that it is known that p -+ q holds. We should then be able to deduce that it is known that q holds. But for all .z, p(.z) and p(.z)-+ q(.z) imply that q(.z). In particular, the antecedents hold for all .z in W, and so q(.z) holds for all.z in W. Since W is non-empty, q: W = {.}.
7. Some Re·ult· from Applylns the Model to Problem Solvln1
McCarthy lSI has suggested a certain kind or problem as a test or the adequacy or models or knowledge. These problems deal with knowledge about knowledge and are often hard to solve because of their complicated structure. We have applied our model to several such non-toy problems, among others tbe well-known "Mr. S. and Mr. P." problem (Freudenthal, 10M). It has turned out that with our model we can solve these problems by computer in a simple way. The modelling and solving methods are described in detail in ISJ. Many problems dealing with false knowledge cu be bandied within first order logic: without risking ooo-moaotooicity. For a larce class of problems 1) the formalization is very similar to the original problem, and 2) tbe formalization can alm06t directly be used as computer program which generates the solutions. Due to the stereotypical form of the formalizations, they are extremely easy to translate to a logic programming language, for instance Prolog.
The backtracking depth-first strategy of Prolog leads to an "enu merate and test" solution process. This strategy is sometimes very inefficient (especially when the domain is infinite), although the pr~ gram in many cases can be rewritten or transformed to a more efficient form. Future research will have to lind out if and how that can be done automatically.
8. Acknowledgment.
Gunnar Blomberg's help to typeset this article is much appre ciated. Also, I want to thank my colleagues at UPMAIL for useful comments to earlier drafts of this paper.
V. Appendix
To exemplify, we shall give a formalization of the "Mr. S. and Mr. P." problem. The formalization is followed by a program that solves the problem.
The problem goes as follows: A person thinks of two numbers between 2 and lUI , inclusive. (This defines the domain.) He then tells Mr. S. the sum (constraint p 1 ), and Mr. P. the product (p 2 ). A dialogue starts between Mr. S. and Mr. P. "I don't know the numbers," says Mr. P. (p 3 ). "I don't know them either, but I knew that you wouldn't know," says Mr. S. (p,). "Then I know them!" answers Mr. P. (p 6 ). "Then I know them too," says Mr. S. (p 0 ).
The w:s in the formalization represent the successive sets of solu tions, which are restricted by the constraints p1· The set of solutions is the final set of p06sibilities from the problem solver's point of view, W(01 , ·), or the set of z such that w(O., 1 , z) holds.
w(O, 1 , (m, n)) +-+mE {2, . . . , 99} An E {2, ... ,m}. w(S1 , ' · z) +-+ w(O, 1 , z) A p1 (· , z). w(P1 , 1, z) +-+ w(O, 1 , z) A p 2 (· , z). w(Sz , ·, z) +-+ w(S,, '· z) A Ps(z). w(P2 , ' · z) +-+ w(P., 1, z) A p,(z). w(S1 , 1 , z) +-+ w(S2 , ' · z) A p 6 (z). w( O., 1 , z) +-+ w(O, 1, z) A p1 (z) A p,(z) A P&(z) A Po(z). p1((m, n), (i, i)) +-+ m + n = i + j . p 2 ((m,n), (i, i)) +-+ mn = ij. p1 (z) +-+ {Ill w(P., z, u)} = {., ., · · · }. p,(z) +-+ {ul w(Sz , z, u)} = {., . , .. . }A {p1 (z) I w(S1, z, .:r)) = {True}. p 6 (z) .... {Ill w(Ps , z, u)} = {.}.
p 0 (z) +-+{Ill w(Ss , z, y)} = {.}.
The Prolog program for the problem is written in Dec-lO Prolog diaJect (OJ . The answers are generated by asking the system "! - w(ol , .,X)."
w(O, S, (M,N)):- inclo·ed(M,(%,99]), inclowl(N,(%, M)). incloud(l, [J, L]) : - J =< L, (I= J; K i· J + 1, inclo·ed(I,(K,L])). value(X, true) :- call(X). value(X, fal·e) :- \ +caU(X). w(ll,S, X) : - w(O, S , X), p1(S,X). w(p1, S,X) : - to(O,S,X), p2(S, X). w(·2, S , X) : - w(ll,S,X), p3(X). w(p2, S, X) : - w(pl, S, X), p4(X). w(·3, S , X) : - w(·2,S,X), p5(X). w(ol , S, X) : - w(O, S, X), p3(X), p4(X), pS(X), pG(X). p1((M, N), (/, J)) :- M + N = :=I+ J. p2((M, N),(/,J)) :- M·N=:=l·J.
p3(X) : - ·etof(Y, w(pl , X, Y), [., ., ..· 1). p4(X) : - ·etof(Y, w(·2,X ,Y), [.,., ..· ]), ·etof(Z, W A (w(ll, X, W), 11alue(pJ(W), Z)), [true]). p5(X) : - ·etof(Y, w(p2, X, Y), [.1). p6(X) : - ·etof(Y, w(·3, X, Y), (.]).
The efficiency of this Prolog program can be raised if we replace the calls to ·etof by some procedure that does not generate more instances of the first argument than necessary. Also, the definition of w(ll, S ,X) can be made more efficient by integrating w(O, S ,X) and pl(S, X), and similarly for w(p1 , S,X). The CPU-time required to solve the problem on a Dec-2060 is then on the order of 20 minutes.
10. References
- [tJ Hintikka, J.: Knowledge and Belief: Aa /atrotlactioa to tile Logic of tile Two Notion·. Cornell University Press, Ithaca, New York , 1962.
- [21 Konolige, K. : A Firlt-Order Forrnali.:ratioa of Knowledge utl Actio a for a Malti-Agent Planning S111tem. Technical Note 232, SRI International, Menlo Park, California, 1980.
- (3J Levesque, H. J.: Tile lrlleractioa witll Incomplete Knowledge Bau1: A Formal Treatment. In Proc. IJCAI-81. Vancouver, B.C., Canada, August, 1981, Vol. 1, pp. 24~245.
- [41 McCarthy, J.: Firlt Order Tlleorie· of lntlindaal Concept· and Propolition1. In J.E. Hayes Ill D. Michie Ill L.l. Mikulich: Machine Intelligence 9. Ellis Horwood Ltd, 1979, pp. 120- 147.
- "Challenge· attributed to John McCarthy. AISB Quarterly, Issue 35, October, 1979, p. 38.
- [6J McCarthy, J. & P.J. Hayes: Some Pllilo·opllical Problem~ from the Standpoint of Artificial Intelligence. In B. Meltzer Ill D. Michie: Machine Intelligence 4. Edinburgh University Press, Edinburgh, 1969, pp. 463-502.
- (71 Moore, R.: RetJioning &boat Knowledge &lltl Action. Technical Note 191, SRI International, Menlo Park, California, 1980.
- [8J Nilsson, M.: A Logical Model of K11.owledge tll&t Ha11.dlu Fal1e Knowledge. Technical Report (in preparation). UPMAIL, Com puting Science Department, Uppsala University, Sweden, 1983.
- (9J Pereira, L. M. Ill F. Pereira Ill D. Warren: U1er'1 Gaide to DEC1111tem-10 Prolog. Laboratorio Nacional de Engenharia Civil, Lisbon, Portugal, 1979.
@inproceedings{ijcai1983p89,
title = {A Logical Model of Knowledge},
author = {Nilsson, Martin},
booktitle = {Proceedings of the Eighth International Joint Conference on
Artificial Intelligence, {IJCAI-83}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Alan Bundy},
pages = {374--375},
year = {1983},
note = {Knowledge Representation},
url = {https://ijcai.org/proceedings/1983/89},
}
TY - CPAPER TI - A Logical Model of Knowledge AU - Nilsson, Martin T2 - Proceedings of the Eighth International Joint Conference on Artificial Intelligence, IJCAI-83 PB - International Joint Conferences on Artificial Intelligence PY - 1983 SP - 374 EP - 375 UR - https://ijcai.org/proceedings/1983/89 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: