Potyka, Nico (FernUniversität Hagen) | Thimm, Matthias (Institute for Web Science and Technologies (WeST))

The classical probabilistic entailment problem is to determine upper and lower bounds on the probability of formulas, given a consistent set of probabilistic assertions. We generalize this problem by omitting the consistency assumption and, thus, provide a general framework for probabilistic reasoning under inconsistency. To do so, we utilize inconsistency measures to determine probability functions that are closest to satisfying the knowledge base. We illustrate our approach on several examples and show that it has both nice formal and computational properties.

We introduce a novel logical notion--partial entailment--to propositional logic. In contrast with classical entailment, that a formula P partially entails another formula Q with respect to a background formula set \Gamma intuitively means that under the circumstance of \Gamma, if P is true then some "part" of Q will also be true. We distinguish three different kinds of partial entailments and formalize them by using an extended notion of prime implicant. We study their semantic properties, which show that, surprisingly, partial entailments fail for many simple inference rules. Then, we study the related computational properties, which indicate that partial entailments are relatively difficult to be computed. Finally, we consider a potential application of partial entailments in reasoning about rational agents.

We introduce a novel logical notion-partial entailment-to propositional logic. In contrast with classical entailment, that a formula P partially entails another formula Q with respect to a background formula set Γ intuitively means that under the circumstance of Γ, if P is true then some "part" of Q will also be true. We distinguish three different kinds of partial entailments and formalize them by using an extended notion of prime implicant. We study their semantic properties, which show that, surprisingly, partial entailments fail for many simple inference rules. Then, we study the related computational properties, which indicate that partial entailments are relatively difficult to be computed. Finally, we consider a potential application of partial entailments in reasoning about rational agents.

Giordano, Laura, Dupré, Daniele Theseider

In this work we study a rational extension $SROEL^R T$ of the low complexity description logic SROEL, which underlies the OWL EL ontology language. The extension involves a typicality operator T, whose semantics is based on Lehmann and Magidor's ranked models and allows for the definition of defeasible inclusions. We consider both rational entailment and minimal entailment. We show that deciding instance checking under minimal entailment is in general $\Pi^P_2$-hard, while, under rational entailment, instance checking can be computed in polynomial time. We develop a Datalog calculus for instance checking under rational entailment and exploit it, with stratified negation, for computing the rational closure of simple KBs in polynomial time.

Hinrichs, Timothy L. (University of Chicago) | Kao, Jui-Yi (Stanford University) | Genesereth, Michael R. (Stanford University)

Real-world automated reasoning systems must contend with inconsistencies and the vast amount of information stored in relational databases. In this paper, we introduce compilation techniques for inconsistency-tolerant reasoning over the combination of classical logic and a relational database. Our resolution-based algorithms address a quantifier-free, function-free fragment of first-order logic while leveraging off-the-shelf database technology for all data-intensive computation.