Van Harmelen F., Lifschitz V., Porter B. Handbook of Knowledge Representation

Подождите немного. Документ загружается.

312 7. Answer Sets

[21] F. Buccafurri, N. Leone, and P. Rullo. Adding weak constraints to disjunctive dat-

alog. In Proceedings of the 1997 Joint Conference on Declarative Programming

APPIA-GULP-PRODE’97, 1997.

[22] W. Chen, T. Swift, and D.S. Warren. Efﬁcient top–down computation of queries

under the well-founded semantics. Journal of Logic Programming, 24(3):161–

201, 1995.

[23] K. Clark. Negation as failure. In Logic and Data Bases, pages 293–322. Plenum

Press, 1978.

[24] A. Colmerauer, H. Kanoui, R. Pasero, and P. Roussel. Un système de commu-

nication homme–machine en français. Technical report, Groupe de Intelligence

Artiﬁcielle Université de Aix-Marseille, 1973.

[25] J.P. Delgrande, T. Schaub, H. Tompits, and K. Wang. A classiﬁcation and survey

of preference handling approaches in nonmonotonic reasoning. Computational

Intelligence, 20(2):308–334, 2004.

[26] Y. Dimopoulos, J. Koehler, and B. Nebel. Encoding planning problems in non-

monotonic logic programs. In Proceedings of the 4th European Conference on

Planning, Lecture Notes in Artiﬁcial Intelligence (LNCS), vol. 1348, pages 169–

181. Springer, 1997.

[27] T. Eiter, G. Gottlob, and H. Mannila. Disjunctive Datalog. ACM Transactions on

Database Systems, 22(3):364–418, 1997.

[28] T. Eiter, G. Ianni, T. Lukasiewicz, R. Schindlauer, and H. Tompits. Combining

answer set programming with description logics for the semantic web. Technical

Report INFSYS RR-1843-07-04, Institut für Informationssysteme, Technische

Universität Wien, A-1040 Vienna, Austria, January 2007. Preliminary version

appeared in Proc. KR 2004, pages 141–151.

[29] T. Eiter, N. Leone, C. Mateis, G. Pfeifer, and F. Scarcello. A deductive system

for nonmonotonic reasoning. In International Conference on Logic Programming

and Nonmonotonic Reasoning, LPNMR97, LNAI, vol. 1265, pages 363–374.

Springer-Verlag, Berlin, 1997.

[30] T. Eiter, S. Woltran, and M. Fink. Semantical characterizations and complexity of

equivalences in answer set programming. ACM Transactions on Computational

Logic, 2006.

[31] I. Elkabani, E. Pontelli, and T.C. Son. Smodels with CLP and its applications:

A simple and effective approach to aggregates in asp. In Proceedings of ICLP-

04, pages 73–89, 2004.

[32] W. Faber. Unfounded sets for disjunctive logic programs with arbitrary ag-

gregates. In In Proc. of 8th International Conference on Logic Programming

and Non Monotonic Reasoning (LPNMR 2005), LNAI, vol. 3662, pages 40–52.

Springer-Verlag, Berlin, 2005.

[33] W. Faber, N. Leone, and G. Pfeifer. Recursive aggregates in disjunctive logic

programs: Semantics and complexity. In Proceedings of the 8th European Con-

ference on Artiﬁcial Intelligence (JELIA 2004), pages 200–212, 2004.

[34] F. Fages.Consistency of Clark’s completion and existence of stable models. Jour-

nal of Methods of Logic in Computer Science, 1(1):51–60, 1994.

[35] P. Ferraris. Answer sets for propositional theories. In Proceedings of Interna-

tional Conference on Logic Programming and Nonmonotonic Reasoning (LP-

NMR), pages 119–131, 2005.

M. Gelfond 313

[36] P. Ferraris, J. Lee, and V. Lifschitz. A new perspective on stable models. In

Proceedings of International Joint Conference on Artiﬁcial Intelligence (IJCAI),

pages 372–379, 2007.

[37] P. Ferraris and V. Lifschitz. Mathematical foundations of answer set program-

ming. In We Will Show Them, Essays in Honour of Dov Gabbay, vol. 1, pages

615–654. College Publications.

[38] P. Ferraris and V. Lifschitz. Weight constraints as nested expressions. Theory and

