Possibilistic Safe Beliefs Oscar Estrada1 , José Arrazola1 , and Mauricio Osorio2 1 Benemérita Universidad Autónoma de Puebla oestrada2005@gmail.com, arrazola@fcfm.buap.mx . 2 Universidad de las Américas - Puebla osoriomauri@gmail.com Abstract. In the paper by Oscar Estrada et al. it is introduced the concept of “Possibilistic Intuitionistic Logic (PIL)”; In that paper, the authors present results analogous to those of the well-known intuition- istic logic, such as a Deduction Theorem, a Generalized version of the Deduction Theorem, a Cut Rule, a weak version of a Refutation Theo- rem, a Substitution Theorem and Glivenko’s Theorem. The concept of Safe Beliefs was introduced in the paper “Safe Beliefs for Propositional Theories” by Osorio et al. as an extension of the concept of Answer Set. In this paper, we present the analogous concept to Safe Beliefs: Possibilistic Safe Beliefs Candidate. Keywords: Possibilistic Logic, Intuitionistic Logic, Answer Set, Safe Beliefs. 1 Introduction Uncertainty is an attribute of information. The pioneering work of Claude Shan- non [18] on Information Theory led to the universal acceptance that information is statistical in nature; As a consequence, dealing with uncertainty was confined to the Theory of Probability. Dubois et al. presented Possibilistic Logic on [3]; Possibilistic Logic enables to handle information with uncertainty. Their logic is based on the Theory of Possibility of Zadeh [20]; On the paper by Dubois et al. [3], it is included an axiomatization for Possibilistic Logic and an extended resolution-based method which is viable to be implemented on a computer. According to Pascal Nicolas et al. [9], Possibilistic Logic provides a sound and complete machinery for handling qualitative uncertainty with respect to a semantics expressed by means of possibility distributions which rank order the possible interpretations. Pascal mentions that in possibilistic logic it is dealt with uncertainty by means of classical two-valued (true or false) interpretations that can be more or less certain, more or less possible. Possibilistic Logic is not concerned to deal with a vagueness representation in a multi-valued framework but instead, it stays in the framework of classical logic to which it adds a way to graduate the confidence one has in each proposed information [9]. 47 On the other hand, Intuitionistic Logic has become important to the area of computer science since the publication of a paper by David Pearce [17], on which it is established a link between Intuitionistic Logic (and furthermore, all the class of intermediate logics) and Answer Set Programming (ASP) [6, 8]. Considering the importance of the ASP formalism, in combination with its usefulness within the context of intermediate logics, and the need for a better way of handling uncertain information, it was proposed in [10] the Possibilistic Intuitionist Logic (PIL) formalism. It was presented only propositional calculus. On this this paper, following the same flow of ideas, we present the concept of Possibilistic Safe Belief, which tries to establish a link between Safe Beliefs [16] and Possibilistic Intuitionistic Logic [10]. The concept of Safe Belief as presented in [16] is a generalization of the concept of Answer Set. With this in mind, one can argue in favor of developing Possibilistic Safe Beliefs in order to broaden the scope of applications; Hence, a Possibilistic Safe Belief would allow us to an- alyze situations involving uncertainty, for example, in decision making problems. First, in Section 2, we present some background on Possibilistic and Intuition- istic Logic, and we present some theorems from [10] and show some examples. In Section 3, we introduce our main contribution for this paper, the concept of Pos- sibilistic Safe Belief and a Lemma establishing a resemblance with some result of Safe Belief as presented on [16]. Finally, in Section 4 we give the conclusions and sketch some ideas for future work. 2 Background We present the necessary background for this paper. The propositional calculus is built as in the well-known book by Mendelson [7]. 2.1 Intuitionistic Logic Definition 1. Positive Logic is defined by the following set of axioms: Pos 1: ϕ → (ψ → ϕ) Pos 2: (ϕ → (ψ → σ)) → ((ϕ → ψ) → (ϕ → σ)) Pos 3: ϕ ∧ ψ → ϕ Pos 4: ϕ ∧ ψ → ψ Pos 5: ϕ → (ψ → (ϕ ∧ ψ)) Pos 6: ϕ → (ϕ ∨ ψ) Pos 7: ψ → (ϕ ∨ ψ) Pos 8: (ϕ → σ) → ((ψ → σ) → (ϕ ∨ ψ → σ)). Definition 2. Intuitionistic Logic I is defined as positive logic plus the fol- lowing two axioms: Int1: (ϕ → ψ) → [(ϕ → ¬ψ) → ¬ϕ] Int2: ¬ϕ → (ϕ → ψ). 48 Recall that the following are valid meta-theorems of Intuitionism: 1. If C ϕ then, I ¬¬ϕ 2. If ϕ is a tautology (in the classical sense) then, I ¬¬ϕ 3. If C ¬ϕ then I ¬ϕ 4. If ¬ϕ is a tautology (in the classical sense) then, I ¬¬ϕ 5. If ϕ ∈ ¬, ∧ then, I ϕ if and only if, ϕ is a tautology. Theorem 1 (Deduction Theorem [19] ). If Γ is a set of formulas, ψ and σ are well-formed formulas and Γ, ψ I σ, then Γ I ψ → σ. Lemma 1 ([19]). a) I (ϕ → (ψ ↔ σ)) ∧ (ϕ → (ξ ↔ χ)) → (ϕ → ((ψ → ξ) ↔ (σ → χ))) b) I (ϕ → ψ) → (¬ψ → ¬ϕ) c) I (σ → (ϕ ↔ ψ)) → (σ → (¬ϕ ↔ ¬ψ)). 2.2 Possibilistic Logic The following definitions can be found in [3], to which the reader is referred for further details. A necessity-valued formula is a pair (ϕ α), where ϕ is a classical propositional formula and α ∈ (0, 1]. (ϕ α) expresses that ϕ is certain to the extent α, that is, N (ϕ) ≥ α, where N is a necessity measure which models our state of knowledge. The constant α is known as the valuation of the formula and is represented as val(ϕ). On [3], it is proposed an axiom system for Possibilistic Logic: (A1) (ϕ → (ψ → ϕ) 1) (A2) ((ϕ → (ψ → ξ)) → ((ϕ → ψ) → (ϕ → ξ)) 1) (A3) ((¬ϕ → ¬ψ) → ((¬ϕ → ψ) → ϕ) 1) with the inference rules, (GMP) (ϕ α), (ϕ → ψ β)  (ψ min(α, β)). (S) (ϕ α)  (ϕ β) if α ≥ β. 2.3 Possibilistic Intuitionistic Logic (PIL) We now present the axioms for Possibilistic Intuitionistic Logic (PIL) [10]. Definition 3. Possibilistic Intuitionistic Logic (PIL) is defined by means of the axioms Pos1-Pos8, Int1, Int2 where all of them weighted by 1, that is: PIL-1: (ϕ → (ψ → ϕ) 1), PIL-2: ((ϕ → (ψ → σ)) → ((ϕ → ψ) → (ϕ → σ)) 1), etc. Together with the following rules of inference: (GMP) (ϕ α), (ϕ → ψ β) P IL (ψ min {α, β}) (S) (ϕ α) P IL (ϕ β) if α ≥ β 49 Lemma 2. P IL (ϕ → ϕ 1) A Deduction Theorem is given on [3] for Standard Possibilistic Logic, which is based on Classical Logic. However, the Deduction Theorem we present here is taken from [10], which is given in the context of PIL. Theorem 2 (Deduction Theorem [10]). Let Γ ∪ {ϕ, ψ} be a set of formulas in PIL, and α ∈ (0, 1]. Then we have that Γ ∪ {(ϕ 1)} P IL (ψ α) if and only if Γ P IL (ϕ → ψ α) Furthermore, on [10] it is proven the following result. Theorem 3 (Generalized Deduction Theorem [10]). Let Γ ∪ {ϕ, ψ} be a set of PIL formulas and α, β ∈ (0, 1]. Then we have that 1. Γ ∪ {(ϕ β)} P IL (ψ α) implies Γ P IL (ϕ → ψ α) 2. If, furthermore, β ≥ α, then we have the equivalence: Γ ∪ {(ϕ β)} P IL (ψ α) if and only if Γ P IL (ϕ → ψ α) The proof given for the previous theorem on [10] uses theorems also valid on classical logic, so this theorem also holds in Standard Possibilistic Logic. Besides, observe that as a consequence of the previous result, if we fix β = 1 on Theorem 3(2), then we obtain Theorem 2 as a corollary. We now define the concept of “dependence” on a formula [10]. Let (ϕ α) be a formula in a set Γ of formulas, and assume that we are given a deduction D1 , D2 , . . . , Dn from Γ , together with justification for each step in the deduction. We shall say that Di depends on (ϕ α) in this proof if and only if: 1. Di is (ϕ α) and the justification for Di is that it belongs to Γ , or 2. Di is justified as a direct consequence by GMP or by the Rule (S) of some previous formulas of the sequence, where at least one of these preceding formulas depends on (ϕ α). Theorem 4 (Generalized Deduction Theorem (2nd version) [10]). Let Γ ∪ {ϕ, ψ} be PIL formulas and α, β ∈ (0, 1]. Assume that Γ ∪ {(ϕ β)} P IL (ψ α), and let Γ  = {(φ1 ρ1 ), (φ2 ρ2 ), . . . , (φp ρp )} ⊆ Γ be the set of formulas on which the proof of (ψ α) from Γ ∪ {(ϕ β)} depends on; Then, Γ P IL (ϕ → ψ min {ρ1 , ρ2 , . . . , ρp }) Example 1. Observe that if in the previous result we let Γ = ∅, then the theorem states that if (ϕ β) P IL (ψ α), then P IL (ϕ → ψ min {∅}), that is, P IL (ϕ → ψ 1), which is what one would expect; For instance, is clear that (ϕ 0.3) P IL (ϕ 0.3), so when applying this version of the Generalized Deduction Theorem we obtain P IL (ϕ → ϕ 1) which is what is expected , since Int ϕ → ϕ. As a consequence of Theorem 3 one obtains the following results. 50 Theorem 5 (Weak Refutation Theorem [10] ). Let Γ be a set of PIL formulas, and let ϕ be an intuitionistic propositional formula, and α, β ∈ (0, 1]. If β ≥ α, then we have Γ ∪ {(¬¬ϕ β)} P IL (⊥ α) if and only if Γ P IL (¬ϕ α) Theorem 6 (Cut Rule [10]). Let Γ be a set of PIL formulas, let ϕ, ψ two intuitionistic propositional formulas and α, β ∈ (0, 1]. Then we have that If Γ P IL (ϕ β) and Γ ∪ {(ϕ β)} P IL (ψ α) then Γ P IL (ψ min {α, β}) Consider the set of PIL formulas Γ = {(ϕ → ψ 0.2), (ϕ → ¬ψ 0.7), (σ → ϕ 0.3)}. It it easy to see that Γ P IL (¬ϕ 0.2), and also that Γ ∪ {(¬ϕ 0.2)} P IL (¬ψ 0.2). So, by the previous theorem, we have that Γ P IL (¬ψ 0.2). Now it is presented a version of the Substitution Theorem and a version of Glivenko’s Theorem for Possibilistic Intuitionistic Logic; The proofs of this results can be found in [10]. Theorem 7 (Substitution Theorem [10]). Let ϕ be a classical propositional formula and let ψ be a subformula of ϕ; Let ϕ be the formula which results by substituting some, or none, occurrences of ψ in ϕ by a formula σ. 1. P IL ((ψ ↔ σ) → (ϕ ↔ ϕ ) 1) 2. If Γ P IL (ψ ↔ σ α), then Γ P IL (ϕ ↔ ϕ α) Example 2. Consider the set of PIL formulas Γ = {(¬¬ϕ → ϕ 0.3)}. Since P IL (ϕ → ¬¬ϕ 1), it is easy to show that Γ P IL (ϕ ↔ ¬¬ϕ 0.3). Now, by the previous theorem we have that Γ P IL ((ϕ → ψ) ↔ (¬¬ϕ → ψ) 0.3) Theorem 8 (PIL Glivenko’s Theorem [10]). Let Γ ∪{(ϕ α)} be PIL formu- las, and assume that Γ P os (ϕ α); Let Γ ∗ = {(γ1 α1 ), (γ2 α2 ), . . . , (γn αn )} ⊆ Γ be such that the proof of (ϕ α) from Γ depends on the formulas on Γ ∗ , then we have that Γ P IL (¬¬ϕ min {α1 , α2 , . . . , αn }) Example 3. Consider the set of PIL formulas Γ = {(¬α → ϕ 0.8), (α → ϕ 0.7)}. Since: P os ((¬α → ϕ) → ((α → ϕ) → ((¬α ∨ α) → ϕ))) 1), and P os (¬α ∨ α 1) it is easy to show that Γ P os (ϕ 0.7). Now, by Glivenko’s Theorem we have that Γ P IL (¬¬ϕ 0.7) . 3 Contribution We now present our main results. 51 3.1 Possibilistic Safe Beliefs Here, we define the concepts of classical projection of a possibilistic theory, the Inconsistency Degree and Possibilistic Safe Beliefs Candidate. Definition 4. 1. A possibilistic theory T is any finite set of possibilistic for- mulas. 2. Given a possibilistic theory T , we denote by T ∗ the set of classical formulas obtained from T by ignoring the weights of the formulas, that is, if T = {(ϕi αi ) : i = 1, . . . , n} then, T ∗ = {ϕi : i = 1, . . . , n}. We call T ∗ the classical projection of T . 3. We will denote by LT ∗ the set of classical atoms that appear in the formulas in T , and by LT the set of possibilistic atoms whose classical projection is equal to LT ∗ . Example 4. Given a possibilistic theory: T = {(a 0.9), (b → c 0.7), (a → d 0.8), (d 0.1)} then T ∗ = {a, b → c, a → d, d}, so LT ∗ = {a, b, c, d}. Note that LT = {(a α), (b β), (c γ), (d )} with α, β, γ,  ∈ (0, 1]. Definition 5. Given a possibilistic theory Γ we define the inconsistency degree of Γ by Incon(Γ )= max {α : Γ ` (⊥ α)}, where ⊥ is the logical constant bottom. When Incon(Γ ) = 0 we say that Γ is consistent. Remark: If A is a set of classical atoms, we write A e to denote the complement of A, and define ¬A = {¬a | a ∈ A}, also Γ P IL (ϕ α) denotes Γ is consistent and Γ `P IL (ϕ α). Definition 6. Given a possibilistic theory T and a subset M of LT , we say that M is a possibilistic safe belief candidate if: g∗ 1) ∪ (¬¬M ∗ 1)) = 0, 1. Incons(T ∪ (¬M g∗ 1) ∪ (¬¬M ∗ 1) `P IL M 2. T ∪ (¬M Example 5. Consider the theory T = {(¬a ∨ a 1), (a → b 0.7), (¬b → b 0.3)}, where LT ∗ = {a, b} We have that M = {(a 1), (b 0.3)} is the unique possibilistic safe belief candidate of T . Example 6. Let be the theory T = {(¬a 1), (a 1)}, by axiom PIL-5, Incons(T ∪ g∗ 1) ∪ (¬¬M ∗ 1)) = 1, we have that T does not satifies 2 of previous (¬M definition. Example 7. T = {(a 0.9), (b → c 0.7), (a → d 0.8), (d 0.1)}, so LT ∗ = {a, b, c, d}, then M = {(a 0.9), (d 0.8)} is a possibilistic safe belief candidate of T . Lemma 3. For a given theory T , let M be a subset of LT ∗ , then T ∪ (¬M f 1) P IL (M 1) implies T ∪ (¬M f 1) ≡P IL T ∪ (¬M f 1) ∪ (¬¬M 1). 52 Proof. Since T ∪ (¬M 1) P IL (M 1) then T ∪ (¬M  1) P IL (¬¬M 1) (recall that P IL (ϕ −→ ¬¬ϕ 1)). By Monotony we have that T ∪ (¬M  1) P IL  T ∪ (¬M 1) ∪ (¬¬M 1).  1)∪(¬¬M 1) P IL T ∪(¬M Conversely, we obtain immediately that T ∪(¬M  1). Note that the Lemma 3 has resemblance with some result of Safe Belief as presented on [16]. 4 Conclusion On this brief note we presented Possibilistic Intuitionistic Logic in a purely ax- iomatic way. This allowed us to state some basic, but relevant results. These are partial results, but as a first attempt, they pave the way for results on reduc- tion of theories. For future work, we leave the task of finding a suitable semantics. Also, we presented a definition for Possibilistic Safe Beliefs candidate. We have several questions, for example: Is there an equivalence between Safe Beliefs [16] and our Possibilistic Safe Beliefs Candidate?, that is, is it true that M is a possibilistic safe belief candidate of a theory T if and only if M ∗ is a safe belief of the theory T ∗ ?. Such result would allow us to establish a relation between Safe Beliefs as presented on [16] and Possibilistic Intuitionistic Logic (PIL) [10]. References 1. Allen Van Gelder, Kenneth A. Ross, et al.: The Well-Founded Semantics for Gen- eral Logic Programs. J. ACM 38 (1991), no. 3, 620 − 650. 2. J. L. Carballido, M. Osorio, et al.: Equivalence for the G3 −Stable Models Seman- tics. J. Applied Logic 8 (2010), no. 1, 82 − 96. 3. D. Dubois, J. Lang, and H. Prade: Possibilistic Logic. Handbook of Logic in Ar- tificial Intelligence and Logic Programming (Dov. M. Gabbay, C. J. Hogger, and J. A. Robinson, eds.), vol. 3, Oxford University Press, Inc., New York, NY, USA, 1994, pp. 439 − 513. 4. Dick H. J. De Jongh, Lex Hendrix: Characterizations of Strongly Equivalent Logic Programs in Intermediate Logics. Theory and Practice of Logic Programming 3 (2003), no. 3, 259 − 270. 5. Vladimir Lifschitz, David Pearce, et al.: Strongly Equivalent Logic Programs. ACM Trans. Comput. Logic 2 (2001), no. 4, 526 − 541. 6. V. Marek and M. Truszczyn’ski: Stable Models and an Alternative Logic Program- ming Paradigm. In: The Logic Programming Paradigm: a 25-Year Perspective, Springer Verlag, pages 169-181, 1999. 7. Elliot Mendelson: Introduction to Mathematical Logic. fourth ed., Chapman & Hall / CRC, 1997. 8. I. Niemelä: Logic Programs With Stable Model Semantics as a Constraint Pro- gramming Paradigm. Annals of Mathematics and Artificial Intelligence, Vol. 25, pages 241-273, 1999. 9. Pascal Nicolas, Laurent Garcia, et al.: Possibilistic Uncertainty Handling for An- swer Set Programming. Annals Math. Artif. Intell. 47 (2006). 139 − 181. 53 10. O. Estrada, J. Arrazola, M. Osorio: Possibilistic Intuitionistic Logic. To Appear in Proceedings of the 9th Mexican International Conference on Artificial Intelligence (MICAI) 2010. 11. M. Osorio, J. C. Nieves: Possibilistic Well-Founded Semantics. MICAI 2009: Ad- vances in Artificial Intelligence 5845 (2009), 15 − 26. 12. M. Osorio, J. C. Nieves: Pstable Semantics for Possibilistic Logic Programs. MICAI 2007: Advances in Artificial Intelligence 4827 (2007), 294 − 304. 13. M. Osorio, J. A. Navarro, J. Arrazola, V. Borja: Ground Non-Monotonic Modal Logic S5: New Results. J. Log. Computation 15 (2005), no. 5, 787 − 813. 14. M. Osorio, J. A. Navarro, J. Arrazola: Equivalence in Answer Set Programming. LOPSTR, 2001, pp. 57 − 75. 15. M. Osorio, J. A. Navarro, J. Arrazola: Safe Beliefs for Propositional Theories. Annals of Pure and Applied Logic, 134 (2005), 63-82. 16. M. Osorio, J. A. Navarro, J. Arrazola: Applications of Intuitionistic Logic in Answer Set Programming. Theory and Practice of logic programming, 2004, pp. 325 − 354. 17. David Pearce: Stable Inference as Intuitionistic Validity. The Journal of Logic Programming 38 (1999), no. 1, 79 − 91. 18. Claude Shannon: A Mathematical Theory of Communication. Bell System Tech- nical Journal 27 (1948), 379 − 426 & 623 − 656 19. Dirk Van Dalen: Logic and Structure. Springer, March 2004. 20. Lofti A. Zadeh: Fuzzy Sets as a Basis for a Theory of Possibility. Fuzzy Sets and Systems 1 (1978), 3 − 28 54