Possibilistic Reasoning - A Mini-survey and Uniform Semantics
---
paper_title: A modal analysis of possibility theory

paper_content:

In this paper we study possibility theory from the point of view of modal logic. Our first and main result is that the logic of qualitative possibility is nothing else than Lewis's conditional logic VN. Second, we propose a multi-modal logic able to support possibility theory. Some connexions between these formalisms are stressed.
---
paper_title: A guide to completeness and complexity for modal logics of knowledge and belief

paper_content:

Abstract We review and re-examine possible-worlds semantics for propositional logics of knowledge and belief with three particular points of emphasis: (1) we show how general techniques for finding decision procedures and complete axiomatizations apply to models for knowledge and belief, (2) we show how sensitive the difficulty of the decision procedure is to such issues as the choice of modal operators and the axiom system, and (3) we discuss how notions of common knowledge and distributed knowledge among a group of agents fit into the possible-worlds framework, As far as complexity is concerned, we show, among other results, that while the problem of deciding satisfiability of an S5 formula with one agent is NP-complete, the problem for many agents is PSPACE-complete. Adding a distributed knowledge operator does not change the complexity, but once a common knowledge operator is added to the language, the problem becomes complete for exponential time.
---
paper_title: Knowledge in Flux: Modeling the Dynamics of Epistemic States

paper_content:

Knowledge in Flux presents a theory of rational changes of belief, focusing particularly on revisions that occur when the agent receives new information that is inconsistent with the present epistemic state.
---
paper_title: Nonmonotonic Reasoning, Preferential Models and Cumulative Logics

paper_content:

Many systems that exhibit nonmonotonic behavior have been described and studied already in the literature. The general notion of nonmonotonic reasoning, though, has almost always been described only negatively, by the property it does not enjoy, i.e. monotonicity. We study here general patterns of nonmonotonic reasoning and try to isolate properties that could help us map the field of nonmonotonic reasoning by reference to positive properties. We concentrate on a number of families of nonmonotonic consequence relations, defined in the style of Gentzen. Both proof-theoretic and semantic points of view are developed in parallel. The former point of view was pioneered by D. Gabbay, while the latter has been advocated by Y. Shoham in. Five such families are defined and characterized by representation theorems, relating the two points of view. One of the families of interest, that of preferential relations, turns out to have been studied by E. Adams. The"preferential"models proposed here are a much stronger tool than Adams' probabilistic semantics. The basic language used in this paper is that of propositional logic. The extension of our results to first order predicate calculi and the study of the computational complexity of the decision problems described in this paper will be treated in another paper.
---
paper_title: Fuzzy sets in approximate reasoning, part 2: logical approaches

paper_content:

Abstract This second part of an overview of fuzzy set-based methods for approximate reasoning is devoted to deductive approaches dealing with knowledge bases made of a collection of symbolic expressions (e.g. logical formulas) to which numerical weigths are attached. Then such a knowledge base can be viewed as a fuzzy set of formulae (especially if the weights belong to the interval [0, 1]). An important distinction is made, in the interpretation of the weights, between degrees of truth and degrees of uncertainty; the former can be assumed to behave in a fully compositional way while the latter cannot. Rule-based inference systems where fuzzy set operations are used for propagating and combining ‘certainty factors’, are briefly discussed. Then an extensive survey of truth-functional fuzzy logic is provided, and it is followed by a brief presentation of possibilistic logic, a possibility theory-based logic of uncertainty (which is not compositional with respect to every connective). In both cases, the automated deduction and logic programming aspects are emphasized while purely logical considerations which are not directly relevant for approximate reasoning, are not developed.
---
paper_title: A logic for revision and subjunctive queries

paper_content:

We present a logic for belief revision in which revision of a theory by a sentence is represented using a conditional connective. The conditional is not primitive, but rather defined using two unary modal operators. Our approach captures and extends the classic AGM model without relying on the Limit Assumption. Reasoning about counterfactual or hypothetical situations is also crucial for AI. Existing logics for such subjunctive queries are lacking in several respects, however, primarily in failing to make explicit the epistemic nature of such queries. We present a logical model for subjunctives based on our logic of revision that appeals explicitly to the Ramsey test. We discuss a framework for answering subjunctive queries, and show how integrity constraints on the revision process can be expressed.
---
paper_title: Inaccessible worlds and irrelevance: Preliminary report

