Production inference, nonmonotonicity and abduction
Production Inference,Nonmonotonicity
and Abduction
Alexander Bochman
Computer Science Department,
Holon Academic Institute of Technology,Israel
e-mail:bochmana@hait.ac.il
Abstract
We introduce a general formalism of production inference relations that posses both a standard monotonic semantics and a natural non-
monotonic semantics.The resulting nonmonotonic system is shown to
provide a syntax-independent representation of abductive reasoning.
Abduction is a reasoning from facts to their possible explanations that is widely used now in many areas of AI,including diagnosis,truth main-tenance,knowledge assimilation,database updates and logic programming. In this study we are going to show that this kind of reasoning can be given a formal,syntax-independent representation in terms of production infer-ence relations that constitute a particular formalization of input-output logics [MdT00].Among other things,such a representation will clarify the relation between abduction and nonmonotonic reasoning,as well as show the expres-sive capabilities of production inference as a general-purpose nonmonotonic formalism.
We will assume that our basic language is a classical propositional lan-guage with the usual connectives and constants{∧,∨,?,→,t,f}. will denote the classical entailment,and Th the associated provability operator. 1Production Inference Relations
We begin with the following general notion of production inference.
1
De?nition 1.1.A production inference relation is a binary relation ?on the set of classical propositions satisfying the following conditions:(Strengthening)
If A B and B ?C ,then A ?C ;(Weakening)
If A ?B and B C ,then A ?C ;(And)
If A ?B and A ?C ,then A ?B ∧C ;(Truth)
t ?t ;(Falsity)f ?f .
A distinctive feature of production inference relations is that re?exivity A ?A does not hold.It is this ‘omission’,however,that determines their representation capabilities in describing nonmonotonicity and abduction.In what follows,conditionals A ?
B will be called production rules .We extend such rules to rules having arbitrary sets of propositions in premises as follows:for a set u of propositions,we de?ne u ?A as holding when a ?A ,for some ?nite a ?u .
C (u )will denote the set of propositions ‘produced’by u ,that is,C (u )={A |u ?A }.The production operator C will play much the same role as the derivability operator for consequence relations.
1.1Kinds of production inference
A classi?cation of the main kinds of production inference relevant for our study is based on the validity of the following additional postulates:(Cut)
If A ?B and A ∧B ?C ,then A ?C .(Or)If A ?C and B ?C ,then A ∨B ?C .
(Weak Deduction)
If A ?B ,then t ?(A →B ).A production inference relation will be called regular ,if it satis?es Cut;basic ,if it satis?es Or 1;causal if it is both basic and regular;and quasi-classical ,if it is causal and satis?es Weak Deduction.
The rule Cut allows for a reuse of produced propositions as premises in further productions.Any regular production relation will be transitive.
1
Basic production relations correspond to basic input-output logics from [MdT00],while regular productions correspond to input-output logics with reusable output.2
The rule Or allows for reasoning by cases,and hence basic production relations can already be seen as systems of objective production inference, namely as systems of reasoning about complete worlds(see below).
Causal production relations have been introduced in[Boc03];they have been shown to provide a complete characterization for the reasoning with causal theories from[MT97].
Finally,quasi-classical production relations will be shown below to char-acterize‘classical’abductive reasoning.
1.2The Monotonic Semantics
A semantic interpretation of production relations is based on pairs of deduc-tively closed theories called bimodels.By the‘input-output’understanding of productions,a bimodel represents an initial state(input)and a possible ?nal state(output)of a production process.
De?nition1.2.A pair of classically consistent deductively closed sets of propositions will be called a bimodel.A set of bimodels will be called a production semantics.
Note that a production semantics can also be viewed as a binary relation on the set of deductive theories.
De?nition1.3.A production rule A?B will be said to be valid in a pro-duction semantics B if,for any bimodel(u,v)from B,A∈u only if B∈v.
Then the following completeness result can be shown:
Theorem1.1.A relation on the set of propositions is a production inference relation if and only if it is determined by a production semantics.
This representation result serves as a basis for semantic characterizations of di?erent kinds of production relations,described above.
The semantics of regular production relations can be obtained by consid-ering only bimodels(u,v)such that v?u.We will call such bimodels(and corresponding semantics)inclusive ones.
Theorem1.2.?is a regular production relation i?it is generated by an inclusive production semantics.
3
The semantics for the three other kinds of production is obtained by restricting the set of bimodels to bimodels of the form(α,β),whereα,βare worlds.The corresponding production semantics can be seen as a relational possible worlds model W=(W,B),where W is a set of worlds with an accessibility relation B.Validity of productions can now be de?ned as follows:
De?nition1.4.A rule A?B is valid in a possible worlds model(W,B)if, for anyα,β∈W such thatαBβ,if A holds inα,then B holds inβ.
A possible worlds model(W,B)will be called re?exive,ifαBα,for any worldα,and quasi-re?exive,ifαBβimpliesαBα,for anyα,β∈W. Theorem1.3.A production inference relation is
?basic if and only if it has a possible worlds model.
?causal i?it has a quasi-re?exive possible worlds model.
?quasi-classical i?it has a re?exive possible worlds model.
1.3The Nonmonotonic Semantics
The fact that the production operator C is not re?exive creates an important distinction between theories of a production inference relation.
De?nition1.5.A set u of propositions is a theory of a production relation, if it is deductively closed,and C(u)?u.A theory is exact,if u=C(u).
A theory of a production relation is closed with respect to its production rules,while an exact theory describes an informational state in which every proposition is also produced,or explained,by other propositions accepted in this state.Accordingly,restricting our universe of discourse to exact the-ories amounts to imposing a kind of an explanatory closure assumption on admissible states.This suggests the following notion:
De?nition1.6.A(general)nonmonotonic semantics of a production infer-ence relation is the set of all its exact theories.
The above nonmonotonic semantics is indeed nonmonotonic,since adding new rules to the production relation may lead to a nonmonotonic change of the associated semantics,and thereby to a nonmonotonic change in the
4
derived information.This happens even though production rules themselves are monotonic,since they satisfy Strengthening the Antecedent.
Exact theories are precisely the?xed points of the production operator C. Since the latter operator is monotonic and continuous,exact theories(and hence the nonmonotonic semantics)always exist.
Since a basic production inference is already world-based,it naturally sanctions the following strengthening of the general nonmonotonic semantics.
De?nition1.7.An objective nonmonotonic semantics of a(basic)produc-tion inference relation is the set of all its exact worlds.
As has been shown already in[MT97],the above semantics is repre-sentable as a set of all worlds(interpretations)that satisfy a certain classical completion of the set of production rules.
2Abduction versus Production
An abductive framework can be de?ned as a pair A=(Cn,A),where Cn is a consequence relation that subsumes classical entailment2,while A is a distinguished set of propositions that play the role of abducibles,or explana-tions,for other propositions.A proposition B is explainable in an abductive framework A if there exists a consistent set of abducibles a?A such that B∈Cn(a).
It turns out that explanatory relations in an abductive framework can be captured by considering only theories that are generated by the abducibles. De?nition2.1.The abductive semantics AS of an abductive framework A is the set of theories{Cn(a)|a?A}.
The information embodied in the abductive semantics can be made ex-plicit by considering the following generated Scott consequence relation:
b A c≡(?u∈AS)(b?u→c∩u=?)
b A
c holds if an
d only if any set of abducibles that explains b explains also at least on
e proposition from c.3This consequence relation is an exten-sion o
f Cn that describes not only‘forward’explanatory relations,but also 2Such consequence relations are called supraclassical.
3A Tarski consequence relation of this kind has been used for the same purposes in [LU97].
5
abductive inferences from propositions to their explanations.For example, if C and D are the only abducibles that imply A in an abductive framework, then we will have A A C,D.Speaking more generally,the above abductive consequence relation describes the explanatory closure,or completion,of an abductive framework,and allow thereby to capture the abductive process by deductive means(see[CDT91,Kon92]).
The following de?nition arises from viewing explanation as a kind of pro-duction inference.
De?nition2.2.A production inference relation associated with an abductive framework A is a production relation?A determined by all bimodels of the form(u,Cn(u∩A)),where u is a consistent theory of Cn.
Since the above production semantics is inclusive,the associated produc-tion relation will always be regular.Moreover,the following result shows how it is related to the source abductive framework.
Theorem2.1.The abductive semantics of an abductive framework coincides with the nonmonotonic semantics of its associated production relation.
We assume below that the set A is closed with respect to conjunctions, that is,if A and B are abducibles,so is A∧B.To deal with limit cases,we assume also that t and f are abducibles.Then it turns out that the above production relation admits a very simple syntactic characterization,namely
B?A C i?(?A∈A)(A∈Cn(B)&C∈Cn(A))
Note that A?A A holds if and only if A is Cn-equivalent to an abducible from A.Accordingly,we will say that A is an abducible of a production inference relation?,if A?A.The set of such abducibles is closed with respect to conjunctions.Now,production relations associated with abductive frameworks satisfy the following characteristic property:
(Abduction)If B?C,then B?A?C,for some abducible A.
Regular production relations satisfying Abduction will by called abduc-tive production relations.For such relations,the production process always goes through abducibles.The next theorem shows that they are precisely production inference relations that are generated by abductive frameworks. Theorem2.2.A production relation is abductive if and only if it is generated by an abductive framework.
6
Due to the above results,abductive production relations can be seen as a faithful logical representation of abductive reasoning.Notice that abductive production relations provide in this sense a syntax-independent description of abduction:the set of abducibles is determined as a set of propositions having a certain logical property,namely re?exivity.
The abductive subrelation.Any regular production relation?includes an important abductive subrelation de?ned as follows:
A?a B≡(?C)(A?C?C?B)
?a is the greatest abductive relation included in?,and in many natural cases it produces the same nonmonotonic semantics(see[Boc03]).
If A?is the set of abducibles of?,and Cn?the least supraclassical consequence relation including?,then the following result can be shown: Lemma2.3.If?is a regular production relation,then its abductive subre-lation?a is generated by the abductive framework(Cn?,A?).
2.1Causal and classical abductive inference
Abductive frameworks corresponding to causal production relations are de-scribed in the next de?nition.
De?nition2.3.An abductive framework A=(Cn,A)will be called A-disjunctive if A is closed with respect to disjunctions,and Cn satis?es the following conditions,for any abducibles A,A1∈A,and arbitrary B,C:?If A∈Cn(B)and A∈Cn(C),then A∈Cn(B∨C);
?If B∈Cn(A)and B∈Cn(A1),then B∈Cn(A∨A1).4
Theorem2.4.An abductive production relation is causal if and only if it is generated by an A-disjunctive abductive framework.
As we already mentioned,the objective nonmonotonic semantics of such production relations is obtainable by forming a classical completion of the set of production rules(cf.[CDT91]).
4This rule corresponds to the rule Ab-Or in[LU97].
7
An abductive framework will be called classical if Cn is a classical conse-quence relation(that is,it is supraclassical and satis?es the deduction theo-rem).Such a framework is reducible to a pair(Σ,A),whereΣis a domain theory(with the implicit assumption that the background logic is classical). Our last result provides a production counterpart of such frameworks.
Theorem2.5.An abductive production relation is quasi-classical if and only if it is generated by a classical abductive framework.
An interesting negative consequence from the above result is that classi-cal abductive frameworks are already inadequate for reasoning with causal theories of McCain and Turner;the latter is captured,however,by a broader class of A-disjunctive abductive frameworks.
References
[Boc03] A.Bochman.A logic for causal reasoning.In G.Gottlob and T.Walsh,editors,Proceedings Int.Joint Conference on Arti?cial
Intelligence,IJCAI’03,pages141–146,Acapulco,2003.Morgan
Kaufmann.
[CDT91]L.Console,D.Theseider Dupre,and P.Torasso.On the rela-tionship between abduction and deduction.Journal of Logic and
Computation,1:661–690,1991.
[Kon92]K.Konolige.Abduction versus closure in causal theories.Arti?cial Intelligence,53:255–272,1992.
[LU97]J.Lobo and C.Uzc′a tegui.Abductive consequence relations.Arti-?cial Intelligence,89:149–171,1997.
[MdT00]D.Makinson and L.Van der Torre.Input/Output logics.Journal of Philosophical Logic,29:383–408,2000.
[MT97]N.McCain and H.Turner.Causal theories of action and change.
In Proceedings AAAI-97,pages460–465,1997.
8