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