A Modal Logic for Reasoning about Possibilistic Belief Fusion

1 Introduction

In this paper, we propose a modal logic for reasoning about possibilistic belief fusion. This is a combination of multiagent epistemic logic and possibilistic logic. We use graded epistemic operators to represent agents' uncertain beliefs, and the operators are interpreted in accordance with possibilistic semantics. We employ ordered fusion based on a level skipping strategy to resolve the inconsistency caused by direct fusion; that is, the level at which the inconsistency occurs is skipped. Here, we present the formal semantics and an axiomatic system for the logic.

2 Syntax

To encode the degrees of reliability of n agents, we use ordering relations over any subset of {1, . . . , n}. Let T On denote the set of all possible strict total orders over any nonempty subset of {1, . . . , n}. Then, we can associate a unique syntactic notation with each strict total order in T On. Let X = {i1, i2, . . . , im} be a non-empty subset of {1, . . . , n} and > be a strict total order such that ij > ik iff j < k for all 1 ≤, j, k ≤ m. Then, the syntactic notation for (X,>) is the string i1 > i2 > · · · > im.

In this paper, the capital letter O is used to denote metavariables ranging over such notations. Let O be the string i1 > i2 > · · · > im, then the set {i1, i2, . . . , im} is called the domain of O, denoted by δ(O). In this case, O > im+1 denotes i1 > i2 > · · · > im > im+1 if im+1 ̸∈ δ(O). As the syntactic notation is unique for each total order, we can also identify the notation with the total order itself, and write O ∈ T On. Furthermore, the upper-case Greek letter Ω is used to denote meta-variables ranging over nonempty subsets of T On.

We now present the syntax of our logic for reasoning about possibilistic belief fusion based on a level skipping strategy. The logic is called SFPL⊗,ϵ n , where ϵ ∈ [0, 1] is the inconsistency tolerance degree of the logic and ⊗ is a continuous T-norm 1 . Let Φ0 be a set of propositional symbols. Then the set of well-formed formulas (wff) of SFPL⊗,ϵ n is defined as the smallest set containing Φ0 ∪ {⊥, ⊤}, and is closed under Boolean operators and the following rule:

1 A T-norm is any binary operation on [0,1] that is commutative, associative, non-decreasing in each argument, and has 1 as unit.

• if ϕ is a wff, then [Ω]aϕ and [Ω]+a ϕ are wffs for any nonempty Ω ⊆ T On, and any rational number a ∈ [0, 1].

If Ω = {O} is a singleton, we write [O]aϕ (resp. [O]+a ϕ), instead of [{O}]aϕ (resp. [{O}]+a ϕ). Intuitively, [O]aϕ (resp. [O]+a ϕ) means that an agent merging distributed beliefs in accordance with the ordering of O will believe ϕ with a strength at least equal to (resp. more than) a. We can view each O as a virtual agent, and [Ω] corresponds to a distributed belief operator [Fagin et al., 1996] of virtual agents in Ω. Note that our purpose is to ensure the consistency of ordered fusion based on any single order O. When Ω contains more than one order, [Ω]+ϵ ⊥may hold. This does not matter, however, since a non-singleton Ω plays only an auxiliary role in our logic.

3 Semantics

To present the semantics, we briefly review possibility theory [Zadeh, 1978]. In this theory, each possibility distribution π : W → [0, 1] can derive an associated possibility measure Π : 2W → [0, 1] and a necessity measure N : 2W → [0, 1], as Π(X) = supx∈X π(x) and N(X) = 1 - supx̸∈X π(x). A possibility distribution π : W → [0, 1] is normalized if Π(W) = 1. A normalized possibility distribution represents a consistent belief state. If π is not normalized, i.e., supx∈W π(x) < 1, it represents a partially inconsistent belief state. 1 - supx∈W π(x) is called the inconsistency degree of π, and is denoted by ι(π).

An SFPL⊗,ϵ n -structure is a tuple M = (W, (πi)1≤i≤n, V ), where W is a set of possible worlds, each πi maps each world w to a possibility distribution πi,w : W → [0, 1] over W such that ι(πi,w) ≤ ϵ, and V maps elements in Φ0 to subsets of W. We define πO,w for each O ∈ T On and w ∈ W inductively as follows:

Furthermore, we also define πΩ,w for each Ω ⊆ T On and w ∈ W, as πΩ,w = ⊗O∈Ω πO,w. Then, the satisfaction relation |= for SFPL⊗,ϵ n -model is defined as