paper_content:

Recently, the relationship between several forms of default reasoning based on conditional defaults has been investigated, In particular, the systems based on e-semantics, preferential models and (fragments of) modally-defined conditional logics have been shown to be equivalent. These systems form a plausible core for default inference, but are too weak in general, failing to deal adequately with irrelevance. We propose an extension of the (modal) conditional logics in which one can express the truth of sentences at inaccessible possible worlds and show how this logic can be used to axiomatize a simple preference relation on the modal structures of this logic. This preferential semantics is shown to be equivalent to 1-entailment and rational closure. We suggest that many metalogical systems of default inference can be axiomatized within this logic, using the notion of inaccessible worlds.
---
paper_title: A logic for revision and subjunctive queries

paper_content:

We present a logic for belief revision in which revision of a theory by a sentence is represented using a conditional connective. The conditional is not primitive, but rather defined using two unary modal operators. Our approach captures and extends the classic AGM model without relying on the Limit Assumption. Reasoning about counterfactual or hypothetical situations is also crucial for AI. Existing logics for such subjunctive queries are lacking in several respects, however, primarily in failing to make explicit the epistemic nature of such queries. We present a logical model for subjunctives based on our logic of revision that appeals explicitly to the Ramsey test. We discuss a framework for answering subjunctive queries, and show how integrity constraints on the revision process can be expressed.
---
paper_title: A logic for revision and subjunctive queries

paper_content:

We present a logic for belief revision in which revision of a theory by a sentence is represented using a conditional connective. The conditional is not primitive, but rather defined using two unary modal operators. Our approach captures and extends the classic AGM model without relying on the Limit Assumption. Reasoning about counterfactual or hypothetical situations is also crucial for AI. Existing logics for such subjunctive queries are lacking in several respects, however, primarily in failing to make explicit the epistemic nature of such queries. We present a logical model for subjunctives based on our logic of revision that appeals explicitly to the Ramsey test. We discuss a framework for answering subjunctive queries, and show how integrity constraints on the revision process can be expressed.
---
paper_title: What does a conditional knowledge base entail?

paper_content:

This paper presents a logical approach to nonmonotonic reasoning based on the notion of a nonmonotonic consequence relation. A conditional knowledge base, consisting of a set of conditional assertions of the type"if ... then ...", represents the explicit defeasible knowledge an agent has about the way the world generally behaves. We look for a plausible definition of the set of all conditional assertions entailed by a conditional knowledge base. In a previous paper, S. Kraus and the authors defined and studied"preferential"consequence relations. They noticed that not all preferential relations could be considered as reasonable inference procedures. This paper studies a more restricted class of consequence relations,"rational"relations. It is argued that any reasonable nonmonotonic inference procedure should define a rational relation. It is shown that the rational relations are exactly those that may be represented by a"ranked"preferential model, or by a (non-standard) probabilistic model. The rational closure of a conditional knowledge base is defined and shown to provide an attractive answer to the question of the title. Global properties of this closure operation are proved: it is a cumulative operation. It is also computationally tractable. This paper assumes the underlying language is propositional.
---
paper_title: The Probability of a Possibility: Adding Uncertainty to Default Rules

paper_content:

We present a semantics for adding uncertainty to conditional logics for default reasoning and belief revision. We are able to treat conditional sentences as statements of conditional probability, and express rules for revision such as "If A were believed, then B would be believed to degree p." This method of revision extends conditionalization by allowing meaningful revision by sentences whose probability is zero. This is achieved through the use of counterfactual probabilities. Thus, our system accounts for the best properties of qualitative methods of update (in particular, the AGM theory of revision) and probabilistic methods. We also show how our system can be viewed as a unification of probability theory and possibility theory, highlighting their orthogonality and providing a means for expressing the probability of a possibility. We also demonstrate the connection to Lewis's method of imaging.
---
paper_title: Modal Logics for Qualitative Possibility and Beliefs

paper_content:

