User:Rubysargasso

From Wikipedia, the free encyclopedia

Contents 1 Alternatives to Standard Kripke Structures (SKSs) 2 Introduction 3 Alternative Structures 4 Other Alternatives to SKSs 5 Reference 6 See Also

[edit] Alternatives to Standard Kripke Structures (SKSs)

[edit] Introduction

The knowledge operator K is closed under logical consequence in standard Kripke structures (SKS), so SKSs model "logically omniscient" agents. That is, if the formulas K[a]p and K[a]q are true at world w, where p and q are true in every world epistemically accessible to an agent a, then a knows (p or q), K[a](p and q), K[a](if p, then q), and ~K[a]~p at w.

In the actual world, agents commonly do not know formulas entailed by their knowledge -- sometimes because they possesses a sound but incomplete set of inference rules, sometimes because they are unwilling or unable to do the requisite derivations. Defeaters abound.

The alternative structures introduced here provide logical apparatuses for modeling such "resource-bounded" agents. They also provide ways of reasoning about single agent systems, in which an agent's knowledge is intuitively implicit rather than attributed explicitly by the modeler to the agent.

It is useful to keep in mind the following concepts for the purposes of our introduction:

A. Types of Logical Omniscience

Full logical omniscience, which exists in SKS, requires that an agent knows all of the formulas logically implied by the formulas he knows. The following weaker forms of logical omniscience may or may not exist in alternative structures:

(1) Knowledge of Valid Formulas: Agent knows all valid (i.e. necessarily true) formulas.

(2) Closure Under Logical Implication: Agent knows q if and only if (i) agent knows p, and (ii) (p logically implies q).

(3) Closure Under Logical Equivalence: Agent knows q if and only if (i) agent knows p, and (ii) p and q are logically equivalent.

(4) Closure Under Material Implication: Agent knows q if and only if (i) agent knows (p => q), and (ii) agent knows p.

(5) Closure Under Conjunction: Agent knows p and q if and only if (i) agent knows p, and (ii) agent knows q.

B. Locality of Knowledge

In SKSs, we can define classes of worlds which are indistinguishable to an agent. Worlds w and v are indistinguishable to an agent if, when she knows p in state w, she also knows p in state v, in cases in which w is related to an v by an equivalence relation (reflexivity, symmetry, and transitivity). Because some alternative structures abandon the use of equivalence relations, we are not able to discuss the locality of knowledge in their models.

C. Standard Propositional Semantics

Standard propositional semantics allows us to reduce the number of cases in proofs by induction by allowing equivalencies between logical connectives. Under standard propositional semantics, (p or q) <=> ~(~p and ~y); (if p then q) <=> (~p or q). These equivalencies hold in SKSs but not in some alternative structures.

[edit] Alternative Structures

A. Explicit Representations of Truth

1. Syntactic Structures

a. The Model

SKSs consist of a frame F = (W, K[1], . . . , K[n]) and a valuation function [pi] which assigns truth values to the primitive propositions in each world. The syntactic approach replaces the standard valuation function [pi] with [sigma], a valuation which "explicitly represents truth", as it is not constrained by standard propositional semantics in its assignment of truth values. So [sigma] may assign true to both p and ~p in world w.

It is important to note that standard propositional semantics, perhaps counterintuitively, does hold in syntactic structures. As a result, the true formula p or q is equivalent to ~(~p and ~q) in world w, despite the fact that ~(~p and ~q) may be false in w.

It is also important to note that we can engineer [sigma] to force our model to approximate the standard definition of knowledge, which is one source of flexibility in this approach.

b. Properties of Knowledge on Syntactic Structures

Given valid, logically equivalent formulas p and q, [sigma] may assign false to the formula K[a]p and true to the formula K[a]q. In other words, the K operator is not an equivalence relation under this model, and thus knowledge is not defined as truth in all possible worlds. As a result, no form of logical omniscience, including knowledge of valid formulas, necessarily holds in syntactic structures.