Practice of Logic Programming, 5:45–74, 2005.

[39] M. Gebser, B. Kaufman, A. Neumann, and T. Schaub. Conﬂict-deriven answer

set enumeration. In C. Baral, G. Brewka, and J. Schlipf, editors. Proceedings

of the 9th International Conference on Logic Programming and Nonmonotonic

Reasoning (LPNMR’07), LNAI, vol. 3662, pages 136–148. Springer, 2007.

[40] A.V. Gelder, K.A. Ross, and J.S. Schlipf. The well-founded semantics for general

logic programs. Journal of ACM, 38(3):620–650, 1991.

[41] M. Gelfond. On stratiﬁed autoepistemic theories. In Proceedings of Sixth Na-

tional Conference on Artiﬁcial Intelligence, pages 207–212, 1987.

[42] M. Gelfond. Epistemic approach to formalization of commonsense reasoning.

Technical Report TR-91-2, University of Texas at El Paso, 1991.

[43] M. Gelfond and N. Leone. Knowledge representation and logic programming.

Artiﬁcial Intelligence, 138(1–2), 2002.

[44] M. Gelfond and V. Lifschitz. The stable model semantics for logic programming.

In Proceedings of ICLP-88, pages 1070–1080, 1988.

[45] M. Gelfond and V. Lifschitz. Classical negation in logic programs and disjunctive

databases. New Generation Computing, 9(3–4):365–386, 1991.

[46] M. Gelfond and V. Lifschitz. Action languages. Electronic Transactions on AI,

3(16):193–210, 1998.

[47] E. Giunchiglia, Y. Lierler, and M. Maratea. Answer set programming based on

propositional satisﬁability. Journal of Automated Reasoning, 36:345–377, 2006.

[48] P.J. Hayes and J. McCarthy. Some philosophical problems from the standpoint of

artiﬁcial intelligence. In B. Meltzer and D. Michie, editors. Machine Intelligence

4, pages 463–502. Edinburgh University Press, 1969.

[49] S. Heymans, D.V. Nieuwenborgh, and D. Vermeir. Guarded open answer set

programming. In Proc. of 8th International Conference on Logic Programming

and Non Monotonic Reasoning (LPNMR 2005), LNAI, vol. 3662, pages 92–104.

Springer-Verlag, Berlin, 2005.

[50] T. Janhunen, I. Niemela, P. Simons, and J. You. Partiality and disjunction in stable

model semantics. In Proceedings of the 2000 KR Conference, pages 411–419,

2000.

[51] T. Janhunen and E. Oikarinen. LPEQ and DLPEQ—translators for automated

equivalence testing of logic programs. In Proc. of 8th International Conference

on Logic Programming and Non Monotonic Reasoning (LPNMR 2004), LNAI,

vol. 2923, pages 336–340. Springer-Verlag, Berlin, 2004.

[52] R. Kowalski. Logic for Problem Solving. North-Holland, 1979.

[53] R.A. Kowalski and M. Sergot. A logic-based calculus of events. New Generation

Computing, 4(4):319–340, 1986.

[54] N. Leone, G. Pfeifer, W. Faber, T. Eiter, G. Gottlob, S. Perri, and F. Scarcello. The

DLV system for knowledge representation and reasoning. ACM Transactions on

Computational Logic, 7:499–562, 2006.

314 7. Answer Sets

[55] N. Leone, P. Rullo, and F. Scarcello. Disjunctive stable models: Unfounded sets,

ﬁxpoint semantics and computation. Information and Computation, 135:69–112,

1997.

[56] V. Lifschitz andA. Razborov. Whyare there so manyloop formulas?ACM Trans-

actions on Computational Logic, 7(2):261–268, 2006.

[57] V. Lifschitz, D. Pearce, and A. Valverde. Strongly equivalent logic programs.

ACM Transactions on Computational Logic, 2:526–541, 2001.

[58] F. Lin and Y. Zhao. ASSAT: Computing answer sets of a logic program by SAT

solvers. Artiﬁcial Intelligence, 157(1–2):115–137, 2004.

[59] D. Makinson. General patterns in nonmonotonic reasoning. In The Handbook on

Logic in AI and Logic Programming, vol. 3, pages 35–110. Oxford University

Press, 1993.

[60] V.W. Marek and M. Truszczynski. Stable semantics for logic programs and de-

