Chapter 11

Knowledge and Logic: Some Notions

In computer science and AI, people often talk of “knowledge”, “knowledge representation”, “efficient usage of knowledge”, etc.

We may wonder whether logic, which allowed us, for example, to verify whether a reasoning is correct, to obtain conclusions from premises, to reason with fuzzy concepts, to qualify formulas as necessary or possible and to deduce consequences, to take time into account in formulas, and to reason on these formulas…will also allow us to talk of (and define) knowledge and to reason while taking into account the knowledge of an agent in a world where there are other agents, possibly with a different knowledge.

The goal of this chapter is to try to answer this question.

Up to now, we have assumed (implicitly or explicitly) that “knowledge” was more or less a synonym of “premise” and that the initial premises did not evolve when they interacted with the environment.

But while handling problems in which the state of knowledge may change, new difficulties will arise.

In game theory (an entire discipline by itself that we only mention here), it is also necessary to take an environment that is not passive into account, meaning that the actions of the other agents in the environment are relevant in the design of strategies to reach a goal.

Recall that the ideas on probabilities play a very important role in knowledge theory (for the time being we admit the intuitive meaning of knowledge): it suffices to think of natural science. We may define probability as a numerical encoding of a state of knowledge (a probability 1 would mean a certain event and a probability 0 an impossible event)¹.

The notion of “information” is closely related to that of knowledge, and therefore to that of probability. Information can be defined as anything that leads to a change in the assignment of probabilities².

From a historical point of view, it is interesting to note that until 1660, probabilities were in opposition with knowledge, and in Galileo’s times, for example, sets of experiments did not replace proofs³.

We may now move on to the next stage: specify the abstractions that will allow us to formalize things.

11.1. What is knowledge?

A few questions and remarks naturally arise.

– What interest is there (for computer science and AI among others) to study this concept and possibly those that are related?

– A little of introspection is sufficient to imagine that those problems related to knowledge must have been studied by philosophers for a very long time: this is indeed the case.

– The Greeks and medieval philosophers were interested in this problem but experts seem to agree on the fact that the topic was studied systematically starting with Descartes, Leibniz, Hume and others (17th Century). A theory of knowledge was only envisaged starting with Kant (18th Century).

– The notion of knowledge seems inseparable from that of environment, and implicitly from our senses that allow us to interact with it.

– Philosophers propose: “to know is the action during which a subject (in computer science or AI we would say an agent) comprehends an object”, thanks to a representation (today we would say thanks to a model). It is interesting to note that Stoicians already used the notion of representation.

– Of course, problems arise, such as: “is it possible to know the entire environment (all of reality), or will we only be able to comprehend part of it?” (Note the similarity with the difficulties experienced during the act of modeling.) These problems have to be tackled by all those who study natural science, especially physicists.

– The notion of “reality” itself leads to some problems.

– Philosophers talk of “sensitive reality” and “intelligible reality”.

– Sensitive reality can often be misleading (think, for example, of optical illusions, the principle of inertia, the free fall of bodies of different weights, quantum mechanics, etc.).

– This characteristic is the reason why intelligible reality is often considered as superior to sensitive reality.

– Some schools of philosophy that considered the notion of “experience” as a key notion studied it from a broad point of view, i.e. not only as an account of phenomena but also taking into account an elaboration that can be intellectual, historical, introspective, etc.

At this stage, we can already try to identify the characteristics that we want to keep in our formalization.

– The social factor (several knowing agents) in knowledge and interaction between agents (agent X knows that agent Y does not know that agent Z …). Furthermore, it is clear that science, for example, is a social production.

– Introspection (X knows that he knows,…).

– Related to inner experience: what difference between knowledge and belief ?

– About the differences between knowledge and belief, they are opposed by the current discourse, but we can say that there is some sort of belief in knowledge, for example, that the laws of the universe do not change (with time) and that it is possible to know them.

– Belief could be defined as an adherence to an idea, an opinion, that we acknowledge as true and, partly at least, as subjective.

– It is related to the notion of probability, of which one definition is the degree of belief.

– Etymology does not seem capable of helping us, this time.

– In the search for a logical formalization, we shall make use of the following definitions, among others, that are proposed by philosophers (even if they are difficult to grasp).

– Knowledge: act of thought that penetrates and defines the object of its knowledge.