c. Agents Modeled by Syntactic Structures

A model in a syntactic structure could neatly capture intuitions about knowledge in the following scenario: A child cannot determine that p=q, where p=x*0, q=y*0, x=/=y, x and y are integers, because she has not learned that multiplying an integer by 0 results in the product 0. In such a case, the child has a consistent set of base knowledge and a sound set of arithmetic inference rules, but she is resource-bound by the fact that her set of inference rules is incomplete, i.e. it does not allow her to prove all of the truths in the arithmetic.

d. Weaknesses of Syntactic Structures

Because the K operator is not an equivalence relation, syntactic structures do not have possibility relations between their worlds, and consequently syntactic assignments cannot capture the notion of the locality of an agent's knowledge. Moreover, the structure is not negation complete, which means that we cannot prove the compactness of its models.

Because they explicitly represent knowledge, syntactic structures may violate our intuitions concerning reasoning about knowledge. Due to this lack of expressive power, syntactic structures have been dubbed a means of representing knowledge rather than a means of modeling it.

2. Semantic Structures

a. The Model

A semantic structure, or a Montague-Scott structure (MS), is a tuple (W, [pi], C[1], . . . , C[n]) where W is a set of worlds, [pi](w) is a truth assignment to the primitive propositions for each world w in W, and C[i](w) is a set of subsets of W, for i = 1, . . . , n. MSs explicitly represent the truth values of propositions by defining the valuation [pi] as a function mapping propositions to worlds, rather than propositions to truth values. Accordingly, the semantics of these structures is specified in terms of sets of worlds in which given propositions in the model are true, i.e. in terms of the "intensions" of its propositions. As a result, to an agent, p is indistinguishable from q just in case p and q have the same intension, or are true in exactly the same worlds. Unlike syntactic structures, MSs explicitly fix the semantics of propositions while retaining the notion of possible worlds.

Because the semantic approach reduces the semantic content of known formulas to sets of worlds, we can capture an agent's knowledge by listing the set of worlds in which the propositions he knows hold true. We refer to this set with the notation (C[a](w)), where a is an agent and w is a world, and C is the set of worlds containing only those propositions that a knows at w.

Standard propositional semantics holds for atomic propositions, conjunctions, and negations, but the semantics of the knowledge operator is specified in terms of (C[a](w)). We say that a world logically implies knowledge of a proposition if and only if that world is in the set of worlds in which the proposition is true.

b. Properties of Knowledge on MSs

Because the knowledge operator is given meaning in terms of its membership in a class of models that make a proposition true, we have closure under logical equivalence in semantic structures. That is, where p=q, the axiom (if K[a]p, then K[a]q) holds because, by definition, formulas with the same truth values in all possible worlds are indistinguishable to an agent.

Although there is a failure of all other forms of logical omniscience in MSs, we can accommodate other properties of knowledge by constraining the intensions of propositions. Knowledge of valid formulas, for example, is secured when we stipulate that all worlds are in the intension of K[a]p. Similarly, we get closure under conjunction by stipulating that the intensions of the propositions p and q are equivalent to the worlds in the intersection of C[a]p and C[a]q.

c. Weaknesses of MSs

MSs are able to model types of logical omniscience other than closure under conjunction without increasing the complexity of reasoning required to make the appropriate derivations in the structure. However, once we modify the structure to allow for closure under conjunction, semantic structures become PSPACE-complete rather than NP-complete, and this is undesirable for reasons beyond the scope of this entry.

B. Nonstandard Structures

Nonstandard Structures leave the SKS knowledge operator K in tact but change the semantics of epistemically available propositions. In other words, these structures have the expressive power provided by equivalence relations, but they are restricted from expressing certain types of logical omniscience because of the nature of the propositions able to be known by agents in the structures.

