W - A Logic System Based on the Shared Common Knowledge Views

1. Introduction

Undoubtedly, the representation of and reasoning of common knowledge is a typical problem in KR (Knowledge representation and Reasoning) research; It is typical because it plays an important role in multi -agent reasoning, communication, distributed computing system, etc .. But what is common knowledge? How do we use common knowledge? Just as knowledge, there are different opinions about these questions among different people. But everyone agree that the representation of and reasoning of common knowledge depends on the representation of and reasoning of knowledge in which common knowledge.exists. To put it briefly, there are three opinions about common knowledge [Barwise 1988]. One is "infinite level" or "iterate level" opinion [Lewis 1969]. Say cp is common knowledge for the agent group G, if

1. each agent in group G knows cp;

2. each agent in group G knows the fact "1"; n+ 1. each agent in group G knows the fact "n";

It is shown that [Halpern & Moses 1984], tlus kind of knowledge can not be gained in a synchronous and most distributed processing systems.

The second is the so called "fixed point" opinions [Harman 1977]. By introducing an operator Ca. we get a complete axiomatization to express the common knowledge's properties. The axioms and inference rules involved are follows [Halpern and Moses 1985]:

C3 is called Ca's fixed point a'<iom, and RC1 is the common knowledge inductive inference rule. Obviously, this opinion of common knowledge characterizes the properties of common knowledge, but it gives no hint on how to use it.

The last is the shared environment common knowledge opinion where every knowledge is associated itself with a situation and each situation is also every agents' cognizable object [Clark and Marshall 1981]. For example, let p, q be two agents, we have three statements under situation S:

Then cp is p and q' s common knowledge. This opinion of common knowledge leads to the outcome of PROS IT system [Nakashima, et al 1991]. Undoubtedly, situation logic can express and apply common knowledge effectively; Can other logics, for example classical modal logic, express and apply the shared common knowledge effectively? In this paper, the answer is "Yes".

The paper is organized as follows: In section 2, we discuss the characteristics of logic under the shared common knowledge, we introduce the conception of "common knowledge agent" (we simply call it fool reasoner). Subsequently, an axiom logic system W based on knowledge language is given, it characterizes the multi-agent reasoning system based on shared common knowledge. In section 3, we briefly describe the proof properties of W, and conclude that: W is monotonic, powerful and can do common sense reasoning; W has four levels of contradictions. This means that local contradiction can not spread into global contradiction, one agent's contradiction can not lead other agents to be contradictive. In section 4, we prove that Conway Paradox can be easily solved in W. At last we give the future work under development.

2. Logic Under Shared Common Knowledge Views

In order to express shared common knowledge in logic, one of the obvious methods is to introduce a "virtual agent" in logic. Tlris agent's knowledge is common knowledge, so it is also be called "fool reasoner". This agent must have following properties:

1. Common knowledge agent (denoted by 0) must believe all tautology instance statement.
2. 2.If 0 believes p, then 0 also believes that every agent believes p. Here 'believe' has the same meaning as 'know'.
3. If 0 believes p, then p must necessarily be true.
4. If Kip is common knowledge, then p is also common knowledge.
5. How to use O's knowledge is also common knowledge. For example, "if agent i believes p and p -+ q is common knowledge, then agent i believes q" is also common knowledge.

Every agent can have his own axioms and inference rules. The inference rules can be non-monotonic [Wang 1990, Wang and Chen 1990]. In this paper, we only consider the simple case where every agent (apart from 0 agent) are same, they have no local axioms and inference rules. We especially consider how common knowledge can be used by each agent. Considering the logic be constructed for multi-agent reasoning system, we do not need the knowledge axiom: Kip -+ p. Definition 1. Let FO be basic proposition set, AG={0,1, ... ,n} is the set of agents in which 0 is called commmtknowledge agent, then the well-founded formula based on FO and AG is defined as follows:

1. Basic formula
2. If p E FO, then p is basic formula.
3. If p, q are basic formulas, then p & q, .., p are basic formulas.

b. Fonnula

1. Basic formula is formula.
2. If p and q are formulas, then.., p, p & q, Kip are formulas, here i=O, 1 , ... ,n.

Define p v q · .., (.., p & .., q), p -+ q · .., (p & .., q).

Definition 2. Defme formula Kil...Kilp to be simple formula, if l :<!: 0, i1, ... ,ilEAG, pis basic formula.

Definition 3. LetT be a set of formula, we call T to be a view of the world. In general we divide T into (n+2) parts.

T = Ts v KOTO v ... v KnTn.

Here, Ti ={p I Kip E T} for i=O, ... ,n.

Ts is called system knowledge, and Ti is called agent i's vtew.

Example 1. Conway Paradox