fault reasoning. In Proc. of the North American Conf. on Logic Programming,

pages 243–257, 1989.

[61] V.W. Marek and M. Truszczynski. Nonmonotonic Logics; Context Dependent

Reasoning. Springer-Verlag, Berlin, 1993.

[62] V.W. Marek and M. Truszczynski. Stable models and an alternative logic pro-

gramming paradigm. In The Logic Programming Paradigm: a 25-Year Perspec-

tive, pages 375–398. Springer-Verlag, Berlin, 1999.

[63] N. McCain and H. Turner. A causal theory of ramiﬁcations and qualiﬁcations. In

Proceedings of IJCAI-95, pages 1978–1984, 1995.

[64] J. McCarthy. Circumscription—a form of non-monotonic reasoning. Artiﬁcial

Intelligence, 13:27–39, 1980.

[65] J. McCarthy. In V. Lifschitz, editor. Formalization of Common Sense.Ablex,

1990.

[66] J. Minker. On indeﬁnite data bases and the closed world assumption. In Proceed-

ings of CADE-82, pages 292–308, 1982.

[67] J. Minker. Logic and databases: a 20 year retrospective. In H. Levesque and F.

Pirri, editors. Logical Foundations for Cognitive Agents: Contributions in Honor

of Ray Reiter, pages 234–299. Springer, 1999.

[68] R.C. Moore. Semantical considerations on nonmonotonic logic. In Proceedings

of the 8th International Joint Conference on Artiﬁcial Intelligence, pages 272–

279. Morgan Kaufmann, August 1983.

[69] E.T. Mueller. Commonsense Reasoning. Morgan Kaufmann, 2006.

[70] I. Niemela. Logic programs with stable model semantics as a constraint program-

ming paradigm. Annals of Mathematics and Artiﬁcial Intelligence, 25(3–4):241–

247, 1999.

[71] I. Niemela and P. Simons. Smodels—an implementation of the stable model

and well-founded semantics for normal logic programs. In Proceedings of the

4th International Conference on Logic Programming and Non-Monotonic Rea-

soning (LPNMR’97), Lecture Notes in Artiﬁcial Intelligence (LNCS), vol. 1265,

pages 420–429. Springer, 1997.

[72] I. Niemela, P. Simons, and T. Soininen. Extending and implementing the stable

model semantics. Artiﬁcial Intelligence, 138(1–2):181–234, June 2002.

[73] I. Niemela and P. Simons. Smodels—an implementation of the stable model

and well-founded semantics for normal logic programs. In Proceedings of the

M. Gelfond 315

4th International Conference on Logic Programming and Non-Monotonic Rea-

soning (LPNMR’97), Lecture Notes in Artiﬁcial Intelligence (LNCS), vol. 1265,

pages 420–429. Springer, 1997.

[74] M. Nogueira, M. Balduccini, M. Gelfond, R. Watson, and M. Barry. An A-Prolog

decision support system for the Space Shuttle. In PADL 2001, pages 169–183,

2001.

[75] D. Pearce. A new logical characterization of stable models and answer sets. In

Non-Monotonic Extension of Logic Programming, Lecture Notes in Artiﬁcial In-

telligence (LNCS), vol. 1216, pages 57–70. Springer-Verlag, 1997.

[76] N. Pelov, M. Denecker, and M. Bruynooghe. Well-founded and stable semantics

of logic programs with aggregates. Theory and Practice of Logic Programming,

7:355–375, 2007.

[77] T. Przymusinski. On the declarative semantics of deductive databases and logic

programs. In J. Minker, editor. Foundations of Deductive Databases and Logic

Programming, pages 193–216. Morgan Kaufmann, 1988.

[78] R. Reiter. On closed world data bases. In Logic and Data Bases, pages 119–140.

Plenum Press, 1978.

[79] R. Reiter. A logic for default reasoning. Artiﬁcial Intelligence, 13(1–2):81–132,

1980.

[80] R. Reiter. Knowledge in Action—Logical Foundations for Specifying and Imple-

menting Dynamical Systems. MIT Press, September 2001.

[81] C. Sakama. Induction from answer sets in nonmonotonic logic programs. ACM

Transactions on Computational Logic, 6(2):203–231, April 2005.