Nonstandard structures utilize aspects of the syntactic approach in their free assignment of truth values, and they also define propositional semantics in terms of worlds as in the semantic approach.

In nonstandard models we say that an agent has logical omniscience "with respect to" the nonstandard semantics of the formulas in the model. There are several ways to make propositional semantics nonstandard; here we present an approach which modifies the standard semantics of negation.

1. The Model

A nonstandard Kripke structure M is a tuple (W, [pi], K[1], . . . , K[n], *), where the tuple (W, [pi], K[1], . . . , K[n]) is a Kripke structure, and * is a unary function from the set of worlds W to itself (where we write w* for the result of applying the function * to the world w) such that w** = w for every w in W. Though we retain the notion of possible worlds, we redefine each world w as a set of databases, one containing the formulas that are true in the world and one containing those that are false. Without loss of generalization, we say that p is true if it belongs to the "database" of true formulas, such that p can belong to both the true and false databases at any given point in time. Furthermore, every world w has a counterpart world w* which contains the set of databases that are compliments of those in the "source" world w.

Talk of membership in databases allows p to have "an independent truth value": a truth value that is not defined semanticaly in terms of its negation. The propositional semantics of negation is correspondingly modified: ~p is true in w not if p is not logically implied by w, but rather only if ~p has membership in the compliment class of false formulas in w*. If w=w*, then we secure the standard propositional semantics of negation.

If p and ~p are in neither database, then neither proposition is true or false, hence nonstandard models do not presuppose monotonicity. We refer to a world in which p and ~p hold as incoherent, and one in which neither p nor ~p hold as incomplete.

2. Properties of Knowledge in Nonstandard Structures

One interesting feature of nonstandard structures is that logical implication is not synonymous with material implication. In order for K[a](p => q) to hold, whenever K[a]q holds, K[a]p must hold as well. This is on account of the independence of the truth values of propositions in nonstandard structures, which prevents (p => q) from being logically equivalent to (~p or q). Nonstandard structures therefore define a new logical connective which allows them to express material implication which has the meaning specified above.

There are no valid formulas in nonstandard structures in part on account of its treatment of negation. It is not the case that a world makes p true if and only if the world does not logically imply ~p. Thus, anther interesting feature of nonstandard structures is that, while knowledge of valid formulas holds, there are no valid formulas in nonstandard structures, this property of knowledge has an idiosyncratic meaning.

3. Agents Modeled by Nonstandard Structures

Because nonstandard models can represent worlds in which both p and ~p are true, they provide a means of modeling situations in which, for example, witnesses provide conflicting information about a crime without our logic suffering from the disadvantages of the explicit representation approaches.

4. Advantages of Nonstandard Structures

Some find standard propositional semantics unintuitive or otherwise problematic. For instance, it is far from obvious that any formula is logically implied by an invalid statement. So it is sometimes appealing to provide propositions with nonstandard semantics. Indeed, as opposed to the syntactic structure outlined above, the semantics of nonstandard models actually provides these structures with comparatively intuitive and instructive means of reasoning about knowledge.

C. Impossible Worlds Structures

While logicians consider worlds in which agents have knowledge of contradictions impossible, such impossible worlds are often epistemically available to agents for reasons outlined in the introduction, and we want to model them when they figure into agent's reasoning processes.

1. The Model

Impossible world structures augment a set of standard possible worlds with a set of worlds in which the standard rules of propositional logic do not apply. For example, we may have (p and q) true in a world in which neither p nor q is true. Such worlds are referred to as impossible worlds, and they serve only as epistemiclly accessible, but not metaphysically possible, states of affairs. Logical implication and validity are determined solely with respect to the standard worlds. Thus, while standard propositional semantics holds in possible worlds, the semantics in impossible worlds can functions in fanciful ways.

2. Properties of Knowledge in Impossible World Structures

