Tremendous research e↵ort has been dedicated over the years to thoroughly investigate non-monotonic reasoning. With the abundance of non-monotonic logical formalisms, a unified theory that enables comparing the di↵erent approaches is much called for. In this paper, we present an algebraic graded logic we refer to as LogAG capable of encompassing various non-monotonic logics. One of the most widely studied logics of uncertainty is possibilistic logic tailored for non-monotonic reasoning under incomplete and partially inconsistent knowledge. We show how to encode possibilistic theories as LogAG theories, and prove that the LogAG logical consequence relation subsumes its possibilistic counterpart. Since possibilistic logic subsumes any non-monotonic inference relation satisfying Makinson's rationality postulates, our results prove that LogAG subsumes such inference relations as well while remaining immune to the drowning problem.
Non-monotonic logics are attempts to model commonsense defeasible
reasoning that allows making plausible, albeit possibly fallible, assumptions about the
world in the absence of complete knowledge. The term “non-monotonic” refers
to the fact that new evidence can retract previous contradicting assumptions.
This contrasts with classical logics where new evidence never invalidates previous
assumptions about the world. Modelling non-monotonicity has been the focus
of extensive studies in the knowledge representation and reasoning community
for many years giving rise to a vast family of non-monotonic formalisms. The
currently existing approaches to representing non-monotonicity can be classified
into two orthogonal families: fixed point logics and model preference logics [
Another widely studied approach to non-monotonicity developed
independently from the mainstream of the non-monotonic formalisms research is
possibilistic logic [
In this paper, we will show how to encode possibilistic theories as LogAG
theories, and prove that the LogAG logical consequence relation subsumes its
possibilistic counterpart. In doing so, we prove that LogAG captures any
nonmonotonic inference relation satisfying Makinson’s rationality postulates as well,
while staying immune to the drowning problem which plagues all logics based
on such relations [
In Section 2, LogAG will be reviewed describing its syntax and semantics. Section 3 will briefly review possibilistic logic. In Section 4, the main results of this paper, proving that LogAG subsumes possibilistic logic, will be presented. Finally, some concluding remarks are outlined in Section 5. 2
LogAG
LogAG is a graded logic for reasoning with uncertain beliefs. “Log” stands for
logic, “A” for algebraic, and “G” for grades. In LogAG, a classical logical
formula could be associated with a grade representing a measure of its uncertainty.
Non-graded formulas are taken to be certain. In this way, LogAG is a logic for
reasoning about graded propositions. LogAG is algebraic in that it is a language
of only terms, some of which denote propositions. Both propositions and their
grades are taken as individuals in the LogAG ontology. While some multimodal
logics such as [
While most of the graded logics we are aware of employ non-classical modal
logic semantics by assigning grades to possible worlds [
LogAG consists of algebraically constructed terms from function symbols. There are no sentences in LogAG; instead, we use terms of a distinguished syntactic type to denote propositions. Propositions are included as first-class individuals in the LogAG ontology and are structured in a Boolean algebra giving us all standard truth conditions and classical notions of consequence and validity. Additionally, grades are introduced as first-class individuals in the ontology. As a result, propositions about graded propositions can be constructed, which are themselves recursively gradable.
A LogAG language is a many-sorted language composed of a set of terms partitioned into three base sorts: P is a set of terms denoting propositions, D is a set of terms denoting grades, and I is a set of terms denoting anything else. A LogAG alphabet includes a non-empty, countable set of constant and function symbols each having a syntactic sort from the set = { P , D, I } [ {⌧ 1 ! ⌧ 2 | ⌧ 1 2 { P , D, I }} and ⌧ 2 2 } of syntactic sorts. Intuitively, ⌧ 1 ! ⌧ 2 is the syntactic sort of function symbols that take a single argument of sort P , D, or I and produce a functional term of sort ⌧ 23. In addition, an alphabet includes a countably infinite set of variables of the three base sorts; a set of syncategorematic symbols including the comma, various matching pairs of brackets and parentheses, and the symbol 8; and a set of logical symbols defined asP ,th{e u,n=.io}n✓ of tDhe!followDing!sets: P{¬,}a n✓d {PG!} ✓ PP, {!^ , _} ✓ D ! P ! P . TPe!rms involving ) 4, , , and 9 can always be expressed in terms of the above logical operators and 8. 3 Given the restriction of the first argument of function symbols to base sorts, LogAG is, in a sense, a first-order language. 4 Through out this paper we will use ) to denote material implication. 2.2
A key element in the semantics of LogAG is the notion of a LogAG structure.
S = hD, A, g, <, ei, where – D, the domain of discourse, is a set with two disjoint, non-empty, countable subsets: a set of propositions P, and a set of grades G. – A = hP, +, ·, , ? , >i is a complete, non-degenerate Boolean algebra. – g : P ⇥ G ! P is a grading function. – <: G ⇥ G ! P is an ordering function. – e : G ⇥ G ! {? , >} is an equality function, where for every g1, g2 2 G: e(g1, g2) = > if g1 = g2, and e(g1, g2) = ? otherwise.
A valuation V of a LogAG language is a triple hS, Vf , Vxi, where S is a LogAG structure, Vf is a function that assigns to each function symbol an appropriate function on D, and Vx is a function mapping each variable to a corresponding element of the appropriate block of D. A valuation V = hS, Vf , Vxi is called a natural valuation if P is made up of three disjoint sets: the set of base propositions PB forming a subalgebra that does not contain any grading proposition, the set of grading propositions PG = Range(g), and the set of all other propositions PB [ P G, and Vf maps all propositional terms that do not contain G to PB, all grading propositional terms to a proposition in PG, and all other propositional terms to PB [ P G. An interpretation of LogAG terms is given by a function [[·]]V .
Definition 2. Let L be a LogAG language and let V be a valuation of L. An interpretation of the terms of L is given by a function [[·]]V : – [[x]]V = Vx(x), for a variable x – [[c]]V = Vf (c), for a constant c – [[f (t1, . . . , tn)]]V = Vf (f )([[t1]]V , . . . , [[tn]]V ), for an n-adic (n
symbol f – [[(t1 ^ t2)]]V = [[t1]]V · [[t2]]V – [[(t1 _ t2)]]V = [[t1]]V + [[t2]]V – [[¬t]]V = [[t]]V – [[8x(t)]]V = Y [[t]]V[a/x]
a2D – [[G(t1, t2)]]V = g([[t1]]V , [[t2]]V ) – [[t1 . t2]]V = [[t1]]V < [[t2]]V – [[t1 = t2]]V = e([[t1]]V , [[t2]]V )
2.3
We define logical consequence using the familiar notion of filters from Boolean
algebra [
A propositional term is a logical consequence of a set of propositional terms if it is a member of the filter of the interpretation of , denoted F ([[ ]]V ). [[ ]]V 2 F ([[ ]]V ) where [[ ]]V =
Y [[ ]]V .
2
Unfortunately, the definition of logical consequence presented in the previous section cannot address uncertain reasoning with graded propositions. To see that, consider the following situation. You see a bird from far away that looks a lot like a penguin. You know that any penguin does not fly. To make sure that what you see is indeed a penguin, you ask your brother who tells you that this bird must not be a penguin since your sister told him that she saw the same bird flying. This situation can be represented in LogAG by a set of propositions Q as shown in Figure 1 where p denotes that the bird is a penguin, and f denotes that the bird flies. For the ease of readability of Figure 1, we write ¬f instead of f and p ) ¬ f instead of p + f . Since you are uncertain about whether the bird you see is a penguin, this is represented as a graded proposition g(p, d1) where d1 is your uncertainty degree in what you see. What your brother tells you is represented by the grading chain g(g(f, d2), d3) where d2 represents how much you trust your brother, and d3 represents how much you trust your sister. Now, consider an agent reasoning with the set Q. Initially, it would make sense for the agent to be able to conclude p even if p is uncertain (and, hence, graded) since it has no reason to believe ¬p. The filter F (Q), however, contains the classical logical consequences of Q, but will never contain the graded proposition p. For this reason, we extend our classical notion of filters into a more liberal notion of graded filters to enable the agent to conclude, in addition to the classical logical consequences of Q, propositions that are graded in Q (like p) or follow from graded propositions in Q (like ¬f ). This should be done without introducing inconsistencies. Due to nested grading, graded filters come in degrees depending on the depth of nesting of the admitted graded propositions. In Figure 1, F 1(Q) is the graded filter of degree 1. F 1(Q) contains everything in F (Q) in addition to the nested graded propositions at depth 1, p and g(¬q, d1). ¬f is also admitted to F 1(Q) since it follows classically from {p, p ) ¬ f }. Hence, at degree 1, we end up believing that the bird is a penguin that does not fly. To compute the graded filter of degree 2, F 2(Q), we take everything in F 1(Q) and try to add the graded proposition f at depth 2. The problem is, once we do that, we have a contradiction with ¬f (we now believe that bird flies and does not fly at the same time). To resolve the contradiction, we admit to F 2(Q) either p (and consequently ¬f ) or f . In deciding which of p or f to kick out we will allude to their grades. The grade of p is d1, and f is graded in a grading chain containing d2 and d3. To get a fused grade for f , we will combine both d2 and d3 using an appropriate fusion operator. If d1 is less than the fused grade of f , p will not be admitted to the graded filter, together with it consequence ¬f . Otherwise, f will not be admitted, and p and ¬f will remain. If we try to compute F 3(Q), we get everything in F 2(Q) reaching a fixed point.
In general, the elements of F i(Q) will be referred to as the graded consequences at depth i. The rest of this section is dedicated to formally defining graded filters together with our graded consequence relation based on graded filters. In the sequel, for every p 2 P and g 2 G, g(p, g) will be taken to represent a grading proposition that grades p. Moreover, if g(p, g) 2 Q ✓ P , then p is graded in Q. The set of p graders in Q is defined to be the set Graders(p, Q) = { | q q 2 Q and q grades p}. Throughout, a LogAG structure S = hD, A, g, <, ei is assumed.
As a building step towards formalizing the notion of a graded filter, the structure of graded propositions should be carefully specified. For this reason, the following notion of an embedded proposition is defined.
Since a graded proposition p might be embedded at any depth n 2 N, the degree of embedding of a graded proposition p is defined as follows.
Q(p) = 0; and
Q(p) = e + 1, where e = minq2 Graders(p,E(Q)){ Q(q)}.
For notational convenience, we let the set of embedded propositions at depth n be En(Q) = {p 2 E(Q) | Q(p) n}, for every n 2 N.
Example 1. Consider Q = {g(g(g(p, 2), 3), 4), g(g(g(r, 2), 3), 5), g(g(g(p, 2), 3), 5), g(g(p, 2), 6), q}.
– E0(Q) = Q. – E1(Q) = E0(Q) [ { g(g(p, 2), 3), g(g(r, 2), 3), g(p, 2)}. – E2(Q) = E1(Q) [ { g(p, 2), g(r, 2), p}. – E3(Q) = E2(Q) [ { r}. – E(Q) = E3(Q). – The degree of embedding – The degree of embedding
grading p is 2). – The degree of embedding
Q(r) = 3.
Q(q) = 0.
Q(p) = 2 (since the length of the minimum chain tu
The key to defining graded filters is the intuition that the set of consequences of a proposition set Q may be further enriched by telescoping Q and accepting some of the propositions graded therein. For this, we need to define (i) the process of telescoping, which is a step-wise process that considers propositions at increasing grading depths, and (ii) a criterion for accepting graded propositions which, as mentioned before, depends on the grades of said propositions. Since the nesting of grading chains is permissible in LogAG, it is necessary to compute the fused grade of a graded proposition p in a chain C to decide whether it will be accepted or not. The fusion of grades in a chain is done according to an operator ⌦ . Further, since a graded proposition p might be graded by more than one grading chain, we define the notion of the fused grade of p across all the chains grading it by an operator .
P 5. A telescoping structure for S is a quadruple T = hT , O, ⌦ , i , where
– T ✓ P , referred to as the top theory;
– O is an ultrafilter of the subalgebra induced by Range(<) (an ultrafilter is a
maximal filter with respect to not including ? ) [
Recasting the familiar notion of a kernel of a belief base [
Definition 8. For a telescoping structure T = hT , O, ⌦ , i
6 Q ✓ P , if X ✓ Q , then p 2 X survives X given T if
1. p is ungraded in Q; or
and a fan-in-bounded
5 P is depth-bounded if every grading chain has at most d distinct grading propositions
and is fan-out-bounded if every grading proposition grades at most fout propositions
where d, fout 2 N [
(fT(q, Q) < fT(p, Q)) 2 O.
The notion of a proposition p being supported in Q is defined as follows.
1. p 2 F (T ); or
The T-induced telescoping of Q is defined as the set of propositions supported given T in the set of kernel survivors of E1(F (Q)).
E1(F (Q)) is fan-in-bounded, then the T-induced telescoping of Q is given by ⌧ T(Q) = &( (E1(F (Q)), T), T ).
Observation 1 If Q is consistent (F (Q) 6= P), then ⌧ T(Q) = E1(F (Q)).
If F (Q) has finitely-many grading propositions, then ⌧ T(Q) is defined, for every telescoping structure T. Hence, provided that the right-hand side is defined, let ⌧ Tn(Q) = ⇢ Q if n = 0
⌧ T(⌧ Tn 1(Q)) otherwise Definition 11. A graded filter of a top theory T , denoted F n(T), is defined as the filter of the T-induced telescoping of T of degree n.
In the following example, we now go back to the situation we introduced at the beginning of this section in Figure 1. We show how the formal construction of the graded filters matches the intuitions we pointed out earlier. Example 2. Consider Q = { p + f, g(p, 2), g(g(f, 2), 3)} and T = hQ, O, ⌦ , i where = max, and ⌦ = mean. In what follows, let ⌧ Tn be an abbreviation for ⌧ Tn(Q).
– ⌧ T0 = Q – ⌧ T1 = ⌧ T(⌧ T0 ) = &( (E1(F (Q)), T), T )
F (Q) = Q [ { p + f.g(p, 2), g(g(f, 2), 3) + g(p, 2), ....} E1(F (Q) = F (Q) [ { p, g(f, 2)} (E1(F (Q), T) = E1(F (Q)) ⌧ T1 = (E1(F (Q), T) = &( (E1(F (Q), T), Q) F 1(T) = F (⌧ T1 ) Upon telescoping to degree 1, there are no contradictions in E1(F (Q)) (no ? kernel X ✓ E1(F (Q)). Hence, everything in E1(F (Q)) survives telescoping and is supported. At level 1, we believe that the bird we saw is indeed a penguin. – ⌧ T2 = ⌧ T(⌧ T1 )
E1(F (⌧ T1 )) = F (⌧ T1 ) [ { f } (E1(F (⌧ T1 )), T) = F (⌧ T1 ) { p} ⌧ T2 = &( (E1(F (⌧ T1 )), T), Q) = (E1(F (⌧ T1 )), T) { f } F 2(T) = F (⌧ T2 ) Upon telescoping to degree 2, there are two ? kernels {f, f } and {p, p + f, f }. f survives the first kernel as it is not graded in Q. f survives the first kernel as well as it is the only graded proposition in the kernel with another member f 2/ F (Q). p does not survive the second kernel as the kernel contains another graded proposition f and the grade of p (2) is less than the fused grade of f (mean(2, 3) = 2.5). Accordingly, f loses its support and is not supported in the set of kernel survivors. The graded filter of degree 2 does not contain p or f . At level 2, we start taking into account the information our brother told us. Since our combined trust in our brother and sister is higher that our trust in what we saw, we end up not believing that the bird we saw is a penguin since we believe that it flies. – ⌧ T3 = ⌧ T(⌧ T2 ) ⌧ T3 = &( (E1(F (⌧ T2 )), T), Q) = (E1(F (⌧ T2 )), T) F 3(T) = F (⌧ T3 ) = F 2(T) reaching a fixed point. tu
We use graded filters to define graded consequence as follows. Given a LogAG theory T ✓ P and a valuation V = hS, Vf , Vxi, let V(T) = {[[p]]V | p 2 T}. Further, for a LogAG structure S, an S grading canon is a triple C = h⌦ , , ni where n 2 N and ⌦ and are as indicated in Definition 7.
Definition 12. Let T be a LogAG theory. For every p 2 P , valuation V = hS, Vf , Vxi where S has a set P which is depth- and fan-out-bounded, and S grading canon C = h⌦ , , ni, p is a graded consequence of T with respect to C, denoted T |'C p, if F n(T) is defined and [[p]]V 2 Fn(T) for every telescoping structure T = hV(T), O, ⌦ , i for S where O extends F (V(T) \ Range(<))7.
It is worth noting that |'C reduces to |= if n = 0 or if F (E(V(T))) does not
contain any grading propositions. However, unlike |=, |'C is non-monotonic in
general.
7 An ultrafilter U extends a filter F , if F ✓ U .
Possibilistic logic is a weighted logic that handles uncertainty, in a qualitative
way by associating certainty levels, to classical logic formulas [
Given the possibility distribution ⇡ , the following two measures can be defined on the formulas in the language.
– The possibility degree ⇧ ⇡ ( ) = max{⇡ (! ) | ! 2 [ ]} (where [ ] is the set of models of ) evaluates the extent to which is consistent with the available information expressed by the possibility distribution ⇡ . – The necessity degree N⇡ ( ) = 1 ⇧ ⇡ (¬ ) evaluates the extent to which is entailed by the available information.
The semantic determination of a belief set is defined as the set of formulas whose possibility measures are greater than the possibility of their negations.
BS(⇡ ) = { | ⇡ ( ) > ⇡ (¬ )}
An epistemic state can also be represented syntactically in possibilistic logic. On the syntactic level, a possibilistic knowledge base is defined as a finite set of weighted formulas ⌃ = {( i, ai)} where ai is a lower bound on the necessity measure of i. A possibilistic knowledge base is said to be consistent if the classical knowledge base, obtained by omitting the weights, is consistent. Each possibilistic knowledge base is associated with an inconsistency degree which is defined as followed.
Inc(⌃ ) = ⇢ 0 max{a | ⌃ a is inconsistent} if ⌃ is consistent otherwise where ⌃ a are the formulas in ⌃ with weights greater than or equal to a.
The syntactic computation of a belief set induced by ⌃ is defined as the logical consequences of the formulas in ⌃ with weights higher than Inc(⌃ ).
BS(⌃ ) = { | ⌃ >Inc(⌃ ) ✏ } 4
Representing Possibilistic Logic in LogAG In this section, we show how to encode possibilistic theories as LogAG theories, and prove that the LogAG subsumes possibilistic logic. Moreover, we discuss the drowning problem that plagues possibilic logic and show that LogAG does not su↵er from the same problem.
In what follows, for any possibilistic knowledge base ⌃ P L, let (a, ⌃ P L) = |A| where A = {ai | ( i, ai) 2 ⌃ P L and ai > a}. Intuitively, (a, ⌃ P L) denotes the number of distinct weights appearing in a possibilistic knowledge base ⌃ P L greater than a.
LogAG theory is defined as ⌃ LogAG = {chain( i, d) | ( i, ai) 2 ⌃ P L and d = (ai, ⌃ P L)} where chain is a function mapping a possibilistic formula (without its weight) and d to a LogAG term denoting a grading proposition as follows: chain(, d ) = ⇢ G(, 1)
G(chain(, d
if d = 0 1), 1) otherwise Example 3. Consider ⌃ P L = {(p, 1), (p ) b, 1), (p ) ¬ f, 0.6), (b ) f, 0.3), (b ) w, 0.1)} where b denotes “bird”, p denotes “penguin”, f denotes “flies”, and w denotes “has wings”. The following table shows the corresponding LogAG theory terms constructed according to Definition 13.
( i, ai) (p, 1) (p ) b, 1) (p ) ¬ f, 0.6) (b ) f, 0.3) (b ) w, 0.1) (ai, ⌃ P L) 0 0 1 2 3 ⌃ LogAG term
G(p, 1)
G(p ) b, 1)
G(G(p ) ¬ f, 1), 1)
G(G(G(b ) f, 1), 1), 1)
G(G(G(G(b ) w, 1), 1), 1), 1)
LogAG theory ⌃ LogAG, and Q = {[[ ]]V | 2 ⌃ LogAG} where V is a natural valuation. For any weighted formula ( i, ai) 2 ⌃ P L, the degree of embedding of of the interpretation of in Q, Q([[ i]]V ), is (ai, ⌃ P L) + 1.
It is worth noting that the corresponding ⌃ LogAG theory will always be consistent using this construction. The propositions in the corresponding LogAG theory can be associated with any grade as we rely on only the degree of embedding to reflect the weight of the proposition in the original possiblistic logic knowledge base. For simplicity, we just associate the grade 1 with all graded propositions in ⌃ LogAG. It follows directly from Observation 2 that the interpretations of all formulas with the same weight in ⌃ P L have the same embedding degree in Q. The less the weight ai of a formula i in ⌃ P L, the higher the embedding degree of [[ i]]V in Q.
LogAG theory ⌃ LogAG, and Q = {[[ ]]V | 2 ⌃ LogAG} where V is a natural valuation. The graded filter F n(T) of degree n = (Inc(⌃ P L), ⌃ P L) for some telescoping structure T of Q, is identical to F (En(Q)).
Proof. We prove this by induction on n.
Base case (n=0): By Definition 11, F 0(T) = F (⌧ T0 (Q)) = F (Q) = F (E0(Q)) since E0(Q) = Q.
Induction Hypothesis: For n 0, suppose that F n(T) = F (En(Q)). Induction Step: F n+1(T) = F (⌧ Tn+1(Q)) = F (⌧ T(⌧ Tn(Q))) = F (&( (E1(F (⌧ Tn(Q)))) = F (&( (E1(F n(T)))). By the induction hypothesis, F n+1(T) = F (&( (E1(F (En(Q)))))). Since Q is consistent given it is the set of interpretations of ⌃ LogAG which is consistent according to how it was constructed, then F n(T) must be consistent according to Definition 11. Consequently, F (En(Q)) must be consistent too. Since En(Q) contains only the propositions in Q (which are only grading propositions according to how ⌃ LogAG was constructed) in addition to the propositions with embedding degrees less than or equal to n, then F (En(Q)) contains nothing other than the propositions in En(Q) in addition to their trivial consequences. Hence, E1(F (En(Q))) = F (E1(En(Q))) = F (En+1(Q)), and F n+1(T) = F (&( (F (En+1(Q))))). Let ( , a) 2 ⌃ P L where Inc(⌃ P L) = a. According to Observation 2, ( , Q) = (Inc(⌃ P L), ⌃ P L) + 1 > n + 1 (since n + 1 = (Inc(⌃ P L), ⌃ P L)). It follows then that En+1(Q) is consistent. By Observation 1, &( (F (En+1(Q)))) = F (En+1(Q)). Therefore, F n+1(T) = F (F (En+1(Q))) = F (En+1(Q)). tu
responding LogAG theory. For every non-grading proposition and grading canon C = h⌦ , , ni with n = (Inc(⌃ P L), ⌃ P L), 2 BS(⌃ P L) if and only Proof. In what follows, let Q = {[[ ]]V | 2 ⌃ LogAG} be the valuation of ⌃ LogAG where V is a natural valuation.
Suppose that 2 BS(⌃ P L). Then, by definition of BS(⌃ P L), it must be that is logically implied by a set S = { | ( , a) 2 ⌃ P L and a > Inc(⌃ P L)}. According to how ⌃ LogAG was constructed by and Observation 2, for every formula 2 S in Q, Q([[ ]]V ) = (a, ⌃ P L) + 1 where a is the weight of in ⌃ P L. Since a > Inc(⌃ P L), it follows that Q([[ ]]V ) n and [[ ]]V 2 En(Q). Hence, by Observation 3, [[ ]]V 2 Fn(T) for all telescoping structures T of Q. By Definition 12, it must be that ⌃ LogAG |'C .
Now suppose that ⌃ LogAG |'C , then according to Definition 12, it must be that [[ ]]V 2 Fn(T) for all telescoping structures T of Q. According to Observation 3, [[ ]]V 2 F (En(Q)). Let S = {p | p 2 En(Q) \ P B}. It follows that is logically implied by a set of propositional terms whose interpretations are in S, and each p 2 S has an embedding degree m less than or equal to n. Let be the propositional term denoting p. It must be that ( , a) 2 ⌃ P L since the only embedded non-grading propositions in ⌃ LogAG are the formulas appearing in ⌃ P L according to Definition 13. Further, by Observation 2, m = (a, ⌃ P L) + 1. Therefore, m < n and a > Inc(⌃ P L). By the definition of BS(⌃ P L), it must be that 2 BS(⌃ P L). tu Example 4. Consider the possibilistic knowledge base ⌃ P L and its corresponding LogAG theory in Example 3. The inconsistency degree Inc(⌃ P L) = 0.3. Therefore, BS(⌃ P L) = { | {p, p ) b, p ) ¬ f } ✏ } since p, p ) b, and p ) ¬ f are the formulas in ⌃ P L with weights higher than the inconsistency degree. The graded filter of degree n = (Inc(⌃ P L), ⌃ P L) = 2, F 2(T) = F (E2(Q)) where T is a telescoping structure of Q denoting the valuation of ⌃ LogAG. The only non-grading propositions in E2(Q) are p, p ) b, and p ) ¬ f . Hence, the set of propositional terms whose interpretations are in F (E2(Q)) is equal to BS(⌃ P L). In both BS(⌃ P L) and F 2(T) we end up believing that a penguin is a bird that does not fly. tu
It should be obvious that the formulas in a possibilistic knowledge base ⌃ P L
with weights less than Inc(⌃ P L) are blocked even if they do not contribute
to the inconsistency. This problem is one limitation of possibilistic logic and
is referred to in the literature as the drowning problem [
n = 0 0.1 ⌃ L0ogAG n = 1 1.1. ⌃ L0ogAG 1.2. p 1.3. p ) b 1.4. G(p ) ¬ f, 1) 1.5. G(G(b ) f, 1), 1) 1.6. G(G(G(b ) w, 1), 1), 1) 1.7 b Upon telescoping to degree 3, we believe that a penguin is a bird that does not fly. The rule b ) f does not survive telescoping as it has a lower grade ( 31 ) than p (1), p ) b (1), p ) ¬ f ( 12 ). Upon telescoping to degree 4, we believe that a penguin has wings since the rule b ) w survives telescoping and we still believe that penguins have birds. According to the semantics of LogAG and the definition of graded filters, no proposition will ever be discarded unless it directly contributes to a contradiction.
Note that the LogAG logical consequence relation is only equivalent to its possibilistic counterpart for a grading canon C = h⌦ , , ni with n = (Inc(⌃ P L), ⌃ P L) as illustrated in Example 4. This is by no means the recommended use of LogAG. If we continue telescoping beyond n = (Inc(⌃ P L), ⌃ P L) as illustrated in Figure 2 (which is what should naturally happen in LogAG), the drowning problem is avoided. 5
Conclusion
We presented an algebraic graded non-monotonic logic we refer to as LogAG. It
is our conviction that LogAG provides an interesting alternative to the
currentlyexisting approaches for handling non-monotonicity. LogAG can be regarded as a
unified framework for non-monotonicity as it can capture various non-monotonic
logics. In this paper, we showed how possibilistic theories can be encoded in
LogAG, and we proved that the LogAG logical consequence relation captures
possibilistic inference. Since possibilistic logic is proven to capture any
nonmonotonic inference relation satisfying Makinson’s rationality postulates, our
results prove that LogAG captures such non-monotonic inference relations as
well while staying immune to the drowning problem. We are currently working
on relating LogAG to circumscription, default logic, and auto-epistemic logic.
In [