Abstract

Available from UMI in association with The British Library. Requires signed TDF. ;Minimal consequence is embodied in many approaches to non-monotonic reasoning. In this thesis we define minimal consequence in sentential logic and present a number of results of a model theoretic and recursion theoretic character about this newly introduced non-monotonic consequence relation. We show that the minimal consequence relation is not compact and is $\Pi\sbsp{2}{0}$ and not $\Sigma\sbsp{2}{0}$. We also connect this relation to questions about the completion of theories by "negation as failure." We give a complete characterization of the class of theories in sentential logic which can be consistently completed by "negation as failure" using the newly introduced notion of a subconditional theory. We show that the class of theories consistently completable by negation as failure is $\Pi\sbsp{2}{0}$ and not $\Sigma\sbsp{2}{0}$. ;In first order logic minimal consequence is the semantic notion underlying circumscription formalisms. We study domain, predicate, and formula minimal consequence, which are obtained by varying the type of minimization involved and correspond to domain, predicate, and formula circumscription, respectively. The results, again, are model theoretic and serve to clarify properties of minimal consequence in first order logic. Relationships between domain, predicate, and formula minimal consequence are established. We show that every satisfiable theory in a finite language can be finitely expanded to a minimally satisfiable theory in an extended language which has the same logical consequences in the original language as the original theory. We also show that minimal satisfiability is not compact for any of the types of minimality under consideration