=Paper= {{Paper |id=Vol-1444/paper3 |storemode=property |title=Algebraic Semantics for Graded Propositions |pdfUrl=https://ceur-ws.org/Vol-1444/paper3.pdf |volume=Vol-1444 |dblpUrl=https://dblp.org/rec/conf/ki/IsmailE15 }} ==Algebraic Semantics for Graded Propositions== https://ceur-ws.org/Vol-1444/paper3.pdf
 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning




    Algebraic Semantics for Graded Propositions

                    Haythem O. Ismail1,2 and Nourhan Ehab2
              1
               Cairo University, Department of Engineering Mathematics
          2
              German University in Cairo, Department of Computer Science
                   {haythem.ismail,nourhan.ehab}@guc.edu.eg



      Abstract. We present LogA G, an algebraic language for reasoning about
      graded propositions. LogA G 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 LogA G ontology. Thus, the lan-
      guage includes terms denoting graded propositions, grades of proposi-
      tions, grading propositions, and graded grading propositions in an arbi-
      trary compositional structure. In this paper, we present the syntax and
      semantics of LogA G, defining an infinite sequence of graded logical con-
      sequence relations, each corresponding to accepting graded propositions
      at some nesting depth. We show the utility of LogA G in default rea-
      soning, reasoning about information provided by a chain of sources with
      varying degrees of trust, and representing the dilemma one is in when
      facing paradoxical liar-like sentences.


1   Introduction

Graded, or weighted, logics have witnessed increased attention and interest over
the years, which may be attested by the sheer length of the bibliography of a
recent comprehensive survey [1]. Whether the interest is in modelling uncertain
beliefs [2, 3, for instance], reasoning with vague predicates [4, 5, for instance],
revising a logical theory [6], or jumping to default conclusions [7], weighted
logics are always an obvious resort. To demonstrate the variety of phenomena
falling under the rubric of weighted logics, we present three problems (two of
which are classical) that we shall carefully revisit in Section 4.

The Case of Opus and Tweety. Tweety is a bird and Opus is a penguin.
  You believe that penguins are birds. In the absence of other information,
  you would like to jump to the conclusion that Tweety flies and Opus does
  not. How do you do so gracefully and without succumbing to absurdity?
The Case of Superman. You open the Daily Planet and read a report by Lois
  Lane claiming that Superman was seen in downtown Metropolis at noon. You
  happen to have seen Clark Kent at his office at noon, and you have always
  had a feeling that Superman is Clark Kent. What should you believe about
  the whereabouts of Superman if you trust your perception very much, you
  trust Lois Lane’s honesty, you only mildly trust the Daily Planet, and you
  still have your doubts about whether Superman is indeed Clark Kent?


                                        29
 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning




The Case of the Liar. The first sentence of the paragraph titled “The Case
  of the Liar” in this paper is not true. Having read the previous sentence,
  should you believe it or not? (cf. [8].)

    Weighted logics have something to say about each of the above cases (or,
at least, so we claim). In this report, we present the syntax and semantics of
a family of logical languages, LogA G, for reasoning about graded propositions
and, in Section 4, we demonstrate how the above cases are treated within LogA G
theories. While most of the weighted logics we are aware of employ some form
of non-classical, possible-worlds, semantics, basically assigning some notion of
grade to possible worlds or truth values, LogA G is a non-modal logic, with
classical notions of worlds and truth values. This is not to say that LogA G is a
common classical logic—it surely is not—but it is closer in spirit to classical non-
monotonic logics in artificial intelligence [9, 7, for example].3 In such formalisms,
as in LogA G, there is a classical logical consequence relation on top of which we
define a non-classical relation which is more restrictive, selecting only a subset
of the classical models. We achieve this by taking the algebraic, rather than the
modal, route.
    LogA G is algebraic in the sense that it only contains terms, algebraically
constructed from function symbols. No sentences are included in a LogA G lan-
guage; instead, there are terms of a distinguished syntactic type that are taken
to denote propositions. LogA G is a variant of LogA B [10] and LogA S [11], which
are algebraic languages for reasoning about, respectively, beliefs and temporal
phenomena. The inclusion of propositions in the ontology, though non-standard,
has been suggested by several authors [12–15, for example]. (See [10] and [15] for
a thorough defense of this position.) In the LogA G ontology, propositions are
structured in a Boolean algebra, giving us, almost for free, all standard truth
conditions and standard notions of consequence and validity. In addition, we also
admit grades as first-class individuals in the ontology. Thus, we combine propo-
sitions and grades to construct propositions about graded propositions, which,
recursively, are themselves gradable. This yields a language that is on one hand
quite expressive and, on the other hand, intuitive and very similar in syntax to
first-order logic.4


2   LogA G Languages

LogA G is a class of many-sorted languages that share a common core of logical
symbols and differ in a signature of non-logical symbols. In what follows, we
identify a sort σ with the set of symbols of sort σ. A LogA G language is a set of
terms partitioned into three base syntactic sorts, σP , σD and σI . Intuitively, σP
3
  But it is neither second-order like circumscriptive theories [9] nor dependent on
  special default rules like default logic [7].
4
  While multi-modal logics such as those presented in [16] and [17] may be used to
  express graded grading propositions, the grades themselves are embedded in the
  modal operators and are not amenable to reasoning and quantification.


                                        30
 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning




is the set of terms denoting propositions, σD is the set of terms denoting grades
of propositions, and σI is the set of terms denoting anything else.
    As is customary in many-sorted languages, an alphabet of LogA G is made up
of a set of syncategorematic punctuation symbols and a set of denoting symbols
each from a set σ = {σP , σD , σI } ∪ {τ1 −→ τ2 |τ1 ∈ {σP , σD , σI } and τ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 τ2 . Given the restriction of the first argument of function symbols to base
sorts, LogA G is, in a sense, a first-order language.
    A LogA G alphabet is a union of four disjoint sets: Ω ∪ Ξ ∪ Σ ∪ Λ. The set
Ω, the signature of the language, is a non-empty, countable set of constant and
function symbols. Each symbol in the signature has a designated syntactic type
from σ. The set Ξ = {xi , di , pi }i∈N is a countably infinite set of variables, where
xi ∈ σI , di ∈ σD , and pi ∈ σP , for i ∈ N. Σ is a set of syncategorematic symbols,
including the comma, various matching pairs of brackets and parentheses, and
the symbol ∀. The set Λ is the set of logical symbols of LogA G, defined as the
union of the following sets.

 1. {¬} ⊆ σP −→ σP
 2. {∧, ∨} ⊆ σP −→ σP −→ σP
         .
 3. {≺, =} ⊆ σD −→ σD −→ σP
 4. {G} ⊆ σP −→ σD −→ σP

A LogA G language with signature Ω is denoted by LΩ . It is the smallest set of
terms formed according to the following rules; as usual, terms involving ⇒, ⇔,
and ∃ may be introduced as abbreviations in the standard way.

 – Ξ ⊂ LΩ
 – c ∈ LΩ , where c ∈ Ω is a constant symbol.
 – f (t1 , . . . , tn ) ∈ LΩ , where f ∈ Ω is of sort τ1 −→ . . . −→ τn −→ τ (n > 0)
   and ti is of sort τi .
                                                                   .
 – {¬t1 , (t1 ∧t2 ), (t1 ∨t2 ), ∀x(t1 ), G(t1 , t2 ), t3 ≺ t4 , t3 = t4 } ⊂ LΩ ; where t1 , t2 ∈
   σP ; t3 , t4 ∈ σD ; and x ∈ Ξ.

   The basic ingredient of the LogA G semantic apparatus is the notion of a
LogA G structure.
Definition 1. A LogA G structure is a quintuple S = �D, A, g, <, e�, where

 – D, the domain of discourse, is a set with two disjoint, non-empty, countable
   subsets P and G.
 – A = �P, +, ·, −, ⊥, �� is a complete (closed under arbitrary products and
   sums), non-degenerate (� �= ⊥) Boolean algebra [18].
 – g : P × G −→ P.
 – <: G ×G −→ P satisfies the following properties for every distinct g1 , g2 , g3 ∈
   G:
   O1. g1 < g2 = −(g2 < g1 ).
   O2. [(g1 < g2 ) · (g2 < g3 )] + g1 < g3 = g1 < g3 .


                                             31
 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning




         1 < g1 = ⊥. �
    O3. g�
    O4.     g1 < g =   g < g1 = �.
          g∈G              g∈G
 – e : G × G −→ {⊥, �}, where, for every g1 , g2 ∈ G, e(g1 , g2 ) = �, if g1 = g2 ,
   and e(g1 , g2 ) = ⊥, otherwise.

Intuitively, the domain D is partitioned into three cells: (i) a set of proposi-
tions P, structured as a Boolean algebra; (ii) a set of grades G, and (iii) a set
of individuals P ∪ G. These stand in correspondence to the syntactic sorts of
LogA G. In what follows, we let DσP = P, DσD = G, and DσI = P ∪ G. g is a
function which maps a proposition p and a grade g to the proposition that p is a
proposition of grade g. By refraining from imposing any constraints on g (other
than functionality), we are admitting virtually any intuitive interpretation of
grading. Properties O1–O4 require propositions in the range of < to give rise
to an irreflexive linear order on G which is serial in both directions. Similarly,
the rigid definition of e gives rise to the identity relation on G.

Definition 2. A valuation V of a LogA G language LΩ is a triple �S, VΩ , VΞ �,
where

 – S = �D, A, g, <, e� is a LogA G structure;
 – VΩ is a function that assigns to each constant of sort τ in Ω an element of
   Dτ , and to each function symbol f ∈ Ω of sort τ1 −→ . . . −→ τn −→ τ an
                                    n
    n-adic function VΩ (f ) :     × D −→ D ; and
                                   i=1
                                         τi         τ

 – VΞ : Ξ −→ D is a variable assignment, where, for every i ∈ N, vΞ (pi ) ∈ DσP ,
   vΞ (di ) ∈ DσD , and vΞ (xi ) ∈ DσI .

In what follows, for a valuation V = �S, VΩ , VΞ � with x ∈ Ξ of sort τ and a ∈ Dτ ,
V[a/x] = �S, VΩ , VΞ [a/x]�, where VΞ [a/x](x) = a, and VΞ [a/x](y) = VΞ (y) for
every y �= x.

Definition 3. Let LΩ be a LogA G language and let V be a valuation of LΩ . An
interpretation of the terms of LΩ is given by a function [[·]]V :

 – [[x]]V = VΞ (x), for x ∈ Ξ
 – [[c]]V = VΩ (c), for a constant c ∈ Ω
 – [[f (t1 , . . . , tn )]]V = VΩ (f )([[t1 ]]V , . . . , [[tn ]]V ), for an n-adic (n ≥ 1) function
   symbol f ∈ Ω
 – [[(t1 ∧ t2 )]]V = [[t1 ]]V · [[t2 ]]V
 – [[(t1 ∨ t2 )]]V = [[t1 ]]V + [[t2 ]]V
 – [[¬t]]V = −[[t]]   �
                         V

 – [[∀x(t)]] = a∈Dτ [[t]]V[a/x]
               V

 – [[G(t1 , t2 )]]V = g([[t1 ]]V , [[t2 ]]V )
 – [[t1 ≺ t2 ]]V = [[t1 ]]V < [[t2 ]]V
         .
 – [[t1 = t2 ]]V = e([[t1 ]]V , [[t2 ]]V )


                                               32
 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning




In LogA G, logical consequence is defined in pure algebraic terms without allud-
ing to the notion of truth. This is achieved using the natural partial order ≤
associated with A [18], where, for p1 , p2 ∈ P, p1 ≤ p2 =def p1 · p2 = p1 .

Definition 4. Let LΩ be a LogA G language. For every φ ∈ σP and Γ ⊆ σP ,
φ�is a logical consequence of Γ, denoted Γ |= φ, if, for every LΩ valuation V,
   [[γ]]V ≤ [[φ]]V .
γ∈Γ

In [10], it is shown that |= has the distinctive properties of classical Tarskian
logical consequence and that it satisfies a counterpart of the deduction theorem.


3     Graded Filters

In what follows, for every p ∈ P and g ∈ G, we say that g(p, g) grades p and that
g(p, g) is a grading proposition. Moreover, if g(p, g) ∈ Q ⊆ P, we say that p is
graded in Q. We define the set of p graders in Q to be the set G(p, Q) = {q|q ∈ Q
and q grades p}. Throughout, we assume a LogA G structure S = �D, A, g, <, e�.
   According to Definition 4, the set of logical consequences of a set Γ of σP -
terms corresponds to the filter F ([[Γ]]) generated by the set [[Γ ]] of denotations
of members of Γ [18]. In order to accommodate a richer, non-classical set of
consequences which includes some acceptable propositions graded in [[Γ]], we
need a more liberal notion of graded filters.


3.1   Embedding and Chains

In order to develop the notion of a graded filter, we need to sharpen our intuitions
about the nesting structure of propositions graded in a given set.

Definition 5. A proposition p ∈ P is embedded in Q ⊆ P if (i) p ∈ Q or (ii) for
some g ∈ G, g(p, g) is embedded in Q. Henceforth, let E(Q) = {p|p is embedded
in Q}.

Definition 6. For Q ⊆ P, let δQ : E(Q) −→ N, where

1. if p ∈ Q, then δQ (p) = 0; and
2. if p ∈
        / Q, then δQ (p) = e + 1, where e = minq∈G(p,E(Q)) {δQ (q)}.

δQ (p) is referred to as the degree of embedding of p in Q.

In the sequel, we let E n (Q) = {p ∈ E(Q) | δQ (p) ≤ n}, for every n ∈ N.

Definition 7. A grading chain of p ∈ P is a finite sequence �q0 , q1 , . . . , qn � of
grading propositions such that qn grades p and qi grades qi+1 , for 0 ≤ i < n.
�q0 , q1 , . . . , qn � is a grading chain if it is a grading chain of some p ∈ P.


                                        33
 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning




    A grading chain C2 = �q0 , q1 , . . . , qn � extends a grading chain C1 if C1 is a
grading chain of q0 . The grading chain C1 � C2 is said to be an extension of C1
(where � denotes sequence concatenation).
    We say that C is a grading chain in Q, if every proposition in C is in Q. Given
that we impose no special restrictions on the function g and the proposition
algebra, grading chains in a set Q may, in general, be quite counter-intuitive.
Hence, we need to introduce some especially interesting sets of propositions.

Definition 8. Let Q ⊆ P.

1. A grading chain is well-founded if all its extensions are well-founded. Q is
   well-founded if every grading chain in Q is well-founded.
2. A grading chain �q0 , q1 , . . . , qn � is acyclic if, for every 0 ≤ i, j ≤ n, qi = qj
   only if i = j. Q is acyclic if every grading chain in Q is acyclic.
3. Q is depth-bounded if there is some d ∈ N such that every grading chain in
   Q has at most d distinct grading propositions.
4. Q is fan-out-bounded if there is some fout ∈ N such that every grading
   proposition in Q grades at most fout propositions.
5. Q is fan-in bounded if there is some fin ∈ N where |G(p, Q)| ≤ fin , for every
   p ∈ Q.
6. Q is non-explosive if for every R ⊆ Q, if R has finitely-many grading propo-
   sitions, then so does F (R).

   Given the above notions, if p ∈ E(Q), then a grading chain C of p in Q is a
longest grading chain of p in Q if

 1. C is acyclic; and
 2. if C extends a grading chain C � , then C � � C is not acyclic.

Proposition 1. 5 Let Q ⊆ P.

1. If P is depth-bounded, then it is not acyclic.
2. If Q is depth-bounded and acyclic, then Q is well-founded.
3. If E(Q) is depth-bounded, then there is some n ∈ N such that δQ (p) ≤ n, for
   every p ∈ E(Q).
4. If P is fan-out-bounded and Q is non-explosive with finitely-many grading
   propositions, then E n (F (Q)) has finitely-many grading propositions, for ev-
   ery n ∈ N. Further, if E(F (Q)) is depth-bounded, then it has finitely-many
   grading propositions.
5. If Q is depth-bounded, then every graded p ∈ Q has a longest grading chain
   in Q. Further, if Q is fan-in-bounded, then every graded p ∈ Q has finitely-
   many longest grading chains in Q.

    Note that, for the existence of longest grading chains, it suffices to have a
single, bounded grading chain of p.
5
    Proofs of observations and propositions are omitted for space limitations. A longer
    version of the paper includes all the proofs.


                                          34
 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning




3.2    Telescoping
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 embedded therein. For this, we need to define (i) the process of
telescoping, which is a step-wise process that considers propositions at increasing
degrees of embedding, and (ii) a criterion for accepting embedded propositions
which, as should be expected, depends on the grades of said propositions.

Definition 9. Let S be a LogA G structure with a depth- and fan-out-bounded
P. A telescoping structure for S is a quadruple T = �T , O, ⊗, ⊕�, where
 – T ⊆ P;
 – O is�an ultrafilter of the subalgebra induced by Range(<) (see [18]);
             ∞
 – ⊗ : �i=1 G i −→ G; and
              ∞
 – ⊕ : i=1 G i −→ G is commutative in the sense that ⊕(t) = ⊕(π(t)), where
    π(t) is any permutation of the tuple t.
                               �∞
Definition 10. Let ⊗ : i=1 G i −→ G, and let C = �q0 , q1 , . . . , qn � be a grading
chain of p ∈ P. The fused ⊗-grade of p with respect to C is the grade f⊗ (p, C) =
⊗(�g0 , . . . , gn �), where qi = g(qi+1 , gi ), for 0 ≤ i < n, and qn = g(p, gn ).

Definition 11. Let T be a telescoping structure. If p ∈ Q, for a fan-in-bounded
Q ⊂ P, then the T-fused grade of p in Q is defined as
                                    �               n
                        fT (p, Q) =    �f⊗ (p, Ck )�k=1
             n
where �Ck �k=1 is a permutation of the set of longest grading chains of p in Q.6

    Recasting the familiar notion of a kernel of a belief base [19] into the context
of LogA G structures, we say that a kernel of Q ⊆ P is a subset-minimal X ⊆ Q
                                              �




such that F (X ) is improper (�= P). Let Q ⊥ be the set of Q kernels.

Definition 12. For a telescoping structure T = �T , O, ⊗, ⊕� and a fan-in-
bounded Q ⊆ P, if X ⊆ Q, then p ∈ X survives X in T if
1. p ∈ T ; or
2. G(p, Q) �= ∅ and there is some q ∈ X , with G(q, Q) �= ∅, such that
   (fT (q, Q) < fT (p, Q)) ∈ O.
The set of kernel survivors of Q in T is the set
                                         �




         κ(Q, T) = {p ∈ Q| if p ∈ X ∈ Q ⊥ then p survives X given T}.

Observation 1 If F (T ) is proper, then F (κ(Q, T)) is proper.

Definition 13. Let Q, T ⊆ P. We say that p is supported in Q given T if
6
    Note that T-fusion is well-defined given the fan-in-boundedness of Q and the final
    clause of Proposition 1.


                                         35
Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning




1. p ∈ F (T ); or
2. there is a grading chain �q0 , q1 , . . . , qn � of p in Q with q0 ∈ F (R) where every
   member of R is supported in Q.

The set of propositions supported in Q given T is denoted by ς(Q, T ).

   The following simple observation will prove useful later.

Observation 2 ς(Q, T ) = F (T ) ∪ G, for some set G of propositions graded in
Q.

Definition 14. Let T be a telescoping structure for S. If Q ⊂ P such that
E 1 (F (Q)) is fan-in-bounded, then the T-induced telescoping of Q is given by
τT (Q) = ς(κ(E 1 (F (Q)), T), T )

Proposition 2. For a telescoping structure T, τT is a function from fan-in-
bounded sets in 2P to sets in 2P .

    It may be shown that if Q is non-explosive with finitely-many grading propo-
sitions, then τT (Q) is defined, for every telescoping structure T. On the other
hand, if F (Q) is improper, then τT (Q) is undefined. In what follows, provided
that the right-hand side is defined, let
                                  �
                                    Q              if n = 0
                        τTn (Q) =
                                    τT (τTn−1 (Q)) otherwise

Definition 15. Let T be a telescoping structure. We refer to F (τTn (T )) as a
degree n(∈ N) graded filter of T, denoted Fn (T).

   Unfortunately, even with a finite and fan-in-bounded T , the existence of a
fixed-point for graded filters is not secured. (Check Example 3 in Section 4.) We
can only prove a weaker property for a special class of telescoping structures.

Theorem 1. Let T be a telescoping structure where T is finite. There is some
n ∈ N such that if Fi (T) is defined and Fi (T) ∩ Range(g) = τ i (T) ∩ Range(g)
for every i ≤ n, then for every j ∈ N, there is some k ≤ n such that Fn+j (T) =
Fk (T).

   A fixed-point is guaranteed if, under the same conditions in Theorem 1, we
happen to stumble upon a maximal graded filter in the following sense.
Corollary 1. If, in Theorem 1, Fn (T) = F (E(T )) for some n < 2|E(T )| + 1,
then Fn+k (T) = Fn (T), for every k ∈ N.
Telescoping can never generate an inconsistent theory if the top theory is con-
sistent.
Theorem 2. If T is a telescoping structure where F (T ) is proper, then, if de-
fined, Fn (T) is proper, for every n ∈ N.


                                          36
 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning




4     LogA G Theories

Given the definition of a LogA G structure, we impose some reasonable con-
straints on which sets of LogA G terms qualify as LogA G theories. A LogA G
theory is a finite set T ⊆ σP such that E ∪ O ⊆ T, where

 – E is the smallest set containing the following terms:
              .
    1. ∀d[d = d]
                      .          .
    2. ∀d1 , d2 [d1 = d2 ⇒ d2 = d1 ]
                           .        .             .
    3. ∀d1 , d2 , d3 [(d1 = d2 ∧ d2 = d3 ) ⇒ d1 = d3 ]
                         .
    4. ∀p, d1 , d2 [(d1 = d2 ∧ G(p, d1 )) ⇒ G(p, d2 )]
   and
 – O is the smallest set containing the following terms:
                                                .
    1. ∀d1 , d2 [¬(d1 ≺ d2 ) ⇔ (d2 ≺ d1 ∨ d2 = d1 )]
    2. ∀d1 , d2 , d3 [(d1 ≺ d2 ∧ d2 ≺ d3 ) ⇒ d1 ≺ d3 ]

Given a LogA G theory T and a valuation V = �S, VΩ , VΞ �, let V(T) = {[[φ]]V | φ ∈
T}). Further, for a LogA G structure S, an S grading canon is a triple C =
�⊗, ⊕, n� where n ∈ N and ⊗ and ⊕ are as indicated in Definition 9.
Definition 16. Let T be a LogA G theory and V = �S, VΩ , VΞ � a valuation,
where S has a set P which is depth- and fan-out-bounded, for some LogA G
language LΩ . For every φ ∈ σP and S grading canon C = �⊗, ⊕, n�, φ is a
                                                       C
graded consequence of T with respect to C, denoted T |� φ, if Fn (T) is defined
         V    n
and [[φ]] ∈ F (T), for every telescoping structure T = �V(T), O, ⊗, ⊕� for S,
where O extends F (V(T) ∩ Range(<)).7
                              C
It should be clear that |� , where C = �⊗, ⊕, n�, reduces to |= if n = 0 or if
F (E(V(T))) does not contain any grading propositions. Further, for n > 0, no
φ is a graded consequence of T with respect to C if F (V(T)) is not proper. In
                                 C
what follows, let TC = {φ | T |� φ}. When we are considering a set of canons
which only differ in the value of n, we write Tn instead of TC .
                 C
    Unlike |=, |� is, in general, non-monotonic. (In the sequel, we interpret
grades by the rational numbers, with their natural order remaining implicit.)

Example 1 (Opus and Tweety). We can represent the case of Opus and Tweety
from Section 1 using a LogA G theory TOT1 = E ∪ O ∪ ΓOT1 , where ΓOT1 is made
up of the following terms.
 1. ∀x[Bird(x) ⇒ G(F lies(x), 5)]
 2. ∀x[P enguin(x) ⇒ G(¬F lies(x), 10)]
 3. ∀x[P enguin(x) ⇒ Bird(x)]
 4. P enguin(Opus)
 5. Bird(T weety)

Figure 1 displays the relevant graded consequences of TOT1 with respect to
a series of canons, with 0 ≤ n ≤ 2. Upon telescoping to n = 1, we believe
7
    An ultrafilter U extends a filter F , if F ⊆ U .


                                           37
 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning




                                n=0        0.1. TOT1
                                           0.2. Bird(Opus)
                                           0.3. G(F lies(T weety), 5)
                                           0.4. G(F lies(Opus), 5)
                                           0.5. G(¬F lies(Opus), 10)

                                n=1        1.1. T0OT1
                                           1.2. F lies(T weety)
                                           1.3. ¬F lies(Opus)




       Fig. 1. Graded consequences of the LogA G theory TOT1 from Example 1


that Tweety flies and Opus does not fly. The embedded proposition that Opus
flies does not survive telescoping since we trust that Opus does not fly, being a
penguin, more than we trust that it flies, being a bird. T1OT1 is a fixed point. Now,
consider the theory TOT2 = E ∪ O ∪ ΓOT2 , where ΓOT2 is similar to ΓOT1 , but
with propositions (1) and (2) replaced by “G(∀x[Bird(x) ⇒ F lies(x), 5)” and
“G(∀x[P enguin(x) ⇒ ¬F lies(x), 10)”, respectively. Thus, we trade the “de re”
representation of TOT1 for the “de dicto” representation in TOT2 . This change
results in a change in the fixed point that we reach. In T1OT2 , as in T1OT1 , we
end up believing that Opus does not fly. Unlike T1OT1 however, we give up our
belief in the proposition that birds fly and, hence, cannot conclude that Tweety
flies.                                                                            �
   Example 1 showcases the use of graded propositions in default reasoning.
The following example illustrates the utility of nested grading.
Example 2 (Superman). Recalling the case of Superman from Section 1, we can
describe the situation using LogA G in at least two theories. Consider the theory
TSM1 = E ∪ O ∪ ΓSM1 , where ΓSM1 is made up of the following terms.
 1. ∀p[Source(p, LL) ⇒ G(p, 11)]
 2. ∀p[Source(p, DP ) ⇒ G(p, 4)]
 3. ∀p[P erceive(p) ⇒ G(p, 15)]
 4. ∀l, t[G(At(KC, l, t) ⇔ At(SM, l, t), 10.5)]
 5. ∀l1 , l2 , t, x[(Disjoint(l1 , l2 ) ∧ At(x, l1 , t)) ⇒ ¬At(x, l2 , t)]
 6. P erceive(Source(Source(At(SM, DT, 12 : 00), LL), DP ))
 7. P erceive(At(KC, Of f ice, 12 : 00))
 8. Disjoint(Of f ice, DT )

Figure 2 displays relevant members of TnSM1 with respect to a series of canons,
with ⊗ = mean and ⊕ = max, and with 0 ≤ n ≤ 3. Note that, for 1 ≤ n ≤ 2, we
trust the proposition that Superman was at the office at noon (1.6). However,
upon telescoping to n = 3, we lose our trust in said proposition, since we trust
what Lois Lane says more than we trust our belief in the identity of Superman
and Clark Kent (1.3).
   Alternatively, consider the theory TSM2 = E ∪ O ∪ ΓSM2 , where ΓSM2 is made
up of the following terms.
 1. G(G(G(At(SM, DT, 12 : 00), 11), 4), 15)


                                                 38
Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning




          n=0         0.1. TSM1
                      0.2. G(Source(Source(At(SM, M DT, 12 : 00), LL), DP ), 15)
                      0.3. G(At(KC, Of f ice, 12 : 00) ⇔ At(SM, Of f ice, 12 : 00), 10.5)
                      0.4. G(At(KC, Of f ice, 12 : 00), 15)

          n=1         1.1. T0SM1
                      1.2. Source(Source(At(SM, DT, 12 : 00), LL), DP )
                      1.3. At(KC, Of f ice, 12 : 00) ⇔ At(SM, Of f ice, 12 : 00)
                      1.4. At(KC, Of f ice, 12 : 00)
                      1.5. G(Source(At(SM, DT, 12 : 00), LL), 4)
                      1.6. At(SM, Of f ice, 12 : 00)

          n=2         2.1. T1SM1
                      2.2. Source(At(SM, DT, 12 : 00), LL)
                      2.3. G(At(SM, DT, 12 : 00), 11)

          n=3         3.1. Everything at n = 2 except 1.3, 1.6, and anything they support
                      3.2. At(SM, DT, 12 : 00)




       Fig. 2. Graded consequences of the LogA G theory TSM1 from Example 2


 2. G(At(KC, Of f ice, 12 : 00), 15)
 3. ∀l, t[G(At(KC, l, t) ⇔ At(SM, l, t), 10.5)]
 4. ∀l1 , l2 , t, x[(Disjoint(l1 , l2 ) ∧ At(x, l1 , t)) ⇒ ¬At(x, l2 , t)]
 5. Disjoint(Of f ice, DT )
Figure 3 displays the different consequences with respect to the same canons
employed with TSM1 . In this case, we get a different fixed point; we end up (at
n = 2) believing that Superman was at the office at noon, contrary to what has
been reported by Lois Lane in the Daily Planet. The reason is that, due to the
nesting of grading propositions, the fused grade of “AT (SM, DT, 12 : 00)” is
now only 10 (which is less than 10.5, the grade of (1.4)), being pulled down by
the low grade attributed to the Daily Planet.                                 �



           n=0         0.1. TSM2
                       0.2. G(At(KC, Of f ice, 12 : 00) ⇔ At(SM, Of f ice, 12 : 00), 10.5)

           n=1         1.1. T0SM2
                       1.2. G(G(At(SM, DT, 12 : 00), 11), 4)
                       1.3. At(KC, Of f ice, 12 : 00)
                       1.4. At(KC, Of f ice, 12 : 00) ⇔ At(SM, Of f ice, 12 : 00)
                       1.5. At(SM, Of f ice, 12 : 00)
                       1.6. ¬At(SM, DT, 12 : 00)

           n=2         2.1. T1SM2
                       2.2. G(At(SM, DT, 12 : 00), 11)

           n=3         3.1. T2SM2




       Fig. 3. Graded consequences of the LogA G theory TSM2 from Example 2




                                                  39
 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning




                               n=0       0.1. TL

                               n=1       1.1. T0L
                                         1.2. φ
                                         1.3. G(¬φ, 5)

                               n=2       2.1. T0L




       Fig. 4. Graded consequences of the LogA G theory TL from Example 3


Finally, we revisit the pathological case of the liar.
Example 3 (The Liar). Consider the theory TL = E∪O∪{G(φ, 5), φ ⇔ G(¬φ, 5)}.
This is the closest we can get, within LogA G, to the case of the liar from Sec-
tion 1; given the non-degeneracy of the Boolean algebra, we can never have the
situation where [[φ]]V = −[[φ]]V (cf. [10]). Figure 4 shows what happens as n
increases, given any grading canon. In such a problematic situation, we never
reach a fixed point, indefinitely iterating through T0L and T1L . But this is just
as well, for it fairly captures the dilemma one is in when encountering liar-like
sentences. While this is similar in spirit, but not identical, to the treatment of
the liar paradox within the revision theory of truth (RTT) [20], RTT tackles the
liar paradox head-on, not via the more tame version expressible in LogA G. (Also
see [21] for a treatment of the liar paradox within a fuzzy logical framework.)
                                                                                �


5   Conclusion
Notwithstanding the abundance of weighted logics in the literature, it is our
conviction that LogA G provides an interesting alternative. While it has a non-
classical semantics, LogA G is arguably intuitive, expressive, and quite similar in
syntax to first-order logic. We hope to have demonstrated the utility of LogA G
in default reasoning, reasoning with information reported through a chain of
sources, and even reasoning with paradoxical propositions. A careful examination
of how LogA G relates to other graded logics and non-monotonic formalisms is
called for. On a first pass, we believe that LogA G subsumes possibilistic logic
[2], circumscription [9], and default theories with at most one justification per
default (which includes normal defaults) [7]. We are currently working on the
implementation of a proof theory for LogA G based on a reason maintenance
system (cf. [22]). The primary objective we have in mind is prioritized belief
revision based on graded propositions.


References
 1. Dubois, D., Godo, L., Prade, H.: Weighted logics for artificial intelligence—an
    introductory discussion. International Journal of Approximate Reasoning 55(9)
    (2014) 1819–1829


                                        40
 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning




 2. Dubois, D., Prade, H.: Possibilistic logic: A retrospective and prospective view.
    Fuzzy Sets and Systems 144 (2004) 3–23
 3. Halpern, J.: Reasoning About Uncertainty. MIT Press, Cambridge, MA (2005)
 4. Hájek, P., Cintula, P.: On theories and models in fuzzy predicate logic. The Journal
    of Symbolic Logic 71(3) (2006) 863–880
 5. Smith, N.: Vagueness and Degrees of Truth. Oxford university Press, Oxford
    (2008)
 6. Alchourron, C.E., Gärdenfors, P., Makinson, D.: On the logic of theory change:
    Partial meet contraction and revision functions. The Journal of Symbolic Logic
    50(2) (1985) 510–530
 7. Reiter, R.: A logic for default reasoning. Artificial Intelligence 13 (1980) 81–132
 8. Kripke, S.: Outline of a theory of truth. Journal of Philosophy 72(19) (1975)
    690–716
 9. McCarthy, J.: Circumscription— A form of non-monotonic reasoning. Artificial
    Intelligence 13 (1980) 27–39
10. Ismail, H.O.: LogA B: A first-order, non-paradoxical, algebraic logic of belief. Logic
    Journal of the IGPL 20(5) (2012) 774–795
11. Ismail, H.O.: Stability in a commonsense ontology of states. In: Proceedings of
    the Eleventh International Symposium on Logical Formalization of Commonsense
    Reasoning (COMMONSENSE 2013), Agya Napa, Cyprus (2013)
12. Church, A.: On carnap’s analysis of statements of assertion and belief. Analysis
    10(5) (1950) 97–99
13. Bealer, G.: Theories of properties, relations, and propositions. The Journal of
    Philosophy 76(11) (1979) 634–648
14. Parsons, T.: On denoting propositions and facts. Philosophical Perspectives 7
    (1993) 441–460
15. Shapiro, S.C.: Belief spaces as sets of propositions. Journal of Experimental and
    Theoretical Artificial Intelligence 5 (1993) 225–235
16. Demolombe, R.: Graded trust. In: Proceedings of the Workshop on Trust in Agent
    Societies (TRUST’09), Budapest, Hungary (2009)
17. Milošić, M., Obnjanović, Z.: A first-order conditional probability logic. Logic
    Journal of the IGPL 20(1) (2012) 235–253
18. Burris, S., Sankappanavar, H.P.: A Course in Universal Algebra. Springer-Verlag
    (1982)
19. Hansson, S.O.: Kernel contraction. Journal of Symbolic Logic 59(3) (1994) 845–
    859
20. Gupta, A., Belnap, N.: The Revision Theory of Truth. MIT Press, Cambridge,
    MA (1993)
21. Hájek, P., Paris, J., Shephedson, J.: The liar paradox and fuzzy logic. The Journal
    of Symbolic Logic 65(1) (2000) 339–346
22. Ismail, H.O.: A reason maintenance perspective on relevant Ramsey conditionals.
    Logic Journal of the IGPL 18(4) (2010) 508–529


A     Proofs

A.1    Proof of Theorem 1

To prove Theorem 1, we need the following result.


                                          41
 Proceedings of the KI 2015 Workshop on Formal and Cognitive Reasoning




Lemma 1. If T is a telescoping structure then, for every n ∈ N, if Fi (T) is
defined and Fi (T) ∩ Range(g) = τ i (T) ∩ Range(g) for every i ≤ n, then Fn (T) =
F (Q), for some Q ⊆ E(T ) and Fn (T) ∩ Range(g) ⊆ E n (T ).

Proof. We prove the lemma by induction on n. For n = 0, F0 (T ) = F (T ), where
T ⊆ E(T ). Further, F0 (T ) ∩ Range(g) = τ 0 (T) ∩ Range((g)) = T ∩ Range(g) ⊆
E 0 (T ). Now assume that the statement holds for some k ∈ N. By the induction
hypothesis, Fk (T) ∩ Range(g) ⊆ E k (T ). Therefore, all propositions graded in
E 1 (Fk (T)) are in E k+1 (T ). Moreover, E 1 (Fk (T)) ∩ Range(g) ⊆ E k+1 (T ). By
Observation 2, τTk+1 (T ) = τT (Fk (T)) = ς(κ(E 1 (Fk (T))), T), T ) = F (T ) ∪ G,
where G is a set of propositions graded in κ(E 1 (Fk (T))). By Definition 12,
κ(E 1 (Fk (T))) ⊆ E 1 (Fk (T)). Hence, G ⊆ E k+1 (T ). Thus, Fk+1 (T) = F ([F (T ) ∪
G]) = F (T ∪ G), where T ∪ G ⊆ E(T ). Moreover, Fk+1 (T) ∩ Range(g) =
τ k+1 (T) ∩ Range(g) ⊆ E k+1 (T ).                                                 �

    We now proceed to proving the theorem. By Definition 9 and Clause 4 of
Proposition 1, E(T ) has finitely-many grading propositions. In fact, since T is
finite, then E(T ) is finite. Let b = |E(T )|. Now, taking n = 2b + 1, suppose that,
for every i ≤ 2b + 1, Fi (T) is defined and Fi (T) ∩ Range(g) = τ i (T) ∩ Range(g).
By Lemma 1, Fi (T) = F (Qi ), for some Qi ⊆ E(T ). Since there are only 2b
subsets of E(T ), then Fn (T) = Fj (T), for some j ≤ 2b . Further, by Proposition
2, for every j ∈ N, there is some k ≤ n such that Fn+j (T) = Fk (T).            �


A.2    Proof of Corollary 1
We prove the case of k = 1 and the result follows by the same argument for all
k ∈ N.
Fn+1 (T)
= F (ς(κ(E 1 (Fn (T)), T)), T ) (Definitions 14 and 15)
= F (ς(κ(E 1 (F (E(T ))))))
= F (ς(κ(F (E(T )))))           (Definition of E and the assumption of Theorem 1)
= F (ς(F (E(T ))))              (Since F (E(T )) is proper given that Fn+1 (T)
                                 is defined)
= F (F (E(T )))                 (Since every p ∈ F (E(T )) is supported given that
                                F (E(T )) = Fn (T) and Definitions 14 and 15)
= F (E(T ))

                                                                                  �


A.3    Proof of Theorem 2

For n = 0, the statement is trivial, since F0 (T) = F (T ). Otherwise, the statement
follows directly from Observation 1 since, by Definition 15, Fk+1 (T) = F (K),
for some K ⊆ κ(E 1 (Fk (T)), T).                                                  �




                                        42