=Paper=
{{Paper
|id=Vol-494/paper-21
|storemode=property
|title=Comparing Strengths of Beliefs Explicitly
|pdfUrl=https://ceur-ws.org/Vol-494/famaspaper3.pdf
|volume=Vol-494
|dblpUrl=https://dblp.org/rec/conf/mallow/JonghG09
}}
==Comparing Strengths of Beliefs Explicitly==
https://ceur-ws.org/Vol-494/famaspaper3.pdf
Comparing strengths of beliefs explicitly
Dick de Jongh Sujata Ghosh
Institute for Logic, Language and Computation Institute of Artificial Intelligence
Universiteit van Amsterdam Rijksuniversiteit Groningen
Email: D.H.J.deJongh@uva.nl Email: Sujata.Ghosh@rug.nl
Abstract—Inspired by a similar use in provability logic, for- The third time Fiona and Gregory apply. About both she is
mulas p ÂB q and p B {t | M, t |= ψ}.
of Belief logic with explicit ordering (KD45 −O), whose Thus, ÂB is also a global notion. We will now show
language is defined as follows: that the universal modality U can also be expressed in
KD45 −O. The modality Eϕ (the abbreviated form of
Definition II.1 Given a countable set of atomic propositions ¬U ¬ϕ) can be defined as ϕ ÂB ⊥, and hence U ϕ itself
Φ, formulas ϕ are defined inductively: as ⊥ B Y , where X >B Y iff X ≥B Y If one wants to base the strength of belief ordering on
and not (Y ≥B X). the plausibility ordering of the worlds, then immediately
3) If X is non-empty, then X >B ∅. the following option comes to mind: the interpretation of
ϕ ÂB ψ can be that there exist ϕ-worlds which are more
The first condition says that larger sets of worlds are more plausible than any ψ-world (similar to the proposal in [9]).
plausible, the second one that the sets containing the center For ϕ B . We have already seen that
ordering ≥B between the sets of worlds in the plausibility Eϕ can be defined as ϕ ÂB ⊥, because of the 3rd condition
models. We have put very minimal requirements on this that >B satisfies in the model. Using lin-axiom it is easy to
ordering. In fact, as we will see in section II-B, belief can be show that U ϕ is equivalent to ⊥ B is the corresponding strict ordering, the following
axioms need no introduction: From this the principle Bϕ → U Bϕ readily follows. The
transitivity and the symmetry axioms for U follow because of
ϕ 1 V (χ) iff ψ ÂB χ is true in the
and the center axiom describes property 2. With U and E model. These follow from the first three ordering axioms.
defined as indicated previously, one can easily show that the Moreover, if V (ψ) ⊆ V (χ) then V (ψ) ≥1 V (χ) (subset
S5-axioms are derivable for U . It is also not very hard to condition), by the axiom: U (χ → ψ) → ψ 1
V (χ) (sufficient belief condition) by the axiom: Bψ ∧¬Bχ →
Assume 0KD45 −O ϕ. We will have to construct a counter- ψ ÂB χ.
model to ϕ as a KD45 −O-model. We take a finite adequate So, ≥1 behaves properly on the representable elements of
set Φ containing ϕ. In this case an adequate set will be: a P(W ). What remains is to extend ≥1 to an ordering ≥ with
set of formulas that is closed under subformulas containing the right properties over all of P(W ).
with each formula ψ (a formula equivalent to) ¬ψ, containing Take an arbitrary subset X of W . We define R(X) to be
with Bψ and Bχ (a formula equivalent to) B(ψ ∧ χ) and the largest subset of X that is representable. That such a set
a formula (equivalent to) B(ψ ∨ χ). We also need Φ to exists follows from the fact that the representable subsets are
contain with each formula Bϕ a formula (equivalent to) U Bϕ. closed under finite unions and the finiteness of the model.
Finally, Φ contains B> and B⊥. It is easy to see that any We now define X ≥ Y iff R(X) ≥1 R(Y ). This imme-
finite set is contained in a finite adequate set. We use the diately makes ≥ a quasi-linear order. That ≥ satisfies the
Henkin method restricted to Φ. Consider the m.c. (maximally subset condition follows from the fact that, if X ⊆ Y , then
consistent) subsets of Φ. In particular consider such an m.c. R(X) ⊆ R(Y ).
set Φ0 containing ¬ϕ. When we now refer to U ψ we mean
its translation into KD45 −O. It can be shown that the S5- We will conclude this proof with a lemma showing
axioms to hold for this translation. The proof is made more that B is representable, i.e. B = R(B). From that result
perspicuous by referring to U . it follows that, if B ⊆ X, then B ⊆ R(X). This is
The relations RB and RU are defined as follows: clearly sufficient to ensure the sufficient belief condition. So,
once we finish the proof of the following lemma, we are done.
P RB Q iff (1) for all Bϕ in P , ϕ as well as Bϕ are in Q,
(2) for all ¬Bϕ in P , ¬Bϕ in Q.
P RU Q iff (1) for all U ϕ in P , ϕ as well as U ϕ are in Q, Lemma. B is representable.
(2) for all ¬U ϕ in P , ¬U ϕ in Q Proof of Lemma. Consider w not in B. Then it is not the
We have to show that RU is an equivalence relation and case that wRB w. This means that, for some particular B(ψw )
RB a Euclidean sub-relation of RU . Finally, within one U - in Φ, B(ψw ) is in w but ψw is not. Note that this implies that
equivalence class there is one, nonempty set of B-reflexive ψw is true all over B. Consider the conjunction ψ of all ψw for
elements, which forms a B-equivalence class. Since all these w in the complement of B. B(ψ) is a member of Φ while ψ
things are standard we skip this part. is true in all elements of B, but is falsified at all elements u in
We now take the submodel generated by RU from Φ0 . The the complement of B, since ψ implies ψu and ψu is falsified
set of worlds W of our model will be the set of worlds in u. We have shown that B is represented by ψ.
Since the counter-model constructed is finite, we also have M, s |= ¤ϕ iff M, t |= ϕ for all worlds t ≤ s.
that the logic KD45−O is decidable. Before ending this
section we mention some intuitively true formulas, which we which says that ϕ can be safely believed at some world s if it
did not need as axioms, but are definitely worth thinking about. holds at all the worlds which are at least as plausible as s. In
One of them is, the following we will introduce the safe belief modality in the
setting of KD45−O, and give a complete axiomatization of
(ϕ ÂB ⊥) → (> ÂB ¬ϕ), this logic. The language of the logic KD45−OS is defined
as follows:
which says that if ϕ is true somewhere then ¬ϕ is not as
much to be believed as a tautology. The other direction of the Definition II.4 Given a countable set of atomic propositions
implication can be derived. An equivalent formulation is, Φ, formulas ϕ are defined inductively:
(ϕ ) → (⊥ B X.
beliefs, and the relevant ordering axioms, viz. refl, trans, lin,
This seems a very reasonable addition as it makes the models center, existence, U ϕ, given by
where K̂ψ := ¬K¬ψ. They gave complete axiomatizations for ϕ := p | ¬ϕ | ϕ ∨ ϕ | P ϕ
conditional doxastic logic (logic of conditional belief) as well
as the logic of knowledge and safe beliefs. We do not consider We read P ϕ as “ϕ is plausible”. As mentioned above,
knowledge but for this part of the discussion it can be replaced the intuitive meaning of P ϕ can be captured by the formula
by U . Neither do we talk about conditional belief here, but ϕ ÂB ¬ϕ, and as such, the truth definition of P ϕ in the
belief can be defined in terms of the existential modality and KD45−O model is given by,
safe belief (i.e. in terms of safe belief and belief ordering) as
M, s |= P ϕ iff {t | M, t |= ϕ} >B {t | M, t |= ¬ϕ}.
follows:
Bϕ := E¤ϕ Theorem II.6 P -logic is complete and its validities are com-
Once we have in this manner the modal operator B as pletely axiomatized by the following axioms and rules:
a defined concept, we can easily derive all its well-known (a) all propositional tautologies and inference rules
properties in KD45−OS, but if that holds fully for its (b) plausibility axioms:
relations with
generally mean that we tend to believe in its happening rather c) monotonicity rule:
than its not happening. That is the interpretation we take here. if ϕ → ψ then P ϕ → P ψ
Hence, in terms of ordered formulas, P ϕ can be expressed
as ϕ ÂB ¬ϕ. Of course, there are other possible notions of Proof: First of all, we show that any formula in P-logic
plausibility, but here we interpret P ϕ as ‘more plausible than is equivalent to a formula with P -depth at most one. For that
not’. We now explore this notion of ‘plausibility’ in terms of purpose we first derive the following schemes:
belief ordering. 1) P ψ → (ϕ ↔ ϕ[>/P ψ])
2) ¬P ψ → (ϕ ↔ ϕ[⊥/P ψ])
An important principle that will be valid for the plausibility
operator P is U (ϕ → ψ) → (P ϕ → P ψ). This holds because Here, ϕ[>/P ψ] means ϕ with > substituted for some
if U (ϕ → ψ), not only will belief in ψ be at least as strong occurrences of P ψ. We prove by induction on the complexity
as in ϕ, but U (ϕ → ψ) implies U (¬ψ → ¬ϕ), so belief in of formulas ϕ with possible occurrences of > and ⊥.
¬ψ is not greater than in ¬ϕ. This leads to consequences like
In the base case, that is for the atomic propositions and
P (ϕ ∧ ψ) → P ϕ.
propositional constants, the result follows immediately.
The reason to take the set semantics for ordering formulas
(cf. Definition II.2) becomes clear. If we would adhere to the Induction step. This is trivial for the boolean connectives.
semantics we may have had for ÂB in terms of plausibility So, it suffices to prove it for P ϕ assuming it holds for ϕ.
ordering for worlds (instead of sets of worlds), P ϕ would From the induction hypothesis for the first scheme it follows
become equivalent to Bϕ, which obviously is undesirable. that (P ψ ∧ ϕ) ↔ (P ψ ∧ ϕ[>/P ψ]) is provable. Now assume
P ψ and P ϕ. By an axiom P (ϕ ∧ P ψ) follows. From the
fact just proved it follows that P (ϕ[>/P ψ] ∧ P ψ) and hence Evidently, P ϕ is a global notion - its value does not
P (ϕ[>/P ψ]). The proof for the second scheme is very similar. vary through the model. Again, P is clearly an introspective
notion. Interestingly, the principles 4 and 5 for the modal
To see that these schemes imply that each formula in operator P are derivable in this P -logic, but the K-axiom
P -logic is equivalent to a formula with P -depth at most one, is not. That P ϕ ∧ P ψ → P (ϕ ∧ ψ) ought not to be a
just note that ` ϕ ↔ ((P ψ ∧ ϕ) ∨ (¬P ψ ∧ ϕ)). Now, if we valid principle in the P -logic is clear if we interpret P ϕ as
want to get rid of occurrences of P ψ in ϕ we can replace ϕ ϕ ÂB ¬ϕ.
by ((P ψ ∧ ϕ[>/P ψ]) ∨ (¬P ψ ∧ ϕ[⊥/P ψ])). By doing this
consecutively for all occurrences of P ψ with no occurrences Let us finally note that an interpretation of P ϕ as ϕ
of P in ψ we obtain the desired result. as having probability more than 0.5 (or any other number
between 0.5 and 1) leads to exactly the P -axioms provided
Next, we show that any consistent set has a model. Assume one considers the probability statements themselves to always
we have a consistent set in the P -logic which can be extended have probability 1.
to a maximal consistent set Γ, say. Since we can restrict
attention to formulas which are boolean combinations of We now consider a system having both belief and the
atoms and formulas of the form P ϕ where ϕ no longer plausibility operator, viz. the BP -system. This system will
contains P , a maximal consistent set is essentially only a provide pointers to discuss logics of belief and disbelief in the
set of atoms, negations of atoms, such P ϕ’s and ¬P ϕ’s and next subsection. The language is that of the P -logic, together
their boolean combinations. with the additional modal operator for belief, B.
ϕ := p | ¬ϕ | ϕ ∨ ϕ | P ϕ | Bϕ
We now make a model in our sense where P ϕ gets
interpreted as ϕ >B ¬ϕ. The worlds will be simply defined Some validities of this logic in the KD45−O model are,
by a number of atoms being true in it and the rest of • Bϕ → P ϕ
the atoms false. Let us now consider the following model, • P ϕ → BP ϕ
M = (S, ≤, ≥B , V ), where S is the set of all maximal • ¬P ϕ → B¬P ϕ
consistent subsets. The ordering of the subsets is as follows:
There are 5 equivalence classes in the ordering starting with Theorem II.7 BP -logic is complete and its validities are
the highest grade of believability. We take membership of completely axiomatized by the following axioms and rules:
those classes to determine the degree of belief in the sets. a) all propositional tautologies and inference rules
(1) The whole set, which is of course represented by >. b) all KD45 axioms and rules
(2) The sets represented by those ϕ for which P ϕ is in Γ c) all P axioms and rules
(except for >). d) special axioms:
(3) The sets represented by those ϕ for which ¬P ϕ is in Γ Bϕ → (ψ ↔ ψ[>/Bϕ])
as well as ¬P ¬ϕ. ¬Bϕ → (ψ ↔ ψ[⊥/Bϕ])
(4) The sets represented by those ϕ for which P ¬ϕ is in Γ
(except for ⊥). Bϕ → P ϕ
(5) The empty set, which is of course represented by ⊥. The proof is very similar to that for the P -logic. It uses
These are all possibilities because of axiom P ϕ → ¬P ¬ϕ. the fact that the axioms force all formulas to be equivalent
Finally we take B, the center, to be the whole set (so, there to boolean combinations of atoms and formulas of the form
are no beliefs except the trivial one in >). P ϕ and Bϕ, where ϕ is boolean. It is noteworthy that the
principle Bϕ ∧ P ψ → P (ϕ ∧ ψ) of [23] fails in the BP -logic.
The two things we have to check are: First, that, if It is not difficult to construct a counterexample.
a set is in class (2), then any larger one will be in (2)
as well (or in (1)). This follows from the monotonicity D. Disbelief
rule. Similarly for the other classes. Second, that, if a set Disbelief in a proposition is governed by exactly the
X contains all of B, and another set Y doesn’t, then X opposite situation to the one discussed in the previous
> Y . That is trivial: X has to be B, the whole set, and Y isn’t. subsection, Dϕ can be expressed as ¬ϕ ÂB ϕ, that is P ¬ϕ.
As earlier, we can induce an ordering over all subsets With the huge amount of work going on in logics of
satisfying the required conditions. All the single worlds have to beliefs and belief revision, consideration of disbelief as a
be taken to be equally plausible, i.e. s ≤ t, for all s, t ∈ S. So, separate epistemic category came to fore in the latter part
for each consistent set we can have a model in KD45−O. So, of last decade ([24], [25]). Consideration of changing or
the axioms and rules given in Theorem 2.6 axiomatize the P - revising disbeliefs as a process analogous to belief revision
logic of ‘more plausible then not’. It is also worth-mentioning was taken up by [26]. Belief-disbelief pairs i.e. simultaneous
why (P ϕ ∧ P ψ) → P (ϕ ∧ ψ) will fail in general. There may consideration of belief and disbelief sets were also taken up
be sets in (2), the intersection of which, is not in (2). ([27], [28]) through which various connections of possible
inter-connectivity of beliefs and disbeliefs have come into b) all KD45 axioms and rules
focus. As mentioned earlier our notion of explicit belief c) disbelief axioms:
ordering provides another path into expressing the concept of Dϕ → (ψ ↔ ψ[>/Dϕ])
disbelief.
¬Dϕ → (ψ ↔ ψ[⊥/Dϕ])
The basic idea for disbelieving a proposition is that, the Dϕ → ¬D¬ϕ
inclination to believe in its negation is stronger than that D⊥
to believe it. Consequently, disbelieving is a much weaker d) special axioms:
notion than believing the negation of the proposition, but it Bϕ → (ψ ↔ ψ[>/Bϕ])
should imply that one does not believe in the proposition. In
other words, Dϕ is implied by B¬ϕ and implies ¬Bϕ but ¬Bϕ → (ψ ↔ ψ[⊥/Bϕ])
not the other way around in either case. Bϕ → D¬ϕ
e) anti-monotone rule:
To exemplify the matter a bit, let us consider the following if ϕ → ψ then Dψ → Dϕ
situation. Due to the unpredictable weather conditions, Pom’s
belief in that she should not cycle from Amsterdam to Leiden Some interesting validities of this logic are,
is much stronger than her belief that she should. When
options like this are available, it is very natural to have this • B¬ϕ → Dϕ
sort of ordering dilemma playing around people’s mind. This • Dϕ → ¬Bϕ
can be interpreted as that Pom disbelieves that she should • Dϕ → BDϕ
bike, which evidently implies that she does not believe that • ¬Dϕ → B¬Dϕ
she should bike. But that ‘she believes that she should not • ¬Dϕ → DDϕ
bike’ is a much stronger statement, which fails to express the • ¬Bϕ → DBϕ
finer interplay of doubts that is always prevalent in one’s mind. On the other hand, as in P -logic and BP -logic,
the corresponding intuitively incorrect principle,
In general, if a person faces a decision based on whether Dϕ ∧ Dψ → D(ϕ ∨ ψ) can also be avoided in the
a certain state of affairs is the case or an event happens, she BD-logic.
may not have enough evidence to believe that the state of
affairs is the case or is not the case. Then she may base her
decision on whether she thinks the state of affairs plausible or E. Preference
disbelieves in it. Only in the case that her strength of belief There is a very close relationship between an agent’s beliefs
in the two possibilities is equal, translated into our framework and her preferences which has been extensively discussed in
as ϕ ≡B ¬ϕ, it is a real tossup for her. ([30], [3]). Based on the ideas from optimality theory, intrinsic
preference on the basis of priority sequences P1 >> . . . >>
Various principles for the ‘disbelief’ operator together Pn is formulated. Here, the Pi0 s are first-order formulas with
with the ‘belief’ one have been discussed in [25] in the exactly one free variable, which is common to all of them.
autoepistemic logic framework of [29]. As such, the possible Preferences over objects can be defined in terms of these
world semantics provided there which is based on separate sequences. The basic idea is to define objective preference
sets of worlds for beliefs and disbeliefs is not very interesting, by:
and suffers from ‘disjointedness’ as well as ‘mirror-image’
P ref (d, e) ⇔ ∃i(Pi d∧¬Pi e)∧∀j < i (Pj d ↔ Pj e)
problems. These questions will not arise in the semantics we
propose here. The basic reason is the fact that ‘disbelief’ is For subjective preferences over objects, which in fact are
given a global stance in contrast to ‘belief’ which is apparent considered to be influenced by beliefs, several options are
from their respective interpretations. This also emphasizes the considered. We mention a few of them for the benefit of the
fact that disbelieving something is different from both from readers, their meanings are more or less obvious.
‘not believing’ as well as ‘believing the negation’.
P ref (d, e) ⇔ ∃i(B(Pi d) ∧ ¬B(Pi e) ∧ ∀j < i(B(Pj d) ↔
We now focus on getting a more feasible logic of belief and B(Pj e)))
disbelief in similar lines to BP logic introduced earlier. From
our formal understanding Dϕ is same as P ¬ϕ and hence we P ref (d, e) ⇔ ∃i(¬B(¬Pi d) ∧ B(¬Pi e) ∧ ∀j < i(B(¬Pj d)
get the following dual axiomatization of the BD-logic - ↔ B(¬Pj e)))
Theorem II.8 BD-logic is complete and its validities are P ref (d, e) ⇔ ∃i ((B(Pi d) ∧ ¬B(Pi e)) ∨ (¬B(¬Pi d)∧
completely axiomatized by the following axioms and rules: B(¬Pi e)) ∧ ∀j < i ((B(Pj d) ↔ B(Pj e)) ∧ (B(¬Pj d)
↔ B(¬Pj e))))
a) all propositional tautologies and inference rules
It is clear that the above three approaches are different
attempts to express that up to a certain level of the priority
sequence the degree of belief in the objects d and e having ψ
the mentioned properties is the same and that at the next level
the degree of belief in d having the right property is greater
than that in e having it. Here we can express this directly in
the language as below, and the way greater strength of belief
Fig. 2. A public announcement ψ is uttered
is to be taken in a particular application is then delegated to
the semantics.
also, with the introduction of formulas like Ua ϕ. The notion
P ref (d, e) ⇔ ∃i(Pi d ÂB Pi e ∧ ∀j < i(Pj d ≡B Pj e)).
of comparative classes [17] which gives the set of worlds that
an agent considers relevant while positioned at her current
F. Multi-agent case world comes into play. Formally, a comparative class of some
We have been focusing on beliefs and strengths of beliefs of world is just the set of worlds that are related to the current
a single agent. The whole idea can be generalized to the multi- world by the plausibility order. To give meaning to agents’
agent framework. We only give some preliminary ideas here. beliefs, strength of beliefs, these relevant worlds are needed
The technical details need to be worked out, and we leave it to be considered only, unlike the single agent case, where the
for the future. The language of the logic of belief ordering in whole model is taken into account. As mentioned earlier, we
the multi-agent case, KD45 −OM can be defined as follows: leave the technical details for later.
Definition II.9 Given a finite set of agents A, and a countable
III. DYNAMICS OF ORDERING FORMULAS
set of atomic propositions Φ, formulas ϕ are defined induc-
tively: Till now we have been talking about the static language of
ϕ := ⊥ | p | ¬ϕ | ϕ ∨ ϕ | Ba ϕ | ϕ ⇑ψ ⇑ψ
B Y , where >B denotes the
corresponding strict ordering.
The model satisfies the following conditions: 3) If X is non-empty, then X >⇑ψ B ∅.
1) If X ⊆ Y ⊆ S !ψ , then Y ≥!ψ B X The truth definitions of the formula [!ψ]ϕ in a KD45−O
2) if B !ψ is the new set of plausible worlds, truth on which model is given by,
suffices to make an assertion to be believed, then B !ψ ⊆
X ⊆ S !ψ ∧ B !ψ 6⊆ Y ⊆ S !ψ ⇒ X >!ψ !ψ M, s |= [⇑ ψ]ϕ iff M⇑ψ , s |= ϕ.
B Y , where >B
denotes the corresponding strict ordering. We have the following theorem:
3) If X is non-empty, then X >!ψ B ∅.
Theorem III.4 If we take L to be a complete axiomatization
The truth definitions of the formula [!ψ]ϕ in a KD45−O of KD45−O with conditional beliefs, then its extension under
model is given by, announcement of soft information with lexicographic upgrade
is complete and its validities are completely axiomatized by
M, s |= [!ψ]ϕ iff if M, s |= ψ, then M!ψ , s |= ϕ.
the following axioms and rules in addition to L:
Any logic L completing KD45−O to contain conditional (a) reduction axioms:
beliefs will have to contain [⇑ ψ]q ↔ q
B ψ ϕ ∧ ¬B ψ χ → (ψ ∧ ϕ) ÂB (ψ ∧ χ). [⇑ ψ]¬ϕ ↔ ¬[⇑ ψ]ϕ
This axiom ensures that the updated model still has the [⇑ ψ](ϕ ∧ χ) ↔ ([⇑ ψ]ϕ ∧ [⇑ ψ]χ)
necessary property 2 of Definition II.2 and thus will be a [⇑ ψ]B χ ϕ ↔ (E(ψ ∧ [⇑ ψ]χ) ∧ (B ψ∧[⇑ψ]χ [⇑ ψ]ϕ ∨
KD45−O model. We have the following theorem: B [⇑ψ]χ [⇑ ψ]ϕ))
[⇑ ψ](ϕ