[82] C. Sakama and K. Inoue. Prioritized logic programming and its application to

commonsense reasoning. Artiﬁcial Intelligence, 123:185–222, 2000.

[83] T. Sato. Completed logic programs and their consistency. Journal of Logic Pro-

gramming, 9:33–44, 1990.

[84] J. Schlipf. Some remarks on computability and open domain semantics. In Pro-

ceedings of the Workshop on Structural Complexity and Recursion-Theoretic

Methods in Logic Programming of the International Logic Programming Sym-

posium, 1993.

[85] J. Schlipf. The expressive powers of logic programming semantics. Journal of

Computer and System Sciences, 51(1):64–86, 1995.

[86] M. Shanahan. Solving the Frame Problem: A Mathematical Investigation of the

Commonsense Law of Inertia. MIT Press, 1997.

[87] T. Soininen and I. Niemela. Developing a declarative rule language for appli-

cations in product conﬁguration. In Proceedings of International Symposium on

Practical Aspects of Declarative Languages, pages 305–319, 1998.

[88] T.C. Son and E. Pontelli. A constructive semantic characterization of aggregates

in answer set programming. Theory and Practice of Logic Programming, 7:355–

375, 2007.

[89] T.C. Son, P.H. Tu, M. Gelfond, and A.R. Morales. An approximation of action

theories of and its application to conformant planning. In Proc. of 8th Interna-

tional Conference on Logic Programming and Non Monotonic Reasoning (LP-

NMR 2005), LNAI, vol. 3662, pages 172–184. Springer-Verlag, Berlin, 2005.

[90] V.S. Subrahmanian and C. Zaniolo. Relating stable models and AI planning do-

mains. In Proceedings of ICLP-95, pages 233–247, 1995.

316 7. Answer Sets

[91] H. Turner. Representing actions in logic programs and default theories: A situa-

tion calculus approach. Journal of Logic Programming, 31(1–3):245–298, June

1997.

[92] H. Turner. Order-consistent programs are cautiously monotonic. Journal of The-

ory and Practice of Logic Programming (TPLP), 1(4):487–495, 2001.

[93] J. Vaghani, K. Ramamohanarao, D.B. Kemp, Z. Somogyi, P.J. Stuckey, T.S.

Leask, and J. Harland. The Aditi deductive database system. The VLDB Journal,

3(2):245–288, 1994.

Handbook of Knowledge Representation

Edited by F. van Harmelen, V. Lifschitz and B. Porter

DOI: 10.1016/S1574-6526(07)03008-8

317

Chapter 8

Belief Revision

Pavlos Peppas

8.1 Introduction

Philippa, a Greek nineteen year old student at Patras University, has just discovered

that Nikos and Angela are not her true parents; she was adopted when she was six

months old from an orphanage in Sao Paulo. The news really shook Philippa. Much

of what she used to believe all her life about herself and her family was wrong. After

recovering from the initial shock she started putting her thoughts back in order: so

that means that Alexandros is not really her cousin, and she did not take her brown

eyes from (who she used to believe was) her grandmother, and she no longer needs to

worry about developing high blood pressure because of the bad family history from

both Nikos’ and Angela’s side. Moreover, she probably has siblings somewhere in

Brazil, and if she really looked into it, she might be entitled to a Brazilian citizenship

which could come in handy for that long trip she always wanted to make to Latin

America.

This is a typical (although rather dramatic) instance of a belief revision scenario:

a rational agent receives new information that makes her change her beliefs. In the

principal case where the new information contradicts her initial belief state, the agent

needs to withdraw some of the old beliefs before she can accommodate the new

information; she also needs to accept the consequences that might result from the

interaction of the new information with the (remaining) old beliefs.

The study of the process of belief revision, which gave rise to an exciting research

area with the same name,

can be traced back to the early 1980s. The article that is

widely considered to mark the birth of the ﬁeld is the seminal work of Alchourron,

Gardenfors, and Makinson reported in [1]. As a matter of fact, the framework that

evolved from [1]—now known as the AGM paradigm (or simply AGM) after the ini-

tials of its three founders—is to this date the dominant framework in Belief Revision.

Of course much has happened since 1985. The formal apparatus developed in [1]

has been enhanced and thoroughly studied, newresearch directions haveemergedfrom

