This paper focuses on the expressive power of disjunctive and normal logic programs under the stable model semantics over finite, infinite, or arbitrary structures. A translation from disjunctive logic programs into normal logic programs is proposed and then proved to be sound over infinite structures. The equivalence of expressive power of two kinds of logic programs over arbitrary structures is shown to coincide with that over finite structures, and coincide with whether or not NP is closed under complement. Over finite structures, the intranslatability from disjunctive logic programs to normal logic programs is also proved if arities of auxiliary predicates and functions are bounded in a certain way.

(l) I have enough evidence to render the sentence S probable. (la) So, relative to what I know, it is rational of me to believe S. (2) Now that I have more evidence, S may no longer be probable. (2a) So now, relative to what I know, it is not rational of me to believe S. These seem a perfectly ordinary, common sense, pair of situations. Generally and vaguely, I take them to embody what I shall call probabilistic inference. This form of inference is clearly non-monotonic. Relatively few people have taken this form of inference, based on high probability, to serve as a foundation for non-monotonic logic or for a logical or defeasible inference. There are exceptions: Jane Nutter [16] thinks that sometimes probability has something to do with non-monotonic reasoning. Judea Pearl [ 17] has recently been exploring the possibility. There are any number of people whom one might call probability enthusiasts who feel that probability provides all the answers by itself, with no need of help from logic. Cheeseman [1], Henrion [5] and others think it useful to look at a distribution of probabilities over a whole algebra of statements, to update that distribution in the light of new evidence, and to use the latest updated distribution of probability over the algebra as a basis for planning and decision making. A slightly weaker form of this approach is captured by Nilsson [15], where one assumes certain probabilities for certain statements, and infers the probabilities, or constraints on the probabilities of other statement. None of this corresponds to what I call probabilistic inference. All of the inference that is taking place, either in Bayesian updating, or in probabilistic logic, is strictly deductive. Deductive inference, particularly that concerned with the distribution of classical probabilities or chances, is of great importance. But this is not to say that there is no important role for what earlier logicians have called "ampliative" or "inductive" or "scientific" inference, in which the conclusion goes beyond the premises, asserts more than do the premises. This depends on what David Israel [6] has called "real rules of inference". It is characteristic of any such logic or inference procedure that it can go wrong: that statements accepted at one point may be rejected at a later point. Research underlying the results reported here has been partially supported by the Signals Warfare Center of the United States Army.

Many writers have observed that default logics appear to contain the "lottery paradox" of probability theory. This arises when a default "proof by contradiction" lets us conclude that a typical X is not a Y where Y is an unusual subclass of X. We show that there is a similar problem with default "proof by cases" and construct a setting where we might draw a different conclusion knowing a disjunction than we would knowing any particular disjunct. Though Reiter's original formalism is capable of representing this distinction, other approaches are not. To represent and reason about this case, default logicians must specify how a "typical" individual is selected. The problem is closely related to Simpson's paradox of probability theory. If we accept a simple probabilistic account of defaults based on the notion that one proposition may favour or increase belief in another, the "multiple extension problem" for both conjunctive and disjunctive knowledge vanishes.

We propose a norm of consistency for a mixed set of defeasible and strict sentences, based on a probabilistic semantics. This norm establishes a clear distinction between knowledge bases depicting exceptions and those containing outright contradictions. We then define a notion of entailment based also on probabilistic considerations and provide a characterization of the relation between consistency and entailment. We derive necessary and sufficient conditions for consistency, and provide a simple decision procedure for testing consistency and deciding whether a sentence is entailed by a database. Finally, it is shown that if al1 sentences are Horn clauses, consistency and entailment can be tested in polynomial time.

In this paper an approach to automated deduction under uncertainty,based on possibilistic logic, is proposed ; for that purpose we deal with clauses weighted by a degree which is a lower bound of a necessity or a possibility measure, according to the nature of the uncertainty. Two resolution rules are used for coping with the different situations, and the refutation method can be generalized. Besides the lower bounds are allowed to be functions of variables involved in the clause, which gives hypothetical reasoning capabilities. The relation between our approach and the idea of minimizing abnormality is briefly discussed. In case where only lower bounds of necessity measures are involved, a semantics is proposed, in which the completeness of the extended resolution principle is proved. Moreover deduction from a partially inconsistent knowledge base can be managed in this approach and displays some form of non-monotonicity.