Possibilistic logic has been proposed as a numerical formalism for reasoning with uncertainty. There has been interest in developing qualitative accounts of possibility, as well as an explanation of the relationship between possibility and modal logics. We present two modal logics that can be used to represent and reason with qualitative statements of possibility and necessity. Within this modal framework, we are able to identify interesting relationships between possibilistic logic, beliefs and conditionals. In particular, the most natural conditional definable via possibilistic means for default reasoning is identical to Pearl's conditional for e-semantics.
---
paper_title: A logic for revision and subjunctive queries

paper_content:

We present a logic for belief revision in which revision of a theory by a sentence is represented using a conditional connective. The conditional is not primitive, but rather defined using two unary modal operators. Our approach captures and extends the classic AGM model without relying on the Limit Assumption. Reasoning about counterfactual or hypothetical situations is also crucial for AI. Existing logics for such subjunctive queries are lacking in several respects, however, primarily in failing to make explicit the epistemic nature of such queries. We present a logical model for subjunctives based on our logic of revision that appeals explicitly to the Ramsey test. We discuss a framework for answering subjunctive queries, and show how integrity constraints on the revision process can be expressed.
---
paper_title: The Probability of a Possibility: Adding Uncertainty to Default Rules

paper_content:

We present a semantics for adding uncertainty to conditional logics for default reasoning and belief revision. We are able to treat conditional sentences as statements of conditional probability, and express rules for revision such as "If A were believed, then B would be believed to degree p." This method of revision extends conditionalization by allowing meaningful revision by sentences whose probability is zero. This is achieved through the use of counterfactual probabilities. Thus, our system accounts for the best properties of qualitative methods of update (in particular, the AGM theory of revision) and probabilistic methods. We also show how our system can be viewed as a unification of probability theory and possibility theory, highlighting their orthogonality and providing a means for expressing the probability of a possibility. We also demonstrate the connection to Lewis's method of imaging.
---

Title: Possibilistic Reasoning - A Mini-survey and Uniform Semantics

Section 1: Introduction
Description 1: Introduce the two main logical formalisms for reasoning about possibility and necessity, and describe the aim of integrating these approaches into a uniform formalism.

Section 2: A Mini-survey
Description 2: Review various logics for reasoning about possibility and necessity including modal logic, conditional logic, possibilistic logic, quantitative modal logic, and qualitative possibility logic.

Section 3: Modal Logic
Description 3: Discuss the modern development and syntax, semantics, possible world models, and applications of modal logic.

Section 4: Conditional Logic
Description 4: Explain the syntax and semantics of conditional logic and its applications in nonmonotonic reasoning and belief revision.

Section 5: Possibilistic Logic
Description 5: Describe the syntax and semantics of possibilistic logic, comparing it with first-order logic and discussing its applications.

Section 6: Quantitative Modal Logic
Description 6: Introduce quantitative modal logic, its syntactic and semantic extensions, and its use in representing nested necessity and possibility measures.

Section 7: Qualitative Possibility Logic
Description 7: Explain the syntax and semantics of qualitative possibility logic, focusing on the comparison of possibility measures between different formulas.

Section 8: The Logic LCP
Description 8: Introduce the proposed Logic for Conditional Possibility (LCP), its syntax, and semantics, and why it serves the purpose of unifying other logics.

Section 9: LCP as a Uniform Framework
Description 9: Demonstrate the expressiveness of LCP by presenting translation lemmas and relations to other logics like QML, QPL, conditional logic, and PL.

Section 10: Applications and Generalization
Description 10: Explore how LCP can be applied to formulate nonmonotonic inference relations, handle partial consistency, and generalize for different reasoning types.

Section 11: Handling Partial Consistency
Description 11: Discuss how recent developments in handling partial inconsistency in possibilistic logic can be integrated into the LCP framework.

Section 12: Related Work and Further Research
Description 12: Review related works and discuss potential future research directions to expand and refine the proposed framework.

Section 13: Conclusion
Description 13: Summarize the contributions of the paper, emphasizing the shift from absolute semantics to the more expressive LCP framework, and suggest areas for future work, including the development of a proof theory for LCP.