We shall use the capitalized term “Belief Revision” to refer to the research area; the same term in

lower case letters will be used for the process of belief change.

318 8. Belief Revision

it, connections with neighboring ﬁelds have been established, and a lot more is cur-

rently under way. This article will journey through the main developments in Belief

Revision, pretty much in a historical order, starting with the classical AGM paradigm

and following the trail till the present day.

8.2 Preliminaries

Let us ﬁrst ﬁx some notation and terminology. Alchourron, Gardenfors, and Makinson

build their framework working with a formal language L governed by a logic which

is identiﬁed by its consequence relation . Very little is assumed about L and , mak-

ing the AGM paradigm quite general. In particular, L is taken to be closed under all

Boolean connectives, and  has to satisfy the following properties:

(i)  ϕ for all truth-functional tautologies A (superclassicality).

(ii) If  (ϕ → ψ) and  ϕ, then  ψ (modus ponens).

(iii)  is consistent, i.e.  L.

(iv)  satisﬁes the deduction theorem, that is, {ϕ

,ϕ

,...,ϕ

}ψ iff  ϕ

∧

∧···∧ϕ

→ ψ.

(v)  is compact.

For a set of sentences Γ of L, we denote by Cn(Γ ) the set of all logical conse-

quences of Γ ,i.e.Cn(Γ ) ={ϕ ∈ L: Γ  ϕ}. A theory K of L is any set of sentences

of L closed under ,i.e.K = Cn(K). We shall denote the set of all theories of L

by K

. A theory K of L is complete iff for all sentences ϕ ∈ L, ϕ ∈ K or ¬ϕ ∈ K.

We shall denote the set of all consistent complete theories of L by M

. For a set of

sentences Γ of L, [Γ ] denotes the set of all consistent complete theories of L that con-

tain Γ . Often we shall use the notation [ϕ] for a sentence ϕ ∈ L, as an abbreviation

of [{ϕ}]. For a theory K and a set of sentences Γ of L, we shall denote by K + Γ the

closure under  of K ∪ Γ ,i.e.K + Γ = Cn(K ∪ Γ). For a sentence ϕ ∈ L we shall

often write K + ϕ as an abbreviation of K +{ϕ}. Finally, the symbols  and ⊥ will be

used to denote an arbitrary (but ﬁxed) tautology and contradiction of L, respectively.

8.3 The AGM Paradigm

In AGM, beliefs are represented as sentences of L and belief sets as theories of L.

The process of belief revision is modeled as a function ∗ mapping a theory K and a

sentence ϕ to a new theory K ∗ ϕ. Of course certain constraints need to be imposed

on ∗ in order for it to capture the notion of rational belief revision correctly. A guiding

intuition in formulating these constraints has been the principle of minimal change

according to which a rational agent ought to change her beliefs as little as possible in

order to (consistently) accommodate the new information. Of course, at ﬁrst glance it

It should be noted that representing a belief set as a theory, presupposes that agents are logically

omniscient. In this sense the AGM paradigm is tailored for ideal reasoners.

P. Peppas 319

is not clear how one should measure change between belief sets, or even if the notion

of minimal change is at all expressible within a purely logical framework.

8.3.1 The AGM Postulates for Belief Revision

Despite the apparent difﬁculties, Gardenfors [29] succeeded in formulating a set of

eight postulates, known as the AGM postulates for belief revision,

which are now

widely regarded to have captured much of what is the essence of rational belief revi-

sion:

(K ∗ 1) K ∗ ϕ is a theory of L.

(K ∗ 2) ϕ ∈ K ∗ ϕ.

(K ∗ 3) K ∗ ϕ ⊆ K + ϕ.

(K ∗ 4) If ¬ϕ/∈ K then K + ϕ ⊆ K ∗ ϕ.

(K ∗ 5) If ϕ is consistent then K ∗ ϕ is also consistent.

(K ∗ 6) If  ϕ ↔ ψ then K ∗ ϕ = K ∗ ψ .

(K ∗ 7) K ∗ (ϕ ∧ ψ) ⊆ (K ∗ ϕ) + ψ.

(K ∗ 8) If ¬ψ/∈

K ∗ ϕ then (K ∗ ϕ) + ψ ⊆ K ∗ (ϕ ∧ ψ).

y function ∗:K

× L → K

satisfying the AGM postulates for revision