During a card game both Max and Pat have an ace. If asked whether they have any knowledge about the other person's cards they will answer no and this answer won't be different if the question repeated ; But if someone tells them "At least one of you has an ace", a fact they can infer from their own cards, the answer will be 'no' for the first answering (Max) and 'yes, he/she has an ace' for the second of the two (Pat). Suppose p be the statement 'Max has an ace', q 'Pat has an ace' ,then the Conway Paradox's formal description is a view: T1 = {p,q, KO(p v q), KO(K1p v K1.., p), KO(K2q v K2.., q), K1p, K2q}

• = {p,q} v ;system knowledge

KO{p v q, K1p v K1.., p, K2q v K2.., q} v; at least one has an ace, each man knows whether he has an ace.

Obviously system's knowledge p, q can not be knowledge of every agent, so the knowledge generalization rule: q, ~ Ki q, does not hold in our logic system. In W this rule is replaced by a weaker rule: KO q, ~ KOKi q,.

Definition 4. W logic system.

W's axioms:

AI. For every tautology p, we have KOp.

A2. KO((Ki(p -+ q) & KOp) -+ Kiq)

A3. KO((KO(p-+ q) & Kip)-+ Kiq)

A4. KOp-+ p

A5. KOKip -+ KOp

A6. KO(Kip -+ KiKip)

W's inference rules:

Rl. KOp ~ KOKip

When n=O, R2 become general modus ponens rule p, p -+ q ~ q. R2 is called multi-level modus ponens rule (MMP). Now we explain what these axioms mean.

A 1 says that every tautology is common knowledge.

A2 says that 'If pis common knowledge and agent i knows p -+ q, then agent i knows q' is common knowledge. This means that every agent can do common sense reasoning by using common knowledge and its own knowledge. This axiom is called common knowledge's distributed axiom 1. A3 says that 'if p -+ q is common knowledge, and agent i knows p, then agent i knows q' is common knowledge. It is called common knowledge's distributed axiom2.

A4 says that common knowledge must be system's knowledge, it must be true.

AS says that 'If agent i knows p is common knowledge, then pis also common knowledge'.

A6 says that 'If agent i knows p, then agent i knows that it knows p' is also common knowledge. It means that every agent knows that each agent has positive introspective ability. In section 3, we will prove some basic properties of W.

3. Basic Properties of W

Definition 5. Suppose Tis a view, we define T f- <p, if there is a sequences of formulas: fO, ... ,fx, x :2:: 0 such that:

2. For every i: x :<:: i :2:: 0,

fi is an axiom; or

fi is a formula ofT; or

fi is a formula of the form KOK.ip, such that there a fj, i :2:: j :2::0, fj is KOp, we say we have got fi by using rule R1 on fj; or

fi is in the fonn of Kil...Kil q, and there is fjl,fj2 such that i > j1j2:.:: 0, fj1 is K.il...Kil(p-+ q), fj2 is Kil...Kilp. We say fi has been got by using rule R2 on formulas fjl,fj2.

Call fO, ... ,fn a proof sequence of <p, and we denote{} f- <p by r- <p.

Suppose T={f1, .. . ,fn} (n>=O), we sometimes denote T f- <p by fl , ... ,fn f- <p.

Lemma 1. For every tautology p, f- Kip

Proof: Kip's proof sequence is: KOp, KOK.ip, KOK.ip-+ Kip, Kip.

Lemma 2. For every tautology p, il , .. . , il E AG, f­ Ki1 ... Kilp

Proof:

We first prove that for any l :2:: 0 we have:

We inductively prove it.

When 1=0 , it obviously holds.

Suppose l=t, it also holds.

When l=t+ 1, Since f- KOKi2 ... Kit+ 1 p,KOKi2oo.KOKit+ 1 p ~ KOKi1Ki2oo.Kit+1p

So by using rule Rl, we get f- KOKil.. .Kilp.

Since f- KOKil...Kilp KOKil...Kilp-+ Kil...Kilp So, f- Kil...Kilp . .

Lemma 3. p -+ q, .., q f- .., p

Proof:

.., p's proof sequences is:

p-+q,

.., q-+-, p,

.., q,

.., p.

Lemma 4. Let il, 000 ,il E AG then

Kil...Kil(p-+ q),Kil...Kil,.., q f- Kil...Kil.., p Proof:

Omitted.

Lemma 5.let i1, oo .,il E AG,p,q are formulas then

Proof:

Omitted.

Proof:

Omitted.

A general result is:

Theorem 7. Suppose il, .. . ,il EAG, q is a tautology· consequence of p1,p2, .. . ,pm, then Kil...Kilpl,oo. , Kil...Kilpm f-Kil...Kilq

Proof:

As q is a tautology of pl ,p2, .. . ,pm

Inductively we can prove that:

The logic system W is strong: Every agent has enough ability to do reasoning. It should be noticed that W itself is a monotonic logic. Because there is a common knowledge agent, we can not use Kripke model to define W's model semantics directly. Its proper model semantics is under development.