– The perfect knowledge of a thing, in this sense, is that which, when considered subjectively, does not leave anything obscure or unclear in the known thing, or that which, when considered objectively, does not leave anything that exists in the reality in which it applies outside.

– Belief: in a weak and large sense, it is the equivalent of an opinion, and denotes an imperfect consent that, similarly to an opinion, can have any degree of probability.

– …and we call probability (absolutely speaking) the character of the event it is the most reasonable to expect.

– To synthesize, we shall retain an environment of which the knowing agent(s) is (are) a particular case.

Among the logics that we have studied, modal logics (see section 10.3) are those that seem most naturally suited to be logics of knowledge because of the concepts they handle; the following definition is therefore oriented toward using these logics.

DEFINITION 11.1.– (knowledge).

– An agent knows a fact if is true in all world it considers as possible given its current knowledge.

– An agent considers as possible the worlds that are not in contradiction with the facts it holds as indubitable.

– An agent considers a fact as possible if it does not know .

REMARK 11.1.– (on the definition of knowledge).

– “Given its current knowledge” naturally leads to thinking that knowledge can change with time, which in turn naturally leads to think of the notion of learning.

– In general (always?) we have partial information about the environment.

– We could say that the more information in the possession of an agent, the less possible worlds it will consider. In other words, the number of worlds it considers as possible is directly related to its uncertainty (think of the scientific process or of a game of cards, etc.). For example, if an agent rolls a die, there are six possible worlds. If it makes an object fall, there is only one possible world.

DIGRESSION 11.1.– The knowledge modeling that is used in game theory or in mathematical economics uses concepts that are close to probabilities, in which a key notion is that of an event, i.e. the set of possible worlds.

We could say that instead of working with logical formulas, those working in these disciplines work directly on their denotation: for example, “n is an odd number” will be replaced by the set of worlds in which n is odd. “n is odd and greater than 2007” will be replaced by the intersection of the set of all worlds (states) in which n is odd, and the set of worlds (states) in which n > 2007⁴.

11.2. Knowledge and modal logic

11.2.1. Toward a formalization

The description language must be able to express the retained notions:

– We assume n agents (n ).

– Propositions on the states of the world (or on the worlds) (for example, the weather is nice, I have an ace, etc.). : the set of all atomic propositions (formulas).

– K_i. agent i knows .

11.2.2. Syntax

11.2.2.1. What expressive power? An example

– We will be able to write formulas such as (proposition P meaning: agent 1 has an ace)

– meaning: agent 1 knows that agent 2 knows that he (agent 1) has an ace and agent 2 does not know that agent 3 knows that agent 1 has an ace.

11.2.2.2. Semantics

An e-frame (e stands for epistemic):

– W ≠ ∅ : set of possible worlds

– K_i W² : accessibility relations of the agents

– v : or where, as usual, 2^W and denote sets of subsets of W and , respectively. (v is called a valuation and indistinctly gives the set of worlds in which a proposition is evaluated to T or the set of propositions that are evaluated to T in each world).

iff for all w' such that

We can see that, with the semantics of the accepted definition of knowledge, the latter is relative to the possible worlds (i.e. to the world we belong to) and to the agents (i.e. to the worlds that are accessible to them).

EXAMPLE 11.1.- (Fagin et al.).

– = (W, K₁, K₂, v)

– W = {w₁, w₂, w₃}

– v(P) = {w₁, w₃}

– K₁ = {(w₁,w₁), (w₁,w₂), (w₂, w₁), (w₂,w₂), (w₃,w₃)}

– K₂ = {(w₁,w₁), (w₁,w₃), (w₂, w₂), (w₃,w₁), (w₃,w₃)}

The accessibility relations and the valuation are, similarly to the other modal logics, represented in a compact way as a graph:

In world w₃, agent 1 knows that , but in world w₁, he does not. Agent 2 knows that in both worlds, but does not in world w₂.

To summarize, operator K_i permits descriptions in which:

– A world (state) is not completely characterized by v. Each agent has its “particular view” of reality. For example, if P is an arbitrary proposition (T in world w1), it is possible for agent 1 not to know P, and for agent 2 to know P but not to know that agent 1 does not know P,...:

We will say that a formula is valid in an e-frame , noted iff for all

is satisfiable in iff there exists w W such that

Finally, is valid iff is valid in all e-frames, and is satisfiable iff it is satisfiable in an e-frame.

11.2.3. New modal operators

To formalize the abstractions that were retained for knowledge, three modal operators are introduced (G ≠ ∅: subset of agents).