(K ∗ 1)–(K ∗ 8) is called an AGM revision function. The ﬁrst six postulates (K ∗ 1)–

(K ∗ 6) are known as the basic AGM postulates (for revision), while (K ∗ 7)–(K ∗ 8)

are called the supplementary AGM postulates.

Postulate (K ∗ 1) says that the agent, being an ideal reasoner, remains logically

omniscient after she revises her beliefs. Postulate (K ∗ 2) says that the new informa-

tion ϕ should always be included in the new belief set. (K ∗ 2) places enormous faith

on the reliability of ϕ. The new information is perceived to be so reliable that it pre-

vailsover all previous conﬂicting beliefs, no matter what these beliefs might be.

Later

in this chapter (Section 8.7) we shall consider ways of relaxing (K ∗ 2). Postulates

(K ∗ 3) and (K ∗ 4) viewed together state that whenever the new information ϕ does

not contradict the initial belief set K, there is no reason to remove any of the original

beliefs at all; the new belief state K ∗ ϕ will contain the whole of K, the new informa-

tion ϕ, and whatever follows from the logical closure of K and ϕ (and nothing more).

Essentially (K ∗ 3) and (K ∗ 4) express the notion of minimal change in the limiting

case where the new information is consistent with the initial beliefs. (K ∗ 5) says that

the agent should aim for consistency at any cost; the only case where it is “acceptable”

for the agent to fail is when the new information in itself is inconsistent (in which

case, because of (K ∗ 2), the agent cannot do anything about it). (K ∗ 6) is known as

Although these postulate where ﬁrst proposed by Gardenfors alone, they were extensively studied in

collaboration with Alchourron and Makinson in [2]; thus their name.

The high priority of ϕ over previous beliefs may not always be related to its reliability. For example,

in the context of the Ramsey Test for conditionals, ϕ is incorporated into a theory K as part of the process

of evaluating the acceptability of a counterfactual conditional ϕ>ψ(see [30]).

320 8. Belief Revision

the irrelevance of syntax postulate. It says that the syntax of the new information has

no effect on the revision process; all that matters is its content (i.e. the proposition it

represents). Hence, logically equivalent sentences ϕ and ψ change a theory K in the

same way.

Finally, postulates (K ∗ 7) and (K ∗ 8) are best understood taken together. They

say that for any two sentences ϕ and ψ, if in revising the initial belief set K by ϕ one

is lucky enough to reach a belief set K ∗ ϕ that is consistent with ψ, then to produce

K ∗ (ϕ ∧ ψ) all that one needs to do is to expand K ∗ ϕ with ψ; in symbols K ∗ (ϕ ∧

ψ) = (K ∗ ϕ) + ψ. The motivation for (K ∗ 7) and (K ∗ 8) comes again from the

principle of minimal change. The rationale is (loosely speaking) as follows: K ∗ ϕ is a

minimal change of K to include ϕ and therefore there is no way to arrive at K ∗ (ϕ∧ψ)

from K with “less change”. In fact, because K ∗ (ϕ ∧ ψ) also includes ψ one might

have to make further changes apart from those needed to include ϕ. If however ψ is

consistent with K ∗

ϕ,

these further changes can be limited to simply adding ψ to

K ∗ ϕ and closing under logical implications—no further withdrawals are necessary.

The postulates (K ∗ 1)–(K ∗ 8) are certainly very reasonable. They are simple,

elegant, jointly consistent, and they follow quite naturally from the notion of minimal

change. Moreover, according to Alchourron, Gardenfors, and Makinson, these pos-

tulates are not only sound but, given the limited expressiveness of a purely logical

framework, there are also (in some sense) complete. Now this is a strong statement,

especially since one can show that (K ∗ 1)–(K ∗ 8) do not sufﬁce to uniquely de-

termine the belief set K ∗ ϕ resulting from revising K by ϕ,givenK and ϕ alone.

In other words, there is more than one function ∗ that satisﬁes (K ∗ 1)–(K ∗ 8). Yet

the plurality of AGM revision functions should not be seen as a weakness of the pos-

tulates but rather as expressing the fact that different people may change their mind

in different ways. Hence the AGM postulates simply circumscribe the territory of all

different rational ways of revising belief sets.

Nevertheless, one may still be skeptical about whether the territory staked out by