Two major difficulties in using default logics are their intractability and the problem of selecting among multiple extensions. We propose an approach to these problems based on integrating nommonotonic reasoning with plausible reasoning based on triangular norms. A previously proposed system for reasoning with uncertainty (RUM) performs uncertain monotonic inferences on an acyclic graph. We have extended RUM to allow nommonotonic inferences and cycles within nonmonotonic rules. By restricting the size and complexity of the nommonotonic cycles we can still perform efficient inferences. Uncertainty measures provide a basis for deciding among multiple defaults. Different algorithms and heuristics for finding the optimal defaults are discussed.

This extended abstract presents a logic, called Lp, that is capable of representing and reasoning with a wide variety of both qualitative and quantitative statistical information. The advantage of this logical formalism is that it offers a declarative representation of statistical knowledge; knowledge represented in this manner can be used for a variety of reasoning tasks. The logic differs from previous work in probability logics in that it uses a probability distribution over the domain of discourse, whereas most previous work (e.g., Nilsson [2], Scott et al. [3], Gaifinan [4], Fagin et al. [5]) has investigated the attachment of probabilities to the sentences of the logic (also, see Halpern [6] and Bacchus [7] for further discussion of the differences). The logic Lp possesses some further important features. First, Lp is a superset of first order logic, hence it can represent ordinary logical assertions. This means that Lp provides a mechanism for integrating statistical information and reasoning about uncertainty into systems based solely on logic. Second, Lp possesses transparent semantics, based on sets and probabilities of those sets. Hence, knowledge represented in Lp can be understood in terms of the simple primative concepts of sets and probabilities. And finally, the there is a sound proof theory that has wide coverage (the proof theory is complete for certain classes of models). The proof theory captures a sufficient range of valid inferences to subsume most previous probabilistic uncertainty reasoning systems. For example, the linear constraints like those generated by Nilsson's probabilistic entailment [2] can be generated by the proof theory, and the Bayesian inference underlying belief nets [8] can be performed. In addition, the proof theory integrates quantitative and qualitative reasoning as well as statistical and logical reasoning. In the next section we briefly examine previous work in probability logics, comparing it to Lp. Then we present some of the varieties of statistical information that Lp is capable of expressing. After this we present, briefly, the syntax, semantics, and proof theory of the logic. We conclude with a few examples of knowledge representation and reasoning in Lp, pointing out the advantages of the declarative representation offered by Lp. We close with a brief discussion of probabilities as degrees of belief, indicating how such probabilities can be generated from statistical knowledge encoded in Lp. The reader who is interested in a more complete treatment should consult Bacchus [7].

This paper describes a natural framework for rules, based on belief functions, which includes a repre- sentation of numerical rules, default rules and rules allowing and rules not allowing contraposition. In particular it justifies the use of the Dempster-Shafer Theory for representing a particular class of rules, Belief calculated being a lower probability given certain independence assumptions on an underlying space. It shows how a belief function framework can be generalised to other logics, including a general Monte-Carlo algorithm for calculating belief, and how a version of Reiter's Default Logic can be seen as a limiting case of a belief function formalism.

To operate intelligently in the world, an agent must reason about its actions. The consequences of an action are a function of both the state of the world and the action itself. Many aspects of the world are inherently stochastic, so a representation for reasoning about actions must be able to express chances of world states as well as indeterminacy in the effects of actions and other events. This paper presents a propositional temporal probability logic for representing and reasoning about actions. The logic can represent the probability that facts hold and events occur at various times. It can represent the probability that actions and other events affect the future. It can represent concurrent actions and conditions that hold or change during execution of an action. The model of probability relates probabilities over time. The logical language integrates both modal and probabilistic constructs and can thus represent and distinguish between possibility, probability, and truth. Several examples illustrating the use of the logic are given.

Linear representations for a subclass of boolean symmetric functions selected by a parity condition are shown to constitute a generalization of the linear constraints on probabilities introduced by Boole. These linear constraints are necessary to compute probabilities of events with relations between the. arbitrarily specified with propositional calculus boolean formulas.