Since every agent's knowledge is closed, so there are four sorts of contradictive concepts in W.

Definition 6. We defme a view Tis hidden contradictive, if there are il, ... , il E AG (l ::<!: !),formula <p such that:

We defme a view Tis contradictive about agent i if there is a formula <p such that:

We defme a view Tis commonly contradictive if there is a formula <p such that:

We say view Tis basically contradictive, if there is a formula <p such that:

We call a view T is locally contradictive if it is hidden contradictive or contradictive about some agent i, here i>O. There four sorts of contradictions have the following relation:

That is: If view T is commonly contradictive then it must be basically contradictive, hidden contradictive and contradictive about any agent; if view Tis contradictive about agent i then it must be hidden contradictive.

4. How W Solve The Conway Paradox.

Continuing Example 1, we inquire" Can agent 1 (Max) know q?" to view Tl, agent 1 will answer "No". So we have not ( n rKlq).

5. Conclusion

In this paper, we propose a logic system W based on the idea of shared common knowledge views. It characterizes shared common knowledge under a multi-agent reasoning system. W's axioms and inference rules describe the properties and usage of common knowledge. These axioms and inference rules are primitively computable, soW has good computability. W has the following characteristics:

1. The fool reasoner is used to describe the common knowledge of all agents.

2. The knowledge in view is in different levels. For example let f E T, but f may be not known by agent i; This means that W is not a knowledge system which has the knowledge generalization inference rule: f ~Kif; Also what agent knows may be not true, so knowledge axiom Ki f --+ f does not hold. 3. Every agent's inference ability is not weaker than propositional inference.

4. Every agent has enough power to utilize common knowledge.

5. As regards to 2, a view can not be basically contradictive caused by local contradiction.

Though with such features, W is still an initial logic system, · there are many unsolved aspects, including:

1. W 's model theory.
2. W's consistence.
3. W's effective proof algorithms.

All these three aspects are very important. The results presented in this paper can serve as a standpoint for the research on common knowledge. Further research work on the formalism of common knowledge is expected to enrich our understanding of common knowledge and to obtain more fruitful results.

Acknowledgements

Tins research was partly supported by Chinese NSF contract No. 69203003 and Chinese High. Tech. program contract No. 8633060516D. Thanks to members of Chinese KR&R research group for their helpful discussion, and to the anonymous IJCAI reviewers for comments and criticism.

Reference

[Barwise, 1988] Barwise, J. 1988. Three Views of Common Knowledge. TARK'88, pp. 365-380.

[Clark and Marshall, 1981] Clark, H. and Marshall, C., 1981. Definite Reference and Mutual Knowledge, In Elements of Discourse Understanding. pp.l0-63 Ed. A. Joshi, B. Webber and J. Sag, Cambridge Un. Press.

[Fagin and Halpern 1988] R. Fagin and D. Y. Halpern, Reasoning About Knowledge and Probability: Preliminary Report, TARK'88, pp. 277-293.

[Harman, 1977] Harman, G., 1977. Review of Linguistic Behavior. Edt. by Jonathan Bennett, Language 53:417-424. [Halpern and Moses, 1984] Halpern, J. Y. and Moses, Y., 1984. Knowledge and Common Knowledge In Distributed Environment. In Proc. 3rd ACM Symp. on Principle of Distributed Computing. pp50-61

[Halpern and Moses, 1985] Halpern, J.Y. and Moses, Y., 1985. A Guide to the modal Logic of Knowledge and Belief. IJCAI'85, pp. 480-490.

[Konolige, 1982] Konolige, K., 1982. Circumscriptive Ignorance. AAAI-82, pp. 202-204.

[Lewis, 1%9] Lewis, D., 1%9. Convention. A Philosophical Study, Harvard V. Press.

[Nakashima. et al, 1991] Nakashima, H., Peter, S. and Schutze, H., 1991. Communication and Inference Through Situations. IJCAI'91 pp. 76-81.

[Schiffer, 1972] Schiffer, S., 1972. Meaning. Oxford Un. Press.

[Wang, 1990] Xianchang Wang, 1990. A Multi-Reasoner Reasoning System Logic - MRSL. <<Knowledge Engineering Advance in China 1990>>, China Un. of Geoscience Press.

[Wang and Chen, 1990] Xianchang Wang and Huowang Chen, 1990. On Assumption Reasoning In Multi Reasoner System. Proc. of PRICAI'90, Nagoya, Japan.

[Wang, 1992] Xianchang Wang, 1992. Knowledge I Common Knowledge: Their Representation and Reasoning. Workshop on the Representation and Reasoning About Common Knowledge, Sponsored by Chinese High. Tech. Expert Comnlittee on Intelligence Computer System.