Probabilistic Default Reasoning with Conditional Constraints.
We present an approach to reasoning from statistical and subjective knowledge, which is based on a combination of probabilistic reasoning from conditional constraints with approaches to default reasoning from conditional knowledge bases. More precisely, we introduce the notions of i>z-, lexicographic, and conditional entailment for conditional constraints, which are probabilistic generalizations of Pearl's entailment in system i>Z, Lehmann's lexicographic entailment, and Geffner's conditional entailment, respectively. We show that the new formalisms have nice properties. In particular, they show a similar behavior as reference-class reasoning in a number of uncontroversial examples. The new formalisms, however, also avoid many drawbacks of reference-class reasoning. More precisely, they can handle complex scenarios and even purely probabilistic subjective knowledge as input. Moreover, conclusions are drawn in a global way from all the available knowledge as a whole. We then show that the new formalisms also have nice general nonmonotonic properties. In detail, the new notions of i>z-, lexicographic, and conditional entailment have similar properties as their classical counterparts. In particular, they all satisfy the rationality postulates proposed by Kraus, Lehmann, and Magidor, and they have some general irrelevance and direct inference properties. Moreover, the new notions of i>z- and lexicographic entailment satisfy the property of rational monotonicity. Furthermore, the new notions of i>z-, lexicographic, and conditional entailment are proper generalizations of both their classical counterparts and the classical notion of logical entailment for conditional constraints. Finally, we provide algorithms for reasoning under the new formalisms, and we analyze its computational complexity.
Introduction
In this paper, we elaborate a combination of probabilistic
reasoning from conditional constraints with approaches to
default reasoning from conditional knowledge bases. As a
main result, this combination provides new notions of entailment
for conditional constraints, which respect the ideas
of classical default reasoning from conditional knowledge
bases, and which are generally much stronger than the classical
notion of logical entailment based on conditioning.
Moreover, the results of this paper can also be applied for
handling inconsistencies in probabilistic knowledge bases.
Informally, the ideas behind this paper can be described as
follows. Assume that we have the following knowledge at
hand: "all penguins are birds" (G1), "between 90 and 95%
of all birds fly" (G2), and "at most 5% of all penguins fly"
(G3). Moreover, assume a first scenario in which "Tweety is
a bird" (E1) and second one in which "Tweety is a penguin"
(E2). What do we conclude about Tweety's ability to fly?
A closer look at this example shows that the statements
G1-G3 describe statistical knowledge (or objective knowl-
while E1 and E2 express degrees of belief (or subjective
knowledge). One way of handling such combinations of
statistical knowledge and degrees of belief is reference class
reasoning, which goes back to Reichenbach (1949) and was
further refined by Kyburg (1974; 1983) and Pollock (1990).
Another related field is default reasoning from conditional
knowledge bases, where we have generic statements of the
form "all penguins are birds", "generally, all birds fly", and
"generally, no penguin flies" in addition to some concrete
evidence as E1 and E2. The literature contains several different
approaches to default reasoning and extensive work on
the desired properties. The core of these properties are the
rationality postulates proposed by Kraus et al. (1990). These
rationality postulates constitute a sound and complete axiom
system for several classical model-theoretic entailment
relations under uncertainty measures on worlds. In detail,
they characterize classical model-theoretic entailment under
preferential structures (Shoham 1987; Kraus et al. 1990),
infinitesimal probabilities (Adams 1975; Pearl 1989), possibility
measures (Dubois & Prade 1991), and world rankings
(Spohn 1988; Goldszmidt & Pearl 1992). They also characterize
an entailment relation based on conditional objects
(Dubois & Prade 1994). A survey of all these relationships
is given in (Benferhat et al. 1997). Recently, Friedman and
Halpern (2000) showed that many approaches describe to
the same notion of inference, since they are all expressible
as plausibility measures.
Mainly to solve problems with irrelevant information, the
notion of rational closure as a more adventurous notion
of entailment has been introduced by Lehmann (Lehmann
1989; Lehmann & Magidor 1992). This notion of entailment
is equivalent to entailment in system Z by Pearl (1990), to
the least specific possibility entailment by Benferhat et al.
(1992), and to a conditional (modal) logic-based entailment
by Lamarre (1992). Finally, mainly in order to solve problems
with property inheritance from classes to exceptional
subclasses, the maximum entropy approach to default entailment
was proposed by Goldszmidt et al. (1993); the notion
of lexicographic entailment was introduced by Lehmann
(1995) and Benferhat et al. (1993); the notion of conditional
entailment was proposed by Geffner (Geffner 1992; Geffner
Pearl 1992); and an infinitesimal belief function approach
was suggested by Benferhat et al. (1995).
Coming back to our introductory example, we realize
that G1-G3 and E1-E2 represent interval restrictions for
conditional probabilities, also called conditional constraints
(Lukasiewicz 1999b). The literature contains extensive
work on reasoning about conditional constraints (Dubois &
Prade 1988; Dubois et al. 1990; 1993; Amarger et al. 1991;
Jaumard et al. 1991; Th-one et al. 1992; Frisch & Haddawy
1994; Heinsohn 1994; Luo et al. 1996; Lukasiewicz 1999a;
1999b) and their generalizations, for example, to probabilistic
logic programs (Lukasiewicz 1998).
Now, the main idea of this paper is to use techniques for
default reasoning from conditional knowledge bases in order
to perform probabilistic reasoning from statistical knowledge
and degrees of beliefs. More precisely, we extend
the notions of entailment in system Z, Lehmann's lexicographic
entailment, and Geffner's conditional entailment to
the framework of conditional constraints.
Informally, in our introductory example, the statements
G2 and G3 are interpreted as "generally, a bird flies with
a probability between 0.9 and 0.95" (G2 ? ) and "generally,
a penguin flies with a probability of at most 0.05" (G3 ? ),
respectively. In the first scenario, we then simply use the
whole probabilistic knowledge to conclude
under classical logical entailment that "Tweety flies
with a probability between 0.9 and 0.95". In the second
scenario, it turns out that the whole probabilistic knowledge
precisely,
is inconsistent in the context of a pen-
guin. In fact, the main problem is that G2 ? should not be
applied anymore to penguins. That is, we can easily re-solve
the inconsistency by removing G2 ? , and then conclude
from classical logical entailment that
"Tweety flies with a probability of at most 0.05".
Hence, the results of this paper can also be used for
handling inconsistencies in probabilistic knowledge bases.
More precisely, the new notions of nonmonotonic entailment
coincide with the classical notion of logical entailment
as far as satisfiable sets of conditional constraints are con-
cerned. Furthermore, they allow desirable conclusions from
certain kinds of unsatisfiable sets of conditional constraints.
We remark that this inconsistency handling is guided by
the principles of default reasoning from conditional knowledge
bases. It is thus based on a natural preference relation
on conditional constraints, and not on the assumption that
all conditional constraints are equally weighted (as, for ex-
ample, in the work by Jaumard et al. (1991)).
The work closest in spirit to this paper is perhaps the one
by Bacchus et al. (1996), which suggests to use the random
worlds method (Grove et al. 1994) to induce degrees
of beliefs from quite rich statistical knowledge bases. How-
ever, differently from (Bacchus et al. 1996), we do not make
use of a strong principle such as the random worlds method
(which is closely related to probabilistic reasoning under
maximum entropy). Moreover, we restrict our considerations
to the propositional setting.
The main contributions of this paper are as follows:
We illustrate that the classical notion of logical entailment
for conditional constraints is not very well-suited for default
reasoning with conditional constraints.
We introduce the notions of z-entailment, lexicographic
entailment, and conditional entailment for conditional
constraints, which are a combination of the classical notions
of entailment in system Z (Pearl 1990), Lehmann's
lexicographic entailment (Lehmann 1995), and Geffner's
conditional entailment (Geffner 1992; Geffner & Pearl
1992), respectively, with the classical notion of logical
entailment for conditional constraints.
We give some examples that analyze the nonmonotonic
properties of the new notions of entailment for default reasoning
with conditional constraints. It turns out that the
new notions of z-entailment, lexicographic entailment,
and conditional entailment have similar properties like
their classical counterparts.
We show that the new notions of z-entailment, lexicographic
entailment, and conditional entailment for conditional
constraints properly extend the classical notions
of entailment in system Z, lexicographic entailment, and
conditional entailment, respectively.
We show that the new notions of z-entailment, lexicographic
entailment, and conditional entailment for conditional
constraints properly extend the classical notion of
logical entailment for conditional constraints.
Note that all proofs are given in (Lukasiewicz 2000).
Preliminaries
We now introduce some necessary technical background.
We assume a finite nonempty set of basic propositions
(or atoms) . We use ? and > to denote the propositional
constants false and true, respectively. The set of classical
formulas is the closure of [f?;>g under the Boolean
operations : and ^. A strict conditional constraint is an expression
real numbers l; u2 [0; 1] and classical
formulas and . A defeasible conditional constraint
(or default) is an expression ( k)[l; u] with real numbers
classical formulas and . A conditional
constraint is a strict or defeasible conditional constraint.
The set of strict probabilistic formulas (resp., probabilistic
formulas) is the closure of the set of all strict conditional
constraints (resp., conditional constraints) under the
Boolean operations : and ^. We use
and to abbreviate :(:F ^:G), :(F ^:G), and
(:(:F ^G))^ (:(F ^:G)), respectively, and adopt the
usual conventions to eliminate parentheses.
A probabilistic default theory is a pair
P is a finite set of strict conditional constraints and D is
a finite set of defeasible conditional constraints. A probabilistic
knowledge base KB is a strict probabilistic formula.
Informally, default theories represent strict and defeasible
generic knowledge, while probabilistic knowledge bases express
some concrete evidence.
A possible world is a truth assignment I :  ! ftrue,
falseg, which is extended to classical formulas as usual. We
use I to denote the set of all possible worlds for . A possible
world I satisfies a classical formula , or I is a model
of , denoted I
A probabilistic interpretation Pr is a probability function
on I (that is, a mapping Pr : I ! [0; 1] such that all
Pr(I) with I 2 I sum up to 1). The probability of a classical
formula  in the probabilistic interpretation Pr , denoted
Pr(), is defined as follows:
For classical formulas  and with Pr () > 0, we use
Pr( to abbreviate Pr(). The truth of
probabilistic formulas F in a probabilistic interpretation Pr ,
denoted Pr inductively defined as follows:
Pr
Pr
Pr
Pr G.
We remark that there is no difference between strict and
defeasible conditional constraints as far as the notion of truth
in probabilistic interpretations is concerned.
A probabilistic interpretation Pr satisfies a probabilistic
formula F , or Pr is a model of F , iff Pr
a set of probabilistic formulas F , or Pr is a model of F ,
denoted Pr is a model of all F 2F . We say F
is satisfiable iff a model of F exists.
We next define the notion of logical entailment as fol-
lows. A strict probabilistic formula F is a logical consequence
of a set of probabilistic formulas F , denoted F
iff each model of F is also a model of F . A strict conditional
constraint ( j)[l; u] is a tight logical consequence
of F , denoted F is the infimum
(resp., supremum) of Pr( j) subject to all models
Pr of F with Pr() > 0 (note that we canonically define
We remark that every notion of entailment for conditional
constraints is associated with a notion of consequence and a
notion of tight consequence. Informally, the notion of consequence
describes entailed intervals, while the notion of
tight consequence characterizes the tightest entailed inter-
val. That is, if ( j)[l; u] is a tight consequence of F , then
Motivating Examples
What should a probabilistic knowledge base entail under a
probabilistic default theory? To get a rough idea on the reply
to this question, we now introduce two natural notions of
entailment and analyze their properties. It will turn out that
neither of these two notions is fully adequate for probabilistic
default reasoning with conditional constraints.
In the sequel, let D) be a probabilistic default
theory. We first define the notion of 0-entailment,
which applies to probabilistic knowledge bases of the
In detail, a strict conditional constraint
( j)[l; u] is a 0-consequence of KB , denoted
It is a tight
0-consequence of KB , denoted KB k 0
tight ( j)[l; u], iff
Informally, we use the concrete
evidence in KB to fix our "point of interest" and the
generic knowledge in T to draw the requested conclusion.
That is, we perform classical conditioning.
We next define the notion of 1-entailment, which applies
to all probabilistic knowledge bases KB . A strict probabilistic
formula F is a 1-consequence of KB , denoted
strict conditional constraint
( j)[l; u] is a tight 1-consequence of KB , denoted
tight ( j)[l; u], iff P[D[fKBg
Informally, we draw our conclusion from the union of the
concrete evidence in KB and the generic knowledge in T .
We now analyze the properties of these two notions of
entailment. Our first example concentrates on the aspects of
ignoring irrelevant information and property inheritance.
Example 1 The knowledge "all penguins are birds" and
"at least 95% of all birds have legs" can be expressed by
the following probabilistic default theory
should entail that "generally, birds have legs
with a probability of at least 0.95" (that is, e.g., if we know
that Tweety is a bird, and we do not have any other knowl-
edge, then we should conclude that the probability of Tweety
having legs is at least 0.95). Indeed, this conclusion is drawn
under both 0- and 1-entailment (see item (1) in Table 1).
should entail that "generally, yellow birds
have legs with a probability of at least 0.95" (as the property
"yellow" is not mentioned at all in T 1 and thus irrelevant),
and that "generally, penguins have legs with a probability of
at least 0.95" (as the set of all penguins is a nonexceptional
subclass of the set of all birds, and thus penguins should
inherit all properties of birds). However, while 1-entailment
still allows the desired conclusions, 0-entailment just yields
the interval [0; 1] (see items (2)-(3) in Table 1). 2
We next concentrate on the principle of specificity and the
problem of inheritance blocking.
Example 2 Let us consider the following probabilistic default
theory
(fly k bird)[:9; :95];
(fly k penguin)[0;
This default theory should entail that "generally, penguins
fly with a probability of at most 0.05" (as properties of
more specific classes should override inherited properties of
less specific classes). Indeed, 0-entailment yields the desired
conclusion, while 1-entailment reports an unsatisfiability
(see item (7) in Table 1).
Moreover, should entail that "generally, penguins have
legs with a probability of at least 0.95", since penguins are
exceptional birds w.r.t. to the ability of being able to fly, but
not w.r.t. the property of having legs. However, 0-entailment
provides only the interval [0; 1], and 1-entailment reports
even an unsatisfiability (see item (5) in Table 1). 2
The following example deals with the drowning problem
(Benferhat et al. 1993).
Example 3 Let us consider the following probabilistic default
theory
f(fly k bird)[:9; :95]; (fly k penguin)[0; :05];
(easy to see k
This default theory should entail that "generally, yellow
penguins are easy to see", as the set of all yellow penguins

Table

1: Examples of 0- and 1-entailed tight intervals.
tight
(easy to seej>) [0; 1] [1; 0]
undefined [:86; :91]
undefined [1; 0]
is a nonexceptional subclass of the set of all yellow objects.
But, 0-entailment gives only the interval [0; 1], and 1-entail-
ment reports an unsatisfiability (see item (8) in Table 1). 2
The next example is taken from (Bacchus et al. 1996).
Example 4 Let us consider the following probabilistic default
theory
This default theory should entail "generally, the probability
that magpies chirp is between 0.7 and 0.8", since we
know more about birds w.r.t. the property of being able to
chirp than about magpies. Indeed, both 0- and 1-entailment
yield the desired conclusion (see item (9) in Table 1). 2
The following example concerns ambiguity preservation
(Benferhat et al. 1995).
Example 5 Let us consider the following probabilistic default
theory
f(fly k metal wings)[:95; 1]; (fly k bird)[:95; 1];
(fly k penguin)[0;
Assume now that Oscar is a penguin with metal wings. As
Oscar is a penguin, we should conclude that the probability
that Oscar flies is at most 0.05. However, as Oscar has also
metal wings, we should conclude that the probability that
Oscar flies is at least 0.95. As argued in the literature on
default reasoning (Benferhat et al. 1995), such ambiguities
should be preserved. Indeed, 0-entailment yields the desired
interval [0; 1], while 1-entailment reports an unsatisfiability
(see item (10) in Table 1). 2
What about handling purely probabilistic evidence?
Example 6 Let us consider again the probabilistic default
theory T 2 of Example 2. Assume a first scenario in which
our belief is "the probability that Tweety is a bird is at least
0.9" and "the probability that Tweety is a penguin is at least
0.1" and a second scenario in which our belief is "the probability
that Tweety is a bird is at least 0.9" and "the probability
that Tweety is a penguin is at least 0.9". What do we
conclude about Tweety's ability to fly in these scenarios?
The notion of 0-entailment is undefined for such purely
probabilistic evidence, whereas the notion of 1-entailment
yields the probability interval [:86; :91] in the first scenario,
and reports an unsatisfiability in the second scenario (see
items (11)-(12) in Table 1). 2
Summarizing the results, 0-entailment is too weak, while
1-entailment is too strong. In detail, 0-entailment often
yields the trivial interval [0; 1] and is even undefined for
purely probabilistic evidence, while 1-entailment often reports
unsatisfiabilities (in fact, in the most interesting sce-
narios, as 1-entailment is actually monotonic).
Roughly speaking, our ideal notion of entailment for
probabilistic knowledge bases under probabilistic default
theories should lie somewhere between 0- and 1-entailment.
One idea to obtain such a notion could be to strengthen 0-
entailment by adding some inheritance mechanism. Another
idea is to weaken 1-entailment by handling unsatisfiabilities.
In the rest of this paper, we will focus on the second idea.
Probabilistic Reasoning
In this section, we extend the classical notions of entailment
in system Z (Pearl 1990), Lehmann's lexicographic entailment
(1995), and Geffner's conditional entailment (Geffner
1992; Geffner & Pearl 1992) to conditional constraints.
The main idea behind these extensions is to use the following
two interpretations of defaults. As far as default
rankings and priority orderings are concerned, we interpret a
"generally, if  is true, then the probability
of is between l and u". Whereas, as far as notions
of entailment are concerned, we interpret ( k)[l; u] as "the
conditional probability of given  is between l and u".
Preliminaries
A probabilistic interpretation Pr verifies a default ( k)[l;u]
It falsifies a default
set of defaults
D tolerates a default d under a set of strict conditional
constraints has a model that verifies d. A set
of defaults D is under P in conflict with d iff no model of
verifies d.
A default ranking  on D maps each d 2D to a nonnegative
integer. It is admissible with iff each set of
defaults D 0 D that is under P in conflict with some default
d 2D contains a default d 0 such that (d 0 ) <(d). A probabilistic
is -consistent iff there
exists a default ranking on D that is admissible with T . It is
-inconsistent iff no such default ranking exists.
A probability ranking  maps each probabilistic interpretation
on I to a member of f0;
for at least one interpretation Pr . It is extended
to all strict probabilistic formulas F as follows. If F is sat-
isfiable, then
We say  is admissible with F iff (:F
It is admissible with a default ( k)[l; u] iff
Roughly speaking, the intuition behind this definition is to
"generally, if  is true, then the probability
of is between l and u". A probability ranking  is
admissible with a probabilistic default theory
is admissible with all F 2P and all d 2D.
System Z
We now extend the notion of entailment in system Z (Pearl
1990; Goldszmidt & Pearl 1996) to conditional constraints.
In the sequel, let D) be a -consistent probabilistic
default theory. The notion of z-entailment is linked to an
ordered partition of D, a default ranking z, and a probability
ranking  z .
We first define the z-partition of D. Let (D
the unique ordered partition of D such that, for
each D i is the set of all defaults in D
that are tolerated under P by D
that we define D
call this (D the z-partition of D.
Example 7 The z-partition for the probabilistic default theory
is given as follows:
(f(legs k bird)[:95; 1]; (fly k bird)[:9; :95]g;
f(fly k penguin)[0;
We now define the default ranking z. For
each d 2D j is assigned the value j under z. The probability
ranking  z on all probabilistic interpretations Pr is then
defined as follows:
z(d) otherwise.
The following result shows that, in fact, z is a default
ranking that is admissible with T , and  z is a probability
ranking that is admissible with T .
Lemma 8 a) z is a default ranking admissible with T .
b)  z is a probability ranking admissible with T .
We next define a preference relation on probabilistic in-
terpretations. For probabilistic interpretations Pr and Pr 0 ,
we say Pr is z-preferable to Pr 0 iff  z (Pr) < z (Pr 0
A model Pr of a set of probabilistic formulas F is a z-
minimal model of F iff no model of F is z-preferable to Pr .
We are now ready to define the notion of z-entailment
as follows. A strict probabilistic formula F is a z-con-
sequence of KB , denoted KB k z F , iff each z-minimal
model of P [ fKBg satisfies F . A strict conditional constraint
( j)[l; u] is a tight z-consequence of KB , denoted
tight ( j)[l; u], iff l (resp., u) is the infimum (resp.,
supremum) of Pr( j) subject to all z-minimal models Pr
of P [ fKBg with Pr() > 0.
Coming back to Examples 1-6, it turns out that the non-monotonic
properties of z-entailment differ from the ones of
0- and 1-entailment (see Table 2).
In detail, in the given examples, z-entailment ignores irrelevant
information, shows property inheritance to globally
nonexceptional subclasses, and respects the principle
of specificity. Moreover, it may also handle purely probabilistic
evidence. However, properties are still not inherited
to more specific classes that are exceptional with respect to
some other properties. Moreover, z-entailment still has the
drowning problem and does not preserve ambiguities.
The following examples illustrate how z-entailed tight intervals
are determined.
Example 9 Given T 2 of Example 2, we get:
tight (legs j >)[0; 1]
Here, the interval "[0; 1]" comes from the tight logical consequence
Given T 5 of Example 5, we get:
tight (fly j
Here, the interval "[0; :05]" comes from the tight logical
consequence
metal wingsj>)[1; 1]g
Lexicographic Entailment
We now extend Lehmann's lexicographic entailment
(Lehmann 1995) to conditional constraints.
In the sequel, let D) be a -consistent probabilistic
default theory. We now use the z-partition (D
of D to define a lexicographic preference relation on probabilistic
interpretations.

Table

2: Examples of z-, lexicographically, and conditionally entailed tight intervals.
tight k lex
tight k ce
tight
(fly j>) [:9; :95] [:9; :95] [:9; :95]
(fly j>) [0; :05] [0; :05] [0; :05]
(easy to see j>) [0; 1] [:95; 1] [:95; 1]
(fly j>) [0; :05] [0; :05] [0; 1]
(fly j>) [:86; :91] [:86; :91] [:86; :91]
(fly j>) [0; :15] [0; :15] [0; :15]
For probabilistic interpretations Pr and Pr 0 , we say Pr
is lexicographically preferable to Pr 0 iff there exists some
for all i < j  k. A model Pr of a set of probabilistic formulas
F is a lexicographically minimal model of F iff no
model of F is lexicographically preferable to Pr .
We now define the notion of lexicographic entailment as
follows. A strict probabilistic formula F is a lexicographic
consequence of KB , denoted KB k lex F , iff each lexicographically
minimal model of P [fKBg satisfies F . A strict
conditional constraint ( j)[l; u] is a tight lexicographic
consequence of KB , denoted KB k lex
tight ( j)[l; u], iff l
(resp., u) is the infimum (resp., supremum) of Pr( subject
to all lexicographically minimal models Pr of P[fKBg
with Pr () > 0.
Coming back to Examples 1-6, it turns out that lexicographic
entailment has nicer nonmonotonic features than
z-entailment (see Table 2).
In detail, in the given examples, lexicographic entailment
ignores irrelevant information, shows property inheritance
to nonexceptional subclasses, and respects the principle of
specificity. Moreover, it does not block property inheritance,
it does not have the drowning problem, and it may also handle
purely probabilistic evidence. However, lexicographic
entailment still does not preserve ambiguities.
The following examples illustrate how lexicographically
entailed tight intervals are determined.
Example 11 Given T 2 of Example 2, we get:
tight (legs j >)[:95;
Here, the interval "[:95; 1]" comes from the tight logical consequence
(fly k penguin)[0; :05],
Example 12 Given T 5 of Example 5, we get:
tight (fly j
Here, the interval "[0; :05]" comes from the tight logical
consequence
metal wingsj>)[1; 1]g
Conditional Entailment
We next extend Geffner's conditional entailment (Geffner
1992; Geffner & Pearl 1992) to conditional constraints.
In the sequel, let D) be a probabilistic default
theory.
We first define priority orderings on D as follows. A priority
ordering  on D is an irreflexive and transitive binary
relation on D. We say  is admissible with T iff each set
of defaults D 0 D that is under P in conflict with some default
d 2D contains a default d 0 such that d 0  d. We say T
is -consistent iff there exists a priority ordering on D that
is admissible with T .
Example 13 Consider the probabilistic default theory
2. A priority ordering  on D 2
that is admissible with T 2 is given by (fly k bird)[:9; :95]
(fly k penguin)[0; :05]. 2
The existence of an admissible default ranking implies the
existence of an admissible priority ordering.
Lemma 14 If T is -consistent, then T is -consistent.
We next define a preference ordering on probabilistic interpretations
as follows. Let Pr and Pr 0 be two probabilistic
interpretations and let  be a priority ordering on D. We
say that Pr is -preferable to Pr 0 iff fd 2D j Pr 6j= dg 6=
fd 2D j Pr 0 6j= dg and for each d 2D such that Pr 6j= d and
there exists some default d 0 2D such that d  d 0 ,
Pr model Pr of a set of probabilistic
formulas F is a -minimal model of F iff no model of F
is -preferable to Pr . A model Pr of a set of probabilistic
formulas F is a conditionally minimal model of F iff Pr is
a -minimal model of F for some priority ordering  admissible
with T .
We finally define the notion of conditional entailment. A
strict probabilistic formula F is a conditional consequence
of KB , denoted KB k ce
F , iff each conditionally minimal
model of P [ fKBg satisfies F . A strict conditional constraint
( j)[l; u] is a tight conditional consequence of KB ,
denoted KB k ce
tight ( j)[l; u], iff l (resp., u) is the infimum
(resp., supremum) of Pr( j) subject to all conditionally
minimal models Pr of P [ fKBg with Pr() > 0.
Coming back to Examples 1-6, we see that among all introduced
notions of entailment, conditional entailment is the
one with the nicest nonmonotonic properties (see Table 2).
In detail, in the given examples, conditional entailment
ignores irrelevant information, shows property inheritance
to nonexceptional subclasses, and respects the principle of
specificity. Moreover, it does not block property inheritance,
and it does not have the drowning problem. Finally, conditional
entailment preserves ambiguities and may also handle
purely probabilistic evidence.
The following examples illustrate how conditionally entailed
tight intervals are determined.
Example 15 Given T 2 of Example 2, we get:
ce
tight (legs j >)[:95;
Here, the interval "[:95; 1]" comes from the tight logical consequence
(fly k penguin)[0; :05],
Example Given T 5 of Example 5, we get:
ce
tight (fly j >)[0;
Here, the interval "[0; 1]" is the convex hull of the intervals
"[0; :05]" and "[:95; 1]", which come from the tight logical
consequences
metal wings j>)[1; 1]gj= tight (fly j >)[0; :05] and P 5 [f(fly k
bird)[:95; 1], (fly k metal wings)[:95; 1], (penguin ^ metal
wings
Relationship to Classical Formalisms
We now analyze the relationship to classical default reasoning
from conditional knowledge bases and to classical probabilistic
reasoning with conditional constraints.
logical formula is a probabilistic formula that contains
only conditional constraints of the kind ( j)[1;1] or
strict logical formula is a strict probabilistic
formula that contains only strict conditional constraints of
the form ( j)[1; 1]. A logical default theory T is a probabilistic
default theory that contains only logical formulas. A
logical knowledge base KB is a strict logical formula.
We use the operator
on logical formulas, sets of logical
formulas, and logical default theories, which replaces
each strict conditional constraint ( j)[1; 1] (resp., defeasible
conditional constraint ( k)[1; 1]) by the classical implication
Given a
logical ce ) to
denote the classical notion of z-, (resp., lexicographic, con-
ditional) entailment with respect to
The following result shows that the introduced notions of
z-, lexicographic, and conditional entailment are generalizations
of their classical counterparts.
Theorem 17 Let D) be a logical default theory
and let KB be a logical knowledge base. Then, for every
semantics s 2 fz; lex ; ceg:
The next result shows that, when the union of generic
and concrete probabilistic knowledge is satisfiable, the notions
of z-, lexicographic, and conditional entailment coincide
with the notion of 1-entailment.
Theorem D) be a probabilistic default theory
and let KB be a probabilistic knowledge base such
that P [D[ fKBg is satisfiable. Then, for every semantics
1. KB k s F iff P [D[ fKBg
2. KB k s
tight ( j)[l; u] iff P[D[fKBgj= tight ( j)[l; u].
Summary and Outlook
We presented the notions of z-entailment, lexicographic en-
tailment, and conditional entailment for conditional con-
straints, which combine the classical notions of entailment
in system Z, Lehmann's lexicographic entailment, and
Geffner's conditional entailment with the classical notion of
logical entailment for conditional constraints. We showed
that the introduced notions for probabilistic default reasoning
with conditional constraints have similar properties like
their classical counterparts. Moreover, they properly extend
both their classical counterparts and the classical notion of
logical entailment for conditional constraints.
An interesting topic of future research is to extend other
formalisms for classical default reasoning to the probabilistic
framework of conditional constraints.

Acknowledgments

I am very grateful to the referees for their useful comments.
This work was supported by a DFG grant and the Austrian
Science Fund Project N Z29-INF.



--R

The Logic of Conditionals
Constraint propagation with imprecise conditional probabilities.

From statistical knowledge bases to degrees of beliefs.
Inconsistency management and prioritized syntax-based entailment
Representing default rules in possibilistic logic.


Belief functions and default reasoning.
Logical Foundations of Probability.
Chicago: University of Chicago Press.
Theory of Probability.
On fuzzy syllogisms.
Computational Intelligence
Possibilistic logic
Conditional objects as non-monotonic consequence relationships


Qualitative reasoning with imprecise probabilities.
Journal of Intelligent Information Systems
Inference with imprecise numerical quantifiers.
Complexity results for default reasoning from conditional knowledge bases.
A logic for reasoning about probabilities.
Plausibility measures and default reasoning.
Anytime deduction for probabilistic logic.
Conditional entailment: Bridging two approaches to default reasoning.
Reasoning: Causal and Conditional Theories.

Qualitative probabilities for default reasoning
A maximum entropy approach to nonmonotonic reasoning.
Random worlds and maximum entropy.
Probabilistic description logics.
Column generation methods for probabilistic logic.



A promenade from monotonicity to non-monotonicity following a theorem prover
What does a conditional knowledge base entail?
What does a conditional knowledge base entail?
Another perspective on default reason- ing
Probabilistic logic programming.
Local probabilistic deduction from taxonomic and probabilistic knowledge-bases over conjunctive events
Probabilistic deduction with conditional constraints over basic events.
Probabilistic default reasoning with strict and defeasible conditional constraints.

Computation of best bounds of probabilities from uncertain data.
Probabilistic semantics for nonmontonic reasoning: A survey.
System Z: A natural ordering of defaults with tractable applications to default reasoning.
Nomic Probabilities and the Foundations of Induction.
Theory of Probability.
A semantical approach to nonmonotonic logics.
Ordinal conditional functions: A dynamic theory of epistemic states.
Towards precision of probabilistic bounds propagation.
--TR

--CTR
Thomas Lukasiewicz, Nonmonotonic probabilistic logics under variable-strength inheritance with overriding: Complexity, algorithms, and implementation, International Journal of Approximate Reasoning, v.44 n.3, p.301-321, March, 2007
Donald Bamber , I. R. Goodman , Hung T. Nguyen, Robust reasoning with rules that have exceptions: From second-order probability to argumentation via upper envelopes of probability and possibility plus directed graphs, Annals of Mathematics and Artificial Intelligence, v.45 n.1-2, p.83-171, October   2005
Veronica Biazzo , Angelo Gilio , Thomas Lukasiewicz , Giuseppe Sanfilippo, Probabilistic logic under coherence: complexity and algorithms, Annals of Mathematics and Artificial Intelligence, v.45 n.1-2, p.35-81, October   2005
Thomas Lukasiewicz, Weak nonmonotonic probabilistic logics, Artificial Intelligence, v.168 n.1, p.119-161, October 2005
Angelo Gilio, Probabilistic Reasoning Under Coherence in System P, Annals of Mathematics and Artificial Intelligence, v.34 n.1-3, p.5-34, March 2002
Gabriele Kern-Isberner , Thomas Lukasiewicz, Combining probabilistic logic programming with the power of maximum entropy, Artificial Intelligence, v.157 n.1-2, p.139-202, August 2004
conditional constraint;system Z;probabilistic default reasoning;conditional entailment;lexicographic entailment