• w |= p iff w ∈ V (p), for each p ∈ Φ0,
• w ̸|= ⊥ and w |= ⊤,
• w |= ¬ϕ iff w ̸|= ϕ,
• w |= ϕ ∨ ψ iff w |= ϕ or w |= ψ,
• w |= [Ω]aϕ iff NΩ,w(|ϕ|) ≥ a,
• w |= [Ω]+a ϕ iff NΩ,w(|ϕ|) > a,

where |ϕ| is the truth set of ϕ in the model and NΩ,w is the necessity measure associated with πΩ,w.

A set of wffs Σ is satisfied in a world w, written as w |= Σ, if w |= ϕ for all ϕ ∈ Σ. We write Σ |=M ϕ if, for each possible world w in M, w |= Σ implies w |= ϕ; and Σ |=SFPL⊗,ϵ n ϕ if Σ |=M ϕ for each SFPL⊗,ϵ n -structureM. Σ can be omitted when it is an empty set, so a wff ϕ is valid in M, denoted by |=M ϕ, if ∅ |=M ϕ, and |=SFPL⊗,ϵ n ϕ denotes ∅ |=SFPL⊗,ϵ n ϕ. The subscript is usually omitted if it is clear from the context.

· Axioms:

1. P: all tautologies of the propositional calculus

1. Bookkeeping:
2. (a) [Ω]cϕ ⊃ [Ω]+d ϕ if c > d
3. (b) [Ω]+c ϕ ⊃ [Ω]cϕ
4. (c) [Ω]0ϕ
5. (d) ¬[Ω]+1 ϕ
6. V1:
7. (a) ([Ω]aϕ∧ [Ω]a(ϕ ⊃ ψ)) ⊃ [Ω]aψ
8. (b) ([Ω]+a ϕ∧ [Ω]+a (ϕ ⊃ ψ)) ⊃ [Ω]+a ψ
9. V2: ¬[i]+ϵ ⊥
10. V3: if Ω1 ∩Ω2 = ∅, then
11. (a) ([Ω1]aϕ∧ [Ω2]bϕ) ⊃ [Ω1 ∪Ω2]a⊕bϕ
12. (b) ([Ω1]+a ϕ∧ [Ω2]+b ϕ) ⊃ [Ω1 ∪Ω2]+a⊕bϕ
13. O1:

1. O2:

• Rules of Inference:
• R1 (Modus ponens, MP):

1. R2 (Generalization, Gen):

Figure 1: The axiomatic system for SFPL⊗,ϵ n

4 Proof Theory

An axiomatic system can be developed for SFPL⊗,ϵ n by generalizing the corresponding axioms of DBFsn [Liau, 2005] and PL⊗n [Boldrin and Saffiotti, 1999]. The axiomatic system for SFPL⊗,ϵ n is presented in Figure 1. The symbol ⊕ in axiom V3 denotes the T-conorm corresponding to ⊗, which is defined as a ⊕ b = 1 - (1 - a) ⊗ (1 - b). The axiom V2 is the requirement that the inconsistency degree of each agent's belief state is not more than ϵ, which is the inconsistency tolerance degree of the logic. The axioms O1 and O2 further enforce the same property for each virtual agent O.

A wff ϕ is derivable from the system SFPL⊗,ϵ n , or simply, ϕ is a theorem of SFPL⊗,ϵ n , if there is a finite sequence ϕ1, . . . , ϕm such that ϕ = ϕm and every ϕi is an instance of an axiom schema; or it is obtained from earlier ϕj's by the application of an inference rule. It is written as ⊢SFPL⊗,ϵ n ϕ if ϕ is a theorem of SFPL⊗,ϵ n . Let Σ∪ {ϕ} be a subset of wffs, then ϕ is derivable from Σ in the system SFPL⊗,ϵ n , written as Σ ⊢SFPL⊗,ϵ n ϕ, if there is a finite subset Σ′ of Σ such that ⊢SFPL⊗,ϵ n ∧ Σ′ ⊃ ϕ. We drop the subscript when no confusion occurs. We then have the soundness and completeness theorem for SFPL⊗,ϵ n .

Theorem 1 For any wff ϕ of SFPL⊗,ϵ n , |= ϕ iff ⊢ ϕ.

5 Concluding Remarks

In this paper, we present a modal logic for reasoning about ordered fusion of possibilistic beliefs based on a level skipping strategy. While direct fusion and ordered fusion in epistemic logic [Fagin et al., 1996; Cholvy, 1994; Liau, 2005], as well as direct fusion in possibilistic logic [Boldrin and Saffiotti, 1999] have been proposed previously in the literature, the results in this paper fill a gap in the previous works. The modal logic should be applicable to reasoning in multi-agent systems. In future work, it should be possible to consider operations other than T-norms for the fusion of possibility distributions.