Position Paper: Paraconsistent Reasoning for the Semantic Web S. Schaffert1 , F. Bry2 , P. Besnard3 , H. Decker4 , S. Decker5 , C. Enguix5 , A. Herzig3 1 Salzburg Research Forschungsgesellschaft, Salzburg, Austria 2 Ludwig-Maximilians-Universität München, Germany 3 Institut de Recherche en Informatique de Toulouse, France 4 Instituto Tecnológico de Informática, Valencia, Spain 5 Digital Enterprise Research Institute, Galway, Ireland Abstract works on the track in France have not been entered into the German system. Human beings can easily cope with such Due to the Semantic Web’s decentralised and dis- inconsistencies in various ways (e.g. identify which informa- tributed management, contradictory information is tion is more likely or “don’t care”). Reasoning systems on the and will remain frequent. However, classical rea- (Semantic) Web must equally be able to derive useful conclu- soning systems fail to work properly in the pres- sions from the “inconsistency-free” premises. ence of inconsistencies, because they implicitly or explicitly assume the ex contradictione quod li- Coping with Change bet (ECQL) principle stating that anything follows Belief change is the field of artificial intelligence devoted to from contradictory premises. Paraconsistent rea- the rational change of belief in the light of new evidence. E.g., soning challenges this ECQL principle. a train timetable might be updated with new train connec- Stressing practical cases of reasoning on the Web, tions that have to be taken into account in further reasoning. this position paper first argues that paraconsistent Likewise, train connections might have been removed mak- reasoning is likely to become a key issue for suc- ing previously drawn conclusions invalid. cessful deployment of the Semantic Web. Then, it In practice, changes like updates to an information system briefly introduces the main approaches to date to may cause inconsistencies that cannot be discarded. Standard paraconsistent reasoning. methods for belief change are based on classical logic and hence accept the ECQL principle. As a consequence, they cannot be used for deriving useful conclusions in presence of 1 Introduction updates causing contradictions. Classical and other logic, upon which modern computing is Inconsistencies Welcome! based, requires the complete absence of contradictions. With In some situations, inconsistencies are even desirable. This the classical ex contradictione quod libet (ECQL) rule (or is, e.g., the case when contradictory viewpoints are present principle of explosion), everything, and thus nothing useful at and need to be reconciled. For instance, two ontologies de- all, can be inferred from a contradiction. For instance, from scribing appartment rental offers and appartment sale offers a contradiction in a train information system can be derived might well inconsistently describe preferences and prices for that the moon is made of green cheese. Nonetheless, incon- city areas. This obviously should neither prevent considering sistencies play an important role in practice (Section 2). both ontologies nor deriving meaningful conclusions in the Paraconsistent logics are a rather novel direction in math- same reasoning context (like helping in taking a decision for ematical logics that challenge the ECQL principle in order buying or renting an appartment). Obviously, human beings to allow “reasonable” reasoning in the presence of inconsis- are capable of doing so without applying the ECQL principle, tencies without introducing more problems than are already and so should automated reasoning systems on the Web. present in the data. Several different approaches to paracon- Another example is policy reasoning. At the beginning of a sistent logics exist and are briefly outlined in Section 3. negotiation towards selling/buying a Web service, the policies We conclude this article with a perspective for paraconsis- of the buyer and seller might be contradictory. Instead of ap- tent reasoning on the Semantic Web (Section 4). plying the ECQL principle, a reasoning system should strive to overcome the inconsistencies, i.e. find a way to pass a con- 2 Cases for Paraconsistent Reasoning tract acceptable for both the service buyer and seller without Distributed Information Systems requiring them to change their policies. In distributed information systems, like the online informa- “Dialetheias” tion systems of European railways companies, contradic- In practice, there are cases where contradictions are inherent tory information is frequent. For example, the German rail- to the problem, so-called “dialetheias”. Since such cases arise way company might give different arrival times for trains to in knowledge modelling, they will also arise on the Seman- Paris than the French railway company, because construction tic Web. This is in particular the case with the well known Liar’s Paradox where a sentence states its own falsity (“this 4 Paraconsistency on the Semantic Web sentence is not true”). We believe that dealing with inconsistencies will play a cen- On the Semantic Web, dialetheias might easily arise though tral role in the emergence of the Semantic Web. Paraconsis- reification, especially of RDF statements, and through modal- tent reasoning provides foundations and techniques that will ities – such as “A believes B” or “A does not believe what B allow future applications to function properly in the presence states” – that are needed e.g. for policy reasoning. Liar sen- of inconsistencies. In particular, we think that paraconsistent tences can also be indirect consequences of statements that reasoning will influence the following areas: are themselves unproblematic, e.g. when combining knowl- edge from different Web resources. Paraconsistency in Ontology Reasoning Ontology reasoning (e.g. instance checking) on the Seman- 3 Approaches to Paraconsistent Reasoning tic Web is usually based on reasoning techniques, e.g. the Most approaches to paraconsistent logic and reasoning allow tableaux calculus, developed for description logics. There- a formula F and its negation ¬F to hold in an interpreation fore, a first step towards an “inconsistency-aware” Seman- (or “model”). Major approaches of paraconsistent logics and tic Web will be to adapt existing reasoning algorithms using reasoning are stressed below: techniques from paraconsistent reasoning. Relevant Logics Paraconsistency in Query Languages Relevant logics have been first proposed by Anderson and Querying data plays a very important role on the Semantic Belnap. Semantics for such logics based on “different Web, as indicated by the multitude of existing Semantic Web worlds” have been developed by Routley and Meyer. Con- query languages. Building upon ontology reasoning, Seman- junction and disjunction behave in the usual way, but each tic Web query languages will likely need to be adapted so as world w has an associated world w ∗ such that ¬A is true in to work in the presence of inconsistencies. w iff A is false in w ∗ (not in w). As a consequence, if A is Paraconsistency and Trust true in w and false in w ∗ , then A ∧ ¬A is true in w. Note that In a distributed environment like the Semantic Web, where requiring w∗ = w yields the standard classical logic. anyone can author content, trust is a key issue. Conflicts with Many-Valued Systems classical logic are apparent: for example, different sources A multi-valued logic is a logic with more than two truth val- might make conflicting assertions about the trustworthiness ues. The formulas that hold in a multi-valued interpretations of a site, and users might be interested in more fine-grained are those which have a specific truth-value, the so-called des- levels of trust besides the binary “trusted” or “not trusted”. ignated formulas. A multi-valued logic is paraconsistent if it allows both a formula and its negation to be designated. References The simplest approach uses three truth values: true and [1] N.D. Belnap. A Useful Four-valued Logic: How a com- false, like in classical logic, and a third truth-value denoting puter should think. In A.R. Anderson, N.D. Belnap, and “both truth and false” such that if a formual F has this third J.M. Dunn, editors, Entailment: The Logic of Relevance truth-value in an interpreation, then so does also ¬F . Con- and Necessity. Princeton University Press, 1992. sidering the real numbers between 0 and 1 instead of discrete [2] P. Besnard and A. Hunter, editors. Handbook of Dea- values results in a paraconsistent fuzzy logic. sible Reasoning and Uncertainty Management Systems, Non-Adjunctive Systems volume 2. Kluwer Academic Publishers, 1998. A non-adjunctive logic is a logic in which one cannot con- [3] François Bry. An Almost Classical Logic for Logic Pro- clude A from A ∧ B. The first non-adjunctive logic, and also gramming and Nonmonotonic Reasoning. In Paraconsis- the first paraconsistent logic, ever proposed is the discussive tent Computational Logic 2002, 2002. (or discursive) logic of Jaskowski. In dicussive logic, sev- eral contributors state “opinions”. Each opinion is consistent [4] N.C.A. da Costa. On the Theory of Inconsistent Formal in itself but might be inconsistent with another opinion. A Systems. Notre Dame Journal of Formal Logic, 15(4), modal logic (S5) is used to define interpretations: a world 1974. corresponds to a contributor, and in it, all the contributor’s [5] J.M. Dunn and G. Restall. Relevance Logic. In D. Gab- sentences are true. Thus, A ∧ ¬A can hold in an interpreta- bay and F. Guenthner, editors, Handbook of Philosophi- tion consisting of several worlds, but not in a single world. cal Logic, volume 6. Kluwer Academic Publishers, 2nd Non-Truth-Functional Logics edition, 2002. Non-truth functional logics have been introduced by da [6] S. Jaskowski. Propositional Calculus for Contradictory Costa. Their idea is to make negation “non-truth-functional” Deductive Systems. In Studia Logica, volume 24. 2001. while keeping the other connectives like in standard, e.g. clas- [7] G. Priest. Paraconsistent Belief Revision. In Theoria, sical, logics. Seeing an interpretation as a function mapping volume 67. 2001. formulas to 0 (false) or 1 (true), a non-truth funtional logic [8] G. Priest. Paraconsistent Logic. In D. Gabbay and gives rise to defining the truth-value of ¬A independently of that of A (while keeping the usual functional dependencies of F. Guenthner, editors, Handbook of Philosophical Logic, the truth-value of A ∧ B, A ∨ B, A ⇒ B, etc. to the truth volume 6. Kluwer Academic Publishers, 2nd edition, values of A and B). 2002.