A theory of nonmonotonic rule systems I. (English) Zbl 0878.68035
Summary: We introduce here the study of general nonmonotonic rule systems. These deal with situations where a conclusion is drawn from a “system of beliefs” \(S\) (and seen to be in \(S\)), based both on some “premises” being in \(S\) and on some “restraints” not being in \(S\). In the monotone systems of traditional logic there are no restraints, conclusions are drawn solely based on premises being in \(S\). Nonmonotonic rule systems capture the essential syntactic, semantic, and algorithmic features of many nonmonotone systems such as default logic, negation as failure, truth maintenance, autoepistemic logic, and also important combinatorial questions from mathematics such as the marriage problem. This reveals semantics and syntax and proof procedures and algorithms for computing belief sets in many cases where none were previously available and entirely uniformly. In particular, we introduce and study deductively closed sets, extensions and weak extensions. Semantics of nonmonotonic rule systems is studied in part II of this paper and extensions to predicate classical, intuitionistic, and modal logics are left to a later paper.
Keywords:
nonmonotonic rule systemsReferences:
| [1] | K.R. Apt., Introduction to logic programming, Technical Report TR-87-35, University of Texas (1988). |
| [2] | K.R. Apt, H.A. Blair and A. Walker, Towards a theory of declarative knowledge, in:Foundations of Deductive Databases and Logic Programming, ed. J. Minker (Morgan Kaufmann, Los Altos, CA, 1987). |
| [3] | N. Bidoit and C. Froidevaux, General logical databases and programs, default logic semantics, and stratification, J. Information and Comput., to appear. · Zbl 0800.68292 |
| [4] | H.A. Blair, A.L. Brown and V.S. Subrahmanian, Monotone logic programming, Technical Report CS-TR-2375, University of Maryland (1989). · Zbl 0686.68009 |
| [5] | J. de Kleer, An assumption-based TMS, Artificial Intelligence 28 (1986) 127-162. · doi:10.1016/0004-3702(86)90080-9 |
| [6] | R.P. Dilworth, A decomposition theorem for partially ordered sets, Ann. Math. 51 (1950) 161-165. · Zbl 0038.02003 · doi:10.2307/1969503 |
| [7] | J. Doyle, A truth maintenance system, Artificial Intelligence J. 12 (1979) 231-272. · doi:10.1016/0004-3702(79)90008-0 |
| [8] | M. Gelfond and V. Lifschitz, Stable semantics for logic programs, in:Proc. 5th Int. Symp. on Logic Programming, Seattle (1988). |
| [9] | M. Gelfond and V. Lifschitz, Logic programming with classical negation, unpublished manuscript (1989). · Zbl 0675.68047 |
| [10] | M. Gelfond and H. Przymusi?ska, On the relationship between circumscription and autoepistemic logic, in:Proc. ISMIS Conf. (1986). |
| [11] | M. Gelfond and H. Przymusi?ska, Inheritance reasoning in autoepistemic logic, to appear in Fund. Inform. |
| [12] | D. Gries,The Science of Programming (Springer, 1981). · Zbl 0472.68003 |
| [13] | P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935) 26-30. · Zbl 0010.34503 · doi:10.1112/jlms/s1-10.37.26 |
| [14] | M. Hall, Distinct representatives of subsets, Bull. Amer. Math. Soc. 54 (1948) 922-926. · Zbl 0032.27101 · doi:10.1090/S0002-9904-1948-09098-X |
| [15] | J.Y. Halpern and Y.O. Moses, Knowledge and common knowledge in a distributed environment,3rd ACM Conf. on the Principles of Distributed Computing (1984) pp. 50-61. |
| [16] | J. Hintikka,Knowledge and Belief (Cornell University Press, 1962). |
| [17] | W-Q. Huang and A. Nerode, Applications of pure recursion theory to recursive analysis, Acta Sinica 28 (1985). · Zbl 0638.03058 |
| [18] | K. Konolige, On the relation between default and autoepistemic logic, Artificial Intelligence J. 35 (1988) 343-382. · Zbl 0647.68088 · doi:10.1016/0004-3702(88)90021-5 |
| [19] | W. Marek and A. Nerode, Decision procedure for default logic, Mathematical Sciences Institute Reports, Cornell University (1990). |
| [20] | W. Marek and M. Truszczy?ski, Relating autoepistemic and default logics, in:Principles of Knowledge Representation and Reasoning (Morgan Kaufmann, San Mateo, 1989). (Full version available as Technical Report 144-89, Computer Science, University of Kentucky, Lexington, KY 40506-0027, 1989.) |
| [21] | W. Marek and M. Truszczy?ski, Stable models for logic programs and default logic, in:Proc. North American Conf. Logic Programming (MIT Press, 1989). (Full version available as Technical Report, Computer Science Department, University of Kentucky, Lexington, KY 40506-0027, 1989.) |
| [22] | J. McCarthy, Circumscription ? a form of nonmonotonic reasoning, Artificial Intelligence J. 13 (1980) 27-39. · Zbl 0435.68073 · doi:10.1016/0004-3702(80)90011-9 |
| [23] | G. Metakides and A. Nerode, Effective content of field theory, Ann. Math. Logic 17 (1977) 289-320. · Zbl 0469.03028 · doi:10.1016/0003-4843(79)90011-1 |
| [24] | M. Minsky, A framework for representing knowledge, in:The Psychology of Computer Vision (McGraw-Hill, 1975) pp. 211-272. |
| [25] | L. Mirsky,Transversal Theory (Academic Press, New York, 1971). |
| [26] | R.C. Moore, Semantical considerations on non-monotonic logic, Artificial Intelligence J. 25 (1985) 75-94. · Zbl 0569.68079 · doi:10.1016/0004-3702(85)90042-6 |
| [27] | A. Nerode and J.B. Remmel, A survey of r.e. substructures, Proc. Symp. Math. 42, Amer. Math. Soc. (1985) 323-376. |
| [28] | A. Nerode and J.B. Remmel, Complexity-theoretic algebra I: vector spaces over finite fields, in:Structures in Complexity (1987) pp. 218-241. |
| [29] | A. Nerode and J.B. Remmel, Complexity-theoretic algebra II: Boolean algebras, Ann. Pure Appl. Logic 44 (1989) 71-99. · Zbl 0703.03023 · doi:10.1016/0168-0072(89)90047-X |
| [30] | A. Nerode and J.B. Remmel, Complexity-theoretic algebra III: bases of vector spaces, in:Feasible Mathematics (Springer, 1990). · Zbl 0846.03020 |
| [31] | M. Reinfrank and O. Dressler, On the relation between truth maintenance and non-monotonic logics, in:Proc. Int. Joint Conf. on Artificial Intelligence (1989). · Zbl 0718.68070 |
| [32] | R. Reiter, A logic for default reasoning, Artificial Intelligence J. 13 (1980) 81-132. · Zbl 0435.68069 · doi:10.1016/0004-3702(80)90014-4 |
| [33] | J.B. Remmel, Recursive Boolean algebras, in:Handbook of Boolean Algebras, ed. J.D. Monk (North-Holland, 1989) chap. 25, pp. 1099-1165. |
| [34] | H. Rogers, Jr.Theory of Recursive Functions and Effective Computability (McGraw-Hill, New York, 1967). · Zbl 0183.01401 |
| [35] | A. Tarski,Logic, Semantics, Metamathematics (Oxford, 1956). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