– E_G : all in G know.

– C_G: it is a common knowledge of all the agents in G (i.e. all know, all know that all know,…).

– D_G: it is a distributed knowledge among the agents in G (i.e. the agents in G know in the worlds they have access to, in other words, is a distributed knowledge among the agents in G iff is T in all worlds that are accessible by all the agents in G).

If G is the set of all agents, we shall write E, C and D.

We extend the syntax to take these new operators into account:

11.2.3.1. Syntax (extension)

– If is a formula, then are also formulas. Thus, we must add to the grammar of section 11.2:

–

…and we must also formally define the semantics of these operators:

11.2.3.2. Semantics (extension)

iff for all

– We note:

–

– % i.e. all those in G know

– % i.e. all those in G know that all those in G know

–

– iff for i = 1,2,...

– iff for all w' such that , we have

– For example we can write:

–

meaning: Agent 1 knows that P is not a common knowledge of agents 2 and 3 and Q is not a common knowledge, but a distributed knowledge in the system.

11.2.4. Application examples

11.2.4.1. Modeling the muddy children puzzle

The problem:

– n children (brothers) are playing in a muddy courtyard. Their mother told them that those who got mud on themselves would be punished.

– During the game, k children get mud stains on their foreheads.

– Of course, each child can see the mud stains on the others’ foreheads, but not on their own.

– Each child hides what he sees.

– Their father, who always tells the truth, comes home and says: at least one of you have a mud stain on your forehead (a fact which, if k > 1 was known by all. If k = 1, then the one with the stain on the forehead did not know that).

– The father repeats again and again the question: “does one of you know that he has a mud stain on the forehead?”

– We assume that the children reason perfectly and that they never lie.

– Thus (this is what needs to be proved) during the first k — 1 times the question is repeated, the children will answer “no”, but when the father asks the question for the k^th time, the children with mud stains on their forehead will answer “yes”.

The modeling:

– Similarly to all modeling phases, the notions of “good” models and information are implicit. There is common knowledge that is implicit (for example, no child is blind).

– P_i: child i has a mud stain on his forehead.

– Each world will be characterized (named) by an n-tuple (x₁, x₂, …x_n); x_i {0, 1}

(with the meaning: “child i has a mud stain (has no mud stain) on the forehead iff x_i = 1 (x_i = 0)”)

– Thus, iff x_i= 1.

– We, therefore, define v, taking this into account.

– For the sake of simplicity we can define:

11.2.4.2. Corresponding Kripke worlds

We assume there are three children. The graph below represents all possible configurations of mud stains on the children’s foreheads (2³ possibilities). The triples (i,j,k) (i,j,k {0,1}) correspond to the valuations (here, we also use them as names of worlds or states). The (double) arrows denote the world (or state) that each child considers as possible (i.e. w.r.t. the accessibility relation) in the world in which he is (i.e. where he sees what he sees).

For the sake of readability, we did not draw for each child and each world the arrows with the same origin and destination.

– We can write, for example:

–

–

–

–

–

–

–

The father speaks the graph changes.

– For example, in (1,0,1), child 1 considers (0,0,1) as possible, and in this world, 3 considers (0,0,0) as possible.

– Hence, 1 considers as possible that 3 considers as possible that no child has a mud stain on the forehead.

– When the father says P, things change:

– No child considers state (0,0,0) is possible anymore.

11.2.4.3. Properties of the (formalization chosen for the) knowledge

Similarly to all modeling phases, the abstraction adopted for knowledge must be subject to analysis to evaluate its pertinence. The researchers who proposed it note that the properties and consequences of the definition of knowledge that was accepted correspond to what we informally expect of this concept.

For example, we can prove:

– % Distribution axiom;

– For all if then % Knowledge generalization rule

This property states that an agent knows every valid formula (…but not necessarily those that are true).

– % Knowledge axiom knowledge ≠ belief (see example 10.17)

This property states that an agent does not know something false.

– % Positive introspection axiom (see example 10.17)

– % Negative introspection axiom

---

1 See definition 11.1.

2 This definition uses “knowledge” as a primitive concept. We shall give a formal definition of this concept in definition 11.1.

3 See section 8.4.

4 In the initial developments of probability theory, people talked of “propositions” with the meaning of events. It is after Kolmogorov’s axiomatization that elementary events were treated as sets. Stochastic situations can be modeled indifferently using sets or propositions.