(K ∗ 1)–(K ∗ 8) contains nothing more but just rational belief revision functions.

Further evidence is needed to support such a strong claim. Such evidence was indeed

provided mainly in the form of formal results known as representation results con-

necting the AGM postulates with other models of belief revision. Some of the most

important representation results will be discussed later in this chapter.

8.3.2 The AGM Postulates for Belief Contraction

Apart from belief revision, Alchourron, Gardenfors, and Makinson studied another

type of belief change called belief contraction (or simply contraction), which can be

described as the process of rationally removing from a belief set K a certain belief ϕ.

Contraction typically occurs when an agent loses faith in ϕ and decides to give it up.

Simply taking out ϕ from K however will not sufﬁce since other sentences that are

present in K may reproduce ϕ through logical closure. Consider, for example, the

theory K = Cn({p → q, p,q}) and assume that we want to contract K by q. Then,

Another interesting instance of contraction is during argumentation. Consider two agents A and B that

argue about a certain issue for which they have opposite views. It is quite likely that for the sake of argument

the two agents will (temporarily) contract their beliefs to reach some common ground from which they will

then starting building their case.

P. Peppas 321

not only do we have to remove q from K, but we also need to give up (at least) one

of p → q or p, for otherwise q will resurface via logical closure.

Like belief revision, belief contraction is formally deﬁned as a function

− mapping

a theory K and a sentence ϕ to a new theory K

−ϕ. Once again a set of eight postulates

was proposed, motivated by the principle of minimal change,

to constraint

− in a way

that captures the essence of rational belief contraction. These postulates, known as

the AGM postulates for belief contraction, are the following:

− 1) K

− ϕ is a theory.

− 2) K

− ϕ ⊆ K.

− 3) If ϕ/∈ K then K

− ϕ = K.

− 4) If  ϕ then ϕ/∈ K

− ϕ.

− 5) If ϕ ∈ K, then K ⊆ (K

− ϕ) + ϕ.

− 6) If  ϕ ↔ ψ then K

− ϕ = K

− ψ.

− 7) (K

− ϕ) ∩ (K

− ψ) ⊆ K

− (ϕ ∧ ψ).

− 8)

If ϕ/∈ K

− (ϕ ∧ ψ) then K

− (ϕ ∧ ψ) ⊆ K

− ϕ.

Any function

−:K

× L → K

that satisﬁes (K

− 1)–(K

− 8) is called an AGM

contraction function. Like the postulates for revision, (K

− 1)–(K

− 8) split into two

groups: the ﬁrst six postulates (K

−1)–(K

−6) are known as the basic AGM postulates

for contraction, while (K

− 7)–(K

− 8) are called the supplementary AGM postulates

for contraction.

Given the agent’s logical omniscience, postulate (K

− 1) is self-evident. Also self-

evident is (K

− 2) since by its very nature, contraction produces a belief set smaller

than the original. Postulate (K

−3) says that if ϕ is not in the initial belief set K to start

with, then there is no reason to change anything at all. (K

− 4) tells us that the only

sentences that are “immutable” are tautologies; all other sentences ϕ can in principle

be removed from the initial beliefs K, and contraction will perform this removal no

matter what the cost in epistemic value might be.

Postulate (K

− 5), known as the

recovery postulate says that contracting and then expanding by ϕ will give us back (at

least) the initial theory K; in fact, because of (K

− 2), we get back precisely K.The

motivation behind (K

− 5) is again the notion of minimal change: when contracting

K by ϕ we should cut off only the part of K that is “related” to ϕ and nothing else .

Hence adding ϕ back should restore our initial belief set.

Postulate (K

− 6), like its belief revision counterpart (K ∗ 6), tells us that contrac-

tion is not syntax-sensitive: contraction by logically equivalent sentences produces the

same result. The last two postulates relate the individual contractions by two sentences

ϕ and ψ, to the contraction by their conjunction ϕ ∧ ψ. Firstly notice that to contract

In this context the principle of minimal change runs as follows: during contraction as little as possible

should be given up from the initial belief set K in order to remove ϕ.

The remarks for postulate (K ∗ 2) are also relevant here.

It should be noted though that, despite its intuitive appeal, the recovery postulate is among the most

controversial AGM postulates—see [60] for a detailed discussion.