This note is concerned with a formal analysis of the problem of non-monotonic reasoning in intelligent systems, especially when the uncertainty is taken into account in a quantitative way. A firm connection between logic and probability is established by introducing conditioning notions by means of formal structures that do not rely on quantitative measures. The associated conditional logic, compatible with conditional probability evaluations, is non-monotonic relative to additional evidence. Computational aspects of conditional probability logic are mentioned. The importance of this development lies on its role to provide a conceptual basis for various forms of evidence combination and on its significance to unify multi-valued and non-monotonic logics

When a physicist performs a quantic measurement, new information about the system at hand is gathered. This presentation studies the logical properties of how this new information is combined with previous information. It presents Quantum Logic as a propositional logic under two connectives: negation and the and then operation that combines old and new information. The and then connective is neither commutative nor associative. Many properties of this logic are exhibited, and some small elegant subset is shown to imply all the properties considered.

Cozman, Fabio Gagliardi (Universidade de Sao Paulo) | Maua, Denis Deratani (Universidade de Sao Paulo)

We examine the inferential complexity of Bayesian networks specified through logical constructs. We first consider simple propositional languages, and then move to relational languages. We examine both the combined complexity of inference (as network size and evidence size are not bounded) and the data complexity of inference (where network size is bounded); we also examine the connection to liftability through domain complexity. Combined and data complexity of several inference problems are presented, ranging from polynomial to exponential classes.

Buehrer, Daniel, Lee, Chee-Hwa

Class algebra provides a natural framework for sharing of ISA hierarchies between users that may be unaware of each other's definitions. This permits data from relational databases, object-oriented databases, and tagged XML documents to be unioned into one distributed ontology, sharable by all users without the need for prior negotiation or the development of a "standard" ontology for each field. Moreover, class algebra produces a functional correspondence between a class's class algebraic definition (i.e. its "intent") and the set of all instances which satisfy the expression (i.e. its "extent"). The framework thus provides assistance in quickly locating examples and counterexamples of various definitions. This kind of information is very valuable when developing models of the real world, and serves as an invaluable tool assisting in the proof of theorems concerning these class algebra expressions. Finally, the relative frequencies of objects in the ISA hierarchy can produce a useful Boolean algebra of probabilities. The probabilities can be used by traditional information-theoretic classification methodologies to obtain optimal ways of classifying objects in the database.

The categorial approach to evidential reasoning can be seen as a combination of the probability kinematics approach of Richard Jeffrey (1965) and the maximum (cross-) entropy inference approach of E. T. Jaynes (1957). As a consequence of that viewpoint, it is well known that category theory provides natural definitions for logical connectives. In particular, disjunction and conjunction are modelled by general categorial constructions known as products and coproducts. In this paper, I focus mainly on Dempster-Shafer theory of belief functions for which I introduce a category I call Dempster?s category. I prove the existence of and give explicit formulas for conjunction and disjunction in the subcategory of separable belief functions. In Dempster?s category, the new defined conjunction can be seen as the most cautious conjunction of beliefs, and thus no assumption about distinctness (of the sources) of beliefs is needed as opposed to Dempster?s rule of combination, which calls for distinctness (of the sources) of beliefs.