The primary feature of impossible world structures that allows us to avoid logical omniscience is that logical implication is evaluated with respect to only possible worlds, while an agent’s knowledge is evaluated with respect to all of the worlds she considers possible, impossible and possible worlds alike. Because validity of a proposition is considered with respect to only possible worlds, and because agents consider impossible worlds, knowledge of valid formulas fails. For example, an agent may consider an impossible world in which p or ~p is false alongside a possible world in which p or ~p is true. Since one of the conjuncts in the proposition K[a]((p or ~p) and (p or ~p)) is false on account of the worlds epistemically accessible to the agent, the proposition is false. Closure under logical implication also fails in impossible world structures.

[edit] Other Alternatives to SKSs

A. Awareness Structures

An awareness structure is a tuple M = (S, [pi], K[1], . . . . , K[n], A[1], . . . , A[n]), where the tuple (W, [pi], K[1], . . . ., K[n]) is a Kripke structure and A[1] is a function associating a set of formulas with each world, for i = 1, . . . , n. By preserving the standard definition of the K operator, referred to in the structure as the "explicit knowledge" operator, awareness structures model agents who are in some sense logically omniscient. But by including an "implicit knowledge" (X) operator and an "awareness" (A) operator, they more accurately reflect the phenomenology of some epistemological states of affairs. Implicit knowledge is knowledge of a proposition in all worlds that an agent considers possible. Explicit knowledge is awareness of implicit knowledge. While all logical consequences of an agent's explicit knowledge are included in the set of his implicit knowledge, definitionally, an agent does not know the logical consequences of his implicit knowledge. The explicit-knowledge operator K[a] may behave differently. Agents do not explicitly know all valid formulas.

By placing restrictions on the awareness operator we can capture some interesting properties of knowledge. For instance, if we stipulate that the following axiom holds in our model: A[a]p, then A[a]A[a]p, then the agents in our model who are aware of the set of formulas in A[a] are also aware that they are aware of these formulas. To require that agents who are aware of formulas of which they do and do not know, we stipulate that A[a]x then K[a]A[a]x and if ~A[a]x then K[a]~Ax.

By definition, the implicit-knowledge operator K[a] behaves just as it does in a Kripke structure, it is closed under material implication, and K[i]x is valid for every valid formula x.

The explicit-knowledge operator K[a] may behave differently. Agents do not explicitly know all valid formulas. An agent's explicit knowledge is not necessarily closed under material implication.

B. Local Reasoning Structures

SKSs capture agents who have a single "frame of mind," that is, those who consider a set of worlds to be possible depending on their location with respect to other states of affairs. It is also useful to model agents who have multiple frames of mind, however. An example of such an agent is a politician whose agenda is determined by rapidly changing current events. Local reasoning structures, which enable an agent to consider different sets of worlds possible depending on her knowledge at a given time, are appropriate for this task.

The knowledge an agent has in a frame of mind is referred to as local knowledge. One interesting property of local reasoning structures follows from the failure of closure under conjunction in them: because the formulas an agent knows are relativized to his position with respect to sets of possible worlds, it is possible for a to know both p and ~p, to have inconsistent knowledge, while still forbidding the model from allowing the agent to know a contradiction. An agent does have knowledge of all valid formulas, however, because no matter where he is situated in the model with respect to other possible worlds, he will see the value of the valid formula as “true”.

[edit] Reference

Fagin, Ronald et al. Reasoning about Knowledge. Cambridge: MIT Press, 2003.

[edit] See Also

Anderson, A. and N. D. Belnap. Entailment: The Logic of Relevance and Necessity. Princeton: Princeton University Press, 1975.

Fagin et al. "A nonstandard approach to the logical omniscience problem." Artificial Intelligence, Volume 74, Number 2, 1995, p. 203-40.

Hintikka, J. Knowledge and Belief. Ithaca: Cornell University Press, 1962.

Montague, R. "Universal Grammar". Theoretica, Volume 36, 1970, p. 373-398.